位置情報を扱いながら高速に検索する必要がある場合、DB上で範囲検索が容易にできると便利です。GeoHashなどの位置情報のハッシュ計算をしておいて、ハッシュで範囲検索をするとインデックスを活用できて良いです。一方でドキュメントの少ないS2ライブラリについて調査したので、ざっくりまとめました。Codeに上がっているのが分かる程度で、あまり情報はないように思えます。アルゴリズム解説のドキュメントは、http://blog.christianperone.com/2015/08/googles-s2-geometry-on-the-sphere-cells-and-hilbert-curve/こちらの記事がわかりやすく、平面状をヒルベルト曲線で埋めていくことや、エンコードされたCellIDの包含判定が前方一致(厳密には末尾1ビットを削る等の処理は必要だが)でできる特徴などがわかりやすく解説されているので良いです。S2他言語へのポートS2のライブラリをGoに移植したものや、Pythonに移植したものが盛んに開発されているので利用すると良いと思います。今回はGoへの移植版を利用してみます。R3の部分、S1の一部等は完了しているのですが、S2の部分はまだ本格的に利用するには機能が足りない部分等が多く見られますが、活発に開発はされているようなので、遠くない未来にいい感じになると思います。PRを送ってみるのもいいかと思います。実際には球の表面に沿って曲がっているのでキャップのような形になっています。点と点の角度や、球の大円に対する比率で扱います。引数は、キャップの頂点となる球面上の点と、キャップの縁の大円に対する比率で表現します。図ですと、赤い部分が球を切ったときのCapです。これがちょうどみかんの皮のように球の表面を完全にキャップが覆っている状態です。地球のサイズの球を想定して比率計算をする必要があります。6371.01になります。s1.Angle(ratio))}こんな風にする必要があります。次はS2の機能を利用してこの円をCellで埋めてみましょう。計算するための型です。30というところで、S2が扱える最小サイズのセルまで使ってもよいと指定し、さらにMaxCellsで被覆するにに使うセル数の最大数を指定しています。}}でどんなCellで円を埋められるのか計算できます。この結果をGoogleMapで可視化してみたものが以下になります。GoogleMapの機能で渋谷駅から半径4kmを描いてみたものです。はみ出しているところが目立ちますねセル上限100の場合すこしはみ出しが減りました。セル上限200の場合かなりはみ出しが改善しました。ユースケースたとえば、データベース上に大量の位置情報を格納しておいて、必要に応じて高速に円の中に含まれているデータを取り出したい場合、あらからじめ位置情報をS2でCellIDに変換しておき、今回の円で得られたCellIDと前方一致で調査するという形になります。これがある地形内(ポリゴン内)に含まれている全データ等を求めたいときにデータベースの範囲インデックスを効かせて計算できるのは非常に高速に求められると思います。残念ながらポリゴンのサポートはまだGo版のS2ではできていませんが、Python版のライブラリもありますし、MongoDBやUber、Forsquareなどのサービスでも利用されているので、位置情報を扱う何かをするときには検討してみても良いかもしれません。まえからS2は気になっていて、今日調査してみたのでまとめてみました。何か成果があれば追ってまとめます。s...2013-09-02NasmでLifeGame更新が非常に空きました。久々にアセンブラです。»プロフィールid:Pocket7878_devプログラミング好きで、仕事の傍らで趣味で書いたもの等があればちょびちょび更新していきます。Inc.はてなブログをはじめよう!Pocket7878_devさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。