c++ - 二维矩形的 boolean 运算

Question

我已经编写了自己的矩形类，它包含一种从一个矩形中减去另一个矩形的方法。该算法简单地确定源矩形与目标矩形的哪条边重叠，然后检查所有可能的情况，包括完全在里面、刚好在边缘上、完全封闭等等。事实上，我正在查看代码并想知道是否有算法或矩形 boolean 运算示例已经可用。

我知道有 generalised clipping algorithms for 2d polytopes但我一直在寻找特定于 2d 矩形的东西，并进行适当的优化和简化。

谁能给我指出正确的方向，或者说 Weiler-Atherton 是否是这类一般问题的最后定论，其中矩形只是一个案例？

Answer 1

如果将两个方向分开，则只有几个基本情况，然后可以将它们组合在嵌套循环中。

基本情况如下所示:

               |              |
       XXXXX   |..............|              1 section
               |              |
            XXXXXXX...........|              2 sections
               |              |
               |...XXXXXXX....|              3 sections
               |              |
               |..........XXXXXXXX           2 secions
               |              |
               |..............|   XXXX       1 section
               |              |
             XXXXXXXXXXXXXXXXXXXX            nothing
               |              |

垂直条是原始矩形的边缘，X 是要减去的矩形，点标记部分。垂直条之间的 X 也是保留的部分，除非与另一个方向的 X 部分组合。 (如果这听起来太复杂:留下的孔由两个方向的 X 部分指定。

我们可以通过将矩形属性左、上、右和下重新设计为最小/最大值数组来分隔方向:

typedef struct Rect Rect;

struct Rect {
    int min[2];
    int max[2];
};

(恐怕代码是 C，不是 C++。)

然后我们可以找到每个方向的部分:

int rect_sub_dir(int sec[], int *skip, Rect a, Rect b, int dir)
{
    int n = 0;

    sec[n++] = a.min[dir];
    if (b.min[dir] > a.min[dir] && b.min[dir] < a.max[dir]) {
        sec[n++] = b.min[dir];
    }
    *skip = n - 1;
    if (b.max[dir] < a.max[dir] && b.max[dir] > a.min[dir]) {
        sec[n++] = b.max[dir];
    }
    sec[n] = a.max[dir];

    // Backpatch if rectangles don't overlap        
    if (b.max[dir] < a.min[dir]) *skip = -1;
    if (b.min[dir] > a.max[dir]) *skip = -1;

    return n;
}

这会在 n 部分之间创建一个 n + 1 边界数组。 skip 值表示垂直条之间标记为 X 的部分。

然后您可以组合两个方向的部分:

int rect_sub(Rect res[], Rect a, Rect b)
{
    int hor[4];
    int ver[4];

    int hskip, nhor;
    int vskip, nver;
    int h, v;
    int n = 0;

    nhor = rect_sub_dir(hor, &hskip, a, b, 0);
    nver = rect_sub_dir(ver, &vskip, a, b, 1);

    printf("%d, %d\n", hskip, vskip);

    for (h = 0; h < nhor; h++) {
        for (v = 0; v < nver; v++) {
            if (h == hskip && v == vskip) continue;

            res[n++] = rect(hor[h], ver[v], hor[h + 1], ver[v + 1]);
        }
    }

    return n;
}

这个解决方案不是最优的。当第二个矩形包含在第一个矩形中时，它将创建八个矩形，这可能不是您要查找的。之后您总是可以尝试合并相邻的矩形。或者您可以重写代码以更智能地拆分矩形。

我已经用一些案例测试了代码，但是因为有很多可能的安排，所以代码没有完全测试。