JavaScript에서 직사각형 자르기

Question

두 개의 겹치는 사각형을 사용하고 사각형 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의 위쪽 가장자리, B의 위쪽 가장자리) - (B의 왼쪽 가장자리 , max (A의 아래쪽 모서리, B의 아래쪽 모서리))
3. B의 오른쪽 가장자리가 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

두 개의 직사각형이 화면을 9 개 구역 (14 개가 아닌)으로 나눕니다.

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

는 x 좌표가 5 개 수직 밴드를 정의하지만 당신은 단지 X1에서 X4에 3 개 밴드에 작업해야하므로 (오른쪽) 첫 번째 (왼쪽)와 마지막으로, 재미있다 : 당신의 구성으로 다시 생각하십시오. y 좌표와 동일 : y1에서 y4까지의 세 개의 수평 밴드.

이렇게 A, B, none 또는 both에 속하는 9 개의 직사각형 구역입니다. 귀하의 예는 다음과 같이 구분됩니다

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

가 그래서, 그들은 유지하는 영역 만 A에 속한 9 개 구역의 어느 찾을 수 A와 B의 좌표를 비교.