在JavaScript中剪裁矩形

我正在尝试编写一个函数，它需要两个重叠的矩形，并返回一个覆盖矩形A区域但排除矩形B区域的矩形数组。看看这个算法看起来像什么，因为可能碰撞的数量是巨大且难以解释的。在JavaScript中剪裁矩形

tl; dr我试图使用另一个矩形剪裁矩形，导致覆盖其余区域的矩形集合。

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

POSSIBLE OVERLAP PATTERNS 

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

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

注意，可能的重叠图案是两倍示出，因为矩形A和B可以是醚矩形任何上述内容中重叠图案。

来源

2013-05-18 Robert Hurst

这可能是使用了顶点这个可行的。您可以根据B中顶点之间的距离A计算新的矩形坐标。 – Nikki

存在另一个问题，结果有时会超过一个矩形。我认为在一到九之间。 –

当然有一个标准的算法？无论如何;一个主意。有4个坐标和4个y坐标，您的新区域将始终是这些区域的组合。 4 x坐标将画布分成5个垂直波段，y坐标划分为5个水平波段，如果最差的情况最差，则有25个不重叠的矩形属于A，B，两者都不是。你保留仅属于A的属性并排除所有其他属性。 – boisvert

不会有任何特定设置一个独特的解决方案，但你可以很容易地找到该算法的解决方案之一：

内的查找矩形高于矩形B.如果顶部A高于B（即在px中具有较低的值），则存在这样的矩形。该矩形由（A的左边缘，A的上边缘）至（A的右边缘，B的上边缘）定义。
如果B的左边缘在A的左边缘的右边，则下一个矩形是:(A的左边缘，min（A的上边缘，B的上边缘））到（B的左边缘，最大值（A的底部边缘，B的底部边缘））
如果B的右边缘到B的右边缘的左侧，类似于上面
...和下文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) ;

来源

2013-05-18 08:24:04

有些情况未涉及 - 例如如果B比A更宽并且将A切入两个...... – boisvert

@boisvert，它将被覆盖。你所有的九个地区都完全覆盖。在数学上不像你的解释那么优雅，但是有一个非常简单的算法。 –

糟糕...我没有注意你使用最小和最大。你是对的，它工作得很好。不要看到任何不雅的事情。 – boisvert

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

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

的X坐标定义5条垂直带，但第一（左）和去年（右）都提不起兴趣，所以你只需要在3个频段工作，从X1到X4。 y坐标相同：从y1到y4三个水平带。

这是9个矩形区域属于A，B，没有或两者。你的榜样划分是这样的：

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

所以比较A和B的坐标，你会发现其中9个区仅属于A.它们是保持区域。

来源

2013-05-18 08:21:05 boisvert

谢谢，这是非常有帮助的。干杯！ –

但是，请参阅dan.p的答案，为您提供一个完整的解决方案... – boisvert

在JavaScript中剪裁矩形

回答

相关问题