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

[David Blasby]

> 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