8

固定平面内にランダムなサイズと位置の、重なり合う可能性のある長方形がいくつかあります。これらの長方形はランダムであるため、一部は重ならない場合があります。

| -----
| | | ---- |
| ---- | | |
          | ---- |

一部は1つのコーナーだけで重なる場合があります。

| ----- |
| |-|-|
|-|-| |
   | ----- |

一部は別の長方形の中に含まれている可能性があります。

| ---------------- |
| |
| | ----- | |
| | | |
| | ----- | |
| ---------------- |

一部は別の長方形を通過する可能性があります。

   | ---------------- |
   | |
|-| ------------------- |
| | | |
|-| ------------------- |
   | ---------------- |

等

入力セットと同じ領域を表すが、重複しない長方形のセットを提供するアルゴリズムを見つけようとしています。明らかな場合もあります。大きな長方形に含まれる長方形は破棄でき、角で重なる長方形は、別の長方形を通過する長方形と同様に3つの長方形に分割できます。私が探しているのは、これらすべてのケースを処理する一般的なアルゴリズムです。それが見事に効率的でなくても、私はあまり気にしません-入力セットはかなり小さいです（最大25個の長方形）

重なっている長方形を見つけるのは簡単ですが、特に1つの長方形が他の複数の長方形と重なっている可能性があることを考えると、そこからすぐに難しくなります。

これは私の頭を使っています。何か提案はありますか？

アップデート：

もう1つ気づきました。

このアルゴリズムは、設定した長方形が1つずつ追加されるとき、またはすべての長方形が追加された後に実行できます。考慮すべき長方形が1つしかないため、長方形が追加されるときにそれを行う方が簡単な場合がありますが、1つの長方形が他の複数の長方形と重なる状況を考慮する必要があります。

4

5 に答える 5

3

長方形はx＆y軸に平行ですか？そうだと思います。

KD-Treesを使用してみることができます。

または、自家製で必ずしも効率的ではないものが必要な場合は、「長方形化」してから、必要に応じて長方形をマージして戻すことができます。

「長方形化」とは、すべての長方形が収まる大きな長方形を最初に見つけることを意味します（基本的に、最小の左端、最大の右端、最小の下端、最大の上端によって形成される長方形）。

次に、長方形のすべてのエッジを伸ばして、大きな長方形を横切って切り取ります。これで「再角度付け」ができました。基本的に、これはすべて、垂直エッジと水平エッジを並べ替え、隣接するペアを選択して小さな長方形を形成することを意味します。小さな長方形ごとに、これが関心のある領域の一部であるかどうかを確認し、そうでない場合は拒否することができます（内側がいっぱいか外側が完全です）。

これで、関心のある領域を構成する小さな長方形（おそらく、O（n ^ 2）、あなたの場合は〜2500）のリストができました。数が将来の処理のために十分に小さい場合は、これらを使用するか、それらをマージして長方形の数を減らすことができます。

マージするには、長方形を検討し、マージの4つの可能性を検討できます（右または左に同じ高さの隣接する長方形、または上または下に同じ幅の隣接する長方形）。

エッジのソートされたリスト（水平と並列の両方）と、場合によってはいくつかのハッシュテーブルを維持することで、（マージ中だけでなく）処理を高速化できます。

于 2010-02-11T19:39:25.513 に答える
1

If you don't have any constraint on the number of rectangles that your algorithm should produce, you can definitely be rash in your treatment!

1. Easiest solution ever

Create a set of all the squares (of area 1) that are covered by the rectangles of the input set. A square being a rectangle... there you are!

2. Minimalist solution ?

Okay, that was rash, however I don't think you should worry about the input set. You problem is in fact different:

Pick up a contiguous area with a complex shape and try and cover it exactly with rectangles, minimizing their number and so that they do not overlap.

Of course, your area may not be contiguous, but it just means you have several contiguous areas you can work on independently.

Now, I freely admit I do not know the best solution for this problem, there are various approaches I can envision and I don't know their performances or result. KD-Tree should yield a solution, don't know if it's the minimalist one though!

于 2010-02-12T12:05:08.050 に答える
1

