Detect if two rectangles can be combined into a single rectangle

I'm looking for an algorithm that takes two rectangles defined by (xa1,ya1,xa2,ya2) and (xb1,yb1,xb2,yb2), checks if they can be combined into a single rectangle and if they can, returns the new rectangle. An example:

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

These two rectangles can be combined开发者_Python百科 into the following rectangle:

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

How would you implement such an algorithm? Thanks!

I'd draw the following pictures and would write it down as algorithm:

...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

Check out for corner cases!

After much fiddling I kind of worked out what you want. Note that there is still some contention to what you mean by 'strict bounding box': the sample in you original question does not satisfy the description you gave:

But the rectangles should only be combined if the bounding box is exactly the size of the two rectangles combined, i.e. the area of the bounding rectangle must be exactly the same as the size of the areas of the two source rectangles. If the area of rect 1 is a1, and the area of rect2 is a2, and the area of the bounding rect is a3, then a1+a2=a3.

This implementation should give you plenty of ideas, and I'm sure you know how to write

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

if you really wanted that.

Codepad code:

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

Output:

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)

They can be combined if and only if one pair of opposite sides of one rectangle overlaps one pair of opposite sides of the other rectangle. By overlap, I mean if they are parallel and contain at least one point in common.

You should be able to figure out the code ;)

EDIT: Oh I forgot to mention the case where the two rectangles are completely overlapping. That shouldn't be too hard to check either.

The two rectangles must intersect. The corners of the bounding rectangle must all land on existing corners.

Those two conditions are necessary and sufficient. Obviously the rectangles have to intersect, and, because you can't create a non-corner empty area using only 2 intersecting rectangles, the bounding corners must land on existing corners.

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

Implementing Intersects, BoundingRectangleWith, Corners, and IsSubsetOf is straightforward. You can then inline them for better performance, but it will be a mess of unreadable comparisons.

Edit

One of your comments suggests you don't want the rectangles to overlap, only to touch. In that case you only need to check that on one axis (i.e. X or Y) the rectangle's ranges are equal and on the other axis the ranges touch. Two ranges touch if the median of their bounds has 2 occurrences. Note that if you want right=1 to touch left=2, you need to add 1 to the ceiling bounds.