典型的な方法は、ドメイン内のサンプル セットのDelaunay 三角形分割(この場合は長方形) を作成し、見つかった三角形をサーフェスとして使用することです。
一般的な点集合のドローネ三角形分割は、外接円に他の点が含まれていない三角形の集合として定義されます。
Delaunay 三角形分割 (すべての三角形を選択して、それらの外接円内に点があるかどうかを確認する) を計算する簡単なアルゴリズムは、次のとおりですO(n^4)
。
インクリメンタル アルゴリズムはO(n log n)
予想される時間内に実行されます。
- 3 点の三角形分割を生成します (あなたの場合、4 - 部屋の角)。
- ポイントごとに
- 三角測量に追加します。
- 新しいポイントの反対側のすべてのエッジに対して再帰的に
- エッジが現在のポイント セットの Delaunay 三角形分割の一部でない場合は、エッジを反転します。
分割統治アルゴリズムO(n log n)
も同様に提供されますがO(n log log n)
、一部のポイント セットも提供されます。
三角測量を取得したら、サーフェスと垂直線を交差させて測定値を見つけるだけです。
- 点がある三角形 ABC を見つけます。
- 点座標を次のように表します
A + k(B-A) + l(C-A)
- 次に、ポイント値は次のように与えられます
A.value + k(B.value-A.value) + l(C.value-A.value)
(三角形を [ドメイン x 範囲] 空間内の平面として扱います。