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

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

スポンサーリンク

Hexagonal Gridのさらなる高率化(スパイラル・ハニカム・インデックス)

Hexagonal Gridを改良しました。これで疎な点群のレンジサーチにも対応できます。

グリッド構造は中心位置を仮定しないような点群を格納するのに優れたデータ構造ですが、疎なデータを単純に範囲検索するような用途にはあまり向いていません。例えばその領域内に一点しか無かった場合もグリッド内の全セルにアクセスしちゃう感じです。

(参考:https://www.redblobgames.com/grids/hexagons/#range

これを改善するには隣接セルの情報を保持するなどしてアクセス回数を減らせればよいのですが、やみくもにインデックスを保持しても更新負荷が激増してしまいます。

そういうことで、今回はHexagonal Grid に適したインデックス構造を考えてみました。

Spiral Honeycomb Index(スパイラル・ハニカム・インデックス)

f:id:fxborg:20180605224212p:plain

  • ・7セル単位でまとめて中心にインデックスを配置する。
  • ・中心のインデックスは半径2セルのエリアをカバーする。  

7セル単位にまとめる

6角形を7つ合わせると大きな6角形になります。この中心にあるセルにインデックスを登録したいのですが、どうやって判定したらいいでしょうか?

これについてはずいぶん考えたのですが結局分らずじまいで・・・、しつこくググるとこちらの答えにたどり着きました。

この中心位置を求めるには以下の簡単な式を使います。

f:id:fxborg:20180605231330p:plain

この結果が0となる座標をインデックス・セルと定めます。この簡潔で強力な式はこちらのやりとりに載っていました。

※C++の場合は負の除数に対応していないので注意が必要です。

インデックスへの登録

 データを追加する時にどのインデックスに登録するかは対象セルとインデックス・セルとの距離によって決まります。2セル以内の距離にインデックスがあれば、そこに自身の存在を記録します。

・・・ただし、実際は位置関係パターンが7とおりしかないのでルックアップ・テーブルを使用して簡単に済ませています。

f:id:fxborg:20180605235158p:plain

こちらは南に点がある最のインデックス位置です。

インデックスのカバー範囲

勘の良い方はお気づきだと思いますが、インデックスのカバーする範囲をちょっと大きめにしています。その理由はインデックス・セルからずれた点を中心に範囲検索をしても精度を落としたくなかったからです。その分インデックス領域は取られますが、疎なデータに対してだったら問題ないと思っています(密なデータなら普通のグリッドで十分)。

探索時の巡回方法

例えば任意の点から範囲検索を行うには、まず最寄のインデックス・セルに移動してそこから同心円状に各インデックス・セルを巡回していきます。各インデックスにはカバー範囲のデータの存否を把握しているのでこれだけで全てのセルの情報の存在確認を行えます。

f:id:fxborg:20180606000712p:plain

距離の求め方

また、インデックス・セル間の距離が分れば周囲のセルの距離も求めることができます。インデックス・セルの位置がコーナーか否かによって距離のパターンが異なるのですがこちらもルックアップ・テーブルで対処しています。

f:id:fxborg:20180606003119p:plain

これで全ての準備が整いました。距離別に色を変えて実際にプロットしてみるとこんな感じです。

f:id:fxborg:20180606004748p:plain

こうしてプロットしてみると見事なスパイラル・ハニカム・モザイクですね。 

最後に

このアイデアはかなり前に出来ていたのですが、検証作業にずいぶん時間が掛かかりました。今この記事が書けてほっとしています。

C++からPythonを呼び出して可視化するなどしてみたのですが、却ってビルド時間が長くなり効率は上がりませんでした。最終的にはストリーム経由でPythonにデータを送ってmatplotlibで表示という線で落ち着きました。また今回はCMake+Ninjaでビルドをしています。

実際のコードはこちらからどうぞ