Re: [Algorithms] self intersecting polygons

[Jonathan B. <jo...@nu...>]

It is pretty easy to concoct examples that would convince you an O(n) 
algorithm is impossible.

For example, take a square, remove the top edge, and replace it with a V 
that stabs through the bottom edge, so that now you have a 
self-intersecting polygon.  From looking at this, you might think 
there's an O(n) solution.

Now take that region where the V stabs through the bottom, remove part 
of the bottom edge, and replace it with 100000000 edge segments that 
bend this way and that in a fractal-ish way, such that maybe they now 
enclose the whole V, or maybe not -- how do you know without searching 
through them?  You can perturb this case so that just one tiny piece of 
this convoluted edge mess crosses the V, or not, changing the desired 
result of the algorithm.  And it can cross, or not, by epsilon.

In order to achieve O(n), you would need to test each input edge against 
a constant-time summary of what has come before, but no summary that 
simple can differentiate between the perturbation of that one tiny piece 
by epsilon or not. 



Nils Pipenbrinck wrote:
> I googled half a day to find a simple answer to this question:
>
> "How do I detect if a polygon (n-gon) is self intersecting or not".
>
> The obvious solution would be to search for edge intersections. This 
> has O(n*log(n)) complexity when doing plane/line sweep.
>
> Does a O(n) algorithm exist? and if so, which?
>
> Thanks,
>  Nils
>
> (btw, poly-tesselation is fun!)
>
>
>
>
> -------------------------------------------------------
> This SF.Net email is sponsored by xPML, a groundbreaking scripting 
> language
> that extends applications into web and mobile media. Attend the live 
> webcast
> and join the prime developer group breaking into this new coding 
> territory!
> http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_id=6188
>