6
$\begingroup$

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.

2 Answers 2

6

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.
  • 0
    yes.. the extra steps. I thought there was a better solution to the original problem. Thanks anyways. :)2018-10-04
0

To help users with the coding aspect as suggested by @libor I wrote a gist (which is quite long) so here is the github gist link - https://gist.github.com/markroxor/86d62360836fd16b65bf10ebf641473f.

enter image description here

This gives the intersection of two quadrilaterals, the intersecting region is bound by black boundary (and a little common sense will tell you what the quardrilaterals were) :)

In addition to @libor's approach I used scipy's convex hull to find out the coordinates in cyclic order. Then I applied shoelace formula to find the area , given the coordinates of a polygon in cyclic order.