グリッド（空間インデックス）

空間インデックスの文脈において、グリッドまたはメッシュとは、多様体または2次元表面を規則的に分割し、連続するセルに分割したものです。これらのセルには一意の識別子が割り当てられ、空間インデックスの作成に使用されます。このようなグリッドには、「正方形」または「長方形」のセルに基づくグリッド、三角形のグリッドまたはメッシュ、六角形グリッド、ひし形セルに基づくグリッドなど、多種多様なものが提案または現在使用されています。「グローバルグリッド」は、地球の表面全体を覆うグリッドの一種です。

グリッドの種類

正方形または長方形のグリッドは、直交座標（緯度と経度）で表現された空間情報をグリッドシステムに変換するなどの目的で頻繁に使用されます。このようなグリッドは、緯度と経度のグリッド線に沿っている場合とそうでない場合があります。たとえば、マースデン方眼、世界気象機関方眼、C方眼などは整列していますが、ユニバーサル横メルカトル座標系や英国国立グリッド参照システムなどのさまざまなローカルグリッドベースのシステムは整列していません。一般に、これらのグリッドは「等角」または「等面積」の2つのクラスに分類されます。「等角」のグリッドは、セルサイズが緯度と経度の度数では一定ですが、面積は不等です（特に緯度が変化すると不等になります）。「等面積」のグリッド（統計グリッド）は、セルサイズが地上の距離（例：100 km、10 km）では一定ですが、特に経度の度数では不等です

一般的に使用されている三角グリッドは、「四分三角メッシュ」（QTM）で、1980年代初頭にジェフリー・ダットンによって開発されました。このメッシュは最終的に、1999年に「地理処理と地図作成のための階層的座標系」と題された論文として発表されました。^{[ 1 ]}このグリッドは、Microsoft Encarta製品の一部である回転可能な地球儀の基盤としても採用されました。

六角形グリッドも使用できます。一般的に、三角形と六角形のグリッドは、等面積（またはほぼ等面積）という目標に近づき、かつ極間をよりシームレスにカバーするように構築されます。これは、正方形や長方形のグリッドでは問題となる領域です。これらのグリッドでは、極でセル幅がほぼゼロになり、極に隣接するセルが4辺ではなく3辺になってしまうためです。GoodchildとKimerling ^{[ 2 ]}は、最適な離散グローバルグリッド化の基準を提案しており、等面積セルが最も重要であると考えられています。

四分木グリッドは、2次元空間全体にわたって、フィッティングするデータの性質と複雑さに応じてグリッドの解像度が変化する特殊なグリッド形式です。極座標グリッドは極座標系を利用し、所定の半径を持つ円を一定の角度の扇形に分割します。座標は、グリッドの中心からの半径と角度で表されます。

グリッドベースの空間インデックス

実際には、グリッドベースの空間インデックスの構築には、関連するオブジェクトをグリッド内の位置に割り当て、オブジェクト識別子とグリッドセル識別子のインデックスを作成して迅速なアクセスを可能にすることが含まれます。これは、「データ駆動型」またはデータ依存型手法とは対照的に、「空間駆動型」またはデータ非依存型手法の例であり、Rigaux et al. (2002) でさらに説明されています。^{[ 3 ]}グリッドベースの空間インデックスには、インデックスの構造を最初に作成し、インデックス構造を変更することなく継続的にデータを追加できるという利点があります。実際、異なるデータ収集およびインデックス作成アクティビティで共通のグリッドが使用されている場合、このようなインデックスはさまざまなソースから簡単にマージできます。一方、Rツリーなどのデータ駆動型構造は、一般的に特定のデータストレージシステムの内部構造に結び付けられていますが、データのストレージと検索実行時の速度においてより効率的です

このような空間インデックスの使用はデジタルデータに限定されません。世界地図帳や街路地図帳の「インデックス」セクションには通常、名前の付いた地物 (町、通りなど) とそれに関連付けられたグリッドスクエア識別子のリストが含まれており、空間インデックスの完全な例として考えることができます (この場合、通常は地物名で整理されますが、概念的にはその逆も可能です)。

その他の用途

グリッドシステムの個々のセルは、例えばデータ分析、プレゼンテーション、マッピングなどの前段階として、集約の単位としても役立ちます。一部のアプリケーション（例：統計分析）では等面積セルが好まれる場合がありますが、他のアプリケーションではこれが主要な考慮事項ではない場合があります

コンピュータサイエンスでは、レイトレーシングや衝突検出のために、グリッド内でレイが通過するすべてのセルを見つける必要があることがよくあります。これは「グリッドトラバーサル」と呼ばれます。

参照

参考文献

^ジェフリー・ダットン「空間効果：研究論文とデータ」Wayback Machineに2007年2月19日アーカイブ
^グローバルジオコーディングシステムの比較のための基準と尺度、キース・C・クラーク、カリフォルニア大学、 2010年6月23日アーカイブ、 Wayback Machine
^ Rigaux, P., Scholl, M., Voisard, A. 2002. 『空間データベース - GISへの応用』 Morgan Kaufmann, サンフランシスコ, 410ページ.

天空のインデックス - クライヴ・ペイジ- 天文学のためのグリッドインデックス

外部リンク

[1] ジェフリー・ダットン「空間効果：研究論文とデータ」Wayback Machineに2007年2月19日アーカイブ

[2] グローバルジオコーディングシステムの比較のための基準と尺度、キース・C・クラーク、カリフォルニア大学、 2010年6月23日アーカイブ、 Wayback Machine

[3] Rigaux, P., Scholl, M., Voisard, A. 2002. 『空間データベース - GISへの応用』 Morgan Kaufmann, サンフランシスコ, 410ページ.

[ 1 ]

[ 2 ]

[ 3 ]