RE: [Algorithms] self intersecting polygons

[Laurent A. <lau...@su...>]

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