Testing whether a polygon is simple or complex

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.

Answer 2

See Bentley Ottmann Algorithm for a sweep based O(N log N) method for this.