Detecting polygon self intersection

I’m looking for the algorithm that determines the fact that a polygon has self intersection or hasn’t. I’m not needed in calculation of the intersection points coordinates or how many intersection points there are.

Solutions Collecting From Web of "Detecting polygon self intersection"

There is the obvious algorithm of comparing all pairs of edges, which is $O(n^2)$ but probably is ok for small polygons. There is the Bentley–Ottmann algorithm sweep algorithm, which is $O(n \log n)$ but is harder to implement and probably only needed if $n$ is large. I think there is a $O(n)$ algorithm by Chazelle, which is very likely to be impractical.

In any case, note that you can test whether two line segments intersect without finding the intersection point. It’s a simple matter of comparing signs of a few determinants. See http://algs4.cs.princeton.edu/91primitives/.