私は、グーグルグアバを使って "同等の" Javaクラスによって実装された長方形のコレクション（Java TreeSet）をチェックする方法を探しています。xとyの範囲 - 交差点と穴。 私はオプションがkd木を使うことができることを知っていますが、私はそのようなkd木をどのように構築するのか分かりません（4dでなければならない矩形のためにはありませんか？ 、穴）。穴と交差の長方形のコレクションをチェックする方法は？
ソートでは、y軸上のx軸が優先されます。
EDIT：（問題を修正再表示しようとする）：ユースケースは、（「プレカラム」、「データ」、長方形の2つのまたは3つのブロックからなる「ヘッダ」）は、任意のテーブルを作成することです。私は各ブロックに交差点や穴がないことを保証する必要があります（これに加えて、ブロックは一緒に収まる必要があります）。 現在（ちょっと考えました）ポジション（x、y）が占有されている2D配列に保存しようとしています。最後にすべての位置を正確に1回占有する必要があります。
このタイプの問題を解決するには、賛否両論の異なるアプローチがあります。ここではそのうちのいくつかされています。長方形のすべてのペアで
長方形ペア交差点+エリア和
ルック - 2つの矩形が交差する場合、重複があります。矩形領域を追加し、合計がキャンバス領域と一致するかどうかを確認します。領域が一致しない場合は、ギャップがあります。
絵画これは、あなたが言及したアプローチがある：あなたのキャンバスの大きさを持つ2次元配列を作成します。次に、矩形を反復処理し、それらを配列にペイントします。
このアプローチの最適化の1つは、座標圧縮です。四角形[（10,20）、（15,25）]と[（7,3）、（15,25）]があるとしましょう。個別のx座標（7,10,15）を見て、それらを（0,1,2）と別個のy座標（3,20,25）に再マッピングし、それらを（0,1,2）に再マップすることができます。 2）。次に、四角形[（1,1）、（2,2）]と[（0,0）、（2,2）]が残っているので、26x26アレイ。
スイープラインアルゴリズム
「面白い」ポイントで停止し、領域が占有されているのを追跡し、左から右にラインをスイープ。
2D範囲木
効率的に矩形範囲にわたってクエリを行うことができるデータ構造。
どちらを選ぶか？
あなたが持っている長方形の数、それらの領域内の分布、アルゴリズムの速さ、複雑さの程度などによって異なります。私が言及した最初の2つのアルゴリズムは、後者の2つよりはるかに簡単なので、そこから始めておくことをお勧めします。
詳細
あなたはこれらのアルゴリズムの詳細についてはしたい場合は、オンラインの「矩形組合」を検索してみてください。最も効率的なソリューションはスイープラインアルゴリズムです。
文献3は、通常、矩形組合のためのラインスイープアルゴリズムの元のソースとして与えられたが、私は実際に見つけることができませんでしたことを認めざるを得ませんさ紙はオンラインで、おそらくそれは "未公開"なので... ...
あなたはこの種の問題とその解決方法を説明する本またはinetlinkへの参照を提供してください。 私の特別なケースでは、多くの矩形（約100）を扱う必要はありませんが、よりよいアルゴリズムがあることを知っている限り、より良い/最良のアルゴリズムを試すことに抵抗することはできません。 – dermoritz
"セクションを私の応答に - うまくいけば助けてくれます。アルゴリズムについての学習を楽しくしてください。 :) –
@Igorが正しいです。ベントレーは、この分野で古典的な論文と精神的な論文をたくさん書いています。彼の論文は私にとって非常に貴重なものでした。あなたが直交の境界に関係しているという事実を最小にしないでください。この分野では多くの作業が行われているため、これは大きな問題です。掃引線アプローチは、軸を選択してその軸に直交するエッジを投影するだけで、この軸のイベントラインは矩形の始点または終点のいずれかを意味するので、この問題に対して簡単に実装することができます。計算幾何学の第8章：PreparataとShamosの紹介を参照してください。 – babernathy
この宿題はありますか？ –
できるだけ詳しく説明してください。あなたが問題を述べることができない場合、解決策は非常に見えにくいです。 –
は、x/y軸に平行な矩形の辺であるか、またはそれらは任意の方向にあり得るか？ – PeskyGnat