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.

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Eric Stucky May 26 '12 at 10:02
  • $\begingroup$ My understanding is that it only applies to convex polygons? $\endgroup$ – Anders Forsgren May 26 '12 at 10:24
  • $\begingroup$ What do you mean by fast? I.e. how fast? $\endgroup$ – M.B. May 26 '12 at 10:31
  • $\begingroup$ Faster than my example predicate at least. $\endgroup$ – Anders Forsgren May 26 '12 at 10:34
  • $\begingroup$ You say "area of overlap" but you're only checking for intersections between segments. What if one polygon is entirely inside the other one? $\endgroup$ – Rahul May 26 '12 at 11:08
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, at least the existence of this algorithm indicates that even O(n log n) is "good. which means that for my n I should probably accept O(n^2) with some fast rejection based on e.g bounding boxes. $\endgroup$ – Anders Forsgren May 26 '12 at 13:05
  • $\begingroup$ @Anders, yes, I was about to suggest that. I assume you know how to test for intersection of two line segments without computing the intersection point. It's just 4 ccw. $\endgroup$ – lhf May 26 '12 at 15:21
  • $\begingroup$ @AndersForsgren Well, to make an approximation, you could compute convex hulls first, and go further only if those intersect. $\endgroup$ – dtldarek May 26 '12 at 17:23
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I wonder if this new answer will be of use six years after the question was asked and an answer accepted. $\endgroup$ – Ethan Bolker May 6 '18 at 23:51
  • $\begingroup$ @EthanBolker: I feel as though your comment might be implicitly discouraging late answers. But I am not worried: satisfying OP's needs is only part of the reason I write answers. The question's been viewed 261 times since it was asked, so I expect it'll be about a week before anyone sees it. Perhaps it will be of value to them. $\endgroup$ – Richard May 7 '18 at 0:08
  • $\begingroup$ Sorry if I offended. I do discourage late repeated answers by new users to easy questions. Yours falls into none of those categories. It's well thought out and well written. I am curious about whether the OP will be able to take advantage of it. Others are likely to see it sooner than a week, since your answer bumps it to the front page. $\endgroup$ – Ethan Bolker May 7 '18 at 0:22
  • $\begingroup$ @EthanBolker: No worries. I'd developed the algorithm as a means of testing for nearby, as well as intersecting, segments. I've just edited the answer to link to my implementation. I think this is a weak point of the Bentley-Ottmann variant mentioned in the other answer: I have not yet found an implementation of it. $\endgroup$ – Richard May 7 '18 at 0:37
  • 1
    $\begingroup$ I can assure you this is still an area of active improvement in the software in question, thanks for your new insights! $\endgroup$ – Anders Forsgren May 7 '18 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.