はじめに
不均一なグリッドを持つデータがある場合、それらを処理する最も重要なステップは、均一なグリッドを持つデータセットに変換することです。 この変換は、リアルタイムのコンピューターシミュレーションまたはその近似に必要です。 不均一なグリッドから直接高さを取得することは、リソースを大量に消費する操作です。
このパートでは、不均一なグリッドを均一なグリッドに変換して、結果の品質をかなり良くするためのアルゴリズムを検討します。
仕事内容
パート1.データの準備
パート2.均一なグリッドの生成
パート3.分析サーフェスの作成
サブタスクの目的
既存の輪郭セットから均一なグリッドを取得する必要があります。 この場合、すべての高さが一貫している必要があります（スムーズな移行）。 輪郭の代わりに、高さを歪めないでください。
アルゴリズム
均一なグリッドを取得するためのさまざまなアルゴリズムがあります。 それらのすべてには、以下の例に加えて、長所と短所があります。
均一なグリッドは作業の中間結果であるため、その作成は事前に行われました。 アルゴリズムの実行時間は、時間とメモリ消費の合理的な制限内でなければなりません。
その精度はそれほど重要ではないため、結果はすでにゲームアプリケーションに使用できます。
前の部分から、実際に希望する解像度の均一なグリッドを既に受け取りました。その上のほとんどの高さのみが計算されていません。 この問題はこの部分で解決されます。
ワークカード
図1は、高さが満たされていない均一なグリッドの例を示しています。 線の色は高さを示し、黒色-高さは不明です。
図1.作業カード
任意の点で高さを取得するアルゴリズムの一般的な説明
地域
占有メモリをより適切に分散するには、マップ全体を領域に分割する必要があります。 高さのないすべてのポイントを通過して計算を行います。
高さ計算
作業領域内の既知の高さを持つ3つの最も近い点を見つけます（目的の正確なものと見つかったものの間のセグメントは、輪郭を交差して触れてはなりません）。 任意の代数的方法を使用して、利用可能なデータから高さを計算します（ 三角形の重心が使用され 、高さは重量として使用されます）。
近くのポイントを見つける
この時点で、 V。Porev「Computer Graphics」による本に言及する必要があります。 コンピューターグラフィックスの基本概念を示し、最も近い点を見つけるための優れたアルゴリズムを提供します。 「正方形の周囲を検索」と呼ばれます。
元のアルゴリズムは2つの最も近いポイントのみを検索しますが、見つかったポイントが部分的または完全に現在のアイソラインの背後にある場合に状況が発生します。 この方法で計算された高さは正しくないため、輪郭との交点を制御してアルゴリズムを3つのポイントに拡張しました。 この場合、以前のアーティファクトは点（いくつかの主要な高さの間の低地）と大きな標高の端で消えます。
図2.元のアルゴリズム。 赤い丸で囲まれたアーティファクト。
図3.変更されたアルゴリズム。
記事内のすべてのコードを提供するのではなく、記事の最後に参照して提供します。 それほど多くはありません。理解するにはコメントで十分です。
処理結果
処理の結果、必要な解像度の均一なグリッドが得られます。 図3に例を示します。高さの間の滑らかな移行があります。 均一なグリッドを持つマップ全体が領域に分割され、占有メモリ量が削減されます。 不規則なグリッドデータはリスト構造に保存されます。
結論
均一なグリッドの生成は、リソースを大量に消費する操作であり、必要な精度と計算能力によっては数日かかる場合があります。 アルゴリズムは完全に並列化されているため、より効率的に計算を実行できます。 「コンピューターグラフィックス」という本のV. Porevのアルゴリズムの修正版が使用されました 。
補間ソースコード