n サイズの Rects のコレクションがあり、そのほとんどが互いに交差しています。交差点を削除し、交差する Rects をより小さな交差しない Rects に減らしたいと思います。
私は簡単に解決策を総当たりすることができましたが、効率的なアルゴリズムを探しています。
視覚化は次のとおりです。
オリジナル：
処理済み:
理想的には、メソッド シグネチャは次のようになります。
public static List<RectF> resolveIntersection(List<RectF> rects);
出力は入力以上になり、出力は上記の視覚的表現を解決します。
スイープライン アルゴリズムは、2D ユニバースの交差を処理するのに適しています。つまり、長方形の端から次の長方形の端まで下に移動する水平線を考えてみましょう。線は多数の長方形に当たり、いわゆるアクティブ リストを形成します。アクティブなリストは、移動するたびに更新されます。
水平線に沿った横座標の範囲を調べることで、重なりを検出できます。
すべての構成を注意深く検討することで、1 回のスイープで必要な方法で四角形を分割でき、ブルート フォースよりも複雑さが低くなります (N^2 よりも N^1.5 に近い)。
これは私が過去に解決した問題です。最初に、エッジの 1 つの x または y 値を使用して四角形を並べ替えます。y 方向に並べて上端を使用するとします。あなたの例の一番上の四角形は、ソート順で最初です。各長方形の y 方向のサイズがわかります。
次に、ソートされたリスト内の各エントリ (現在のエントリと呼びます。四角形に対応します) について、現在のエントリ + 対応する四角形のサイズより大きいエントリに到達するまで、リストを順方向に検索します。（ストップエントリーと呼びます）
現在のエントリとこの停止エントリの間の並べ替えられたリスト内のエントリは、潜在的な交差になります。長方形の x 範囲が交差しているかどうかを確認するだけです。
x 方向または y 方向での並べ替えを選択する場合は、より大きな次元を選択することをお勧めします。これは、平均して交差が少なくなり、チェックが少なくなることを意味するためです。
ここに例があります。長方形は R(x1,x2,y1,y2) として定義されます。ここで、x1 は左側、x2 は右側、y1 は上、y2 は下です。
rectangle 1 (1,5,0,4)
rectangle 2 (7,9,6,8)
rectangle 3 (2,4,2,3)
rectangle 4 (3,6,3,7)
rectangle 5 (3,6,9,15)
y1に従ってソートして与える
# y1 size
rectangle 1 0 4
rectangle 3 2 3
rectangle 4 3 4
rectangle 2 6 2
rectangle 5 9 6
したがって、長方形 1 の y1 + サイズ = 0 + 4 = 4 は、長方形 3 (y1 値 = 3 < 4) および長方形 4 (y1 値 = 3 < 4) と交差する可能性があることを意味しますが、長方形 2 (y1 値 = 6 > 4)...2 の後にリスト内の長方形をチェックする必要はありません
Rectangle 3 の y2 + size = 2 + 3 = 5 は、Rectangle 4 (y1 値 = 3 < 5) と交差する可能性があることを意味しますが、recatngle 2 (y1 値 = 6 > 5) と交差しない可能性があることを意味します。
Rectangle 4 の y2 + size = 3 + 4 = 7 は、Rectangle 2 (y1 値 = 6 < 7) と潜在的に交差するが、recatngle 5 (y1 値 = 9 > 7) とは交差しないことを意味します。
もちろん、長方形の数が多い場合は、通常、交差する可能性のあるペアの一部をチェックするだけで済みます。
あなたが説明しているのはパッキングの問題です。ウィキペディアを見てください
四角形を四角形にパッキングするためのアルゴリズムを説明するこの記事を参照します
これは記事からです：
この記事では、さまざまな幅と高さの一連の四角形を 1 つの囲み四角形にパックする高速アルゴリズムについて説明します。これは、重なり合うことなく、囲み四角形の無駄なスペースの量を最小限に抑えます。