FXボーグ | テクニカル実験室

テクニカル分析を使った自動売買プログラムの開発に挑戦!

スポンサーリンク

近傍点探索のためのHexagonal Grid(その2)

前回のつづき。今回は「キュービック座標上での距離の測り方」についてです。これを理解すると六角形グリッドで近傍探索が行えるようになります。こちらを一通り説明した後にさらなる改良案についても紹介したいと思います。

前回は六角形グリッドに座標データをセットするところまでいきました。今回はグリッド上の各セル間の距離を扱います。例えば、下図のグリーンのセルからの各セルの距離を測る場合はどうしたらよいでしょう。

f:id:fxborg:20180413032040p:plain

距離の測るには

各セル間の距離は下図の様に六角形の対辺の長さと一致します。

f:id:fxborg:20180413111735p:plain

また正六角形の対辺の長さは三角比を使うと求められます。

f:id:fxborg:20180413032100p:plain

図のように三角形を配置するとこの三角形の一角は60°になります。これは正六角形の内角が120°なのでその半分の角度です。そして、この三角形は見てのとおり直角三角形なので各辺の比は「1:2:√3」となります。(参考:三角比(30°,45°,60°)|もう一度やり直しの算数・数学 )

 グリッドの基準サイズは六角形の中心から1頂点までの距離なので、例えばとあるセルから距離10以内のセルを求めるには

グリッド距離=ceil(10 / グリッドサイズ ×2 × √3)

 とすればOKです。

誤差の起こるエリア

通常の場合は上記の計算で問題ないのですが、下図の赤いエリアの点については少し注意が必要です。

f:id:fxborg:20180413134753p:plain

点Oからの近傍点を求めたいときに点Aと点BではAの方が近くにありますが、グリッド距離としてはAの方が遠くになります。

  • ・点OA間のグリッド距離は「2」
  • ・点OB間のグリッド距離は「1」

このことを考慮し、探索距離はセル1つ分ほどを大きくする必要があります。先ほどの式を修正するとこうなります。

探索距離=ceil(10 / グリッドサイズ ×2 × √3)+1 

 これでセル何個分まで探索範囲を広げれば良いか分かりました。

タートルグラフィックスによるアクセス法

 後は中心点から外に向かって対象範囲ぐるぐると移動しながらアクセスするだけです。このような処理には古典的なタートルグラフィックスを使うとよいでしょう。

タートルグラフィックスは1969年にLOGO社が自社の言語の教育目的に亀型のラジコンカーにペンを取り付けて図形を描かせたことに由来します。

f:id:fxborg:20180413140602p:plain

タートルグラフィックスは直進する歩数や方向転換の角度を指示することで、亀を移動させるような感じでプログラミングします。今回は以下のような軌跡で亀を歩かせたいと思います。 

f:id:fxborg:20180413032126p:plain

実際のコード

これは移動方向を定義したものです。6方向あります。

f:id:fxborg:20180413144601p:plain

次はタートルグラフィックスによるセルの移動です。1周分の処理を行います。

f:id:fxborg:20180413144924p:plain

最後は同心円状に探索範囲を拡大しながらリミットまで近傍点を探索します。

f:id:fxborg:20180413145050p:plain

実際のプログラムはこちらにあります。これを実行結果はこんな感じです。

f:id:fxborg:20180413213324p:plain

以上で、六角形グリッドで近傍点探索を行うために必要なポイントの説明は終わりです。

さらなる探求

ここまでの内容で一般的な六角形グリッドと言われるものについては大体分りました。
・・・ただ、もうちょっと改善出来るんじゃないかという思いも残りました。一番気になったのは点群が存在しない場合も、最大範囲までぐるぐるまわりながら全セルを確認する点です。一歩進むのがO(1)であるとは言え、何とかしたいところです。

スパイラル・ハニカム・モザイク

まず始めに「座標をセットする際に付近の情報を記憶させておけばなんとかなりそうだな」と考えました。程よい単位で情報を集約させ、そこに問い合わせれば隣接するセルの情報が確認できるという訳です。

これはちょうど部屋を探す際に不動産屋さんに行けば町中を歩いて探さなくても情報が得られる感じに似ています。

・・・と、ここまではすぐに思いついたのですが「どこにインデックスを配置するべきか」についてはなかなか分りませんでした。それでも調べていくと六角形グリッドと7進数の相性のよさ等が分かってきました。 

f:id:fxborg:20180413203709p:plain

7進数でセルをナンバリングして1桁目が0となる座標にインデックスを配置していくとよさげです。このような構造を「スパイラル・ハニカム・モザイク(Spiral Honeycomb Mosaic)」というそうです。このロジックの詳細については、またの機会に書こうと思います。

参考リンク

最後に参考になったリンク集(アイデアの宝庫のような)を書き残します。

Paul Bourke 氏によるスパイラル・ハニカム・モザイクについての説明
http://paulbourke.net/geometry/tilingplane/

Paul Bourke 氏による基数7と基数10の特徴についての説明
http://pdpseven.wixsite.com/sound-color/baseseven

キューブ座標とスパイラル・ハニカム・モザイクの相互変換についてのQ&A
https://gamedev.stackexchange.com/questions/71785/converting-between-spiral-honeycomb-mosaic-and-axial-hex-coordinates

Jeffrey Ventrella 氏によるフラクタルと空間充填曲線のビジュアルな説明http://www.fractalcurves.com/HorrorVacui.html

Sarah-Marie Belcastro さんによるノード・ゴスパー曲線の編み物をおりまぜた説明http://www.toroidalsnark.net/mkss3-pix/CalderheadJMM2014.pdf

単一モバイルを用いたノード・ゴスパー曲線をベースとした未知のセンサー位置特定
http://journals.sagepub.com/doi/abs/10.1177/155014775780101