Hi Bill, Was just wondering about the 'P[i].y > y0' : takin into account the numeric resolution problems inherent to MI, you're not sure that you'd obtain the 'bottom' of the polygon. There might be an extra (and costly) checking for this. I'm not sure about the way MB computes MBRs ... since they're used in the rendering process, they may well be calculated in another projection than the one used in the mbx, and then translated. Anyway, you're damn right not testing for equality, and even if one has to compute the MBR itself (or the bottom part of it), your code may be faster (replacing multiplications by comparisons).
The biggest point is about bowties : if there's a bowtie in the bottom part of the polygon your code gives a wrong result. Note that computing the signed area may lead to strange results too in this case ... it would just give an average drawing direction ! which can be thought as a graceful exception handling :^! Note too, that if bad luck strikes, a spike on the bottom point gives a sliver exception. Anyway anyone should check the topology of a file before attempting any geometric operation, as this is the best preservation against bad luck ! (and crashes) ;-) Have a nice day. Eric. Eric Maranne EMI Informatiques : www.geovrml.com (33)(+) 4 42 06 22 22 Port de Bouc - France : http://www3.calle.com/info.cgi?lat=43.4000&long=4.9833&name=Port%2dde%2dBouc &cty=France&alt=0 43? 23' 60N 4? 58' 60E Alt: 0 > -----Message d'origine----- > De : [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED]]De la part de Bill Huber > Envoye : mardi 22 janvier 2002 17:18 > A : [EMAIL PROTECTED] > Objet : 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.
