確定並存儲Voronoi單元格鄰接點

我將使用一組數千個點。我可以實現或使用Fortunes算法的現有實現來生成點的Voronoi圖，但是我的應用程序還需要我瞭解每個Voronoi Cell的鄰接關係。確定並存儲Voronoi單元格鄰接點

更具體地說，對於任何Voronoi細胞，我需要知道與此相鄰的細胞。在這一點上，我不會關心輸出或存儲方法，因爲我可能會按照某個實現對我有利。

是否有人知道算法，或者更好地意識到可以完成小區鄰接決定的已實現的算法？我將要做的工作是使用python，但任何事情都會很棒，因爲我可以輕鬆地翻譯代碼。

謝謝！

來源

2012-03-11 csjohn

可能的算法可用here 它使用線性規劃方法。

紙漿產生MPS或LP文件，並致電GLPK，COIN，CPLEX和GUROBI解決線性問題。

PuLP是一個用Python編寫的LP建模器，可以用來在Python中對這個線性程序建模，然後使用GLPK來解決。

來源

2012-03-11 08:00:33 Appleman1234

你可以用幾種不同的方法做到這一點。

如果您只是訪問Voronoi圖，則可以查找單元格之間的共享邊緣段。如果您發現兩個單元共享一個Voronoi邊緣段，則表示它們相鄰。爲整個數據集建立鄰接關係信息的有效方法是通過掃描Voronoi單元列表來構建邊緣散列表。

for (all cells in voronoi diagram) 
    for (all edges in current cell) 
     if (matching edge found in hash table) 
      // the current cell is adjacent to the cell that added 
      // the matching edge segment to the hash table 
     else 
      // push current edge segment onto hash table and mark with 
      // current cell index 
     endif 
    endfor 
endfor

有很多很好的現有軟件包可用於計算點集的Voronoi圖/ Delaunay三角測量。由於這是一個計算昂貴和數字敏感的操作，我建議堅持使用現有的庫。 Triangle和QHull包被廣泛使用。

希望這會有所幫助。

來源

2012-03-11 09:42:26

雖然這是一個古老的問題，但我在尋找相同的東西，並認爲答案可能對某人有所幫助。可以使用scipy模塊中的Delaunay。

from scipy.spatial import Delaunay 
from collections import defaultdict 
import itertools 

points=[[0.0, 0.0], [0.0, 1.0], [0.2, 0.5], [0.3, 0.6], [0.4, 0.5], [0.6, 0.3], [0.6, 0.5], [1.0, 0.0], [1.0, 1.0]] 
tri = Delaunay(points) 
neiList=defaultdict(set) 
for p in tri.vertices: 
    for i,j in itertools.combinations(p,2): 
     neiList[i].add(j) 
     neiList[j].add(i) 

for key in sorted(neiList.iterkeys()): 
    print("%d:%s" % (key,','.join([str(i) for i in neiList[key]]))) 

0:1,2,5,7 
1:0,8,2,3 
2:0,1,3,4,5 
3:8,1,2,4,6 
4:2,3,5,6 
5:0,2,4,6,7 
6:8,3,4,5,7 
7:8,0,5,6 
8:1,3,6,7 

# This is for visualization 
from scipy.spatial import Voronoi, voronoi_plot_2d 
import matplotlib.pyplot as plt 
vor = Voronoi(points) 
voronoi_plot_2d(vor) 
for i,p in enumerate(x): 
    plt.text(p[0], p[1], '#%d' % i, ha='center') 
plt.show()

enter image description here

來源

2013-05-28 12:51:27 imsc

有用。值得強調的是，這種voronoi圖的可視化在界限上可能會產生誤導。例如。節點＃0與＃1和＃7相鄰，但情節沒有顯示。 – Maptopixel 2017-11-08 12:55:15

確定並存儲Voronoi單元格鄰接點

回答

相關問題