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

[Martin Davis]

> 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)
- get JTS 1.5 out with the new CoordinateSequence support
- 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.

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
> >  
>