8

2 つの重なり合う四角形を取り、四角形 A の領域をカバーするが、四角形 B の領域を除外する四角形の配列を返す関数を作成しようとしています。このアルゴリズムがどのように見えるかを理解するのに苦労しています。考えられる衝突の数は膨大であり、説明が困難です。

tl;dr別の長方形を使用して長方形をクリップしようとしていますが、残りの領域を覆う長方形のコレクションになります。

|-------------|                               |-------------|
|A            |                               |R1           |
|     |-------|----|                          |-----|-------|
|     |B      |    |           To             |R2   |
|     |       |    |          ====>           |     |
|     |       |    |                          |     |
|-----|-------|    |                          |-----|
      |            |
      |------------|

POSSIBLE OVERLAP PATTERNS

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

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

上記のオーバーラップ パターンのいずれかで、長方形 A と B がエーテルの長方形になる可能性があるため、可能なオーバーラップ パターンは示されているものの 2 倍であることに注意してください。

4

3 に答える 3

5

2 つの長方形は、画面を 9 つのゾーン (14 ではなく) に分割します。構成をもう一度考えてください。

 y1 -> |-------------|       
       |A            |        
 y2 -> |     |-------|----|   
       |     |B      |    |   
       |     |       |    |   
       |     |       |    |   
 y3 -> |-----|-------|    |   
             |            |
 y4 ->       |------------|
       ^     ^       ^    ^
       x1    x2      x3   x4

x 座標は 5 つの垂直バンドを定義しますが、最初 (左) と最後 (右) は興味がないので、x1 から x4 までの 3 つのバンドでのみ作業する必要があります。y 座標も同様: y1 から y4 までの 3 つの水平バンド。

つまり、A、B、どちらにも属さない、または両方に属する 9 つの長方形のゾーンです。あなたの例は次のように分かれています：

  |-----|-------|----|       
  |A    |A      |none| 
  |-----|-------|----|   
  |A    |Both   |B   |   
  |     |       |    |   
  |     |       |    |   
  |-----|-------|----|   
  |none |B      |B   |
  |-----|-------|----|

したがって、A と B の座標を比較すると、9 つのゾーンのうちどれが A のみに属しているかがわかります。これらは保持するゾーンです。

于 2013-05-18T08:21:05.953 に答える