JavaScript rectangle cropping

Question

I am trying to write a function that takes two overlapping rectangles and returns an array of rectangles that cover the region of rectangle A but exclude the region of rectangle B. I find it difficult to determine what this algorithm looks like since the number of possible collisions is huge and difficult to take into account.

tl; dr I am trying to fix a rectangle using another rectangle, resulting in a collection of rectangles covering the remaining area.

|-------------| |-------------| |A | |R1 | | |-------|----| |-----|-------| | |B | | To |R2 | | | | | ====> | | | | | | | | |-----|-------| | |-----| | | |------------| POSSIBLE OVERLAP PATTERNS |-----| |-----| |-----| |-----| | |---|-| |-|---| | | |-| | | |-| | |-|---| | | |---|-| |-|-|-| | |-| | |-----| |-----| |-| |-----| |-| |-----| |-----| |-|-|-| | |---|-| |-|---| | | |-| | | |---|-| |-|---| | |-----| |-----| |-----| 

Note that the possible overlap patterns are double, which is shown because rectangle A and B can be a simple rectangle in any of the above overlap patterns.

Answer 1

There will be no unique solution for any particular installation, but you can easily find one of the solutions with this algorithm:

• Find the rectangle inside A, which is above the rectangle B. If the vertex A is higher than B (i.e., has a lower value in px), then such a rectangle exists. This rectangle is defined as follows: (left edge A, upper edge A) - (right edge A, upper edge B).
• If the left edge of B is to the right of the left edge of A, the following rectangle is: (left edge of A, min (upper edge of A, upper edge of B)) to (left edge of B, max (lower edge of A, lower edge of B))
• If the right edge of B is to the left of the right edge of B, similarly above
• ... and a possible rectangle below B

In total, you will get from 0 to 4 rectangles.

Pseudo-code with a somewhat unusual but understandable definition of a rectangle:

 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

Two rectangles divide the screen into 9 zones (not 14). Think again about your configurations:

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

The x coordinates define 5 vertical stripes, but the first (left) and last (right) are not interesting, so you only need to work with 3 stripes from x1 to x4. The same for y coordinates: three horizontal stripes from y1 to y4.

So, 9 rectangular zones belonging to A, B, not one, not one or the other. Your example is divided as follows:

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

So, comparing the coordinates of A and B, you will find which of the 9 zones belongs only to A. They are the zones to save.