# Predicate for intersection of polygons

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.

-
Have you looked at the separating axis theorem? I'm not sure if it would help, but it's worth a look. en.wikipedia.org/wiki/Separating_axis_theorem –  Eric Stucky May 26 '12 at 10:02
My understanding is that it only applies to convex polygons? –  Anders Forsgren May 26 '12 at 10:24
What do you mean by fast? I.e. how fast? –  M.B. May 26 '12 at 10:31
Faster than my example predicate at least. –  Anders Forsgren May 26 '12 at 10:34
You say "area of overlap" but you're only checking for intersections between segments. What if one polygon is entirely inside the other one? –  Rahul May 26 '12 at 11:08

You can use the Bentley–Ottmann algorithm sweep line algorithm for testing the existence of crossings among a set line segments in time $O(n \log n$), where $n$ is the total number of segments. You'll have to adapt it to avoid testing segments of the same polygon. There are also variations of this algorithm for red-and-blue sets of segments. See for instance http://www.cs.unc.edu/~snoeyink/demos/rbseg/index.html.
Now, whether the $n$ you have justifies using a more complicated algorithm than the trivial quadratic one, is another matter.