9

これは宿題の質問ではありません:)

画像全体に四角形のセットが散らばっています。交差する長方形のすべてのグループをマージ (ユニオンを作成) したい。長方形が隣接する長方形と交差しない場合、そのまま残ります。

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

したがって、私の考えでは、反復的 (セット内の他のすべての四角形に対して各四角形を試す) および再帰的 (結合された四角形を含む、セットに対して結合された各四角形を再試行する) である必要があります。

これについてどうすればいいですか？私は 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;
}
4

2 に答える 2

4

このネストされた反復アプローチが本当に進むべき道であるかどうかは完全にはわかりません (特に、 への呼び出し後にマージされた領域をどのように処理しているかが正確にわからないためmergePoly)。他のすべてのポリゴンと比較して一度に 1 つのポリゴンで作業する代わりに、中間の手順を保持して、交差点がなくなるまでマージを再実行してみませんか? 次のようなもの：

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 を扱うのは久しぶりですが、ロジックは一目瞭然です。ポリゴンの反復を 2 回実行します。外側の反復は「現在の」ポリゴンであり、すべての内側のポリゴンをマージします (進行中にコレクションからそれらを削除します)。すべての外側の反復の後、(おそらく) マージされたポリゴンでそのインデックスに要素を設定し、シリーズの次のポリゴンに移動します。マージがなくなるまで、これを続けます。これはひどく単純な実装であり、「半分」に分割して、これらの小さなサブセットをマージする方がよい場合があることに注意してください (マージソートを考えてください)。

于 2012-09-05T15:45:44.423 に答える
2

スイープ ライン アルゴリズムを使用して四角形 ( example1、example2 ) の交点を検出し、和集合検索アルゴリズムを使用して四角形のセットを効果的にマージできます。

于 2012-09-05T17:05:16.790 に答える