6
$\begingroup$

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.

  • 0
    @anorton: floats. Sharing edge could mean no-overlapping2012-12-09

1 Answers 1

6

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.

  • 0
    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.2012-12-09