[OSM-dev] Algorithm help

[Nathan Vander Wilt]

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/dev/attachments/20080528/1441de11/attachment.html>