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.
 A: 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.
A: 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.


*

*The boundaries of the two polygons intersect.

*One of the polygons completely contains the other.

*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.
