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

[Sean Gillies]

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.

-- 
Sean Gillies
Programmer
Institute for the Study of the Ancient World
New York University