Is there an easy and fast way of checking if a polygon is self-intersecting?

GWLlosa picture GWLlosa · Feb 2, 2011 · Viewed 19.1k times · Source

I have a System.Windows.Shapes.Polygon object, whose layout is determined completely by a series of points. I need to determine if this polygon is self-intersecting, i.e., if any of the sides of the polygon intersect any of the other sides at a point which is not a vertex.

Is there an easy/fast way to compute this?

Answer

Daniel Gehriger picture Daniel Gehriger · Feb 2, 2011
  • Easy, slow, low memory footprint: compare each segment against all others and check for intersections. Complexity O(n2).

  • Slightly faster, medium memory footprint (modified version of above): store edges in spatial "buckets", then perform above algorithm on per-bucket basis. Complexity O(n2 / m) for m buckets (assuming uniform distribution).

  • Fast & high memory footprint: use a spatial hash function to split edges into buckets. Check for collisions. Complexity O(n).

  • Fast & low memory footprint: use a sweep-line algorithm, such as the one described here (or here). Complexity O(n log n)

The last is my favorite as it has good speed - memory balance, especially the Bentley-Ottmann algorithm. Implementation isn't too complicated either.