地形三角测量算法

Question

我有一个由3D-space中的大点集合呈现的地形。对其进行三角测量的最佳方法是什么？

我可以在2D-space上投影所有点，比在时间O(n * log(n))上做Delaunay三角测量并将其提升回到先前的高度。但这足够好吗？在某些特殊情况下，我已经在时间O(n * log(log(n))中听说过Delaunay三角剖分）。我的情况可能吗？或者，也许我应该使用一些近似算法？

Answer 1

其实你做了你的功课好的，德劳内三角测量是一个很好的解决你的问题。

Answer 2

2D中的投影和Delaunay三角测量当然是一个很好的解决方案，它将生成良好的三角形。对于地形，您可能还需要强制执行某些边缘，因此请查找受约束的Delaunay三角剖分。

至于运行时间：对于真实世界的数据，您可以假设线性为runtime。如果性能很重要，请确保您的输入数据不会退化：扫描设备通常会返回网格上的点。您可以通过添加一些噪音来改善情况。