優化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