5

長方形のコレクション (Java TreeSet) をチェックする方法を探しています。これは、x と y の範囲に Google guavas Range を使用して「同等の」Java クラスによって実装され、交差点と穴についてです。kd ツリーを使用するオプションがあることは知っていますが、そのような kd ツリーを構築する方法 (四角形の場合は 4d である必要がありますね) と、問題を解決する方法 (交差、穴）。

並べ替えでは、y 軸よりも x 軸が優先されます。

編集: (問題をもう一度述べてみてください): 使用例は、任意のテーブルを作成することです (2 つまたは 3 つの長方形のブロック「ヘッダー」、「列前」、「データ」で構成されます)。各ブロックに交差や穴 (つまり、無効な html またはテーブル データの他のソースによって提供される) がないことを保証する必要があります (これに加えて、ブロックは互いに適合する必要があります)。現在（アイデアを得たばかりです）、位置（x、y）が占有されている2次元配列に保存しようとしています。最後に、すべての位置を一度だけ占有する必要があります。

4

1 に答える 1

6

この種の問題を解決する方法は数多くあり、それぞれに長所と短所があります。それらのいくつかを次に示します。

四角形のペアの交点 + 面積の合計

四角形のすべてのペアを見てください。2 つの四角形が交差する場合は、重なりがあります。長方形の領域を合計し、合計がキャンバス領域と一致するかどうかを確認します。領域が一致しない場合は、ギャップがあります。

ペインティング

これはあなたが言及したアプローチです: キャンバスの寸法を持つ 2D 配列を作成します。次に、長方形を繰り返し処理し、それらを配列に「ペイント」します。

このアプローチの最適化の 1 つは座標圧縮です。長方形 [(10,20), (15,25)] と [(7,3), (15, 25)] があるとします。個別の x 座標 (7, 10, 15) を見て (0, 1, 2) に再マッピングし、個別の y 座標 (3, 20, 25) に再マッピングして (0, 1, 2)。次に、長方形 [(1, 1), (2, 2)] および [(0,0), (2,2)] が残るため、26x26 ではなく、3x3 配列のみが必要です。配列。

スイープ ライン アルゴリズム

左から右にラインをスイープし、「興味深い」ポイントで停止し、占有されているエリアを追跡します。

2D レンジ ツリー

長方形の範囲に対して効率的にクエリを実行できるデータ構造。

どちらを選ぶ？

それは、あなたが持っている四角形の数、それらが領域にどのように分布しているか、あなたのアルゴリズムがどれくらい速くなければならないか、あなたが引き受ける複雑さなどに依存します.私が言及した最初の2つのアルゴリズムは、後者よりもはるかに単純です. 2 つなので、そこから始めることをお勧めします。

より詳しい情報

これらのアルゴリズムについて詳しく知りたい場合は、オンラインで「rectangle union」を検索してみてください。最も効率的なソリューションは、スイープ ライン アルゴリズムです。

以下は、スイープ ライン アルゴリズムに関する参考資料です。

  1. 重なり合う長方形の領域を見つけるための効率的なアルゴリズムは何ですか
  2. http://compgeom.cs.uiuc.edu/~jeffe/open/klee.html
  3. JL Bentley、クレーの長方形問題のアルゴリズム。未発表のメモ、カーネギー メロン大学コンピューター サイエンス学部、1977 年

参考文献 3. は、通常、長方形和集合のライン スイープ アルゴリズムの元のソースとして提供されますが、おそらく「未公開」であるため、実際にオンラインで論文を見つけられなかったことを認めなければなりません...

于 2012-02-15T19:05:54.377 に答える