S2 Geometry Library S2Cellsとは

[S2 Geometry Libraryの概要と所感](https://qiita.com/szit/items/83184ca5c8893ba13c2a)の続き。

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

というのも、ライブラリ中で多用されている`Cell`という構造体がよく分からない。
にっちもさっちも行かなそうなので、[S2 Cells](https://s2geometry.io/devguide/s2cell_hierarchy)を読んで理解することにした。

主に、[space-filling curve（空間充填曲線）](https://ja.wikipedia.org/wiki/%E7%A9%BA%E9%96%93%E5%85%85%E5%A1%AB%E6%9B%B2%E7%B7%9A)という技術の話である。

# S2 Cellsとは

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

S2では、単位球面上を`cell`と呼ばれる領域の集合に分解する。
各`cell`は4つの[測地線](https://ja.wikipedia.org/wiki/%E6%B8%AC%E5%9C%B0%E7%B7%9A)を境界とする四角形である。

## `cell`は階層を成している

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

![](https://iwiz-chie.c.yimg.jp/im_siggs.lfgeD.ovywHHxDggaqoA---x320-y320-exp5m-n1/d/iwiz-chie/que-10118662220)

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

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

![](https://s2geometry.io/devguide/img/s2hierarchy.gif)

各`cell`を構成する辺は曲線である理由は、この辺が測地線であるためである。（測地線は曲線になる。[飛行機の航路と同じ](https://blog.esrij.com/arcgisblog/mt-img/arcgisblog/images/2015/10/16/image2_2.png)ように。）

### `cell`はレベルを持つ

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

```math
6 \times 4^{30}
```

レベル30の`cell`は、地球上の距離に換算すると約1平方cmになる。（細か！すごい！）
各`cell`の換算表は[こちら](https://s2geometry.io/resources/s2cell_statistics)。

## `cell`階層のメリット

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

![](https://s2geometry.io/devguide/examples/img/hawaii.gif)

# S2CellIdとは

各`cell`にはユニークな識別子（64ビットの整数）が割り当てられている。これを`S2CellId`と呼ぶ。
これにより、空間インデックスを用いた[参照局所性](https://ja.wikipedia.org/wiki/%E5%8F%82%E7%85%A7%E3%81%AE%E5%B1%80%E6%89%80%E6%80%A7)が可能となる。

## 識別子の割り当て方

[space-filling curve（空間充填曲線）](https://ja.wikipedia.org/wiki/%E7%A9%BA%E9%96%93%E5%85%85%E5%A1%AB%E6%9B%B2%E7%B7%9A)順に識別子が割り当てられている。
S2では、各曲線を`S2 space-filling curve`と呼ぶ。
この曲線は、互いにリンクされた6つの[ヒルベルト曲線](https://qiita.com/taichi_itoh/items/09e075fbd68b32d26135)を含む。
これにより、球の表面を1本の連続曲線で埋め尽くすことができ、この連続曲線は全ての`cell`を通過する。例えば、レベル5の分割を行なった後、ヒルベルト曲線を描いた図が以下である。

![](https://s2geometry.io/devguide/img/s2curve-large.gif)

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

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

### ヒルベルト曲線の定義

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

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

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

#### ヒルベルト曲線の作り方

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

![](https://s2geometry.io/devguide/img/hilbert-figure.gif)

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

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

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

![](https://s2geometry.io/devguide/img/hilbert-cell-center.gif)

```math
H(0.5) = (0.5, 0.5)
```

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

### `S2 space-filling curve`曲線の定義

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

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

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

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

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

![](https://iwiz-chie.c.yimg.jp/im_siggs.lfgeD.ovywHHxDggaqoA---x320-y320-exp5m-n1/d/iwiz-chie/que-10118662220)

![](https://s2geometry.io/devguide/img/s2cell_global.jpg)

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`は異なる数値となる。

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