0

約 100 万個の三角形からなる平面 Delaunay 三角形分割があります。各頂点にはいくつかのスカラー メトリックがタグ付けされており [1]、同じ規則的なグリッド上でこれらの各メトリックの高速で単純な補間を確認したいと考えています。参考までに、私の三角形の結合は、(整数) 座標を持つ約 1000 万のグリッド セルをカバーしています。[2]

シンプルと言えばシンプル。バイリニアは大丈夫​​です！私の理解では、これは (a) 基本的に GPU が生計を立てていることであり、(b) おそらく数え切れないほどの宿題の対象であるということです。私自身は公衆衛生の政府研究者なので、宿題ではありません。:-)

私の遅いが正しい参照実装では、約 10 分で次の計算を行うことができます。

各三角形 T について:

  1. T の境界ボックス内のすべての (整数) デカルト座標の集合 G。
  2. G の各 (x、y) の重心座標 (u、v、w)。
  3. すべてが正ではない (u, v, w) の棄却 — つまり、T 内。
  4. T の残りの各座標の加重合計 (u z_1 + v z_2 + w*z_3)。z_1、z_2、および z_3 は、特定のメトリック [1] の T の頂点でのスカラー値です。

高速にするには、ステップ 1 ～ 3 が本当に必要です。ステップ 4 は些細なことですが、それが私の最終目標です。理想的には、ソリューションは次のいずれかの形式になります。

  • 非常にシンプルな API を備えた、適切にライセンスされた (GPL で問題ありません) ライブラリ。また
  • 中級プログラマーが Fortran、R、Python、または C でコーディングする方法が明らかなほど明確な説明。

このタスクの古典的な定式化は、「TIN から DEM へ」の地形モデリング ジョブです。しかし、最近はその逆がより一般的に必要とされているようです (?)

ポイントが 2 つ以上の三角形によって共有されるエッジまたは頂点に正確に位置する場合に重複を削除するなど、いくつかの基本的なクリーンアップも問題ありません。

お時間とご関心をお寄せいただきありがとうございます。電車を降りたら、フォーマットをクリーンアップし、提案ごとに編集します!

脚注:

[1] 標高、温度、湿度。[2] UTM グリッド上で 20x20m 離れているという意味での整数。したがって、20倍に拡大してください。

4

1 に答える 1

1

あなたの説明の遅さを説明するものは何も見当たりませんが、これをどのように処理するかを次に示します。基本的な構成要素は、まさに「トライアングル スキャナー」です。

Y 上の 3 つの頂点を並べ替えることから始めます。これには 3 つの比較が必要であり、考えられる構成は 6 つだけです。上の Y から中央の Y まで、次に中央の Y から下の Y までの整数の縦座標をループします。すべての縦座標について、左側と右側との交点が間隔を与えます。

左から右に、その間隔の整数横座標をループします。二重ループは、三角形に属するグリッド ノードのみを訪問します。

重心座標を使用する代わりに、平面の方程式を確立できます。つまり、 の係数を評価し、Z = a X + b Y + cこの公式を補間に使用できます。(つまり、値を段階的に計算することもできますが、Z(X + 1) = Z(X) + a三角形ごとの少数のポイントの場合、これが価値があるかどうかはわかりません。)

単純な規則に頼ることで、ポイントの重複を簡単に回避できます。つまり、三角形の右側にあるポイントではなく、左側にあるポイントのみを生成します (これらは、右側の三角形によって生成されます)。

ここに画像の説明を入力

整数縦座標の水平辺などの特殊なケースを処理するために一部の車を使用する必要がありますが、これは管理可能です。

合計ワークロードは、三角形の数、ドメインの Y 範囲、カバーされるグリッド ノードの数に影響され、これらの要因ごとに少数の算術演算がカウントされます。100 万個の三角形と 1,000 万個のグリッド セルの場合、実行時間が 1 秒未満になる可能性は低くありません。

于 2016-05-12T20:19:12.057 に答える