Check if Polygon is Self-Intersecting

Question

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 1

• Easy, slow, low memory footprint: compare each segment against all others and check for intersections. Complexity O(n²).

• Slightly faster, medium memory footprint (modified version of above): store edges in spatial "buckets", then perform above algorithm on per-bucket basis. Complexity O(n² / 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.

Answer 2

Check if any pair of non-contiguous line segments intersects.

Answer 3

For the sake of completeness i add another algorithm to this discussion.

Assuming the reader knows about axis aligned bounding boxes(Google it if not) It can be very efficient to quickly find pairs of edges that have theirs AABB's clashing using the "Sweep and Prune Algorithm". (google it). Intersection routines are then called on these pairs.

The advantage here is that you may even intersect a non straight edge(circles and splines) and the approach is more general albeit almost similarly efficient.