8

Clipping a rectangle into JavaScript

 2 years ago
source link: https://www.codesd.com/item/clipping-a-rectangle-into-javascript.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Clipping a rectangle into JavaScript

advertisements

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.


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




About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK