有谁知道在 O(nlogn) 时间内创建约束 Delaunay 三角剖分的任何算法（如果您知道，请链接到研究论文），以及允许删除和添加不需要重新计算的约束和顶点的任何算法整个 CDT？
问问题
2699 次
1 回答
9
Chew 1989提出了O(nlogn)一种生成 CDT 的算法，Sloan 1992也是如此。我发现 Sloan 的算法更容易遵循，但你的里程可能会有所不同。
对于动态更新，我所知道的最好的算法是由Kallmann 等人提出的。IIRC 他们的算法对约束的数量非常敏感，因此不适用于例如在约束空间很大且高度动态的类似 Minecraft 的世界中的寻路。
所有这些论文都涵盖了二维空间；如果你想要它是 3D 的，我怀疑你必须做一些原创性的研究。不管怎样，祝你好运。
于 2013-11-21T20:28:31.310 回答