在JavaScript中剪切矩形

Question

我正在尝试编写一个函数,它接受两个重叠的矩形并返回一个覆盖矩形A区域的矩形数组,但是排除了矩形B的区域.我很难弄清楚这个算法的样子是什么可能的碰撞数量巨大且难以解释.

tl; dr我正在尝试使用另一个矩形剪切一个矩形,从而产生一个覆盖剩余区域的矩形集合.

|-------------|                               |-------------|
|A            |                               |R1           |
|     |-------|----|                          |-----|-------|
|     |B      |    |           To             |R2   |
|     |       |    |          ====>           |     |
|     |       |    |                          |     |
|-----|-------|    |                          |-----|
      |            |
      |------------|

POSSIBLE OVERLAP PATTERNS

|-----|          |-----|      |-----|        |-----|
| |---|-|      |-|---| |      | |-| |        | |-| |
|-|---| |      | |---|-|      |-|-|-|        | |-| |
  |-----|      |-----|          |-|          |-----|

  |-|          |-----|          |-----|
|-|-|-|        | |---|-|      |-|---| |
| |-| |        | |---|-|      |-|---| |
|-----|        |-----|          |-----|

注意,可能的重叠模式是所示的两倍,因为在上面的任何重叠模式中矩形A和B可以是以太矩形.

Answer 1

这两个矩形将屏幕分为 9 个区域（不是 14 个）。再想想你的配置：

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

x 坐标定义了 5 个垂直波段，但第一个（左）和最后一个（右）没有意义，因此您只需要处理从 x1 到 x4 的 3 个波段。y 坐标相同：从 y1 到 y4 的三个水平带。

所以这是属于 A、B、无或两者的 9 个矩形区域。你的例子是这样划分的：

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

所以比较A和B的坐标，你会发现9个区域中的哪一个只属于A。它们是要保留的区域。

Answer 2

对于任何特定设置，都不会有唯一的解决方案，但您可以使用此算法轻松找到解决方案之一：

1. 在A内找到一个位于矩形B上方的矩形。如果A的顶部高于B（即具有较低的px值），则存在这样的矩形。该矩形的定义为：（A 的左边缘，A 的上边缘）到（A 的右边缘，B 的上边缘）。
2. 如果 B 的左边缘位于 A 左边缘的右侧，则下一个矩形为：(A 的左边缘，min(A 的上边缘，B 的上边缘)) 到 (B 的左边缘，max ( A 的底边、B 的底边))
3. 如果B的右边缘在B的右边缘的左边，类似上面
4. ...以及 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) ;