Boost logo

Geometry :

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

Geometry list run by mateusz at