[Math] Concave polygons overlapping test

algorithmsgeometrypolygons

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.

Best Answer

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.

Related Question