與Voronoi圖算法（財富的掃描線）相混淆

我正在執行Voronoi圖來在視覺上查找地圖中最近的位置。現在我只想在畫布中使用整數座標（x，y）來完成此操作。與Voronoi圖算法（財富的掃描線）相混淆

問題是 - 我對這個算法非常困惑。我閱讀了計算幾何書，還沒有更多關於財富算法的理論。我現在很困惑。當我正在進行編碼時，對我來說似乎非常複雜。

請教我很簡單的voronoi圖的實現（給定座標）。請指教我簡單的Java或Python或計劃代碼，最好不使用散列，多線程，Delaunay Traingulation，花式顏色等。

使用Fortune算法不使用多線程或哈希映射可以實現Voronoi圖嗎？

2009-06-11 fireball003

Voronoi圖只是一個圖：不是數據結構或算法。我認爲它不適合找到一組中最近的點。構建圖表不會改變問題的漸近複雜性，儘管它會使問題更加複雜並且降低內存效率。你最好把你的觀點放在四叉樹或類似的東西上。如果你正在尋找算法，你試圖解決的問題的名稱是「空間索引」。「最近點」是四叉樹和其他空間索引解決的問題之一。

來源

2009-06-11 19:11:03

他試圖描繪近鄰視覺疊加地圖上的Voronoi圖，這樣一方面可以一目瞭然其中X是最接近興趣點見。 – erickson 2009-06-11 20:23:25

Voronoi圖用於解決最近鄰問題：http://en.wikipedia.org/wiki/Voronoi_diagram#Applications – 2011-11-15 17:28:54

Voronoi圖_is_不只是一個圖。它是一個_planar graph_（邊不交叉的邊），帶有頂點和雙向邊。 – bobobobo 2013-06-17 19:23:15

看起來很複雜，因爲它很複雜！您不需要散列表或線程，但您需要一個優先級隊列（通常以堆的形式實現，並可在java和python標準庫中使用）以及一個可讓您在O（log n）中執行範圍查詢的樹，（標準庫中的不太合適，因爲你不能在內部獲得;我建議實現一個AA tree）。算法本身仍然非常多毛。

你可以運行一個外部程序嗎？如果是這樣的話，我真的建議你把重任提升到QHull，這對Voronoi圖很好。可悲的是，比我們兩個人都要好得多。

來源

2009-06-11 19:52:32

我明白你的意思。但我必須親自去做評估。所以，我正在尋找一些可以研究和修改/添加到我的設計中的簡單實現。 – fireball003 2009-06-11 20:03:23

去年我在看Voronoi圖很多，我當然可以理解這種混亂。有一些Voronoi圖生成算法的實現。一對夫婦參見this page，還有here。如上所述，Qhull當然值得研究 - MATLAB使用它來生成Voronoi圖和Delaunay三角剖分以及類似的有趣事物。

來源

2009-06-12 12:53:04

這裏是用Ruby和C另一種實現方式，其中包括可視化：

http://github.com/abscondment/rubyvor/

來源

2010-02-01 21:33:43

顯然，財富的算法是不容易實現。特別是如果你的時間軸consider numerical robustness issues。你不會說你想用什麼編程語言來實現它。如果是C++，可以找到Andriy Sydorchuk爲Boost in frame of GSoC 2010項目完成的工作：Sweepline Algorithm。 Andriy的實現基於Boost.Polygon庫。 Voronoi實現和Boost.Polygon都依賴整數座標來提供數值穩健性。

關於Sweep-Line Algorithm for Voronoi Diagrams of Points, Line Segments and Medial Axis of Polygons in the Plane的BoostCon視頻講座給出了有關該想法，問題和陷阱的非常好的解釋。

不少有關這個Voronoi項目的討論。發生在2010/2011年的Boost郵件列表中。

來源

2011-10-27 13:34:32 mloskot

I opened a github repository與Fortune的原始紙張的港口。財富的實施非常艱難，主要是由於他如何處理數據結構。

This book出現了很多現代

Fortune's original paper需要幾個讀取。

Ken Wong's主要介紹與原文件比財富可以說是更清晰的算法

Ken Wong's presentation有很大的幻燈片（10，11）如何處理一個網站和一個頂點

有一個interactive JavaScript demo（ Archived version），您可以觀看以幫助您查看算法。

A pdf也描述了該算法。

Steven Fortune's original implementation is on his homepage。