Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

enter image description here

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.

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

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.
share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.