Find intersection between Rectangle and Union of a set of rectangles?

Question

I'm looking for a way to calculate the area of an intersection between a single rectangle and the union of a small set of rectangles.

I'm using Java and all of the rectangles are represented in integers (x,y,w,h). All rectangles are axis aligned with x/y axis. Any suggestions?

Answer 1

Both n.m's answer and PQuinn's answer suggest to distribute the intersection across the union, then find the area of the union. That's a good idea.

In java, I suggest creating a new set of non-degenerate intersections between R1 and your Rj's, based on the assumption that most intersections will be degenerate. Then use the algorithm at http://codercareer.blogspot.com/2011/12/no-27-area-of-rectangles.html to find the area of the set of intersections.

Answer 2

Go through and express your rectangles not as (x,y,w,h) but as (x1,y1,x2,y2), which is simply (x,y,x+w,y+h).

Then, loop over all Rj`s and "clip" the rectangles to the coordinates of Rect1:

Rj.x1 = max(Rj.x1, Rect1.x1)
Rj.y1 = max(Rj.y1, Rect1.y1)
Rj.x2 = min(Rj.x2, Rect1.x2)
Rj.y2 = min(Rj.y2, Rect1.y2)

Now, go through and remove any Rj's where Rj.x1>=Rj.x2 or Rj.y1>=Rj.y2 as in that case, the rectangles didn't intersect.

After, sum up all the areas of the remaining rectangles (simply (Rj.x2-Rj.x1) * (Rj.y2-Rj.y1)).

At this point, you will have double-counted any area where any of the clipped Rj`s overlap.

So, you then need to go through and loop over all Ri's and all Rj's where j>i and, clip the two with each other, but this time, if there is an intersection (same test as above), you need to subtract the area of the intersection from the value you have so far to remove the double-counting.

Unfortunately, this will double-remove any areas of a triple-overlap. So, you will then need to find those areas and add them back in. And so on and so forth for quadruple-overlaps, quintuple-overlaps, etc.

Sounds like it'll get pretty messy...

Maybe the easiest is to just draw the Rj's to a canvas in red and then count the red pixels inside Rect1 at the end. (Of course, you don't have to use a real Canvas. You can write your own using a bit-array.) There might even be scenarios (like a small coordinate space with lot's of tiny rectangles), where this is faster than the analytical solution. But, of course this will only work if you have integer coordinates.

Answer 3

An intersection of two rectangles is a rectangle itself (possibly degenerate, but those have zero area and can be ignored). Further, an intersection of unions is the same as a union of intersections (distributivity law). Therefore, you may intersect R1 with each of Rj and find the union of resulting rectangles.

To find the union, the easiest method is perhaps breaking the scene into vertical stripes, by drawing a vertical line through each vertex. Then within each stripe it's a well-known one-dimensional problem, solved by counting points in and out and removing those with count greater than one.

Answer 4

You're going to potentially have a unique intersection between Rect1 and every rectangle in the RectSet union. So you are going to have do the intersection between Rect1 and each rectangle in the union separately. The intersecting area is the union of all intersecting sections between Rect1 and the rectangles in the union.

An optimization is to create a abounding rectangle for the union of rectangles (hopefully done as the union is created). If Rect1 doesn't intersect with this bounding rectangle, you can the skip doing any further intersections and the area in null.