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

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

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

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

查看角落案例!

Answer 2

经过一番摆弄，我终于弄清楚了你想要什么。请注意，对于“严格边界框”的含义仍然存在一些争议：原始问题中的示例不满足您给出的描述：

但只有当边界框恰好等于两个矩形组合的大小时，才应组合矩形，即边界矩形的面积必须与两个源矩形的面积大小完全相同。如果矩形1的面积为a1，矩形2的面积为a2，边界矩形的面积为a3，则a1+a2=a3。

这个实现应该会给你很多想法，我相信你知道如何写

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

如果你真的想要那个。

键盘代码：

// 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)