total area of intersecting rectangles

What is an 开发者_开发问答algorithm for determining the total area of two rectangles that are intersecting and may be rotated off the coordinate axes?

---

Here's roughly what you need to do, expressed as generally as possible, but covering all possibilities:

• Work out the class of intersection. I.e. How many edges does the intersection area have? It could be anything from 0 to 8.
• Find all vertices of the intersection. This will be all intersections between the edges of the rectangles, and associated corners of the rectangles themselves. Working this bit out is the most complex/tedious.
• Work out the area of the intersection, by dividing it up into triangles if necessary.

Here's all the ways the rectangles can intersect:

Update

I've had some thoughts, and the best way to categorize the intersection is to trace round the perimeter of each rectangle and count the number of times each edge intersects another edge. You'll get a vector, e.g. for a six sided intersection area: {1,1,1,1},{0,1,1,1}, and for 8: {2,2,2,2},{2,2,2,2}. The two special cases you'll need to check for are when one rectangle completely encloses the other and when the edges are in line. You'll need to do careful checks, but this would be the starting point for a function to categorize the intersection.

---

Area(R1 union R2) = Area(R1) + Area(R2) - Area(R1 intersection R2), so you can calculate the area of the intersection to have the area of the union.

Intersections of two rectangles (or two convex polygons) are simple:

• They are convex polygons
• Their points are characterized as follows: intersection points of any pair of edges, and points of one rectangle which are inside the other.

So it goes like this:

• L is an initially empty linked list
• R1 has edges e1, e2, e3, e4, R2 has edges f1, f2, f3, f4. Compute intersection points of ei and fj, for all i,j=1,2,3,4. Add them to list L.
• For each vertex v of R1, if v is inside R2, add it to L.
• For each vertex w of R2, if w is inside R1, add it to L.

The convex hull of points in L is your intersection. As every point in L is on the boundary of the intersection, you can triangulate it and compute its area. Easy:

• L = [x0, x1, ... ]
• Sort points in L according to the angle of (xi - x0) with respect to an horizontal line passing through x0
• First triangle is x0, x1, x2
• Second triangle is x0, x2, x3
• nth triangle is x0, x(n+1), x(n+2)

The area of a triangle is given by Heron formula:

• a, b, c are edge lengths
• s = 0.5 * (a + b + c)
• area = sqrt(s * (s - a) * (s - b) * (s - c))

but beware of computing s - a, s - b and s - c independantly since you can encounter roundoff error (what if c ~ a and b << a for instance ?)

---

Ok, you have 3 possibilities: 1. Rectangles don't intersect 2. One rectangle is completely contained within the other (or they coincide) 3. The result of intersection is some convex polygon. You compute the area of a polygon by breaking it into triangles (by drawing segments from the first vertex to every other except for adjacent once). The you sum up the areas. You can use Herodot's theorem to calcaulate triangle's area and that's where midlle school geometry comes in.