在圖像中合併一組矩形的最佳方式是什麼？

Question

這不是一個作業問題:)

我有一組散佈在圖像上的矩形。我想合併（創建一個聯合）每組相交矩形。如果矩形不與其鄰居相交，則它保持不變。

問題是合併的矩形可以與先前未考慮的矩形相交;合併的矩形也可以與新合併的矩形相交。我想抓住這些情況。因此，在我看來，它需要迭代（對集合中的每個其他矩形嘗試每個矩形）和遞歸（再次嘗試每個合併的矩形對集合，包括合併的矩形）。

我該怎麼辦？我正在使用Java，但這更像是一個算法問題，而不是面向語言的問題。

謝謝！

編輯：添加相關的代碼，以更好地說明我現在處理它的糟糕方式。

public static List<BinaryRegion> mergeRegions(List<BinaryRegion> regions) 
{ 
    List<BinaryRegion> merged = new ArrayList<BinaryRegion>(); 
    geoModel = new GeometryFactory(); 

    Polygon polys[] = new Polygon[regions.size()]; 
    for (int i = 0; i < regions.size(); i++) 
    { 
     Polygon p = convertRectangleToPolygon(regions.get(i) 
       .getBoundingBox()); 
     polys[i] = p; 
    } 

    System.out.println("Converted " + regions.size() + " polys"); 

    for (int i = 0; i < regions.size(); i++) 
    { 
     System.out.println("Sending in poly " + i); 
     ArrayList<Polygon> result = mergePoly(polys[i], polys); 
     System.out.println("After run, size=" + result.size()); 
    } 
    return merged; 

} 

private static ArrayList<Polygon> mergePoly(Polygon p, Polygon[] polys) 
{ 
    ArrayList<Polygon> merges = new ArrayList<Polygon>(); 

    for (int i = 0; i < polys.length; i++) 
    { 
     if (p.equals(polys[i])) 
      System.out.println("found the exact match at " + i); 
     else if (p.intersects(polys[i])) 
     { 
      System.out.println("Found intersection at " + i); 
      System.out.println("Other poly is area "+polys[i].getArea()); 
      Polygon u = (Polygon) p.union(polys[i]); 
      System.out.println("Merge size="+u.getArea()); 
      merges.add(u); 
     } 
     else 
      merges.add(polys[i]); 
    } 
    return merges; 
} 

Answer 1

不能完全確定該嵌套迭代方法是否真的去（尤其是因爲我不知道你究竟怎麼了您的通話後處理合並後的地區mergePoly）的方式。與其他多邊形相比，一次只能處理一個多邊形，爲什麼不保留中間步驟並重新運行合併，直到不再有交集？沿線的一些東西：

private static ArrayList<Polygon> mergePoly(Polygon[] polys) 
{ 
    List<Polygon> polygons = new ArrayList<Polygon>(Arrays.asList(polys)); 
    boolean foundIntersection = false; 
    do 
    { 
     foundIntersection = false; 
     for (int i = 0; i < polygons.size(); i++) 
     { 
      Polygon current = polygons.get(i); 
      for (int j = i + 1; j < polygons.size(); j++) 
      { 
       if (current.intersects(polygons.get(j))) 
       { 
        foundIntersection = true; 
        current = (Polygon)current.union(polygons.remove(j--)); 
        System.out.println("Merge size="+u.getArea()); 
       } 
      } 
      polygons.set(i, current); 
     } 
    } while(foundIntersection); 
    return polygons; 
} 

自從我使用過Java以來​​，這已經有一段時間了，但邏輯非常明瞭。您執行多邊形的兩次迭代。外部迭代是您的「當前」多邊形，您將合併所有內部多邊形（隨着您的進行將它們從集合中移除）。在每次外迭代之後，您只需使用（可能）合併的多邊形在該索引處設置該元素，然後繼續到該系列中的下一個多邊形。你會一直這樣做，直到你不再合併爲止。請記住，這是一個非常幼稚的實現，你可能會更好地將它分解成「一半」和合並這些較小的子集（想象mergesort）。

Answer 2

可以使用掃掠線算法查找矩形（example1，example2）和u nion-find algorithm的交集以有效地合併矩形集合。