私は次のようなアルゴリズムを探しています：
重なり合う可能性のある長方形のセット（すべて「回転されていない」、（左、上、右、下）の連符などとして均一に表すことができる）が与えられると、（回転されていない）最小のセットが返されます。同じ領域を占める重複しない長方形。
一見簡単そうに見えますが、注意が必要です（少なくとも効率的に実行するため）。
この/アイデア/ポインタの既知の方法はありますか？
必ずしも最小ではないが、ヒューリスティックに小さいセットのメソッドも興味深いので、有効な出力セットを生成するメソッドも興味深いものです。
ラインスイープアルゴリズムに基づく何かが機能すると思います：
x座標を「start-rectangle」および「end-rectangle」イベントとして配列に並べ替えますy-coordinatesの単純な比較で十分です）y-coordinatesは、まだカバーされていない新しい長方形の部分に設定されます。これがすべてをカバーしているとは完全にはわかりませんが、多少の調整を加えることで、作業を完了することができると思います。または、少なくともいくつかのアイデアを教えてください... :)
ですから、もし私がこれをやろうとしていたとしたら、私が最初にすることは、統一されたグリッドスペースを考え出すことです。すべての一意のx座標とy座標を見つけて、インデックススペースへのマッピングを作成します。したがって、x値が{-1、1.5、3.1}の場合は、それらを{0、1、2}にマップし、同様にyにもマップします。そうすれば、すべての長方形をこれらのパックされた整数座標で正確に表すことができます。
次に、グリッド全体をカバーするビットベクトルなどを割り当て、グリッド内の長方形をラスタライズします。グリッドを使用することの良い点は、操作が非常に簡単であり、グリッドを一意のx座標とy座標に制限することで、最小限で正確になることです。
非常に迅速な解決策を考え出す1つの方法は、グリッドのすべての「ピクセル」をダンプすることです。マッピングを実行し直すと、完了です。より最適な数の長方形を探している場合は、ある種の検索問題が発生します。
隣接する4つのピクセル、2x2の小さな正方形を見てみましょう。私がこのようなアルゴリズムを書くとき、私は通常、頂点、エッジ、および面の観点から考えます。だから、これらは頂点の周りの顔です。それらのうちの3つがオンで、1つがオフの場合、凹型のコーナーがあります。これが唯一の無効なケースです。たとえば、凹型のコーナーがない場合は、範囲を取得して、すべてを1つの長方形としてダンプします。凹型のコーナーごとに、水平方向、垂直方向、またはその両方に分割するかどうかを決定する必要があります。分割は、範囲を見つけるときに交差しないようにエッジをマークすることと考えています。また、あなたにとってより簡単なものは何でも、セットへの着色としてそれを行うことができます。
凹状の角とその分割方向が検索スペースです。任意の最適化アルゴリズムを使用できます。分枝限定法はうまくいくかもしれません。うまく機能する単純なヒューリスティックを見つけることができると思います（たとえば、検討しているコーナーの真向かいに別の凹型コーナーがある場合は、常にその方向に分割します。それ以外の場合は、短い方向に分割します）。あなたはただ貪欲になることができます。または、すべての凹面を両方向に分割することもできます。これにより、通常、すべての「ピクセル」を長方形として出力するよりも長方形が少なくなり、非常に簡単になります。
これを読んで、不明確な領域があるかもしれないことに気づきました。何か明確にしてほしい場合はお知らせください。