# Concave polygons overlapping test

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.

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

-
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