[geos-devel] PostGIS distance() faster than GEOS intersects() ?

Martin Davis mbdavis at VividSolutions.com
Fri Sep 17 15:29:18 EDT 2004

I keep hearing that people find that using the PostGIS distance function
is faster than using the GEOS intersects() function.  Does anyone know
why this is?  My understanding of the PostGIS distance function is that
it's a simple scan of all linesegments, which is O(n^2).  The GEOS code
should be able to do better than this. Of course, likely there's some
overhead in the conversion to GEOS - perhaps that's the source of the
problem (for small to medium geometries, anyway).
Is this still the case for REALLY big geometries?  If it really is just
an copying overhead thing, I would expect the difference to decrease as
the input size gets bigger (copying is O(n), which will get swamped by
O(n^2) at some point).
I'm just asking because I'm curious if there's anything that can be done
to speed up GEOS (both for PostGIS and in general).
Also, if distance is used heavily I wonder whether it's worth spending
some time optimizing the computation using indexing techniques?
Martin Davis, Senior Technical Architect
Vivid Solutions Inc.      www.vividsolutions.com
Suite #1A-2328 Government Street Victoria, B.C. V8T 5G5
Phone: (250) 385 6040 - Local 308 Fax: (250) 385 6046
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/geos-devel/attachments/20040917/addba646/attachment.html

More information about the geos-devel mailing list