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

[Norman Vine]

Martin Davis writes:

> Just for grins, I disabled the self-intersection check and reran the SineStarX2 test.  
> Times are below - they are up to 10 times faster!

Ah  this is more like what I was expecting

>  Currently JTS just checks *everything* for self-intersections.  
> Since many cases involve only polygons without holes, being a bit smarter about 
> what gets checked could produce a substantial performance improvement.

FWIW IMHO trivial rejection tests and caching computations for reuse
are almost *allways* worth the time it takes 

cheers

norman

==========

    bool RobustCGAlgorithms::isPointInRing(Coordinate p,CoordinateList ring)
    {
        int crossings=0;    // number of segment/ray crossings
        int nPts=ring.getSize();
            /*
             *  For each segment l = (i-1, i),
             *  see if it crosses ray from test point in positive x direction.
             */
        double x1=ring.getAt(0).x-p.x;
        double y1=ring.getAt(0).y-p.y;
        for (int i=1;i<nPts;i++) {
            double x2 = x1;
            double y2 = y1;
            x1=ring.getAt(i).x-p.x;
            y1=ring.getAt(i).y-p.y;
            if (((y1>0) && (y2<=0)) || ((y2>0) && (y1<=0))) {
                    /*
                     *  segment straddles x axis, so compute intersection.
                     *  crosses ray if strictly positive intersection.
                     */
                if ( RobustDeterminant::signOfDet2x2(x1,y1,x2,y2)/(y2-y1)  >  0.0 ) {
                    crossings++;
                }
            }
        }
            /*
             *  p is inside if number of crossings is odd.
             */
        if ((crossings%2)==1) {
            return true;
        } else {
            return false;
        }
    }