快速（O(nlogn)）约束性Delaunay三角剖分算法

Question

4

请问有没有任何算法（如果您知道，请提供研究论文链接），可以在O(nlogn)时间内创建受限Delaunay三角剖分？还有任何算法允许删除和添加约束和顶点而不需要重新计算整个CDT吗？

- zaloo

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Seiler · Accepted Answer

Chew 1989提出了一个O(nlogn)的CDT生成算法，Sloan 1992也是如此。我发现Sloan的算法更易于理解，但你的体验可能有所不同。

对于动态更新，我所知道的最好的算法是Kallmann et al提出的。我记得他们的算法对约束数量非常敏感，因此不适合在Minecraft等世界中进行路径规划，其中约束空间既大且高度动态。

所有这些论文都涵盖了二维空间；如果您想在三维中使用，我认为您需要进行一些原始研究。无论如何，祝你好运。