检测两个矩形是否可以合并成一个矩形

Question

我正在寻找一个算法，它可以接受两个由（xa1，ya1，xa2，ya2）和（xb1，yb1，xb2，yb2）定义的矩形，并检查它们是否可以组合成一个单一的矩形。如果可以，它将返回新的矩形。以下是一个示例：

xa1=0,ya1=0,xa2=320,ya2=119
xb1=0,yb1=120,xb2=320,yb2=239

这两个矩形可以组合成下面的矩形：

xc1=0,yc1=0,xc2=320,yc2=240

你如何实现这样的算法？谢谢！

- Andy

---

画几幅图，你很快就能明白了。 - Kerrek SB

你的意思是什么？是指合并后的区域还是重叠的部分？ - bjarneh

你的意思是：找到确切定义两个矩形并集的矩形，如果存在的话？ - sehe

刚注意到我一定是理解你的问题错了。yc2= 240 是从哪里来的？显然，你指的是两个矩形的 _bounding box_，如果它们重叠或接触的话？（假设 240 应该是 239） - sehe

有趣的是，boost库1.47.1今天发布了；它包括一个全新的几何库...它还有simplify和envelope...多么丰富啊。 - sehe

Answer 1

我会画以下图片，并将其写成算法：

...xxxxxxx       xxxxxxx....
.  x  .  x       x   . x   .
.  x  .  x       x   . x   .
...xxxxxxx       xxxxxxx....

xxxxxxx          .......
x     x          .     .
x.....x          xxxxxxx
xxxxxxx          x.....x
.     .          x     x
.......          xxxxxxx

..........
.        .
. xxxx   .
. x  x   .
. x  x   .
. xxxx   .
..........

xxxxxxxxxxxxxx
x            x
x   .......  x
x   .     .  x
x   .     .  x
x   .......  x
x            x
xxxxxxxxxxxxxx

注意边角情况！

- Donotalo

---

我不太擅长编写算法。我可以想出适用于特定情况的解决方案，但我确信它不适用于所有可能的情况 :/ 这就是为什么我更喜欢一些通用的问题解决方案 :) - Andy

不要忘记重要情况，即矩形没有交集。 - Craig Gidney

Answer 2

经过一番摸索，我有点明白你想要什么了。需要注意的是，“严格边界框”这个概念还存在争议：你原来的问题中给出的示例并不符合你所描述的条件：

但是，只有当边界框恰好等于两个矩形的组合大小时，才应该将矩形组合在一起，即边界矩形的面积必须恰好等于两个源矩形的面积之和。如果 rect1 的面积为 a1，rect2 的面积为 a2，边界矩形的面积为 a3，则 a1+a2=a3。

这个实现应该会给你很多灵感，我相信你知道如何编写。

r.area() == a.area() + b.area()

如果你真的想要那个。

---

Codepad 代码：

// Final proposal: combine adjacent rectangles, 
// if they are 'flush': almost touching

#include <iostream>

struct R
{
    int x1,y1,x2,y2;
    int height() const { return y2-y1; }
    int width() const  { return y2-y1; }

    void normalize() 
    { 
        if (x1>x2) std::swap(x1,x2);
        if (y1>y2) std::swap(y1,y2);
    }

    /*
     * adjacent: return whether two rectangles
     * are adjacent; the tolerance in pixels
     * allow you to specify the gap:
     *    tolerance = 0: require at least one pixel overlap
     *    tolerance = 1: accepts 'flush' adjacent neighbours
     * Negative tolerance require more overlap;
     * tolerance > 1 allows gaps between rects;
     */
    bool adjacent(R const& other, int tolerance=1) const
    {
        return !( (other.x1 - x2) > tolerance
               || (x1 - other.x2) > tolerance
               || (other.y1 - y2) > tolerance
               || (y1 - other.y2) > tolerance);
    }
};

/* 
 * tolerance: see R::adjacent()
 * 
 * strict: only allow strict ('pure') combinations of rects
 */
R combined(R const& a, R const& b, int tolerance=1, bool strict=false)
{
    if (!a.adjacent(b, tolerance))
        throw "combined(a,b): a and b don't satisfy adjacency requirements (are the coords normalized?)";

    R r = { min(a.x1, b.x1), 1,1,1};
    r.x1 = min(a.x1, b.x1);
    r.y1 = min(a.y1, b.y1);
    r.x2 = max(a.x2, b.x2);
    r.y2 = max(a.y2, b.y2);

    if (!strict)
        return r;

    if ( (r.height() <= max(a.height(), b.height()))
     &&  (r.width () <= max(a.width (), b.width ())) )
        return r;
    else
        throw "combined(a,b): strict combination not available";
}

std::ostream& operator<<(std::ostream &os, R const& r)
{
    return os << '(' << r.x1 << "," << r.y1 << ")-(" << r.x2 << ',' << r.y2 << ')';
}

int main()
{
    const int tolerance = 1;
    {
        std::cout << "sample from original question" << std::endl;
        R a = { 0, 0,   320, 119 }; /* a.normalize(); */
        R b = { 0, 120, 320, 239 }; /* b.normalize(); */

        std::cout << "a: " << a << "\t b: " << b << std::endl;
        std::cout << "r: " << combined(a,b, tolerance) << std::endl;
    }
    {
        std::cout << "sample from the comment" << std::endl;
        R a = { 0, 0, 1, 320 }; /* a.normalize(); */
        R b = { 0, 0, 2, 320 }; /* b.normalize(); */

        std::cout << "a: " << a << "\t b: " << b << std::endl;

        // NOTE: strict mode
        std::cout << "r: " << combined(a,b, tolerance, true) << std::endl;
    }
}

输出：

sample from original question
a: (0,0)-(320,119)   b: (0,120)-(320,239)
r: (0,0)-(320,239)
sample from the comment
a: (0,0)-(1,320)     b: (0,0)-(2,320)
r: (0,0)-(2,320)

- sehe

---

非常感谢，这正是我正在寻找的（非严格版本）。很抱歉我描述得不好，再次感谢您的帮助！ - Andy

Answer 3

这两个矩形必须相交。边界矩形的角落必须都落在现有的角落上。

这两个条件是必要且充分的。显然，这两个矩形必须相交，并且由于只使用两个相交的矩形无法创建非角落空区域，因此边界角落必须落在现有的角落上。

return r1.Intersects(r2) and r1.BoundingRectangleWith(r2).Corners.IsSubsetOf(r1.Corners.Union(r2.Corners))

实现Intersects、BoundingRectangleWith、Corners和IsSubsetOf很简单。然后您可以将它们内联以获得更好的性能，但这将是一堆难以阅读的比较。

编辑

您的评论之一表明您不希望矩形重叠，只希望它们接触。在这种情况下，您只需要检查一个轴（即X或Y）上矩形的范围是否相等，而在另一个轴上，范围是否接触。如果两个范围的边界中位数有2个出现，则两个范围接触。请注意，如果您希望right=1与left=2接触，则需要将ceiling bounds加1。

- Craig Gidney

Answer 4

只有当一个矩形的一对对边重叠于另一个矩形的一对对边时，它们才能组合在一起。重叠指的是它们是平行的，并且至少包含一个共同点。

你应该能够理解这段代码的意思；）

编辑：哦，我忘了提到两个矩形完全重叠的情况。检查这种情况也不难。

- tskuzzy

---

我没有将其评为-1。尽管如此，我无法想出一些通用算法。正如我上面所说，我可能能够想出一个对于我的特定情况有效的算法，但并不适用于所有情况...这对我的大脑来说太困难了...这就是为什么我希望从这里的数学天才那里得到一些帮助 :) - Andy