RE: [Algorithms] self intersecting polygons
Brought to you by:
vexxed72
|
From: Laurent A. <lau...@su...> - 2006-03-13 20:17:48
|
Except for the "self spiraling" polygon, you can simply check if it is convex. And you can detect this special case by summing all dot products results, but you'll have to normalize each edge vector, though this can = be precomputed. This is a simple and fast way to be sure it isn't, but it will miss all concave non intersecting polygons. Laurent -----Message d'origine----- De=A0: gda...@li... [mailto:gda...@li...] De la part de = Nils Pipenbrinck Envoy=E9=A0: lundi 13 mars 2006 21:08 =C0=A0: gda...@li... Objet=A0: [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=3Dlnk&kid=3D110944&bid=3D241720&dat=3D= 121642 _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 |