Geometry Boost List: [ggl] rtree query interface

Subject: [ggl] rtree query interface
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-09-18 07:10:52

Barend Gehrels wrote:
> What if we don't do this and just use the "filtered" adaptor defined by
> Boost.Range?
> t | filtered(within(g))
>
> The advantage is that AND, OR and NOT are much easier to handle (if
> people write their own predicate - but maybe Phoenix or Lambda can be of
> help here, didn't check this now).
>
> However, the basic requirement is that queries like this are using the
> spatial index. So I don't know how the filtered would use that index. I
> assume that "within" would do that (did you already did some work
> here?). So we indeed need "something which is a Boost.Range adaptor,
> uses the spatial index, and is capable to do user-defined queries at
> compile-time".
>
> We might consider adding a "spatially_filtered" adaptor which acts like
> this.

In order to be handled efficiently these predicates must be passed into 
the query algorithm. Then, different things are done for nodes and 
values (in the rtree). Different things will be done for rtree and for 
kdtree. But we may of course add our own adaptors and in fact this is 
what I've done.

> Outside is actually not (always) the same as ! within, because if a
> geometry partly intersects another, it is ! within and also ! disjoint.
> Outside might be renamed to "disjoint" here.

...

> Basically I like the idea of ! within(g), it is very readable.
>
> But it is, if I'm right, different from Boost.Range adaptors which
> cannot be negated like this. The Boost.Range adaptor overloads operator|
> to get its effect, you additionally need to overload operator! for a
> range adaptor as well. I didn't try but don't know if this is possible
> (probably it is).
>
> Besides that we have to be careful what is exactly the negation, see
> comment above.

The user is able to pass some number of predicates so will be able to 
describe what he want using predicates corresponding to ggl algorithms.

For now it's done by passing std::pair<Pred1, Pred2> or 
boost::tuple<Pred1, Pred2, ...> instead of single predicate to the range 
adaptor.

Currently there are 2 ways of inserting/removing elements to/from the 
rtree and 3 ways of querying:

namespace bgi = boost::geometry::index;

typedef std::pair<Box, int> val_t;

bgi::rtree<val_t, bgi::linear<32, 8> > tree;

Native interface:

// insert/remove

tree.insert(std::make_pair(Box(...), 0));
tree.remove(std::make_pair(Box(...), 0));

std::vector<val_t> result; // multiple results
val_t result_val;          // one result
size_t f = 0;              // number of results

// query

// this uses intersects()
f = tree.query(Box(...), std::back_inserter(result));
f = tree.query(bgi::intersects(Box()), std::back_inserter(result));
f = tree.query(bgi::within(Box()), std::back_inserter(result));
f = tree.query(bgi::overlaps(Box()), std::back_inserter(result));
f = tree.query(bgi::covered_by(Box()), std::back_inserter(result));

f = tree.query(
   boost::make_tuple(
     bgi::covered_by(Box())
   , bgi::intersects(Box())
   , bgi::overlaps(Box())
   )
, std::back_inserter(result));

// nearest

// nearest neighbor
f = tree.nearest(Point(...), result);
// nearest neighbor with predicates
f = tree.nearest(Point(...), bgi::within(Box()), result);
// k nearest neighbors
f = tree.nearest(Point(...), 10, std::back_inserter(result));
// k nearest neighbors with predicates
f = tree.nearest(Point(...), 10
        , bgi::within(Box()), std::back_inserter(result));

Function interface:

bgi::insert(tree, std::make_pair(Box(...), 0));
bgi::remove(tree, std::make_pair(Box(...), 0));

f = bgi::query(tree, Box(...), std::back_inserter(result));
//etc.

f = bgi::nearest(tree, Point(...), 10, std::back_inserter(result));
//etc.

Ranges interface:

tree | bgi::query_filtered(Box(...))
tree | bgi::query_filtered(bgi::within(Box()))

tree | bgi::nearest_filtered(Point(), 10, bgi::within(Box()))
tree | bgi::nearest_filtered(Point(), 10)

In the case of ranges, operator| returns bgi::query_filter<Index> or 
bgi::nearest_filter<Index> which wraps std::vector<val_t> and performs 
the query in the constructor.

Thoughts?

Source code in
https://svn.boost.org/svn/boost/sandbox-branches/geometry/index

Some tests may not work since I changed some names.

additional_sizes_and_times.cpp and additional_glut_vis.cpp works for 
sure. In order to use additional_sizes_and_times.cpp you should have 
config.txt file with at least 3 numbers e.g.

1000000 100000 100000

Regards,
Adam Wulkiewicz