の大きなポイント セットによって表される地形があり3D-spaceます。それを三角測量する最良の方法は何ですか？
すべての点を に射影するだけ2D-spaceで、時間内に Delaunay 三角形分割を行いO(n * log(n))、それを前の高さに戻すことができます。しかし、それで十分ですか？Delaunay 三角形分割について聞いたことがO(n * log(log(n))あります ) いくつかの特別なケースで。私の場合は可能ですか？それとも、近似アルゴリズムを使用する必要がありますか?
2Dでの投影とドロネー三角形分割は、適切な形状の三角形を生成する優れたソリューションです。地形の場合、特定のエッジを適用する必要がある場合もあるため、制約されたドロネー三角形分割を探します。
ランタイムについて：実際のデータの場合、線形ランタイムを想定できます。パフォーマンスが重要な場合は、入力データが縮退していないことを確認してください。スキャンデバイスは、グリッド上のポイントを返すことがよくあります。ノイズを加えることで状況を改善できます。
実際、あなたは宿題をうまくやっていました.Delaunay三角形分割はあなたの問題に対する非常に良い解決策です.
