Concave polygons overlapping test

Question

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.

Answer 1

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.