S2 Geometry Library

S2 Geometry Libraryについてちょっと調べてみたので、その結果をまとめた。
Go言語で幾何学計算を扱いたいなぁ・・・と思ってググっていたら、S2にたどり着いた。

主に、本家ページを参考にした。

所感

先に所感を述べておく。
「触ってみた」訳じゃないけれど、事前調査として得られた情報から推測した所感です。

• パフォーマンスを重視して作られている印象。
  • C++だし、インデックス機能とかも実装されているし・・・。
• Googleで使われていた。多分。

規模の大きな幾何学計算には使えそう。
Googleで使われていたならば、幾何学計算の文脈では、信頼できそう。但し、以下の点で不安がある。

• 情報が少ない。
  • ネット上で検索してもあまり情報が出てこない。英語で検索しても同様。
  • あまり使われていないのかも・・・。
  • Google自身は、本腰を入れて保守しようとは思っていない。多分。
  • こちらのリポジトリのREADME.mdには、「Googleの公式プロダクトではない」との記述がある。
  • 元々、オープンソース化する気が無かったのではないか？
  • コントリビューターも少ない・・・。Go言語向けのライブラリのソースコードなどは、ほとんど１人だけがコミットしてる。

保守性の文脈では、将来性が心配な感じ。

以下、調べて得られた情報

本家ページに色々書いてあったので、読んでみた。
正直言って、有益な情報は少なかったので（利用者はしらなくていいだろという情報が多かった印象）、あまり真面目に読んでいない。

何をするためのライブラリ？

• 幾何学計算

特徴

• Googleで作られた。
  • ただし、本ライブラリは公式のGoogleのプロダクトではないみたいである。
• 元々はC++のライブラリ。後からGo、Python、Java向けに移植された。ただし、C++言語以外では、C++と同様の堅牢性、パフォーマンス、機能は提供できない。
  • Go: 現在も活発に開発されており、ゆくゆくはC++バージョンと完全に同様の要件になることを目指している。しかしながら、リポジトリを見てみると、まだ実装されていない機能も多い。
  • Java: 2011年にリリースされたS2ライブラリを移植したもの。その後、アップデートされていない。
  • Python: SWIGを用いて部分的に移植されたもの。ソースコードは、C++のソースコードと同じリポジトリにある。（・・・どの程度サポートされているか？についての言及はない。）
• 2D平面上の幾何学計算ができる。
• 2D平面上だけでなく、3D球面上の幾何学計算もできる。即ち、地図データも扱えるということ。
• 空間に対するインデックス機能の実装。
  • 高速で、インメモリインメモリ。
  • 点、多角形に対してインデックスを付与。
• ロバスト（以降、「堅牢」と訳す）で効率の良い幾何学計算を実装。

情報源

• 本家ページ

ライセンス

Apache 2.0

このライブラリの価値

平面に描かれた地図は歪んでいるが故に、地図上における幾何学計算結果も歪んでいる。
なぜなら、地球は大雑把に言えば球面であり、その球面上の座標を平面上の点に変換し、地図が作成されているからである。
球面から地図上への変換方法は図法と呼ばれており、よく使われている変換方法は大体決まっている。
（よく使われている図法はこちら）

この歪みを考慮した幾何学計算の実装は非常に面倒臭い。
（多くの数学的知識と、地理情報システムに関する知識が必要）

だから、信頼性のあるライブラリが提供されていることは非常に有り難いのである。

S2で用いられている投影方法（Projection）

S2は、地球上の座標を（数学的に純粋な）球面上の点に変換（spherical projections）し、変換後の球面上で幾何学計算する。
厳密に言えば、地球は完全な球面ではないため、この幾何学計算も歪んでいる。
しかしまあ、平面よりも歪みは小さくできる。
歪みが小さいという主張の根拠は以下である。

• spherical projectionsを用いれば、
  • その歪みを最大で0.56%に抑えることができる。
  • 地球上の位相は保たれる。

