约束Delaunay三角剖分与耳朵修剪

Question

我不是三角测量问题的专家。所以我决定问一下。:)

有一个简单的耳朵修剪算法，其复杂度为O(n^2)

并且存在复杂度为O(n * log )的约束Delaunay算法

所以问题是。Delaunay algoritm比Ear Clipping更快吗？我问，因为我理解，如果n时间对于Delaunay来说明显更大，它可能会更慢。

P.S. http://code.google.com/p/poly2tri/ - Delaunay，http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf - Ear剪辑

顺便问一下，约束Delaunay是最快的吗？

Answer 1

样条Delaunay算法可以是O(n*log(n))而不是O(log(n))。

在点数较少的情况下，最坏情况为O(n^2)的实现可能比O(n*log(n))的实现更快。

一个原因可能是O(n*log(n))算法可能必须使用分层数据结构。不断地添加和删除点以及平衡树可能代价很高，并会使算法运行速度变慢。

Answer 2

在现实世界中，您可以观察Delaunay三角剖分的线性运行时间。至少对于C++来说，有一些库可以每秒三角测量超过1mio点：

www.cgal.org

http://www.geom.at/fade2d/html/

http://www.cs.cmu.edu/~quake/triangle.html

Answer 3

您可以尝试提升这些点，并将提升的点的下凸包投影回2d平面。结果应该是delaunay三角剖分:https://cs.stackexchange.com/questions/2400/brute-force-delaunay-triangulation-algorithm-complexity。