長方形のコレクションの交差領域を削除するための非「ブルートフォース」アルゴリズムを探しています

Question

私はnサイズの長方のコレクションを持っていますが、そのほとんどは互いに交差しています。交差点を削除し、交差する長方形をより小さな非交差する長方形に減らしたいと思います。

解決策を簡単に強制的にブルートできますが、効率的なアルゴリズムを探しています。

視覚化は次のとおりです。

オリジナル：

加工：

理想的には、メソッドの署名は次のようになります。

public static List<RectF> resolveIntersection(List<RectF> rects);

出力は入力または等しくなり、出力が上記の視覚表現を解決します。

Answer 1

これは私が過去に解決した問題です。エッジの1つのxまたはy値を使用して長方形をソートする最初のこと。 Y-directionで注文し、上端を使用してください。例の一番上の長方形は、最初に並べ替えられた順序です。長方形ごとに、y方向のサイズがわかっています。

これで、各エントリ（現在のエントリと呼び、長方形に対応します）について、ソートされたリストで、現在のエントリ +対応する長方形サイズよりも大きいエントリに到達するまで、リストを前方に検索します。 （それを停止エントリと呼んでください）

現在のエントリとこの停止エントリの間のソートされたリストのエントリは、潜在的な交差点になります。 X-rangeが交差するかどうかを確認するだけです。

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 + size = 0 + 4 = 4は、それが潜在的に交差する長方形3（y1値= 3 <4）と長方形4（y1値= 3 <4）であるが、長方形2（y1値= 6>> 4）... 2の後にリスト内の長方形を確認する必要はありません

長方形3にはy2 + size = 2 + 3 = 5があります。

長方形4のy2 + size = 3 + 4 = 7は、それが潜在的に交差する長方形2（y1値= 6 <7）を潜在的に交差することを示唆していますが、recatngle 5（y1値= 9> 7）

もちろん、多数の長方形を使用すると、通常、交差点の可能性のあるペアの一部を確認するだけで済みます。

Answer 2

Sweepline Algoithmsは、2Dユニバースの交差点を処理するのに優れています。私は、長方形のエッジから次の長方形の端まで下に移動する水平線を考慮することを意味します。ラインは多くの長方形にヒットし、いわゆるアクティブリストを形成します。アクティブリストは、すべての動きで更新されたままになります。

水平線に沿ってアブシッサの範囲を研究することにより、オーバーラップを検出できます。

すべての構成を慎重に調べると、ブルートフォースよりも複雑さが低い（n^2よりもn^1.5に近い）、長方形を1回のスイープで必要な方法で分割することができます。

Answer 3

あなたが説明しているのは梱包の問題です、見てください ウィキペディア

それは指します これ 長方形の長方形を梱包するためのアルゴリズムを説明する記事

これは記事からです：

この記事では、さまざまな幅と高さの一連の長方形を単一の囲いの長方形に詰めるための高速アルゴリズムについて説明します。オーバーラップせず、囲いの長方形の無駄なスペースの量を最小限に抑える方法で説明します。