Processing hilbert曲線

Question

processingで再帰について学んでいたのですがこの曲線の描き方だけがどうもうまく再帰プログラムを組むことができません。
どのように書けばうまくこのように描けるのでしょうか。ちなみに再帰ではなく分割統治法なら４つのパターンに分けて処理すればなんとかなりそうだと分かるのですが...。

Answer 1

再帰も一種の分割統治法ですのでヒルベルト曲線の描画ルールについて検討する際の方針は概ね同じと言えると思います。

ヒルベルト曲線はタートルグラフィックの例題としてよく登場すると思います。タートルグラフィックというのは「今ペンがある地点」から「どの方向へ」「どのような線を描くか」で線画を描いていく手法です。

大雑把な方針はある方向へペンを移動する際に３つの線分（レベル１での３辺）を描きながら、各々の線分の間に一つ下のレベルのヒルベルト曲線を（方向に注意しながら）描画するというものです。

すみませんが、詳細な説明を言葉でするよりコードを提示した方が（回答する側にとって）楽なので詳しくはコード例を参考にしてみてください。

本質はhilbert関数です。殆ど答えみたいなものですが、完全なコードを書いてしまうと無粋なので若干部分だけ書かずに残してあります。(A)～(C)に何を埋めればうまく描画できるか考えてみてください。

static final int[][] dirs = { { 1, 0 }, { 0, -1 }, { -1, 0 }, { 0, 1 }};

int level;
float px, py, dist;

// 指定方向へ単位直線を描画する

void turtle(int dir) {
  dir = dir & 3;
  float nx = px + dirs[dir][0] * dist;
  float ny = py + dirs[dir][1] * dist;
  line(px, py, nx, ny);
  px = nx;
  py = ny;
}

// 指定レベルのヒルベルト曲線を描く
// dirはペンの(このレベルでの)最終的な移動方向。
// spinは右回りか左回りかを示す。

void hilbert(int level, int dir, int spin) {
  if (level == 0) return;
  
  hilbert(level - 1, dir + spin, -spin);
  turtle(dir + spin);
  hilbert(level - 1, ...); // (A)
  turtle(dir);
  hilbert(level - 1, ...); // (B)
  turtle(dir - spin);
  hilbert(level - 1, ...); // (C)
}

// level 1～7を繰り返し描画

void setup() {
  size(256, 256);
  level = 1;
  frameRate(1);
}

void draw() {
  fill(255);
  noStroke();
  rect(0, 0, width, height);
  
  stroke(0);
  int div = 1 << level;
  dist = width / (float)div;
  println(level + ":" + dist);
  px = py = dist / 2;

  hilbert(level, 3, 1);

  level = level % 7 + 1;
}

Comments

[Chuchuchu]

丁寧な解説ありがとうございます。参考にして実装を考えてみます。