8

我正在尝试编写一个函数，该函数采用两个重叠的矩形并返回一个矩形数组，这些矩形覆盖矩形 A 的区域，但不包括矩形 B 的区域。我很难弄清楚这个算法是什么样的可能的碰撞数量巨大且难以解释。

tl; dr 我正在尝试使用另一个矩形来裁剪一个矩形，从而生成一组覆盖剩余区域的矩形。

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

POSSIBLE OVERLAP PATTERNS

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

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

请注意，可能的重叠模式是显示的两倍，因为矩形 A 和 B 可能是上述任何重叠模式中的以太矩形。

4

3 回答 3

5

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

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

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

这是 9 个矩形区域，它们分别属于 A、B、不属于或两者兼有。你的例子是这样划分的：

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

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

于 2013-05-18T08:21:05.953 回答
4

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

  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) ;
于 2013-05-18T08:24:04.120 回答
1

使用 dan.p 的代码，使用 boisvert 的建议，我的例程如下所示：

  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）。

于 2019-02-08T14:56:53.720 回答