Testing whether a polygon is simple or complex

Question

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²)?

Answer 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.