Testing whether a polygon is simple or complex

问题:

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:

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

回答1:

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.

回答2:

See Bentley Ottmann Algorithm for a sweep based O((N + I)log N) method for this. Where N is the number of line segments and I is number of intersection points.

回答3:

In fact, this can be done in linear time use Chazelle's triangulation algorithm. It either triangulates the polygon or find out the polygon is not simple.