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

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

スポンサーリンク

近傍点探索のためのHexagonal Grid 

作りかけのサポート・レジスタンスのインジケーターで近傍点探索に使ってるロジックがストリームデータに耐えられないという問題があり、今はHexagonal Grid(六角形グリッド)に置き換える作業をしています。

「近傍点探索」自体は機械学習などでもよくあるテーマですが、ストリームデータ向けのものとなるとあまり情報が見つかりません。

ワールド座標が固定されている場合は領域木などのデータ構造でもよいのですが、ストリームデータでは中心位置がどんどん後方に遠ざかっていくので時間とともにツリーのバランスが崩れてしまいます。それを解消する為には定期的にツリーを再構築するなどの方法を取るのですが、これには無視できない負荷が生じます。

じゃあ中心位置を仮定しなくてもいいデータ構造はないかと調べると「グリッド構造」なら格納できるようです。

領域木とグリッドの違い
  • ・領域木などは互いの点の位置関係により配置先が決定されるので格納順などでデータの配置が変動する。

  • ・グリッド構造の場合は、座標から直接マス目の位置を割り出すので他の点の位置は影響しない。 

グリッド構造の種類

グリッド構造にはマス目の形状によっていくつかの種類があります。正三角形、正方形、正六角形だけが、規則的な形状のグリッドを構成できます。

f:id:fxborg:20180330005550p:plain

最も分りやすいのは正方形のグリッドです。これは方眼紙のイメージです。

六角形グリッドの利点はマス目の中心から隣接するすべてのマス目までの距離が同じなので、近傍点探索に適しています。

解説サイト「Red Blob Games」

六角形グリッドを理解するには、こちらの解説ページが参考になりました。今回の作成したプログラムもこの記事に大きく影響を受けています。

「Hexagonal grid reference」 from Red Blob Games
f:id:fxborg:20180330005820p:plain
https://www.redblobgames.com/grids/hexagons/

全部読んだ方が理解が深まりますが、これだけ知ってれば一応は何とかなります。

  • ・フラットトップとポインティトップの違い
  • ・2D座標をキュービック座標に変換する方法
  • ・グリッド・ストレージの実装方法
  • ・キュービック座標上での距離の測り方

フラットトップとポインティトップの違い

六角形グリッドには横向きと縦向きの2種類があり六角形の頂点が上に来るものを「ポインティトップ(Pointy topped)」と呼び、辺が上に来るものを「フラットトップ(Flat topped)」と呼びます。

f:id:fxborg:20180330225507p:plain

ポインティトップを「バーティカル」、フラットトップを「ホリゾンタル」と呼ぶ場合もあります。これが最初に知っておくべきことです。簡単ですね。

2D座標をキュービック座標に変換する方法

六角形グリッドの座標系にも幾つかの種類があるのですが、とりあえずキュービック座標系が分ればなんとかなります。キュービック座標系は(q,r,s)の3軸からなります。先ほどのポインティトップとフラットトップで軸の向きが異なります。

座標変換を行うには、グリッドの基準サイズを決める必要があります。これは六角形の中心から頂点までの長さを意味します。

f:id:fxborg:20180330233140p:plain

これで計算の準備が整いました、2D座標(x,y)をキュービック座標に(q、r、s)に変換するのはこのようにします。

【ポインティトップ の場合】

f:id:fxborg:20180330225718p:plain

【フラットトップ の場合】

f:id:fxborg:20180330225618p:plain

意外と簡単でしょう。

グリッド・ストレージの実装方法

ここまでのものをプログラムにします。最初に作るのは(q,r,s)の座標を格納するHexagonクラスです。基本的には次のような構成になっています。

f:id:fxborg:20180330235858p:plain

これは(q,r,s)を保存するだけの単純なものですが、このクラスを連想配列のキーとして使えるようにしたいと思います。キーに対応するには、インスタンス同士を比較するための演算子を定義すればよいそうです。こちらの記事にありました。

c++で連想配列といえば通常は std::map、std::unordered_map ですが、速度的にイマイチです。すこし調べてみると「Tessil/ordered-map」というライブラリが見つかりました。これはキーによる参照が平均O(1)でしかも挿入順序保持という優れモノです。

Hexagonクラスをこれに対応するとこうなりました。

/**
 * Hexagon class
 */
