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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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/.