This is the kind of avenue that I was hoping to discover and that could be quicker than the mathematical algorithm.
I have an idea but I do not know how to safely implement it: given any two successive nodes, if the inside of the polygon is to the right of the vector, the direction is clockwise. If it is to the left, it is counter clockwise. How to find that? One possibility; find the mid point and create a point shifted by a tiny x or y in a given direction; find if it is within the original polygon. Assuming that the second point is not the tip of a spike, it should work. How tiny is tiny? The minimum should be probably of the order of 2 or 3 internal precision units to make sure that it will not snap back to the midpoint and that it will be on the proper side of the segment (the midpoint is a numeric expression that will be rounded up to the closest internal grid position if used directly). The maximum should theoretically depend on the minimum angle between successive segments, but the best is to stay as close to the minimum as possible. How does that strikes you? Any suggestions on its validity and implementation? Jacques Paris -----Original Message----- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]]On Behalf Of Bill Huber Sent: January 22, 2002 11:18 To: [EMAIL PROTECTED] Subject: RE: MI-L MB: polygon drawing direction. At 11:24 PM 1/21/02 +0100, Eric wrote: >The most common way is done thru dot products or (quite identical) signed >area : That's a great technique, but it's a lot of work to process large polygons because you have to do the arithmetic at every vertex. It strikes me that a task as conceptually simple as determining polygon orientation ought to require less computation. I found a way by cheating slightly. In systems that maintain minimum bounding rectangle (MBR) information--I believe MapInfo is one of them--there is a faster method. Loop over the vertices until you find one whose Y coordinate equals the minimum Y coordinate. This vertex is at the bottom of the polygon, so just check whether the polygon is being drawn left-to-right or right-to-left at this point to determine whether it is counterclockwise or clockwise, respectively. This works except when the vertex found is the tip of a zero-area sliver, which should not occur. On the average you have to check only half the vertices and the arithmetic is the fastest possible: a simple comparison of two numbers. Here are the details. Assuming the polygon is connected, it can be represented as an array P[0..N+1] of points where P[0] = P[N] and P[1] = P[N+1]. Let the known minimum Y coordinate obtained from the MBR be y0. Assuming there is a function Norm(p) = sqrt(p.x^2 + p.y^2) for the lengths of vectors, then the C-like pseudo-code is short and elegant: for (i=1; i <=N && P[i].y > y0; i++) {} e = P[i] - P[i-1] f = P[i+1] - P[i] return Norm(e)*f.x + Norm(f)*e.x > 0 /* If this expression is zero, there is a problem. */ This function returns true for counterclockwise polygons and false otherwise. It's easily implemented in MapBasic. A production program has to cope with invalid input. The "i<=N" part prevents endless looping if y0 is incorrect. After the loop, check for this condition with i==N+1. (If y0 is guaranteed correct, then removing the "i<=N" check could double the speed of the program.) If the expression "Norm(e)*f.x + Norm(f)*e.x" is zero, then P[i] is the tip of a zero-area sliver. Thus you can reliably detect many bad inputs and bullet-proof your code. It would be interesting to find a solution that is even more efficient than this one. Cheers, Bill Huber _______________________________________________________________________ List hosting provided by Directions Magazine | www.directionsmag.com | To unsubscribe, send e-mail to [EMAIL PROTECTED] and put "unsubscribe MapInfo-L" in the message body. _______________________________________________________________________ List hosting provided by Directions Magazine | www.directionsmag.com | To unsubscribe, send e-mail to [EMAIL PROTECTED] and put "unsubscribe MapInfo-L" in the message body.