楕円体上の点への変換をしないのはなぜ？

楕円体上の幾何学計算コストは高くつくので、球体へ変換している。
実は、地球は球体よりも楕円体に近い。だから、楕円体へ変換した方がより歪みを小さくできる。
しかし、楕円体上の幾何学計算は堅牢ではなく、かつ、パフォーマンスの面で劣る。

ところで、堅牢とは？

堅牢とは、数学的に厳密な保証がある、ことを言う。
S2では、全ての幾何学計算が堅牢である。
・・・とあるが、正直よく分からなかった。計算機科学のテキストを購入し理解した方が良いだろう。堅牢は日本語で「堅牢性」と訳される。多分、これとかに言及があるんじゃないか。

柔軟性がある

S2は、以下の点で柔軟性のあるライブラリだと言える。

• ライブラリの利用者が制御できることを、できるだけ増やしている。
• 豊富なAPIが用意されている。

高パフォーマンス

インメモリインデックスにより、大きな地理データを高速に扱える。

スコープ

S2ライブラリは以下を提供する

• 幾何形状を扱い、それらに対する操作。例えば、角度、範囲、緯度経度の点集合、単位ベクトル等。
• 単位球上の幾何形状。例えば、球冠、緯度経度矩形、緯度経度連続直線、緯度経度多角形。
• 点集合、連続直線、多角形に対する、堅牢な構造的操作と判定関数。
• 点集合、連続直線、多角形に対する、高速なインメモリインデックス。
• 近接するオブジェクトへの距離を測定し、それを探索するためのアルゴリズム。
• 幾何形状を切り取る、歩いは、単純化するための堅牢なアルゴリズム（正確に位相が保たれることが保証されている）。
• 幾何オブジェクト同士の関係性を判定するための効率の良い数学的判定関数。
• 空間インデックス。連続的な領域を、S2 cellsと呼ばれる離散的なデータ構造で近似し、実現している。
• Googleの大規模な地理データによるテスト。
• よく使われているGISフォーマットの変換機能。

階層化された設計

S2のオブジェクトは階層化されていて、各階層毎に操作が可能。
高い階層に対する操作は、それより低い階層に対する操作を隠蔽する。

例えば

• 最低層
  • S2Point, S2CellId, S2LatLng, S2Region, ... etc
• 次の階層
  • この階層では多角形に対する幾何学計算をサポートしている。
  • この階層には点集合や多角形を含む。
  • これらのオブジェクトは、以下のクラスにより構築される。
  • S2Builder, S2ShapeIndex, ... etc
• 最後の階層
  • S2Polygon, S2Loop, S2Polylineのようなクラスを含む。

その他、注目すべき点

S2の辺は、球面上の測地線である。

S2において、辺は球面上の測地線として扱われる。
測地線とは球面上の2点間の最短パスのこと。

測地線として扱うことのメリットは以下。
* 辺が南極、北極、子午線を跨ぐ場合における、特別なケースがなくなる。
例えば、子午線を跨ぐ辺は単に子午線を跨ぐだけであり、子午線で切断されない。

多角形における方向の定義

S2において、Polygon loopは、その左側を内部領域とする。

ライブラリ内部でのデータの持ち方

S2において、点は、内部的には単位球面上の単位ベクトルとして表現されている。緯度・経度の座標ではない。

このようにした理由は、点を測地線と一緒に処理する際、単位ベクトルの方が計算効率が良いからである。
緯度・経度の座標を用いた場合、三角関数を介した計算が必要となる。三角関数の計算は高コストである。

Classes vs. Functions

S2において、ほとんどのアルゴリズムは関数ではなくクラスとして実装されている。

なぜなら、
* データ構造の再利用、キャッシュを実装するためである。
例えば、S2ClosestEdgeQueryオブジェクトにより生成されたクエリは、その内部にキャッシュを持っていて、クエリの再計算を行なわない。