オーバーラップの長方形をマージして分割して、重複しないものを生成します

Question

次のようにアルゴリズムを探しています：

重複する長方形のセット（それらはすべて「回転していない」であり、（左、上、右、下部）チュプレットなどとして均一に表現できます...）。同じ領域を占める非重複した長方形。

一見すると簡単に思えますが、トリッキーであることは（少なくとも効率的に行われることです）。

この/アイデア/ポインターの既知の方法はありますか？

必ずしも最小限ではありませんが、ヒューリスティックに小さいセットも興味深いものであるため、有効な出力セットを生成するメソッドも興味深いものです。

Answer 1

ラインスイープアルゴリズムに基づいた何かが機能すると思います。

• すべての長方形の最小と最大の並べ替え x 「スタートレクタング」および「終了」イベントとして、アレイに調整します
• アレイを踏み出し、遭遇した（Start-Event）それぞれを現在のセットに追加します
• 同時に、出力セットになる「重複しない長方形」のセットを維持する
• 新しい長方形に遭遇したときはいつでも、現在の出力セットに既に完全に含まれているかどうかを確認できます（の単純な比較 y-Coodinatesで十分です）
• そうでない場合は、出力セットに新しい長方形を追加し、 y- まだカバーされていない新しい長方形の一部に設定されています。
• 長方形のエンドイベントにヒットしたときはいつでも、出力セットの長方形を停止し、もう何もカバーしていません。

これがすべてをカバーするかどうかは完全にはわかりませんが、調整することで仕事を成し遂げるべきだと思います。または少なくともあなたにいくつかのアイデアを与えてください... :)

Answer 2

だから、もし私がこれをやろうとしているなら、私が最初にすることは、統一されたグリッドスペースを思いつくことです。すべての一意のXおよびY座標を見つけ、インデックススペースへのマッピングを作成します。したがって、x値{-1、1.5、3.1}がある場合、それらを{0、1、2}にマップし、同様にyに対してマップします。次に、これらの梱包された整数座標ですべての長方形を正確に表すことができます。

次に、ビットベクトルまたはグリッド全体をカバーするものを割り当て、グリッド内の長方形をラスタ化します。グリッドを持っていることの良いところは、操作が非常に簡単であり、一意のXとYの座標に制限することで最小限で正確であることです。

かなり迅速なソリューションを思いつく1つの方法は、グリッドのすべての「ピクセル」をダンプすることです。マッピングでそれらを実行すると、完了です。より最適な数の長方形を探しているなら、あなたの手にある種の検索問題があります。

隣接する4つのピクセル、少し2x2の正方形を見てみましょう。私がこのようなアルゴリズムを書くとき、通常、私は頂点、エッジ、顔の観点から考えます。したがって、これらは頂点の周りの顔です。それらの3つがオンで、1つがオフである場合、凹面のコーナーがあります。これが唯一の無効なケースです。たとえば、凹面の角がない場合は、範囲をつかんで、すべてを単一の長方形としてダンプします。各凹面角について、水平、垂直、またはその両方を分割するかどうかを決定する必要があります。私は、範囲を見つけるときに交差しないようにエッジをマークすると分割することを考えています。また、セットへの着色としてそれを行うこともできます。

凹面の角とその分割方向は、検索スペースです。希望する最適化アルゴリズムを使用できます。ブランチ/バウンドはうまくいくかもしれません。うまく機能する単純なヒューリスティックを見つけることができると思います（たとえば、検討しているものの真向かいに別の凹面コーナーがあり、常にその方向に分割されている場合は、より短い方向に分割されます）。あなたはただ貪欲に行くことができます。または、すべての凹面頂点を両方向に分割することもできます。これにより、一般に、すべての「ピクセル」を長方として出力するよりも長方形が少なくなり、非常に簡単です。

これを読んで、私は不明確な領域があるかもしれないことを認識しています。あなたが私に何かを明確にしてほしいかどうか教えてください。