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.
