5
$\begingroup$

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.

  • 0
    In case no intersections of segments is found, the test for total containment has to be made. It is much quic$k$er than the first part however.2012-05-26

2 Answers 2

3

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.

  • 0
    @AndersForsgren Well, to make an approximation, you could compute convex hulls first, and go further only if those intersect.2012-05-26
1

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.

  • 1
    I can assure you this is still an area of active improvement in the software in question, thanks for your new insights!2018-05-07