[geos-devel] Why many calls to signOfDet2x2 and addIntersections

Martin Davis mbdavis at VividSolutions.com
Wed Nov 20 15:28:03 EST 2002


My mistake - isCCW only calls signOfDet2x2 ONCE per ring.  (JTS does use an algorithm like the one you mention, Dave.)

Almost all signOfDet2x2 calls are due to the segment intersections tests in computeSelfNodes, I believe.

Martin Davis, Senior Technical Specialist
Vivid Solutions Inc.
Suite #1A-2328 Government Street   Victoria, B.C.   V8T 5G5
Phone: (250) 385 6040    Fax: (250) 385 6046
EMail: mbdavis at vividsolutions.com  Web: www.vividsolutions.com


> -----Original Message-----
> From: David Blasby [mailto:dblasby at refractions.net]
> Sent: Wednesday, November 20, 2002 11:50 AM
> To: GEOS Development List
> Subject: Re: [geos-devel] Why many calls to signOfDet2x2 and
> addIntersections
> 
> 
> > In particular:
> > - isCCW is called on each ring - which calls signOfDet2x2 n 
> times (for each pair of consecutive line segments)
> 
> You should be able to do this with only 1 signOfDet2x2.
> 
> (a)    Find the point with the highest Y value.
> (b)    Form a  triangle from the  point before and the point after
> 
>     There are two cases:
> 
>                                             Pn
>                       Pn+1                                   Pn-1
> 
> or
> 
>                                           Pn
>                    Pn-1                                      Pn+1
> 
> 
> You can find if its a left or right turn robustly using signOfDet2x2.
> 
> There is one gotcha - if Pn-1, Pn, Pn+1 all have the same Y 
> value.  This is easy to find - there are no robustness 
> problems (just use "=").  If
>          Pn-1.getY() = Pn.getY() use Pn-2 instead  (you might 
> have to try n-3, etc).
> 
> This back tracking is O(n),  but the whole algorthm is O(n) 
> anyways (to find the Maximum Y value).
> 
> This should be way faster than O(n) signOfDet2x2 computations.
> 
> I havent convinced myself that this backtracking will allways 
> work, but you could always go back to the slow solution in this case.
> 
> Comments,
> 
> dave
> 
> 
> _______________________________________________
> geos-devel mailing list
> geos-devel at geos.refractions.net
> http://geos.refractions.net/mailman/listinfo/geos-devel
> 



More information about the geos-devel mailing list