Re: [Algorithms] self intersecting polygons
Brought to you by:
vexxed72
Menu
▾
▴
Re: [Algorithms] self intersecting polygons
|
From: Ray G. <ra...@da...> - 2006-03-14 08:14:28
|
Hmm... over many polygons, on average it might be O(n/2), because you can short out the moment a pixel rasterizes on top of a previously plotted one. A quick hint-assist would also be to calc the largest interior bbox enclosed by the poly, and hit test with that first. On average, if it's immediately hit half the time... Ray Tom Forsyth 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 > > |
