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

Question

有没有人知道在O(nlogn)时间内创建约束Delaunay三角剖分的任何算法(链接到研究论文),以及任何允许删除和添加不需要重新计算的约束和顶点的算法整个CDT？

Answer 1

Chew 1989提出了O(nlogn)一种CDT生成算法,Sloan 1992也是如此.我发现斯隆的算法更容易理解,但你的里程可能会有所不同.

对于动态更新,我所知道的最佳算法由Kallmann等人提出.IIRC他们的算法对约束的数量非常敏感,因此不适合例如在类似于Minecraft的世界中的寻路,其中约束的空间既大又高度动态.

所有这些论文都涵盖了2D空间; 如果你想要3D,我怀疑你将不得不做一些原创研究.无论哪种方式,祝你好运.