如何將幾何形狀組合成一組重疊形狀

Question

請注意我對解決問題最有效的方法感興趣，並且不希望使用特定庫的建議。

我有大量（〜200,000）的二維形狀（矩形，多邊形，圓形等），我想排序成重疊組。例如，在畫面中，綠色和橙色將被標記爲1組，黑色，紅色和藍色將被標記爲組2

Example

比方說，我會給出一個list<Shape>。緩慢的解決辦法是：

（我沒有運行此代碼 - 只是舉個例子算法）

// Everything initialized with groupid = 0 
int groupid = 1; 

for (int i = 0; i < shapes.size(); ++i) 
{ 
    if (shapes[i].groupid) 
    { 
     // The shape hasn't been assigned a group yet 
     // so assign it now 
     shapes[i].groupid = groupid; 
     ++groupid; 
    } 

    // As we compare shapes, we may find that a shape overlaps with something 
    // that was already assigned a group. This keeps track of groups that 
    // should be merged. 
    set<int> mergingGroups = set<int>(); 

    // Compare to all other shapes 
    for (int j = i + 1; j < shapes.size(); ++j) 
    { 
     // If this is one of the groups that we are merging, then 
     // we don't need to check overlap, just merge them 
     if (shapes[j].groupid && mergingGroups.contains(shapes[j].groupid)) 
     { 
      shapes[j].groupid = shapes[i].groupid; 
     } 
     // Otherwise, if they overlap, then mark them as the same group 
     else if (shapes[i].overlaps(shapes[j])) 
     { 
      if (shapes[j].groupid >= 0) 
      { 
       // Already have a group assigned 
       mergingGroups.insert(shapes[j].groupid; 
      } 
      // Mark them as part of the same group 
      shapes[j].groupid = shapes[i].groupid 
     } 
    } 
} 

更快的解決辦法是把對象變成一個空間樹，以減少j數對象重疊比較（內部循環），但我仍然需要重複其餘部分以合併組。

有什麼更快嗎？

謝謝！

Answer 1

如果有效地找到空間樹中的所有成對交叉，你可以使用union-find algorithm到組對象

Answer 2

希望這可以幫助別人 - 這是我實際執行（以僞代碼）。

tree = new spatial tree 
for each shape in shapes 
    set shape not in group 
    add shape to tree 

for each shape in shapes 
    if shape in any group 
     skip shape 

    cur_group = new group 
    set shape in cur_group 

    regions = new stack 
    insert bounds(shape) into regions 

    while regions has items 
     cur_bounds = pop(regions) 

     for test_shape in find(tree, cur_bounds) 
      if test_shape has group 
       skip test_shape 

      if overlaps(any in cur_group, test_shape) 
       insert bounds(tester) into regions 
       set test_shape group = cur_group