Voronoi圖，Delaunay三角剖分 - 數據結構

我想計算Voronoi及其雙Delaunay三角剖分。我正在使用Watson Bowyer算法。我之後的目標是計算阿爾法形狀（凹球面）。所以我需要快速訪問voronoi單元，給定點，鄰居...Voronoi圖，Delaunay三角剖分 - 數據結構

你使用哪種數據結構爲你的Voronoi/Delaunay算法？我曾經想過在union-find操作中使用不相交集合數據結構，這樣我就可以綁定到一個父代，原始數據集中的點p，Vp中的點集合。然而，Voronoi圖中的一點「屬於」幾個Voronoi單元。

你的建議是什麼，或者你可以暗示一些很好的參考？

問候。

2012-09-08 octoback

我建議你看一看半邊緣的數據結構：

半邊數據結構在許多應用程序和框架中。它的一個實現可以在GEL框架中找到：

2012-09-08 11:47:39 Mortennobel

謝謝！有沒有比數據結構同時存儲面，下一個邊，下一個頂點更簡單的選擇？ – octoback

你知道這個Python的一些實現嗎？謝謝。 – octoback

我不知道任何更簡單的解決方案。我也不瞭解任何Python實現，但代碼應該很容易移植到Python。 – Mortennobel

回答