地形三角測量算法

Question

我有一個由3D-space中的大點集合呈現的地形。對其進行三角測量的最佳方法是什麼？

我可以在2D-space上投影所有點，比在時間O(n * log(n))上做Delaunay三角測量並將其提升回到先前的高度。但這足夠好嗎？在某些特殊情況下，我已經在時間O(n * log(log(n))中聽說過Delaunay三角剖分）。我的情況可能嗎？或者，也許我應該使用一些近似算法？

Answer 1

其實你做了你的功課好的，德勞內三角測量是一個很好的解決你的問題。

Answer 2

2D中的投影和Delaunay三角測量當然是一個很好的解決方案，它將生成良好的三角形。對於地形，您可能還需要強制執行某些邊緣，因此請查找受約束的Delaunay三角剖分。

至於運行時間：對於真實世界的數據，您可以假設線性爲runtime。如果性能很重要，請確保您的輸入數據不會退化：掃描設備通常會返回網格上的點。您可以通過添加一些噪音來改善情況。