S2 Geometry Library

Takami Torao #S2
  • このエントリーをはてなブックマークに追加

概要

S2 Geometry Library は球面上の領域を扱うための空間インデクシング (spatial indexing) ライブラリ。主に地球を対象としており、地理データを分割統治や索引付けのためのセル (区画) に分割することを目的としている。また非常にコンパクトで 64bit 整数で地球表面上の 1cm 四方を表す解像度を持つ。

変換方法

S2 Geometry Library は以下の方法で球体状の領域を 64bit 整数の幅にパックする。

  1. 球体に接する立方体を仮定し、球面上の点 \(P\) を投影する。この投影により点 \(P\) は立方体状の面とその平面上の座標 \(P' = ({\rm face}, x', y')\) で表すことができる。
  2. 投影した状態では角度が小さい位置の領域は小さく、45°に近い位置の領域は大きくなり配置に偏りが生じるため、投影後に拡大率を調整し \((0, 1)\) の範囲となるように変換する。S2 では正確で速度の遅い \(\arctan\) を使った計算ではなく 2 次式を使用している。
  3. 点 \(P\) が投影された立方体の面 (正方形) が適切な精度のセルとなるよう四分木に分割する。四分木の深さを表すレベルは 0 から 30 の範囲をとり、大きくなるほど精度が高く (セルが小さく) なる。分割された正方形から点 \(P\) を含むセルのヒルベルト曲線上の距離 (ステップ数) を求める。
  4. 立方体上の面 \(0 \leq {\rm face} \leq 5\)、四分木の深さレベル \(0 \leq {\rm level} \leq 30\)、ヒルベルト曲線上の位置 \(0 \leq p \leq 2^{2\times{\rm level}}-1\) を 64 ビット整数にパックした値をそのセルの ID とする。

レベルの精度とセルの解像度

地球を半径 \(R\)=6,378km の球体と仮定した場合、その表面積 \(S = 4\pi R^2\) を立方体の 6 面で分割した \(S_0 = \frac{4\pi R^2}{6}\) がレベル 0 のセル相当の面積となる。\(S_0\) をレベルごとのセル数 \(2^{2\times{\rm level}}\) で割った面積がそのレベルで表現できる大まかな精度 (解像度) と考えることができる。

Level Cell
0 85,201,305km²
1 21,300,326km²
2 5,325,082km²
3 1,331,270km²
4 332,818km²
5 83,204km²
6 20,801km²
7 5,200.3km²
8 1,300.1km²
9 325.0km²
Level Cell
10 81.25km²
11 20.31km²
12 5.08km²
13 1.27km²
14 317,400m²
15 79,350m²
16 19,837m²
17 4,959.4m²
18 1,239.8m²
19 310.0m²
Level Cell
20 77.49m²
21 19.37m²
22 4.84m²
23 1.21m²
24 3027.0cm²
25 756.7cm²
26 189.2cm²
27 47.30cm²
28 11.82cm²
29 2.96cm²
30 0.74cm²

レベル 30 では地球上の領域を 1cm×1cm より高い解像度で表すことができる。

参照

  1. s2-geometry-library
  2. Geometry on the Sphere: Google's S2 Library
  3. Google’s S2, geometry on the sphere, cells and Hilbert curve