Predicate for intersection of polygons

An answer to this question on the Mathematics Stack Exchange.

Question

What is a (computationally) fast way of determining whether two polygons intersect, without actually computing this area of intersection?

Definitions

  • polygon: a counterclockwise simply connected sequence of points.
  • intersects: have a nonzero area of overlap.

An example predicate would be that when all segments from p1 are intersected with all segments of p2, there are at least two intersections. But this is an O(N^2) predicate to evaluate.

Answer

Depending on what your input data looks like, the following may be faster.

Particularly, if you have a large set of small polygons and are checking for intersection with a smaller set of large polygons, you can perform caching of intermediate data structures. This algorithm also facilitates checking for segments within some distance $d$ of each other.

An implementation is available here as part of the compactnesslib library.

Quick Filtering

First, find the bounding boxes of both polygons in O(n) time in the number of vertices of the polygons. If the bounding boxes don't overlap, then the polygons do not overlap.

Three Possible Ways To Intersect (Or Not)

Next, note that there are three possible situations.

  1. The boundaries of the two polygons intersect.

  2. One of the polygons completely contains the other.

  3. The polygons do not intersect.

The First Possibility: Boundary Intersection

You can discretize the edges of the polygons into segments not exceeding some maximum length $L$ in O(n) time in the final number of segments.

Having done so, use a hash table with cells of dimension $L\times L$ to bin the segments of one of the polygons. Each segment will be assigned to between 1 and 3 bins.

Now, iterate over the edges of the second polygon, determining which bin(s) they would be assigned to. If a bin is non-empty, perform a segment-segment intersection check. If the line segments intersect, so too do the polygons.

The Second Possibility: Complete Containment

If the boundaries of the polygons do not intersect, then check for the second possibility: complete containment. We don't know which polygon might contain the other, so we have to do two checks.

Label the polygons A and B. Choose an arbitrary point from polygon A and do an O(n) in the number of vertices point-in-polygon check to see if the arbitrary-chosen point is contained in polygon B. If so, return; if not, swap the labels and do the check again.

The Third Possibility: The Polygons Don't Intersect

If you've made it this far, then the polygons don't intersect.