合併多邊形的高效算法

我有一個多邊形列表，在這個列表中，一些多邊形重疊或觸及其他多邊形。合併多邊形的高效算法

我的任務是合併彼此重疊或接觸的所有多邊形。我有一個union方法可以做到這一點。

什麼是最有效的方法來做到這一點？我現在可以想到的是循環多邊形列表，檢查合併列表以查看該多邊形是否已經屬於已經合併列表中的一個多邊形，如果是，將它們聯合起來，如果不是，則添加該多邊形到合併列表的末尾。

重複上述步驟幾次，以確保所有多邊形正確組合。

這種方法看起來很不雅觀;有一個更好的方法嗎？

來源

2010-08-02 Graviton

這裏有一個想法：做一個掃描，以確定哪個多邊形無論如何重疊，然後執行合併。

假設所有多邊形都在輸入列表中。

對於每個Polygon P_i構建一個覆蓋P_i的多邊形的OVERLAP。
從OVERLAP中獲取Polygon P_i和任何仍存在的Polygon P_k，將它們合併，並將P_k的OVERLAP列表添加到P_i的重疊列表中。從輸入列表和P_i的OVERLAP列表中刪除P_k。
如果P_i的OVERLAP列表爲空，則已找到P_i的傳遞聯合。前進到輸入列表中下一個剩餘的多邊形。

有好東西這種方法：

你只需要輸入多邊形（這是可能更小，更復雜，所產生的工會）的相交測試。
您可以使用空間索引來加速多邊形相交檢查，並且不必爲合併的多邊形更新它。
您可以確定哪些多邊形將被合併而不實際執行聯合。這意味着你可以計算出不同的合併組和手的名單在實際合併到一些專門的算法（如果有多邊形合併的兩組，那麼您可以在並行做到這一點！）

下面是一些僞代碼：

-- these are the input arrays 
var input:array[Polygon]; 
-- if Polygon #3 overlaps with #7 and #8 then overlaps[3] contains the list {7,8} 
var overlaps:array[list[integer]]; 

-- compute the overlaps 
for i=1..input.size 
    overlaps[i]=new list[integer]; 
    for k=i+1..input.size 
     if input[i] *overlaps* input[k] then 
      overlaps[i].append(k); 
     end if 
    end for 
end for 

var check:integer 

-- for all polys 
for i=1..input.size 
    -- if this poly is still in the input list (and not neutered with null) 
    if input[i] then 
     -- check all the polys that overlap with it 
     for k=1..overlaps[i].size 
      -- 'check' is a candidate 
      check=overlaps[i][k] 
      -- is this poly still in the input array? 
      if input[check] then 
       -- do the merge 
       input[i] = input[i] *union* input[check] 
       -- and delete this polygon from the input array 
       input[check]=null 
       -- and let input[i] inherits the overlapping polygons of check. 
       overlaps[i].append(overlaps[check]) 
      end if 
     end for 
    end if 
end for

後，「輸入」應該只包含非重疊的多邊形（或空以指示多邊形已經被合併的地方）

來源

2010-08-02 10:50:14

這是什麼意思**來自OVERLAP **的任何仍存在的Polygon P_k？是否有可能爲此發佈僞代碼？ – Graviton 2010-08-02 11:17:36

cyclomatic_complexity> 10！ – 2010-08-02 11:42:14

我還沒有把過多考慮到這一點，但看到如果這工作...

//let L be the list of all polygons, M be the list of all merged polygons 
//let head(L) be the first polygon in the list and tail(L) be the 
//remaining polygons other than the head polygon. 

let h = head(L) 
let t = tail(L) 

while(length(t) > 0) 
    foreach(polygon p in t) 
     if(p intersects h) 
      let h = p union h 
      t.remove(p) 
    M.append(h) 
    let h = head(t) 
    let t = tail(t)

來源

2010-08-02 10:50:46

你可以做預測試與包圍盒/圈，如果它不是已經是工會法的一部分，但你簡單的實現似乎罰款< 1000左右多邊形，甚至10000取決於他們是多麼複雜。有一種方法可以改進之後，就是將您的多邊形存儲在某種空間樹中，如四元，kd，bsp或R樹。請注意，將數據導入這些樹中相對於它們的操作往往是昂貴的，因此在這種情況下，您將不得不在整個軟件中使用它。

來源

2010-08-02 10:58:37

你能更明確嗎？ – Graviton 2010-08-02 11:28:28

合併多邊形的高效算法

回答

相關問題