RE: [Algorithms] self intersecting polygons

[Conor S. <bor...@ya...>]

Or you could reduce "rasterise" to "hash" of course in
some kind of 2 phase approach.  

Wheel officially reinvented.

Cheers,
Conor

--- Tom Forsyth <tom...@ee...>
wrote:

> 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
> 
> 
> 
>
-------------------------------------------------------
> 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
> 


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com