Home > Archives > 2008-11-02

2008-11-02

Hilbert Curve - Flex(AS3.0)

2008-11-02 (Sun)
tech/study
actionscript | flex

モチベーションが上がっている内にたくさんコードを書こう。

ヒルベルト曲線をActionScriptで。再帰曲線というやつですね。

これは空間を覆い尽くす空間充填曲線の一つで、画像工学分野にも応用されています。画像の場合だと、画素をヒルベルト曲線順に走査するヒルベルトスキャンという手法があって、それに関連した論文もたくさん出ています。

今回はFlash Player 10で新たに追加されたグラフィックスAPIを使う練習も兼ねて、drawPathというメソッドを使ってみます。lineToやcurveToを連発しなくても、一度で描画してくれるとのこと。フラクタル図形はたくさんlineToをする必要があるので、テスト用としては適してるかなと思ってここではヒルベルト曲線を選びました。

public function drawPath(commands:Vector.<int>, data:Vector.<Number>, winding:String="evenOdd");

commandsにはmoveToやlineToにあたる定数、dataには座標値を入れます。ここはPoint型ではなくNumber型なので注意。windingはパスが交差したときのふるまいを指定するのですが、ヒルベルト曲線の性質上、線が交わることがないので今回は特に気にしません。

・ソースコード

package {
  import flash.display.Shape;
  import flash.display.GraphicsPathCommand;
  import flash.geom.Point;

  public class Hilbert extends Shape {
    private const WIDTH:int = 400;
    private const HEIGHT:int = WIDTH;
    private var order:int;  // 次数
    private var h:Number;   // 刻み
    private var pt:Point;

    private var commands:Vector.<int> = new Vector.<int>();
    private var data:Vector.<Number> = new Vector.<Number>();

    public function Hilbert(order:int, color:uint) {
      this.order = order;
      pt = new Point();
      graphics.lineStyle(0, color);
      h = 1;
      for(var i:int = 2; i <= order; i++) h = h / (2 + h);
      h *= WIDTH;

      rightUpLeft(order);  // 基本形：コの字
      graphics.drawPath(commands, data);
    }

    private function rightUpLeft(i:int):void {
      if(i == 0) return;
      upRightDown(i - 1);  drawRelative( h, 0);
      rightUpLeft(i - 1);  drawRelative( 0, h);
      rightUpLeft(i - 1);  drawRelative(-h, 0);
      downLeftUp(i - 1);
    }

    private function downLeftUp(i:int):void {
      if(i == 0) return;
      leftDownRight(i - 1);  drawRelative( 0, -h);
      downLeftUp(i - 1);     drawRelative(-h,  0);
      downLeftUp(i - 1);     drawRelative( 0,  h);
      rightUpLeft(i - 1);
    }

    private function leftDownRight(i:int):void {
      if(i == 0) return;
      downLeftUp(i - 1);     drawRelative(-h,  0);
      leftDownRight(i - 1);  drawRelative( 0, -h);
      leftDownRight(i - 1);  drawRelative( h,  0);
      upRightDown(i - 1);
    }

    private function upRightDown(i:int):void {
      if(i == 0) return;
      rightUpLeft(i - 1);    drawRelative( 0,  h);
      upRightDown(i - 1);    drawRelative( h,  0);
      upRightDown(i - 1);    drawRelative( 0, -h);
      leftDownRight(i - 1);
    }

    private function drawRelative(dx:Number, dy:Number):void {
      commands.push(GraphicsPathCommand.LINE_TO);
      data.push(pt.x + dx);
      data.push(pt.y + dy);
      pt.x += dx;
      pt.y += dy;
    }
  }
}

ひたすらlineToしたものと速度比較してみました。
10次のヒルベルト曲線の場合、

・drawPath(): 2142ms
・lineTo(): 1410ms

なん・・だと？
そんなバカなと思ってよく考えてみると、VectorへのpushがlineToの3倍の回数行っているんですよね。
10次のヒルベルト曲線の場合、lineToは約104万回。
ということは、drawPath()で描画する場合は300万回以上Vectorに値をpushしていることになります。
これは仕方ない。それにこういう使い方は普通はしないと思いますし。
ちなみにデモでは8次までしか描画できません。10次はさすがに重いので、、。
指数関数的に計算回数が増えるので11次以上は危険です。フリーズします。

そういえばもう11月ですね。紅葉が綺麗な季節。心が落ち着きます。

＜追記＞11/08
objectタグの打ち間違いのせいで、IEで閲覧している人はFlashが表示されてなかったと思います。
すみません；
修正しておきました。