S2 Geometry Libraryの概要と所感の続き。

軽い雰囲気でGo言語のS2 Geometry Libaryを使ってみたけど、使い方が全然分からなくて挫折。そして猛烈に反省。

というのも、ライブラリ中で多用されているCellという構造体がよく分からない。
にっちもさっちも行かなそうなので、S2 Cellsを読んで理解することにした。

主に、space-filling curve（空間充填曲線）という技術の話である。

S2 Cellsとは

S2ライブラリにおける空間の表現方法

S2では、単位球面上をcellと呼ばれる領域の集合に分解する。
各cellは4つの測地線を境界とする四角形である。

cellは階層を成している

最上位の階層は、正六面体の6つの表面を単位球に被せて得られる。こんな感じか・・・

最下位の階層は、各cellを再帰的に4つの子cellに分割し得られる。

例えば、下の図には緑と赤の2つの最上位のcellがある。赤のcellは再帰的に4つの子cellに分割されていることがわかる。

各cellを構成する辺は曲線である理由は、この辺が測地線であるためである。（測地線は曲線になる。飛行機の航路と同じように。）

cellはレベルを持つ

cellが分割された回数が、そのcellのレベルとなる。レベルの範囲は0から30（計31のレベルがある。）。レベル30のcellはleaf cellと呼ばれる。故に、cellの個数の最大値は以下である。

レベル30のcellは、地球上の距離に換算すると約1平方cmになる。（細か！すごい！）
各cellの換算表はこちら。

cell階層のメリット

cell階層により、空間インデックスを実装している。
そして、点集合や領域の集合は、cellによって表現（近似）される。
一般的に、点はleaf cell、領域は任意のレベルのcellとして表現される。
例えば、ハワイは以下のような22個のcellの集合で近似される。

S2CellIdとは

各cellにはユニークな識別子（64ビットの整数）が割り当てられている。これをS2CellIdと呼ぶ。
これにより、空間インデックスを用いた参照局所性が可能となる。

識別子の割り当て方

space-filling curve（空間充填曲線）順に識別子が割り当てられている。
S2では、各曲線をS2 space-filling curveと呼ぶ。
この曲線は、互いにリンクされた6つのヒルベルト曲線を含む。
これにより、球の表面を1本の連続曲線で埋め尽くすことができ、この連続曲線は全てのcellを通過する。例えば、レベル5の分割を行なった後、ヒルベルト曲線を描いた図が以下である。

レベル5のcellは曲線に従い、昇順に識別子が割り当てられる。
したがって、2つのcellが隣接していれば、それらのS2CellIdも隣接した識別子となる。これにより、局所参照性を実現している。

S2 space-filling curve曲線はヒルベルト曲線に基づいているため、より詳細に識別子の割り当て方を解説するために、ここから暫くはヒルベルト曲線についての説明が続く。
既知の方は読み飛ばしても構わない。

ヒルベルト曲線の定義

ヒルベルト曲線は、定義域（一次元の範囲）[0,1]から値域（二次元平面上の矩形）[0,1]x[0,1]を持つ関数である。この関数は、単位球上の全ての点を通る曲線となる。ヒルベルト曲線は連続であるが微分可能ではない。また、無限の長さを持つと見なす。

Hをヒルベルト曲線の定義域と値域。

ヒルベルト曲線の作り方

下の図のように、再帰的に正方形を分割しながら作る。

最初の分割において、正方形を4つに分割し、分割された全ての領域を通るように曲線を描く。領域を通る順番は決まっている。この例の場合、左下、左上、右上、右下、の順番で曲線が通る。

次の分割において、最初の分割で得られた領域を、さらに4つに分割し、分割された全ての領域を通るように曲線を描く。（曲線は連続するように上手いこと描かれるが、ここでは詳細は述べない。）

一次元の範囲をどのようにして二次元平面上の矩形へ写すの？

具体例で説明する。H(0.5)を二次元平面上へ写す場合を考える。
0.5を二進数表記にすると、

0.1000000000000...

となる。この2進数の小数部を2ビットで区切る。

[10,00,00,00,00,...]

区切られたものを左から順に見ていく。

最初は10で、10進数で2。次が00で、10進数で0。以下同様にして

[2,0,0,0,0,...]

が得られる。

そして、0に左下、1に左上、2に右上、3に右下と割り当てる。
すると、

[右上、左下、左下、左下、左下、...]

となる。
これに従い、以下の図のように再帰的に正方形を分割すると・・・

に収束する。
このようにして、一次元の範囲をどのようにして二次元平面上の矩形へ写す。

S2 space-filling curve曲線の定義

S2 space-filling curveは以下の関数である。

この関数の定義域は一次元の範囲[0,6]、値域は単位球面上となる。

一次元の範囲をどのようにして単位球面上へ写すの？

例えば、S(1.4)を単位球面上へ写す場合を考える。
小数部を除いた整数が1。これは、正六面体の6つの表面を単位球に被せて得られる6つの面のどれであるか？を表している。

1の面は、インドが含まれている面。

そして小数部は、先ほど説明したヒルベルト曲線の0.4となる。
このようにして、一次元の範囲をどのようにして単位球面上へ写す。

識別子の割り当て方（再）

具体的なS2CellIdの割り当て方は以下である。

S2CellIdは、そのcellの中心におけるS2 curveパラメータである。（ただし、S2CellIdを整数値にするためにスケーリングされる）

具体的には例で説明する。
レベル0の面2に割り当てられる識別子は

010.1000000000...

小数部を除いた010は2（面2を表す）。
小数部0.10000000は、その面の中心を表す。
010.1000000000...は整数ではないので、スケーリングして整数にする。具体的には2の61乗をかける。得られる整数値の16進数表記は0x5000000000000000である。これがレベル0の面2に割り当てられるS2CellIdである。

ヒルベルト曲線の性質上、全てのcellの中心が重なることはないため、全てのS2CellIdは異なる数値となる。

<・・・ここから、ちょっと省略。いつか訳す>