How to determine if a polygon has a self-intersection?

Question

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

Now I could run the standard O(N log N) algorithm to check if any two segments intersect. But I believe that since we have an additional structure — the order of the segments and the fact that each two consecutive segments meet at the end points — a simpler and faster (possibly O(N) ?) Algorithm can be developed.

Any ideas?

Answer 1

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

If you only need to find out if there are self-intersections or to find a small number of them, then look here . This article seems to require only what you need, especially in the planarization section of the polygon. I doubt that the described algorithm will be simple or appropriate for any problem of a reasonable size. But such an algorithm exists. Disclaimer: I did not try to work on the document and understand it.