[postgis-devel] Re: PostGIS distance() faster than GEOS intersects() ?

[strk at refractions.net]

The 'distance' function of postGIS returns as soon as it detects
a 0-distance (because it returns the 'minimum distance'), while GEOS
intersects() compute the full intersection matrix before returning.

So intersecting geometries distance will be computed faster by PostGIS 
the by GEOS.

On the other hand non-intersecting geometries will require full
distance to be computed by PostGIS, and will this will be slower
then GEOS.

Possible GEOS speedup would be (IMHO) separating computation of the
DE-9 Intersection Matrix. Full computation should continue to
be available for users willing to check multiple properties, but
cell-specific functions could return sooner.

--strk;

On Fri, Sep 17, 2004 at 12:29:18PM -0700, Martin Davis wrote:
> 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
>