JavaScriptで矩形を切り取る

Question

2つのオーバーラップする矩形を取り、矩形Aの領域をカバーする矩形の配列を返しますが、矩形Bの領域は除外する関数を作成しようとしています。起こりうる衝突の数が膨大であり、説明が困難な場合にこのアルゴリズムがどのように見えるかを調べることです。

tl; dr他の矩形を使用して矩形をクリップして、残りの領域をカバーする四角形のコレクションを作成しようとしています。

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

POSSIBLE OVERLAP PATTERNS 

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

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

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

Answer 1

あり、特定のセットアップのためのユニークなソリューションではありませんが、あなたは簡単にこのアルゴリズムで解決策の一つを見つけることができます：

1. はのトップ場合は長方形B.上にある内の四角形を探しますAがBよりも高い（すなわち、pxの値がより低い）場合、そのような矩形が存在する。この長方形は、（Aの左端、Aの上端）〜（Aの右端、Bの上端）で定義されます。
2. Bの左端がAの左端の右にある場合、次の長方形は、（Aの左端（Aの左端、Aの上端、Bの上端））から（Bの左端、max（Aの下端、Bの下端））
3. Bの右端がBの右端の左にある場合は、上記のように
4. ...と可能な矩形B

合計で、0〜4矩形が得られます。やや珍しいと

は

擬似コードが、明確なこの目的のため、長方形の定義について：

function getClipped(A, B) { 
    var rectangles = []; 
    if (A.top < B.top) { 
     rectangles.push({ left: A.left, top: A.top, right: A.right, bottom: B.top }); 
    } 
    if (A.left < B.left) { 
     rectangles.push({ left: A.left, top: max(A.top, B.top), right: B.left, bottom: min(A.bottom, B.bottom) }); 
    } 
    if (A.right > B.right) { 
     rectangles.push({ left: B.right, top: max(A.top, B.top), right: A.right, bottom: min(A.bottom, B.bottom) }); 
    } 
    if (A.bottom > B.bottom) { 
     rectangles.push({ left: A.left, top: B.bottom, right: A.right, bottom. A.bottom }); 
    } 

    return rectangles; 
} 

var rectA = { left: nn, top: nn, right: nn, bottom: nn}; 
var rectB = { left: nn, top: nn, right: nn, bottom: nn}; 

var clipped = getClipped(rectA, rectB) ; 

Answer 2

2つの矩形は9つのゾーン（14ではなく）で画面を分割します。あなたの構成の再考える：

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

のx座標（右）5本の縦帯を定義しますが、最初（左）と最後のつまらないなので、あなただけのX1からX4から3つのバンドで作業する必要があります。 y座標と同じ：y1からy4までの3つの水平バンド。

これはA、B、none、または両方に属する9つの矩形ゾーンです。あなたの例は次のように分かれていますので、AとBの座標を比較する

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

、あなたは彼らが保持するゾーンであるだけAに所属する9ゾーンのどのわかります。