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.

I have set of $N$ concave polygons, given as list of 2D Euclidean coordinates. How to compute:

a. if any of them are overlapping?

b. if one arbitrarily selected polygon overlaps with any of the remaining $N-1$ polygons?

No need for obtaining points of intersection of the polygon's borders. The second answer b is sufficient, but maybe there also exists specialized algorithm for answering a.

share|improve this question
    
Do you consider two polygons that share an edge to be overlapping? –  anorton Dec 9 '12 at 14:12
    
And, are these integer coordinates or floats? (I'm asking this because it sounds like a programming problem...) –  anorton Dec 9 '12 at 14:19
    
For b, could you use the algorithm described here? stackoverflow.com/questions/2272179/… –  anorton Dec 9 '12 at 14:51
    
@anorton: floats. Sharing edge could mean no-overlapping –  Sydnic Dec 9 '12 at 15:26

1 Answer 1

up vote 2 down vote accepted

If they intersect, either one of the polygons must be fully contained within the other, or their edges must intersect, so it's enough to

  • pick a random vertex of either polygon, and see if it lies inside the other polygon
  • check if there edge segments intersects.

If one of these tests returns true, then they intersect, otherwise they don't.

This can be implemented efficiently with a simple sweep line algorithm.

share|improve this answer
    
In the second step, you mean to check, if there are any edge intersections between polygons? Naive approach would require k*l intersection tests, where k, l are vertex counts of the two polygons. As far as I understand, this can be done quite quick with sweep line algorithm? –  Sydnic Dec 9 '12 at 15:32
    
That's correct:). It's also quite possible to integrate the first check into this sweep line algorithm easily, so that it requires only one pass. –  Lieven Dec 9 '12 at 16:15

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.