Clipping a Rectangle in JavaScript

Question

I'm trying to write a function that takes two overlapping rectangles and returns an array of rectangles that cover the area of rectangle A, but exclude area of rectangle B. I'm having a hard time figuring out what this algorithm looks like as the number of possible collisions is huge and difficult to account for.

tl;dr I'm trying to clip 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 is double that shown because rectangle A and B could be ether rectangle in any of the overlap patterns above.

Answer 1

The two rectangles divide the screen in 9 zones (not 14). Think again of your configurations:

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

The x coordinates define 5 vertical bands, but the first (left) and last (right) are uninteresting, so you only need to work on the 3 bands from x1 to x4. Same for y coordinates: three horizontal bands from y1 to y4.

So that's 9 rectangular zones that belong to A, B, none or both. Your example is divided like this:

  |-----|-------|----|       
  |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 belong to only A. They are the zones to keep.

Answer 2

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

1. Find a rectangle within A that is above rectangle B. If the top of A is higher than B (i.e. has a lower value in px), there is such an rectangle. This rectangle is defined by: (left edge of A, top edge of A) to (right edge of A, top edge of B).
2. If the left edge of B is to the right of the left edge of A, the next rectangle is: (left edge of A, min(top edge of A, top edge of B)) to (left edge of B, max (bottom edge of A, bottom edge of B))
3. If the right edge of B is to the left of the right edge of B, similar to above
4. ...and the possible rectangle below B

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

Pseudocode with a somewhat unusual, but for this purpose clear, definition of 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 3

Working from dan.p's code, using the suggestion by boisvert, my routine looks like this:

  this.clip = function(other) {
    var res = [];
    // Rect has a constructor accepting (left, top, [right, bottom]) for historical reasons
    if (this.top < other.top) {
      res.push(new Rect(Math.max(this.left, other.left), other.top, [Math.min(this.right, other.right), this.top]));
    }
    if (this.left > other.left) {
      res.push(new Rect(other.left, other.top, [this.left, other.bot]));
    }
    if (this.right < other.right) {
      res.push(new Rect(this.right, other.top, [other.right, other.bot]));
    }
    if (this.bot > other.bot) {
      res.push(new Rect(Math.max(this.left, other.left), this.bot, [Math.min(this.right, other.right), other.bot]));
    }
    return res;
  }

I tested with 16 cases (for four independent ifs).