Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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. –  Anders Forsgren May 26 '12 at 13:05
    
@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. –  lhf May 26 '12 at 15:21
    
@AndersForsgren Well, to make an approximation, you could compute convex hulls first, and go further only if those intersect. –  dtldarek May 26 '12 at 17:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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