ヒルベルト曲線

読書会

先日の読書会の自分用メモを整理しておきます。


内容：「ハッカーのたのしみ」第14章 ヒルベルト曲線

  • ヒルベルト曲線の向き
    • 始点と終点の位置関係から、右方向、上方向、左方向、下方向、の4パターンがある
    • 回転の方向から、時計回り、反時計回り、の2パターンがある
    • ヒルベルト曲線は、次数、直線方向、回転方向、の3つのパラメータで完全に決定できる
  • ヒルベルト曲線の生成
    • 次数 n-1 の曲線から次数 n を生成できる
    • したがって再帰的に生成できる
    • ただし、曲線の向きに注意が必要
  • ヒルベルト曲線の道のりから座標を求める(1)
    • まずは素朴に考える
    • 道のりの上位2ビットからX座標の上位1ビットとY座標の上位1ビットが求められる（ヒルベルト曲線の特徴）
    • したがって道のりを上位から2ビットずつ走査することで座標が求められる
    • ただし、曲線の向きに注意が必要
    • 走査する際に、現在の向き（状態）から次の向き（状態）への状態遷移を考慮する
    • なお、ヒルベルト曲線の向きは 4 * 2 = 8 パターンあるが、1つの曲線に再帰的に現れる向きは 4 パターンしかない
  • (1)のソースコードの補足
    • hil_xy_from_s() の引数は道のり、次数、座標
    • row は現在の状態と道のりの2ビットの連結で 0〜15 の値（例えば状態 B で道のり 2 ビットが 10 なら row = 0110b）
    • X座標の上位1ビットは 0x936C の row ビット目にあたる
    • Y座標と次の状態も同様
  • ヒルベルト曲線の道のりから座標を求める(2) [L&S]
    • 道のりの下位2ビットからX座標の下位1ビットとY座標の下位1ビットが求められる
    • ・・・といっても、上位から走査するときほど単純には決定できない
    • 実は、走査しながら座標の交換と反転を行うことでうまく実現できる
  • ヒルベルト曲線の道のりから座標を求める(3)
    • (1)と同様に上位から走査するが、(2)の交換と反転のアイデアを取り込む
    • 状態遷移のかわりに、交換信号と反転信号を使う
  • (3)の論理回路の補足
    • ここではソースコードによる表現でなく、論理回路によって表現している
    • 上の s_i が道のりの各ビット
    • 下の x_i と y_i が座標の各ビット
    • 左から右へ流れる S_i と C_i が交換と反転
  • ヒルベルト曲線の道のりから座標を求める(4)
    • (3)からの発展として、並列プレフィクス演算を使うアイデアが出てくる
    • （並列プレフィクス演算については、本書のセクション5-2を参照）
    • これによって、再帰的なアルゴリズムに比べて高速化がはかれる（O(n)時間でなくO(\log_2 n)時間）
    • ただし、プロセッサの数やビット数への依存に注意（・・・という書き方は変かもしれないが）

読書会で読めたのはここまで。