[geos-devel] isOnLine optimizations
strk at refractions.net
strk at refractions.net
Fri Jun 24 05:26:52 EDT 2005
I've been profiling Union operations.
It seems the most time-spending function
is Envelope::intersects() called by LineIntersector::computeIntersection()
called by CGAlgorithms::isOnLine for every segment of a given
CoordinateSequence.
I think we can optimize this in two ways:
1) easier, quicker: LineIntersector::hasIntersection(p1, p2, q)
so to avoid Z computation and properVar.
2) descend the input CoordinateSequence in a binary
fashion and checking Envelope intersection of the
section. Keep descending until a intersecting segment
is found.
For point (2) we might be able to use one of the existing indexes
but I'm not sure how much overhead we would be adding with that.
What do you think ?
--strk;
More information about the geos-devel
mailing list