最初に、コンポジション内のすべての「アトミック」長方形のセットを作成します。つまり、長方形の交差によって形成され、それ自体が細分化されていない領域です。すべての実際の長方形は、1つ以上の原子長方形をカバーします。次に、SETCOVERなどの組み合わせ最適化アルゴリズムを実行して、すべてをカバーするために必要な長方形の最小数を計算します。

ここにアプローチの図があります。3つの長方形（A、B、C）があります。それらは5つの原子領域（1-5）を作成します：

 +---------+A
 |       1 |
 |    +----+-----+B
 |    |  2 | 3   |
 |    |  +-+---+C|
 |    |  |4|   | |
 +----+--+-+ 5 | |
      |  +-----+ |
      +--+-------+

長方形は、次の表に従って原子領域をカバーしています。

 A  {1,2,4}
 B  {2,3,4,5}
 C  {4,5}

SETCOVER問題は、長方形{A、B、C}の最小サブセットを選択して、長方形で覆われた原子領域をまとめたときにすべての原子領域が覆われるようにすることです。最小限の解決策は（明らかに）

 A {1,2,4} + B {2,3,4,5} = {1,2,3,4,5}

ここで、領域は非長方形であることに注意してください。たとえば、領域3は複雑な形状をしています。この問題は、次の方法で取り除くことができます。元の長方形のコーナーポイントのすべての異なるX座標を取得し、それらをグリッドのX座標と見なして、Y座標に対して同じことを行います。次に、すべての長方形は、細分化されることのないグリッドの正方形のセットをカバーします。

 +---------+A       -
 |       1 |
 |    +----+-----+B -
 |    |  2 | 3   |
 |    |  +-+---+C|  -
 |    |  |4|   | | 
 +----+--+-+ 5 | |  -
      |  +-----+ |  -
      +--+-------+  -

 |    |  | |   | |

これにより、次の5x5グリッドが得られます。

 AAA      A = rectangle A only
 A**BB    B = rectangle B only
 A*#CB    * = A and B
  BCCB    C = rectangles C and B
  BBBB    # = All

これから、5つの領域を簡単に抽出できます。実際のところ、それらはすでにマークされています:)（A、B、C、*、＃）

于 2010-02-11T17:12:23.163 に答える
1

非常に興味深い質問-一度に3つ以上を見るよりも、一度に1対の長方形の問題を解決するのが最善だと思います。他の長方形内のものを破棄することから始めます。これで、3種類の交差点のみが作成されます。コーナーオーバーラップとパススルーオーバーラップおよび部分オーバーラップ（長方形が完全に通過しない場合）です。これらはそれぞれ新しい長方形のセットを作成しますよね？

開始する長方形に1からNまでの番号を付けます。長方形から始めて、交差する長方形が見つかるまで1回繰り返します。新しい長方形を作成します。交差する2つの長方形を削除し、新しく作成した3つ以上の長方形をセットに追加して、最初からやり直します。

結果は、重なり合わない長方形の束全体になります。これにより、作成される長方形が最も少なくなりますか？おそらくそうではありませんが、長方形の数を最小限に抑えることが重要であると指定していません。o（n ^ 2）時間かかりますか？おそらく。

于 2010-02-11T19:48:32.747 に答える
0

長方形のセットがまだない場合は、別の方法でアプローチできます。大きな長方形から始めて、操作できるセットができるまで細かく分割します。これにより、重複がなくなります。

長方形全体から始めます

--------
|      |
|      |
|      |
|      |
|      |
--------

ランダムなポイントで分割し、2つの長方形を保存します。

--------
|      |
|------|
|      |
|      |
|      |
--------

ランダムな点でランダムな長方形を分割します

--------
|      |
|------|
| |    |
| |    |
| |    |
--------

繰り返す 。。。

--------
|      |
|------|
| |    |
| |----|
| |    |
--------

必要な数の長方形ができたら停止します。

毎回分割する長方形をより慎重に選択することで、これに必要な種類の「ランダム性」を生成させることができます。

于 2010-02-11T17:22:51.080 に答える