緯度/経度/標高のペアで構成される標高マップが与えられた場合、特定の標高レベル (またはさらに良いのは 2D 凹包) より上のすべてのポイントを見つける最速の方法は何ですか?
地図の上にオーバーレイをレンダリングして標高の高い地域を視覚的に示す必要がある GIS アプリに取り組んでいます。私が困惑したのは、このポリゴン/領域を決定することです（今のところ）。私は緯度/経度/標高のペア (より具体的にはGTOPO30 DEM ファイル) の単純な配列を持っていますが、それをあなたが提案する任意のデータ構造に自由に変換できます。
Triangulated Irregular Networks (TIN) を指摘されましたが、TIN を生成した後でそのデータを効率的にクエリする方法がわかりません。私たちの問題が等高線図を生成する方法と同じように解決できたとしても驚かないでしょうが、私はその経験がありません. どんな提案も素晴らしいでしょう。
高地の境界を多角形で表現しようとしているようですね。
ラスター データ (長方形のグリッドでサンプリング) を操作している場合は、これを試してください。
グリッドを直角三角形の集まりと考えてください。
ポイントの 3x3 グリッドがあるとしましょう
あなたの三角形は次のとおりです。
アルゴリズムには次のステップがあります。
標高しきい値を超える三角形のリストを作成します。
これらの三角形の結合を取り、多角形の領域を作成します。
多角形の境界を決定します。
必要に応じて、ポリゴンの境界を滑らかにして、レイヤーが表示されたときに適切に見えるようにします。
見栄えの良い等高線を生成しようとしている場合、手順 4 を修正するのは非常に困難です。
ステップ 1 がこの問題の鍵です。
各三角形について、3 つの頂点すべてがしきい値を超えている場合は、三角形全体をリストに含めます。すべてが下にある場合は、三角形を忘れてください。一部の頂点が上にあり、他の頂点が下にある場合は、(標高を補間して) 標高ライン上に正確に位置する新しい頂点を追加して、三角形を 3 つに分割します。これらの新しい三角形の 1 つまたは 2 つをハイランド リストに含めます。
残りのステップでは、まともな 2D ジオメトリ処理ライブラリが必要です。
ポイントが通常のグリッド上にない場合は、ドローネ アルゴリズム (調べることができます) を使用してポイントを三角形に整理することから始めます。次に、上で述べたのと同じアルゴリズムに従います。警告。ポイントがあまりない場合、これは大ざっぱに見えます。
緯度/経度/標高データが配列（または3つの別々の配列）に格納されていると仮定すると、配列クエリ手法を使用して、標高が特定のしきい値を超えるすべてのポイントを選択できるはずです。たとえば、Pythonでは次のnumpyことができます。
indices = where(array > value)
また、変数には、しきい値より大きいindicesすべての要素のインデックスが含まれます。同様のコマンドが他のさまざまな言語で使用できます（たとえば、IDLにはコマンドがあり、Matlabでも同様のことができます）。arrayvalueWHERE()
このインデックスのリストを取得したら、しきい値が満たされた各場所が1に設定された新しいバイナリ配列を作成できます。
binary_array[indices] = 1
（元の緯度/経度/標高と同じサイズの空白の配列を作成し、それを呼び出したと仮定しますbinary_array。
ラスターデータを使用している場合（このタイプの作業に推奨します）、この配列をマップにオーバーレイするだけで、優れた領域のセットを表示できる場合があります。ただし、標高しきい値を超える領域をベクトルポリゴンに変換する必要がある場合は、多くの組み込みGISメソッドの1つを使用して、ラスター->ベクトルを変換できます。
ネストされたC スクエア配置を使用し、各スクエアは事前に計算された最大地上高を持ちます。これにより、最大の高さが検索の高さを超えていない正方形を破棄し、地面の一部が検索の高さを超えている正方形にさらにドリルダウンして、高レベルでスキャンすることができます。
検索の高さのさまざまな設定レベルに取り組んでいる場合は、使用することを決定した最小の正方形 (またはすべての正方形) のさまざまな定義済みレベルの凸包を事前に計算できます。
ポイントのセットが静的であり、特定の標高より上にあるポイントを何度も見つける必要があるのか 、またはクエリを1回だけ実行する必要があるのか 、あなたの質問からは明らかではありません。
最も簡単な解決策は、標高でソートされたポイントを配列に格納することです。特定の標高範囲内のすべてのポイントを見つけることは単なる二分探索であり、並べ替える必要があるのは 1 回だけです。
クエリを 1 回だけ実行する必要がある場合は、取得した順序で配列を線形検索します。とにかく、配列からより手の込んだデータ構造を構築することは O(n) になるため、物事を複雑にすることでより良い結果を得ることはできません。
ユーザーが表示している長方形内のすべてのポイントを効率的にリストする必要がある、または実行時にポイントを追加または削除できるなど、他の要件がある場合は、別のデータ構造の方が適している可能性があります。おそらくある種のツリーまたはグリッド。
レンダリングだけに関心がある場合は、グラフィックス ハードウェアを使用してこれを非常に効率的に実行できます。派手なデータ構造を使用する必要はまったくありません。三角形を GPU に送信し、特定の範囲より上または下のフラグメントを強制終了させることができます。標高。
緯度/経度/高度ポイントが通常のグリッド上にあるかどうかはわかりませんが、そうでない場合は、100 フィートの高度増分と均一な緯度/経度分割を表すために補間される可能性があります (均一な距離分割を与えない)。しかし、それがうまくいくのであれば、インデックスがそれぞれ高度、緯度、経度を表す 3 次元配列を事前に計算してみませんか。次に、航空機が高度以上のポイントに関するデータを必要とする場合、特定の地形について、コードはこの配列内のデータのごく一部を読み取るだけで済みます。これは、連続した「ボクセル」を索引付けスキーム。
もちろん、経度の増分は均一である必要はありません。均一な距離が必要な場合、同じスキームが機能しますが、経度のインデックスは不均一な間隔の経度のセットを指します。
このデータを検索するより高速な方法はないと思います。