[geos-devel] Profiling results

[Norman Vine]

Hi all,

While looking into why all the calls to signOfDet2x2()
I experimented with an early out mechanism in
RobustLineIntersector::computeIntersect(...)

I think that computeIntersect() is still 'correct'
but would appreciate comments as to otherwise
 < see below >

following results from a 2,000,000 point test
< note new functions indexOfMaxY() and getMinMax2() 
  are simple scans of the CoordinateList that 
  reflect the time to traverse the List >

Cheers

Norman

< before >
 81.21      6.31     6.31 28704650     0.00     0.00  RobustDeterminant::signOfDet2x2(double&, double&, double&, double&)
 10.17      7.10     0.79 10352339     0.00     0.00  SegmentIntersector::addIntersections(Edge*, int, Edge*, int)
  3.73      7.39     0.29        1     0.29     0.29  GeometryTestFactory::createSineStar(double, double, double, double, int, int)
  2.83      7.61     0.22        2     0.11     0.11  CoordinateList::getMinMax2D(double*, double*, double*, double*)
  1.16      7.70     0.09        2     0.04     0.04  CoordinateList::indexOfMaxY()
  0.26      7.72     0.02        2     0.01     0.02  LineString::LineString(CoordinateList, PrecisionModel, int)
  0.13      7.73     0.01       19     0.00     0.00  PrecisionModel::PrecisionModel(PrecisionModel const&)
  0.13      7.74     0.01        2     0.01     0.01  LineString::isClosed()
  0.13      7.75     0.01        2     0.01     0.01  PlanarGraph::insertEdge(Edge*)
  0.13      7.76     0.01        2     0.01     0.01  CoordinateList::hasNullElement()
  0.13      7.77     0.01        2     0.01     0.01  EdgeIntersectionList::EdgeIntersectionList(Edge*)

< after >
 66.92      1.78     1.78 17999884     0.00     0.00  RobustDeterminant::signOfDet2x2(double&, double&, double&, double&)
 12.41      2.11     0.33        1     0.33     0.33  GeometryTestFactory::createSineStar(double, double, double, double, int, int)
  9.77      2.37     0.26 10352339     0.00     0.00  SegmentIntersector::addIntersections(Edge*, int, Edge*, int)
  4.89      2.50     0.13        2     0.07     0.07  CoordinateList::getMinMax2D(double*, double*, double*, double*)
  3.38      2.59     0.09        2     0.04     0.04  CoordinateList::indexOfMaxY()
  0.75      2.61     0.02        2     0.01     0.01  LineString::LineString(CoordinateList, PrecisionModel, int)
  0.38      2.62     0.01        6     0.00     0.00  RobustCGAlgorithms::RobustCGAlgorithms()
  0.38      2.63     0.01        2     0.01     0.01  LineString::isClosed()
  0.38      2.64     0.01        2     0.01     0.05  GeometryGraph::addPolygonRing(LinearRing*, int, int)
  0.38      2.65     0.01        2     0.01     0.01  CoordinateList::hasNullElement()
  0.38      2.66     0.01                             _GLOBAL__I__ZN18GeometryCollectionC2Ev


    int RobustLineIntersector::computeIntersect(Coordinate p1,Coordinate p2,
    Coordinate q1,Coordinate q2)
    {
        isProperVar=false;
 
            /**
             * for each endpoint,compute which side of the other
             * segment it lies, if both endpoints lie on the same side 
             * of the other segment,the segments do not intersect
             */

 // But first lets try a trivial reject
 double minq = min(q1.x, q2.x);
 double maxq = max(q1.x, q2.x);
 double minp = min(p1.x, p2.x);
 double maxp = max(p1.x, p2.x);

 if( minp > maxq )
     return DONT_INTERSECT;
 if( maxp < minq )
     return DONT_INTERSECT;
       
 minq = min(q1.y, q2.y);
 maxq = max(q1.y, q2.y);
 minp = min(p1.y, p2.y);
 maxp = max(p1.y, p2.y);

 if( minp > maxq )
     return DONT_INTERSECT;
 if( maxp < minq )
     return DONT_INTERSECT;

        int Pq1=RobustCGAlgorithms::orientationIndex(p1,p2,q1);
        int Pq2=RobustCGAlgorithms::orientationIndex(p1,p2,q2);
                
        if ((Pq1>0 && Pq2>0) || (Pq1<0 && Pq2<0)) {
     return DONT_INTERSECT;
        }
                
        int Qp1=RobustCGAlgorithms::orientationIndex(q1,q2,p1);
        int Qp2=RobustCGAlgorithms::orientationIndex(q1,q2,p2);
 
        if ((Qp1>0 && Qp2>0) || (Qp1<0 && Qp2<0)) {
            return DONT_INTERSECT;
        }
            // if collinear
        if ((Pq1==0) && (Pq2==0) && (Qp1==0) && (Qp2==0)) {
            return computeCollinearIntersection(p1,p2,q1,q2);
        }
            /**
             *  Check if the intersection is an endpoint.
             *  If it is,copy the endpoint as the intersection point.
             *  Copying the point rather than computing it ensures the
             *  point has the exact value, which is important for
             *  robustness.  It is sufficient to simply check for an
             *  endpoint which is on the other line,since at this point
             *  we know that the inputLines must intersect.
             */
        if ((Pq1==0) || (Pq2==0) || (Qp1==0) || (Qp2==0)) {
            isProperVar=false;
            if (Pq1==0) {
                intPt[0].setCoordinate(q1);
            }
            if (Pq2==0) {
                intPt[0].setCoordinate(q2);
            }
            if (Qp1==0) {
                intPt[0].setCoordinate(p1);
            }
            if (Qp2==0) {
                intPt[0].setCoordinate(p2);
            }
        } else {
            isProperVar=true;
            intPt[0].setCoordinate(intersection(p1,p2,q1,q2));
        }
        return DO_INTERSECT;
    }