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

空間インデックスの文脈では、グリッドまたはメッシュは、多様体または2D 表面を一連の連続したセルに分割する規則的な^[要出典] テッセレーションであり、これらのセルに一意の識別子を割り当てて、空間インデックス作成の目的で使用できます。このようなグリッドには、正方形または長方形のセルに基づくグリッド、三角形のグリッドまたはメッシュ、六角形のグリッド、ダイヤモンド形のセルに基づくグリッドなど、さまざまな種類が提案されているか、現在使用されています。「グローバル グリッド」は、地球の表面全体をカバーする一種のグリッドです。

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

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

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

四分木はグリッドの特殊な形式であり、2 次元空間全体にわたって、適合されるデータの性質と複雑さに応じてグリッドの解像度が変わります。極座標グリッドは極座標系を使用し、指定された半径の円を特定の角度のセクターに分割します。座標は、グリッドの中心からの半径と角度として与えられます。

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

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

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

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

• 離散グローバルグリッド
• 凸正多角形によるユークリッドタイル張り
• 測地線グリッド
• 空間インデックス
• グリッドプラン
• グリッド参照
• ジオコード
• 六角形マップ
• 四角形の球形立方体
• クワッドツリー
• Rツリー
• 英数字グリッド
• 電柱#電柱タグの座標（一部は長方形のグリッドに基づく）
• ヒールピックス

• 空のインデックス - Clive Page - 天文学のグリッドインデックス

• グリッドトラバーサルの実装の詳細とアプレットのデモ
• ISEA3H グリッドを使用した PYXIS 離散グローバル グリッド システム