Efficient way to combine intersecting bounding rectangles

Question

I'm trying to simplify the following image using OpenCV:

What we have here are lots of red shapes. Some of them completely contain others. Some of them intersect their neighbors. My goal is to unify all intersecting shapes by replacing any two intersecting shapes with the bounding box of their union's polygon. (repeating until there are no more intersecting shapes).

By intersecting I mean also touching. Hope this makes it 100% clear:

I'm trying to do this efficiently using standard morphology operations; obviously it can be done naively in O(N^2), but that'll be too slow. Dilation doesn't help because some shapes are only 1px apart and I don't want them merged if they're not intersecting.

Answer 1

UPDATE: I misunderstood the question earlier. We don't want to remove rectangles which are completely inside others. We only want to replace the intersecting rectangles. Therefore for the first case, we have to do nothing.

New api (2.4.9) supports & and | operators.

From opencv doc:

• rect = rect1 & rect2 (rectangle intersection)
• rect = rect1 | rect2 (minimum area rectangle containing rect2 and rect3 )

It also supports equality comparision (==)

• rect == rect1

So it is now very easy to accomplish the task. For every pair of rectangle rect1 and rect2,

if((rect1 & rect2) == rect1) ... // rect1 is completely inside rect2; do nothing.
else if((rect1 & rect2).area() > 0) // they intersect; merge them.
    newrect = rect1 | rect2;
    ... // remove rect1 and rect2 from list and insert newrect.

UPDATE 2: (for translating in java)

I know java very little. I also never used the java API. I am giving here some psudo-code (which I think can be easily translated)

For & operator, we need a method which finds the intersect of two rectangles.

Method: Intersect (Rect A, Rect B)
left = max(A.x, B.x)
top  = max(A.y, B.y)
right = min(A.x + A.width, B.x + B.width)
bottom = min(A.y + A.height, B.y + B.height)
if(left <= right && top <= bottom) return Rect(left, top, right - left, bottom - top)
else return Rect()

For | operator, we need a similar method

Method: Merge (Rect A, Rect B)
left = min(A.x, B.x)
top  = min(A.y, B.y)
right = max(A.x + A.width, B.x + B.width)
bottom = max(A.y + A.height, B.y + B.height)
return Rect(left, top, right - left, bottom - top)

For == operator, we can use overloaded equals method.