RE: [Algorithms] self intersecting polygons

[Tom F. <tom...@ee...>]

Rasterise into an arbitrarily-large 2d framebuffer. It's O(n) where n is the
number of lines, but probably not in a way that is very practical :-)

TomF.

> -----Original Message-----
> From: gda...@li... 
> [mailto:gda...@li...] On 
> Behalf Of Nils Pipenbrinck
> Sent: 13 March 2006 12:08
> To: gda...@li...
> Subject: [Algorithms] self intersecting polygons
> 
> 
> 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