【アルゴリズム】 樹木曲線

樹木曲線

一定の角度で枝分かれをして、一定の長さに到達したらまた枝分かれ…というのを繰り返すと、木のようなものが出来上がる。

プログラムで書くために具体的に

1回目に枝分かれしたものは2箇所の頂点ができていて、2回目に枝分かれしたものは4箇所の頂点ができていて…となっている。 枝の先端は2つにわかれていて、更に小さな枝になっている。ここが再帰の構造になっている。

枝を作るために、前へ進んでその進んだ場所と進む前の座標との間を直線で結び、再帰から戻ってくるときに進んだ分戻すという処理が必要になる。

具体的な実装

「C言語による最新アルゴリズム事典」では、plotter.cというのを使っている。plotter.cはポインタを動かして描画するタイプのようである。

これをDXRubyで再現するには、何かしらのクラスを保持しておいたほうが簡単だろうと思ったので、Turtleというクラスを作った。

コード

#!ruby -Ks

require "dxruby"

#
# P.113 樹木曲線
#

class Turtle < Sprite
  def initialize(x, y)
    @x = x
    @y = y

    @beforex = x
    @beforey = y
  end

  def setxy(x, y)
    @beforex = @x
    @beforey = @y

    @x -= x
    @y -= y
  end

  def draw
    Window.drawLine(@beforex, @beforey, @x, @y, [255,255,255])
  end

end


FACTOR = 0.7
TURN = 0.5

BASEX = 320
BASEY = 480
$turtle = Turtle.new(BASEX, BASEY)

def tree(n, length, angle)
  dx = length * Math.sin(angle)
  dy = length * Math.cos(angle)

  $turtle.setxy(dx, dy)
  $turtle.draw
  if n > 0
    tree(n - 1, length * FACTOR, angle + TURN)
    tree(n - 1, length * FACTOR, angle - TURN)
  end

  $turtle.setxy(-dx, -dy)
end

order = 9
length = 100

Window.create
tree(order, length, 0)
Window.update
sleep(15);

2012/11/15 15:35