[geos-devel] isOnLine optimizations

[strk at refractions.net]

On Fri, Jun 24, 2005 at 11:26:52AM +0200, strk at refractions.net wrote:
> 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.

Tried this, time for my example union (20 world countries incremental
union) goes from 1m6sec to 1m0sec (93%, not much).

--strk;

> 
> 	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;
> _______________________________________________
> geos-devel mailing list
> geos-devel at geos.refractions.net
> http://geos.refractions.net/mailman/listinfo/geos-devel