logo标签列表

JavaScript中的矩形裁剪

javascriptmathgeometry2d
8
我正在尝试编写一个函数，它接受两个重叠的矩形并返回一个覆盖矩形A区域但不包括矩形B区域的矩形数组。由于可能发生碰撞的数量巨大且难以计算，因此我很难确定该算法的样子。
简而言之，我正在尝试使用另一个矩形剪切一个矩形，从而得到一组覆盖剩余区域的矩形。
|-------------|                               |-------------|
|A            |                               |R1           |
|     |-------|----|                          |-----|-------|
|     |B      |    |           To             |R2   |
|     |       |    |          ====>           |     |
|     |       |    |                          |     |
|-----|-------|    |                          |-----|
      |            |
      |------------|

POSSIBLE OVERLAP PATTERNS

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

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

请注意，可能的重叠模式是上述显示的两倍，因为矩形A和B可以是上述任何重叠模式中的任意一个矩形。
可能可以使用顶点来实现这个。您可以根据B中顶点与A之间的距离计算新的矩形坐标。 - Nikki
还有另一个问题，结果有时会出现多个矩形。我想在1到9之间。 - Robert Hurst
肯定有一个标准算法吧？无论如何，我有一个想法。有4个x坐标和4个y坐标，你的新区域将始终是这些坐标的组合。4个x坐标将画布分成5个垂直带，y坐标将其分成5个水平带，如果最坏的情况发生，A、B、两者都属于25个不重叠的矩形之一。你保留只属于A的那些，并排除所有其他的。 - boisvert
3个回答
5

这两个矩形将屏幕分为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。它们是需要保留的区域。

4

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

  1. 在A中找到一个位于B上方的矩形。如果A的顶部高于B（即以px为单位的值较低），则存在这样的矩形。该矩形由以下定义：(A的左侧边缘，A的顶部边缘)到(A的右侧边缘，B的顶部边缘)。
  2. 如果B的左侧边缘位于A的左侧边缘右侧，则下一个矩形为：(A的左侧边缘，A的顶部边缘或B的顶部边缘中的较小值)到(B的左侧边缘，A的底部边缘或B的底部边缘中的较大值)
  3. 如果B的右侧边缘位于A的右侧边缘左侧，则类似于上述方式
  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) ;
有一些情况没有涵盖 - 例如，如果B比A更宽，并将A分成两部分... - boisvert
1
@boisvert，已经覆盖了。你的九个区域都被完全覆盖了。虽然不像你的解释那样数学优雅，但是使用非常简单的算法实现。 - dan.p
哎呀...我没有注意你使用了min和max。 你是对的，它运行得非常好。 我也没有发现任何不优美的地方。 - boisvert
这相当优雅。感谢您分解这个问题。非常感激。 - Robert Hurst
@dan.p，还有一个细节...如果矩形不重叠，则剪切区域太大。您需要更多地使用min/max。 - boisvert
1

参考boisvert的建议，我使用dan.p的代码，并编写了以下程序：

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

我进行了16个测试（针对四个独立的if语句）。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接