Area of rectangle-rectangle intersection

c++ math computational-geometry
Vadim picture Vadim · Nov 4, 2011 · Viewed 8k times · Source

Below are 2 rectangles. Given the coordinates of the rectangle vertices - (x1, y1)...(x8, y8), how can the area of the overlapping region (white in the figure below) be caclulated?

Note that:

  1. Coordinates of points might be any
  2. Rectangles may or may not overlap
  3. Assume area is 0 when rectangles don't overlap, or they overlap at point or line.
  4. If one rectangle is inside the other, then calculate area of smaller rectangle.

enter image description here

Answer

Codie CodeMonkey picture Codie CodeMonkey · Nov 4, 2011

Since you stated that the rectangles may not be aligned, possible answers may be nothing, a point, a line segment, or a polygon with 3-8 sides.

The usual way to do this 2d boolean operation is to choose a counterclockwise ordering of the edges, and then evaluate edge segments between critical points (intersections or corners). At each intersection you switch between an edge segment of the first rectangle to an edge of the second, or visa-versa. You always pick the segment to the left of the previous segment.

enter image description here

There are LOTS of details, but the basic algorithm is to find all intersections and order them on their edges with an appropriate data structure. Choose an intersection (if there is one) and choose a line segment leading away from that intersection. Find the segment of the other rectangle to the left of the chosen starting segment. In the picture, we choose the green segment on intersection a (in the direction indicated by the arrow) as the reference segment. The segment of the other rectangle that is to the right, is the segment from a to b. Use that as the next reference segment, and choose a green segment to the left of it. That's the segment from b to c. Find segment cd the same way. The next segment is from d to the corner, so the corner is in the vertex list for the intersection as well. From the corn we get back to a.

To choose the left side each time, you use the determinate of the coordinates of the direction vectors for the edges that meet. If the determinant for the ordered pair of directed edges is positive, you're going the right way.

Now that you have the vertices of the intersection polygon, you can use the surveyor's formula to get the area.

Some of the details that I'm leaving to you are:

  • What if a corner is coincident to to an edge or vertex of the other triangle?

  • What if there are no intersections? (one rectangle is inside the other, or they are disjoint--you can use point-in-polygon checks to figure this out. See the Wikipedia article on polygons.

  • What if the intersection is a single point or a segment?

Related questions

What is the C++ function to raise a number to a power?

How do I raise a number to a power? 2^1 2^2 2^3 etc...

Read More
Is there a standard sign function (signum, sgn) in C/C++?

I want a function that returns -1 for negative numbers and +1 for positive numbers. http://en.wikipedia.org/wiki/Sign_function It's easy enough to write my own, but it seems like something that ought to be in a standard …

Read More
Fast ceiling of an integer division in C / C++

Given integer values x and y, C and C++ both return as the quotient q = x/y the floor of the floating point equivalent. I'm interested in a method of returning the ceiling instead. For example, ceil(10/5)=2 and ceil(11/5)=3. The …

Read More