On May 28, 2008, at 1:35 PM, Richard Duivenvoorde wrote:
Richard Fairhurst wrote:
Can anybody point me in the direction of an algorithm that will
determine whether a closed way (polyline) is clockwise or anti-
clockwise?
Richard,
there is a good set of (explanations of) algorithms here:
http://www.faqs.org/faqs/graphics/algorithms-faq/
If you can treat the earth as a cartesian plane 360 units wide by 180
tall these equations could be used. But be careful here. Lat/lon
coordinates actually are based on a more complicated topology. A
spherical polygon always encloses a finite area less than the surface
area, so the usual method of "checking for negative area" doesn't work
out so well.
If you are trying to catch "inside-out" polygons on a true spherical
surface, you may be better off sanity checking the area enclosed by
the polygon. If this is greater than a hemisphere (or even a lower
threshold might be appropriate for most edits, such as the visible
area while editing), then it's probably wound against convention.
http://mathworld.wolfram.com/SphericalPolygon.html has a simple
formula, but it requires finding the angle at each vertex which is
often not so simple.
"Computing the Area of a Spherical Polygon" by Robert D. Miller
(published in Graphics Gems IV, pp. 132ff) has a method more
analogous to the typical cartesian algorithm. The GG IV implementation
(in C, IIRC) is widely available, and you may even be able to read the
paper in Google books if you search well.
That said, I'm guessing there are other assumptions being made within
OSM that break down under spherical geometry. If your polygon doesn't
contain pole(s) or cross the +/-180 degree meridian, checking the
winding could be handled by a cartesian algorithm.
hope this helps,
-natevw
_______________________________________________
dev mailing list
dev@openstreetmap.org
http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/dev
