Boost logo

Geometry :

Subject: [ggl] rtree query interface
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-08-22 12:48:37

feverzsj wrote:
> hi:
> 1. IIRC, ggl still miss functor interfaces for predicates to use with
> boost.range.
> something like:
> template<class G1>
> struct Predicator
> {
> G1 const& g1;
> Predicator(G1 const& g) : g1(g) {}
> template<class G2>
> bool operator()(G2 const& g2) const
> {
> return predicate(g1, g2);
> }
> };
> such functor may be used with both boost.range and rtee;
> 2. rtree may be consider as either an index structure or a boost.range:
> while using with some predicates(e.g.
> equals/intersects/overlaps/within), rtree works faster as an index
> structure;
> while using with other predicates, rtree may be just taken as a
> boost.range.
> so: "t | index::filtered(within(g))" and "t | filtered(within(g))" give
> the same result but the previous one could be much more faster.
> as for chained case,
> t | pred1() | pred2()| ... | predN()
> Will it return a new rtree for index::filtered()?
> Well, I think this could be less efficient for most use case, and not
> work well with those predicates that rtree not good at.
> I'd prefer simply return a sequential range at the first place.
> so :
> only the first "t | index::filtered(pred(g))" makes use of index
> facility. The followed adaptors will just deal with normal sequential
> range;

First of all I'd like to clarify. I'll be writing about the original
design of the query which probably will be changed. I wanted to use only
the syntax of Boost.Range to build a Query/Expression object containing
all predicates. This object would be passed to the rtree. So the line

tree | index::pred1() | index::pred2() | some_namespace::pred()

would compile and produce a range of objects returned by query filtered
by some_namespace::pred(). But

tree | some_namespace::pred() | index::pred1()

wouldn't even compile.

I now realize that this may be confusing since everybody thinks that
predicates works exactly like filters from Boost.Range but they
shouldn't. They should work more like Expressions.

About the new design...

Using filtered() seems reasonable but I don't know if we need 2 of them.
Type of a conteiner on the left of operator| should define the type of
query. filtered() should take an Basic Expression as a parameter and
return it inside a simple wrapper.
Next, for different containers/ranges this Basic Expression should be
transformed to the right form.
E.g. for Geometry.Index container the Basic Expression should be passed
to the container and transformed by the container. Rtree will transform
it to the different form than Kd-tree.
For stl-like containers Basic Expression will be transformed to the
different form, probably even wrapped inside a iterator of the resulting

Still, this may be confusing because filters will work differently for
different sequences.

t | filtered(Expr) | something()

will produce optimized query but

t | something() | filtered(Expr)

won't and this is probably not how the user thinks about ranges. I don't
even know if spatial index should expose iterators, begin(), end() etc.
and compile in the second case.

Because everybody thinks: "Oh! Boost.Ranges. I know how it works!" maby
it's better to use something else to distinguish between Geometry query
and ranges. Function or operator different than.

index::filtered(t, Expr) | other_filter()
index::query(t, Expr) | other_filter()
t[Expr] | other_filter()
t(Expr) | other_filter()
t >> query(Expr) | other_filter()

Still, there is a problem with operators - they may be defined already.
E.g. vect[Expr] | other_filter().


About the Expression in the next email.


Geometry list run by mateusz at