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.
Detecting polygon self intersection
13
$\begingroup$
geometry
algorithms
-
0Posssible duplicate of http://math.stackexchange.com/questions/52733/equation-to-check-if-a-set-of-vertices-form-a-real-polygon – 2011-11-10
2 Answers
10
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/.