优化Delaunay三角剖分算法

Question

亲爱的社区成员，

我一直在最近在cpp中实现Delaunay三角剖分。尽管我的算法可行，但速度非常慢（100个物体的计算时间约为16秒）。

算法是基于蛮力的方法。给定一个有限的点的集合：

• 我通过每个点迭代三次，检查，如果我能
  创建从这些点的三角形;
• 从这三点来看，我正在创造一个循环，它贯穿了这些要点;
• 我正在遍历整个点集，第四次检查创建的圆是否包含与上述三个不同的点。
• 如果在圆内没有附加点，我假设从这三点创建的三角形是有效的。

就像我刚才提到的，算法是直接实现在这里描述的Delaunay三角剖分：https://en.wikipedia.org/wiki/Delaunay_triangulation。它的工作“完美无缺”，但速度很慢。

任何有关逻辑的想法/建议可以加速它（如果可能，不需要完全改变逻辑）？

Answer 1

谢谢大家的快速反馈。

我已经做了一些额外的研究，可悲的是，似乎减少时间复杂度的最佳方法是完全重写现有的算法。

对于其他人谁也有类似的问题，样品的方法描述如下：https://people.eecs.berkeley.edu/~jrs/274/proj.html