Geometry Boost List: [ggl] rtree query expression

Subject: [ggl] rtree query expression
From: Barend Gehrels (barend)
Date: 2011-08-28 23:43:45

Hi Adam, Luke, list,

Thanks for the discussion. I was a bit behind and this discussion is 
quite extended. I'll try to answer per subject.

>
> Another issue is that there may be some algorithms inside 
> Boost.Geometry which may be using spatial indexes. Maby we should 
> design some spatial_index concept (which is partially done) because 
> the user may want to adapt his own spatial index and use it inside 
> this algorithm. What do you think about this Barend? Do you expect 
> something like this to be created? If so, then maby the interface 
> should be even simpler because user-defined index may not implement 
> predicates or implement some types of queries.

Originally it was indeed the intention that Boost.Geometry could use the 
spatial index internally. And I think it is good to keep the possibility 
open. But at this moment we don't have an immediate need for it. We're 
using, internally, two kinds of "spatial indexing" now, which are both 
not really spatial indexes:
- monotonic sections
- partitioning.

The first is a small helper structure which is built in linear time and 
which helps to avoid doing operations in disjoint sections.
The second is described earlier on the list (I started a blog about this 
but did not (yet) finish it, maybe it will come once). It greatly helps, 
and can easily (and generic) speed up the speed from quadratic to 
logarithmic. It does not built up an index but handles the algorithm 
immediately. It can be used together with the monotonic sections

Especially because of the partitioning, I don't expect a spatial index 
will speed up the process further.

But of course it is good to use a  concept-based design for the 
spatial_index. If it is partially done (good), it should IMO be extended 
to fully. ;-)

Regards, Barend