5
Help us understand the problem. What are the problem?

More than 3 years have passed since last update.

posted at

Organization

S2 Geometry Library S2Cellsとは

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のcellleaf cellと呼ばれる。故に、cellの個数の最大値は以下である。

6 \times 4^{30}

レベル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をヒルベルト曲線の定義域と値域。

H: [0,1] \rightarrow [0,1] \times [0,1]

ヒルベルト曲線の作り方

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

最初の分割において、正方形を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に右下と割り当てる。
すると、

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

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

H(0.5) = (0.5, 0.5)

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

S2 space-filling curve曲線の定義

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

S: [0,6] \rightarrow S^2

この関数の定義域は一次元の範囲[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は異なる数値となる。

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
5
Help us understand the problem. What are the problem?