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

<p>If you only need to find out if self-intersections exist, or find a small amount of them, then look <a href="http://arxiv.org/abs/0812.0893v2" rel="nofollow">here</a>. 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.</p>
How to detect if a polygon has self-intersections?
<p>Imagine you have a 2D polygon (a 2D <a href="http://en.wikipedia.org/wiki/Polygonal_chain" rel="noreferrer">closed polygonal chain</a> to be more precise). How do you check if it contains self-intersections? It can be convex or concave, oriented clockwise or counter-clockwise.</p>

<p>Now, I could just run a standard <code>O(N log N)</code> 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 <code>O(N)</code>?) algorithm could be devised.</p>

<p>Any ideas?</p>