イメージ内の長方形のセットをマージする最適な方法は何ですか？

Question

これは宿題に関する質問ではありません:)

私は画像全体に散在する矩形のセットを持っています。私は交差矩形のすべてのグループのマージ（結合を作成する）したい。矩形が隣接するものと交差しない場合、四角形はそのまま残ります。

問題は、マージされた矩形が、以前は考慮されていなかった矩形と交差する可能性があることです。マージされた矩形は、新たにマージされた矩形と交差することもあります。私はそのようなケースをキャッチしたい。

私の考えでは、反復的に（セット内の他のすべての矩形に対してそれぞれの矩形を試してください）、再帰的に（結合された矩形を含む、

どうすればこの問題を解決できますか？私はJavaで作業していますが、これは言語指向のものよりもアルゴリズム的な問題です。

ありがとうございます！

編集：私が今取り扱っている貧弱な方法をよりよく説明するために関連コードを追加しました。このネストされた反復アプローチが本当に（私はあなたがmergePolyにお電話した後、マージされた領域を扱うている正確にどのように表示されていない、特に以来）移動するための方法であるかどうかを

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

全くわかりません。他のすべてのポリゴンと比較して一度に1つのポリゴンで作業するのではなく、交差点がなくなるまで中間ステップを保ち、マージを再実行しないのはなぜですか？線に沿って何か：私は、Javaで働いてきたので、

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; 
} 

それはしばらくしているが、ロジックはかなり自明です。ポリゴンの2回の繰り返しを実行します。外側の反復はあなたの "現在の"ポリゴンであり、内側のポリゴンをすべてマージします（あなたが進むにつれてそれらをコレクションから削除します）。外側の繰り返しのたびに、（おそらく）マージされたポリゴンでそのインデックスの要素を設定し、シリーズ内の次のポリゴンに移動します。もはや合併がなくなるまでこれを続けます。これはひどく素朴な実装であり、 "半分"に分割し、これらの小さなサブセットをマージする方が良いかもしれないことに留意してください（mergesortを考える）。

Answer 2

矩形の集合を効果的にマージするために、スイープラインアルゴリズムを使用して長方形（example1,example2）とu nion-find algorithmの交差を見つけることができます。