Detect if two rectangles can be combined into one rectangle

Question

I am looking for an algorithm that takes two rectangles, defined (xa1, ya1, xa2, ya2) and (xb1, yb1, xb2, yb2), checks if they can be combined into one rectangle, and if they can, returns a new rectangle. Example:

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

These two rectangles can be combined into the following rectangle:

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

How would you implement such an algorithm? Thanks!

Answer 1

After long grunts, I kind of worked out what you want. Please note that there is still some assertion about what you mean by “strict bounding box”: the sample in the original question does not provide a satisfactory description that you gave:

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

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

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

if you really wanted to.

---

Code 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 << "\tb: " << 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 << "\tb: " << 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) 

Answer 2

I would draw the following figures and write this as an algorithm:

 ...xxxxxxx xxxxxxx.... . x . xx . x . . x . xx . x . ...xxxxxxx xxxxxxx.... xxxxxxx ....... xx . . x.....x xxxxxxx xxxxxxx x.....x . . xx ....... xxxxxxx .......... . . . xxxx . . xx . . xx . . xxxx . .......... xxxxxxxxxxxxxx xx x ....... x x . . x x . . x x ....... x xx xxxxxxxxxxxxxx 

Look at the corner cabinets!

Answer 3

They can be combined if and only if one pair of opposite sides of one rectangle overlaps one pair of opposite sides of another rectangle. Crosswise, I mean, if they are parallel and contain at least one common point.

You should be able to figure out the code;)

EDIT: Oh, I forgot to mention the case where two rectangles completely overlap. This should not be too difficult to verify.

Answer 4

Two rectangles should intersect. The corners of the bounding box must be located at the existing corners.

These two conditions are necessary and sufficient. Obviously, the rectangles must intersect, and since you cannot create a non-angular empty area using only two intersecting rectangles, the bounding angles must land at the existing angles.

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

The implementation of Intersects , BoundingRectangleWith , Corners and IsSubsetOf is simple. You can then embed them for better performance, but it will be a mess of unreadable comparisons.

Edit

One of your comments suggests that you do not want the rectangles to overlap, but only touch. In this case, you only need to verify that the ranges of the rectangles are equal on one axis (i.e., X or Y), and the ranges on the other axis. Two ranges relate if the median of their boundaries has 2 occurrences. Please note: if you want right = 1 to touch left = 2, you need to add 1 to the borders of the ceiling.