algorithm - 地形三角测量算法

Question

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

我可以将所有点投射到 上2D-space，而不是及时进行 Delaunay 三角剖分O(n * log(n))并将其提升到之前的高度。但它足够好吗？O(n * log(log(n))在某些特殊情况下，我及时听说过 Delaunay 三角测量。在我的情况下可能吗？或者也许我应该使用一些近似算法？

Answer 1

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

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

Answer 2

实际上你做功课没问题，德劳内三角测量是解决你问题的一个很好的方法。