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.

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

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.

  • $\begingroup$ 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? $\endgroup$ – Sydnic Dec 9 '12 at 15:32
  • $\begingroup$ 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. $\endgroup$ – Lieven Dec 9 '12 at 16:15

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.