[geos-devel] use of STRtree functions in C API

Martin Davis mbdavis at refractions.net
Mon May 10 12:13:13 EDT 2010


Yes, spatial indexing only pays off when you run many queries against 
the index.

This is the case when processing all interacting pairs from two lists of 
geometries, however.  The index takes this from O(n^2) to O(n log n) 
(roughly).

Sean Gillies wrote:
> Hi everybody,
>
> On Tue, May 4, 2010 at 5:54 PM, Martin Davis <mbdavis at refractions.net> wrote:
>   
>> Howard Butler wrote:
>>     
>>>       
>>>> I need GEOS for Touches/Disjoint (topology operations) anyway, so extra
>>>> dependencies are not a help, rather the opposite.
>>>>
>>>>         
>>> Indexing is orthogonal to GEOS main geometry algebra operations, IMO.  I
>>> don't like that we expose internal indexing stuff publicly because it will
>>> limit the library's options to do something different in the future.  That
>>> it uses an index to do things internally for things like prepared geometry
>>> is an implementation detail.  Small pieces, loosely joined, not giant
>>> monoliths (/me stares in GDAL's
>>> embedding-every-library-in-the-entire-osgis-ecosystem's direction).  I
>>> understand the desire to not have extra dependencies, but if you want a
>>> general, programmable rtree, GEOS' isn't it at this time.
>>>
>>> To the GEOS devs, is GEOS to be an indexing library too?
>>>
>>>       
>> Sure, why not?  At least for in-memory indexes - there are no plans to
>> extend this to disk-based indexes.
>>
>> Reasons are:
>> i) The code is there and well-tested
>> ii) The index is designed to work well with GEOS objects (although as you
>> point out, indexes are fairly independent)
>> iii) This reduces the need for dependencies on other librarries (as I think
>> you have just recommended)
>>
>> Of course as you say this exposes an interface which will need to be
>> maintained in the future.  But there's a fairly low cost to maintaining the
>> simple indexes currently provided (and there are no current plans to stop
>> using them in GEOS itself).
>>
>>     
>>>> All I need is to identify which bounding boxes (envelopes in GEOM-speak)
>>>> intersect for a fixed set of objects whose bounding boxes I can compute, and
>>>> where GEOS is already present and running.
>>>>
>>>>         
>>> Doesn't GEOS' prepared geometry stuff already do this, or is that not
>>> sufficient?  Maybe I don't understand the problem well enough.
>>>
>>>       
>> PreparedGeometry optimizes the computation between two individual
>> geometries, but it doesn't optimize the situation of processing two sets of
>> geometries in pairwise fashion.  For that you need a spatial index.
>>
>>     
>
> I've done a bit of benchmarking using Rtree (libspatialindex) and
> Shapely (GEOS) and am finding that using a spatial index to select
> candidates for intersects() and within() isn't as big a win as I had
> expected. The GEOS predicates short-circuit when the bounding boxes of
> the features don't intersect
>
> http://trac.osgeo.org/geos/browser/trunk/src/operation/relate/RelateComputer.cpp#L67
>
> Testing the bounds is O(N) (N being number of vertexes) and so the
> cost of evaluating intersects() for unrelated features that would be
> excluded by an index search is dwarfed by the cost of evaluating
> intersects() for complicated related features (about O(N log N) yes?).
> I'm finding 2X faster queries when using a spatial index in
> combination with intersects() for small (radius 0.01, N=64) polygons
> related to a large (radius 1.0, N=64) polygon in a 10.0 x 10.0 space.
> Faster, yes, but not justifying the creation of a spatial index for
> one search.
>
>   

-- 
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022



More information about the geos-devel mailing list