[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

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 ?


More information about the geos-devel mailing list