class Hexagon
{
public:
	// constructors
	explicit Hexagon() : q_(0), r_(0), s_(0) {}
	explicit Hexagon(double q, double r) : q_(q), r_(r), s_(-q - r) {}
	explicit Hexagon(double q, double r, double s) : q_(q), r_(r), s_(s) {}

	// copy constructor
	Hexagon(const Hexagon& hex) : q_(hex.q()), r_(hex.r()), s_(hex.s()) {}

	//--- operators ---
	// = operator
	Hexagon& operator = (const Hexagon& hex)
	{
		if (&hex != this)
		{
			q_ = hex.q();
			r_ = hex.r();
			s_ = hex.s();

		}
		return *this;
	}
	// equal operator
	bool operator==(const Hexagon& hex) const
		{ return q() == hex.q() && r() == hex.r() && s() == hex.s();}
	// not equal operator
	bool operator!=(const Hexagon& hex) const	{return !(*this == hex);}

	// greater operator
	bool operator<(const Hexagon& hex) const
		{ return (abs(q()) + abs(r()) + abs(s())) < (abs(hex.q()) + abs(hex.r()) + abs(hex.s()));}

	// less operator
	bool operator>(const Hexagon& hex) const
		{ return (abs(q()) + abs(r()) + abs(s())) > (abs(hex.q()) + abs(hex.r()) + abs(hex.s()));}

	// add operator
	friend Hexagon operator+(const Hexagon& hex0, const Hexagon& hex1)
		{ return Hexagon(hex0.q() + hex1.q(), hex0.r() + hex1.r(), hex0.s() + hex1.s());}

	// subtract operator
	friend Hexagon operator-(const Hexagon& hex0, const Hexagon& hex1)
		{ return Hexagon(hex0.q() - hex1.q(), hex0.r() - hex1.r(), hex0.s() - hex1.s());}

	// multiplication( hex * n )
	friend Hexagon operator*(const Hexagon& hex, const double& n)
		{ return Hexagon((hex.q() * n), (hex.r() * n), (hex.s() * n));}

	// multiplication( n * hex ) 
	friend Hexagon operator*(const double& n, const Hexagon& hex)
		{ return Hexagon((hex.q() * n), (hex.r() * n), (hex.s() * n));}

	// --- members  ---
	double& q() { return q_; }
	double& r() { return r_; }
	double& s() { return s_; }

	double q() const { return q_; }
	double r() const { return r_; }
	double s() const { return s_; }

private:
	double q_;
	double r_;
	double s_;
};

少々長くなりましたが基本的な演算子(=,==, !=, <, >, +, -,*)を追加しただけです。このクラスはデータ型としての意味合いが強いので演算子もいろいろあった方がいいと思って追加しました。

最終的な六角形グリッドのデータ構造はこんな感じです。

f:id:fxborg:20180331004801p:plain

 完全なソース一式はこちらです。(https://github.com/fxborg/hexagonal-grid

 これを実行すると2D座標からキュービック座標へ変換結果が出力されます。ポインティトップとフラットトップの両方で行われます。

f:id:fxborg:20180329021631p:plain

変換前の2D座標群 [a(1,1)、b(1,5)、c(5,1)、d(5,5)、o(3,3)]を可視化するとこんな感じです。

f:id:fxborg:20180331010310p:plain

 出力結果の座標をみてもキュービック座標上にどのように配置されるのかさっぱり分らなかったので図にしてみました。

▼ポインティトップ座標への変換結果

f:id:fxborg:20180329021826p:plain

▼フラットトップ座標への変換結果

 f:id:fxborg:20180329022148p:plain

こうやって実際に描き出すと確かに同じ位置関係になっていることが分ります。グレーの円はグリッドサイズでこの範囲に収まれば同じキーに配置されます。

ポインティトップはy軸の順序関係が維持され、フラットトップ はx軸の順序関係が維持されます。時系列データの場合はx軸方向の順序関係が大事なのでフラットトップがよさそうです。

最後のポイントは「キュービック座標上での距離の測り方」ですが、長くなったので次回にします。

最後に

六角形グリッドは難しいそうな印象を持っていました。特にキュービック座標への変換結果がイメージしづらくてなんだか腑に落ちなかったのですが、イメージさえ掴めれば実はそんなに難しくないことが分ると思います。それからTessil/ordered-mapもパワフルなライブラリなので積極的に利用したいと思います。