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

[strk at refractions.net]

On Mon, Sep 20, 2004 at 03:18:19PM -0700, Martin Davis wrote:
> > 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.
> 
> Yes, I can see that, but I still think my original comment about indexed
> computation beating out O(n^2) for large geometries stands.  Of course,
> the key question is: what is the crossover point?  I'm doing some
> testing here which indicates that for JTS it's somewhere around 500
> vertices (A x B).  I can imagine that lots of PostGIS applications
> rarely hit that threshold.
> 
> So what can be done?  Well, one approach I'm thinking of is to have two
> implementations of key functions like intersects.  One will be a
> scanning implementation short-circuited to within an inch of its life.
> The other will be the existing indexed, full DE-9IM code.  The client
> (e.g PostGIS) will be able to set the crossover threshold.
> 
> There's two nice things about this:  
> - it's quite a bit easier to develop the code for scanning,
> limited-scope methods
> - the scanning method has the very nice property of not requiring
> conversion to JTS geometries (when built using the improved
> CoordinateSequence API coming in JTS 1.5).  This should make it faster
> still.
> 
> Here's a plan of action for making this happen:
> - profile PostGIS and find out where the GEOS hotspots are (or more
> likely, what kinds of datasets produce slowdowns)

I can add profiling support in postgis CVS (LWGEOM).
I imagine NOTICE messages reporting times of POSTGIS->GEOS,
GEOSrun and GEOS->POSTGIS.

> - get JTS 1.5 out with the new CoordinateSequence support

Good luck :)

> - decide to goahead with the "crossover" approach for some functions
> (such as predicates)
> - prototype to see how much difference it makes
> - implement, if it all checks out.

Good stuff...
--strk;

> 
> 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
> 
> 
> > -----Original Message-----
> > From: strk at refractions.net [mailto:strk at refractions.net] 
> > Sent: September 18, 2004 12:19 AM
> > To: Martin Davis
> > Cc: GEOS Development List; pramsey at refractions.net; 
> > postgis-devel at postgis.refractions.net
> > Subject: Re: PostGIS distance() faster than GEOS intersects() ?
> > 
> > 
> > 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
> > >  
> > 
> _______________________________________________
> geos-devel mailing list
> geos-devel at geos.refractions.net
> http://geos.refractions.net/mailman/listinfo/geos-devel