FW: [geos-devel] Profiling results
Martin Davis
mbdavis at VividSolutions.com
Wed Nov 20 14:01:24 EST 2002
Norman, your added tests in LineIntersector are indeed correct. The reason we didn't implement them in RobustLineIntersector in the first place is that we almost always only call computeIntersect once other code has determined that the line segments have a high probability of having their envelopes overlap (that's the function of the sweepline index and the monotone chains, for instance).
It probably doesn't hurt a whole bunch to add these tests in, but it might be nice to provide two separate functions in the LineInteresector API, to avoid the overhead if you are pretty sure the lines' envelopes intersect.
I'm pretty mystified as to why the LineIntersection code is called so many times. The indexing is supposed to prevent this. Are you sure you haven't disable indexing in some way?
Yury, are you getting the same results as Norman for the number of calls to computeIntersect() ?
I guess we should instrument the Java code and see if its numbers compare. I'll take a look at doing this.
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: Norman Vine [mailto:nhv at cape.com]
> Sent: Wednesday, November 20, 2002 10:52 AM
> To: GEOS Development List
> Subject: [geos-devel] Profiling results
>
>
> 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;
> }
>
>
>
>
> _______________________________________________
> 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