Boost logo

Geometry :

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

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(
   , 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));

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

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.


Source code in

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

Adam Wulkiewicz

Geometry list run by mateusz at