亲爱的社区成员,优化Delaunay三角剖分算法
我一直在最近在cpp中实现Delaunay三角剖分。尽管我的算法可行,但速度非常慢(100个物体的计算时间约为16秒)。
算法是基于蛮力的方法。给定一个有限的点的集合:
- 我通过每个点迭代三次,检查,如果我能
创建从这些点的三角形; - 从这三点来看,我正在创造一个循环,它贯穿了这些要点;
- 我正在遍历整个点集,第四次检查创建的圆是否包含与上述三个不同的点。
- 如果在圆内没有附加点,我假设从这三点创建的三角形是有效的。
就像我刚才提到的,算法是直接实现在这里描述的Delaunay三角剖分:https://en.wikipedia.org/wiki/Delaunay_triangulation。它的工作“完美无缺”,但速度很慢。
任何有关逻辑的想法/建议可以加速它(如果可能,不需要完全改变逻辑)?
你必须,如果你想接受的速度改变逻辑。无论你使用什么技巧,n^4都会非常慢,明智的算法是n log n。 –
您是否可以为某些范围的三角形预定义一组圆。然后,看看你的积分是否与其中的一个匹配 – ldgorman
我会给出一个一般性的提示,即很少有人知道:在检查一个点是否在圈内时,不需要取平方根。 – Jay