創建封閉區域多邊形的算法

我在隨機位置有多個圓（作爲連接頂點的列表）。創建封閉區域多邊形的算法

當圓相交，封閉

如何生成所有這些領域的獨立多邊形（維恩圖http://en.wikipedia.org/wiki/Venn_diagram中一樣）創建領域？我們的目標是能夠色彩每一個地區有一個單獨的多邊形就像這個例子：

enter image description here

是用迭代布爾相交操作可能的通用解決方案？

編輯

下面的簡單文檔片斷是[NodeBox](http://nodebox.net/code/index.php/Home)腳本，吸引相交橢圓。

oval(x0,y0,w,h)創建一個橢圓。

根據doc，像p[19].difference(p[17])這樣的路徑上的布爾運算會給出一個「平坦」結果（「由許多直線段組成」）。

可以添加或更改路徑的座標。

size(500, 500) 

p = [] 
s = 54 
nofill() 
stroke(0) 
for k in xrange(10): 
    w = 10+k*s/2 
    w2 = 10+k*s 
    h = 10+k*s 
    h2= 10+k*s 
    p.append(oval(WIDTH/2 - w/2, HEIGHT/2 - h/2, w, h, draw=False)) 
    p.append(oval(WIDTH/2 - w2/2, HEIGHT/2 - h2/2, w2, h2, draw=False)) 


cp = p[19].difference(p[17]).intersect(p[18], flatness = 0.3) 

for pi in p: 
    drawpath(pi) 

fill(color(1,0,0)) 
drawpath(cp)

來源

2013-12-21 synchro

你有什麼信息/數據結構作爲輸入？向我們展示你迄今爲止所做的工作。 – RBarryYoung

我添加了一些NodeBox Python代碼，該庫允許在路徑上進行布爾操作。我的代表太低而無法包含圖片 – synchro

在問題中添加圖片鏈接，我們可以爲您排列。 – RBarryYoung

你說語言不可知，所以我會這樣回答。您可以按照您的建議，通過多邊形上的布爾運算來獲得所需的內容。如果F是一組非相交多邊形的，而P是重疊一個或多個F的新的多邊形，那麼，你想這樣做：

Let p = P 
for each polygon f in F 
    Replace f by f-p and intersect(f, p). 
    Set p = p-f 
end 
add p to F

的想法是使用新的多邊形P將F中現有的「平面」多邊形拆分爲與p共享的部分，並且不與p共享，然後從p本身中刪除與原始多邊形的重疊並繼續。當你這樣做時，剩下的p是與F中的任何東西沒有重疊的部分，所以我們將其作爲新的多邊形添加到F.

因此，要處理隨機收集的圓形多邊形，用F包含其中的一個（這當然是一個平面集合！），並添加更多，一次一個，直到完成。

實際上，這比自定義算法效率低得多。處理這種問題的標準方法是sweep line技術。設想一個垂直線從左向右掃過圓圈。當它「接觸」一個圓時，它開始構建一個多邊形。當它接觸一個十字路口時，一個多邊形關閉，兩個繼續，一個新的開啓（在一般情況下）。當它到達圓的最右點時，關聯的多邊形關閉。將一個「封閉」多邊形從掃描線中移除並添加到輸出列表中。掃描線算法在概念上並不困難，但是在特殊情況下（特別是對於平行於掃除機的線和當一個多邊形的頂點位於另一個多邊形的邊上時，實現很困難，儘管用於解決這些問題的一般技術是simulation of simplicity）。

「廣義排列」是用於描述類似問題的計算幾何學術語。一般化的安排是線，線段和/或多邊形的集合（正常安排只是一組線）。例如，the CGAL library for generalized arrangements可以高效地完成您的問題。 CGAL是C++中的一個大型的通用庫，因此有一些學習成本。用於商業目的的許可證非常棘手。

來源

2013-12-21 17:37:57 Gene

創建封閉區域多邊形的算法

回答

相關問題