How to detect if a polygon has self-intersections?

Question

Imagine you have a 2D polygon (a 2D closed polygonal chain to be more precise). How do you check if it contains self-intersections? It can be convex or concave, oriented clockwise or counter-clockwise.

Now, I could just run a standard O(N log N) algorithm to check if any two segments cross. But I believe that because we have some additional structure -- the order of the segments and the fact that each two consecutive segments meet at endpoints -- a simpler and faster (maybe O(N)?) algorithm could be devised.

Any ideas?

Answer 1

Do you need just to check for self-intersections, or find all of them? The latter is harder than O(N log N), as you can have O(n^2) intersections with n segments.

If you only need to find out if self-intersections exist, or find a small amount of them, then look here. This paper seems to claim just what you need, particularly in the polygon planarization section. I doubt implementing the algorithm described there would be simple, or worthwhile for any problem of reasonable size. But such an algorithm does exist. Disclaimer: I haven't tried to work through the paper and understand it.