Testing whether a polygon is simple or complex

algorithm geometry polygon computational-geometry
Drew Noakes picture Drew Noakes · Oct 23, 2010 · Viewed 14.9k times · Source

For a polygon defined as a sequence of (x,y) points, how can I detect whether it is complex or not? A complex polygon has intersections with itself, as shown:

example complex polygon image

Is there a better solution than checking every pair which would have a time complexity of O(N2)?

Answer

Reed Copsey picture Reed Copsey · Oct 23, 2010

There are sweep methods which can determine this much faster than a brute force approach. In addition, they can be used to break a non-simple polygon into multiple simple polygons.

For details, see this article, in particular, this code to test for a simple polygon.

Related questions

An algorithm for inflating/deflating (offsetting, buffering) polygons

How would I "inflate" a polygon? That is, I want to do something similar to this: The requirement is that the new (inflated) polygon's edges/points are all at the same constant distance from the old (original) polygon's (on the …

Read More
How do I efficiently determine if a polygon is convex, non-convex or complex?

From the man page for XFillPolygon: If shape is Complex, the path may self-intersect. Note that contiguous coincident points in the path are not treated as self-intersection. If shape is Convex, for every pair of points inside the polygon, the …

Read More
Largest circle inside a non-convex polygon

How can I find the largest circle that can fit inside a concave polygon? A brute force algorithm is OK as long as it can handle polygons with ~50 vertices in real-time.

Read More