math - Clipping a Rectangle in JavaScript - Stack Overflow

admin管理员组

文章数量:1355679

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.

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.

• javascript
• math
• geometry
• 2d

Share Improve this question Follow edited May 18, 2013 at 2:03 Robert Hurst asked May 18, 2013 at 1:21 Robert HurstRobert Hurst 9,10288 gold badges4444 silver badges6666 bronze badges 3

• It might be feasible to use the vertex points for this. You can calculate the new rectangle coordinates based on the distance between the vertex points in B from A. – Nikki Commented May 18, 2013 at 1:25
• There lies another problem, the result sometimes more than one rectangle. between one and nine I think. – Robert Hurst Commented May 18, 2013 at 1:29
• Surely there is a standard algorithm? Anyway; an idea. There are 4 x coordinates and 4 y coordinates, your new zones will always be a bination of these. The 4 x coords divide the canvas into 5 vertical bands, the y coords into 5 horizontal bands, if the worst es to the worst there are 25 non-overlapping rectangles belonging to A, B, neither or both. You keep the ones belonging to only A and exclude all others. – boisvert Commented May 18, 2013 at 8:01

Add a ment  | 

3 Answers 3

Sorted by: Reset to default 5

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 paring the coordinates of A and B, you will find which of the 9 zones belong to only A. They are the zones to keep.

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) ; 

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).

本文标签： mathClipping a Rectangle in JavaScriptStack Overflow