# Two Quadrilaterals Intersection Area (Special Case)

I have two intersecting quadrilaterals (the area of intersection is the grey polygon with thick boundary):

These properties holds:

• One quadrilateral is always a rectangle
• There is always some intersection
• Both quadrilaterals are convex (hence the intersection is a convex polygon as well)

The goal is to measure area of intersection (the actual shape is not needed, only a scalar showing how much space is covered by the intersection).

The problem arises in computer graphics (image mosaicing using projective geometry), where one image is stationary and the other is rotated in space and then projected in the same plane as the first one. I need to sort the images according the area of intersection they form.

-

## 1 Answer

Okay, I have probably figured it out. The algorithm goes as follows:

1. For each vertex of the first quadrilateral, check whether it is contained inside the second one - if so, store coordinates of the point.
2. For each vertex of the second quadrilateral, check whether it is contained inside the first one - if so, store coordinates of the point.
3. For each edge of one of the quadrilaterals (does not matter which one), check for intersections with edges of the other. Store coordinates of intersection points.
4. Compute triangulation for all the points stored so far.
5. Sum up areas of the triangles.
-
You could omit step 4 and compute the area using the shoelace formula as a cyclic sum of $2\times2$ determinants $x_iy_{i+1} - x_{i+1}y_i$. YOu still need to order the triangles to form a convex polygon, though. –  MvG Jul 9 '12 at 23:01