Boost logo

Geometry :

Subject: [ggl] Re: rtree ?
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-11-27 08:25:20

Bernhard wrote:
> Adam Wulkiewicz wrote
>> Of course, I'm planning to do it. But first, I'd like to hear from you
>> all, do you like the interface? Maby something should be added or changed?
> Hi Adam,
> I have to admit I don't fully understand your interface. The only example I
> could find is the additional_sizes_and_times.cpp in the tests directory.
> The rtree class provides one query method, which has a Predicates type as
> the first parameter. In additional... some predicates are used and I
> understand that. However, there is also query(intersects(B)) searching time
> test, which has a box as the first parameter. I don't understand why it
> compiles (how is Box a predicate?) and what it does - although I admit it is
> more of a curiosity question as I think I can achieve what I want with the
> given predicates.

Box is a default case and it works just like intersects(Box).

index::intersects(Box) is a function generating object of type
index::detail::intersects<Box>. Internally there is
predicate_check<Predicate, ...>::apply(Predicate const& p, ...) checking
if some value should be returned by the query. Default predicate_check
as well as specialized for index::detail::intersects<Box>, both calls
geometry::intersects(Box, ...).

Other predicates:

intersects, disjoint, covered_by, overlaps, within

In addition you may pass negated predicates. As well as some number of

std::make_pair(intersects(B1), !within(B2))

It works for boost::tuple too.

And there is value(some_fun) predicate where you may pass
function/functor some_fun. It must take one parameter of type Value and
return bool. True if current value should be returned.

> I have one other question. Is it possible to iterate over every item in the
> rtree (without knowing their position, i.e. giving an appropriately large
> bounding box)? Unfortunately I need to do that in the project I'm working
> on.

There is no iterator in the rtree and it possibly won't be any. You may
return all of the elements which are in rtree's Box, but this query will
traverse all nodes and copy all elements to some container, which is ok
if you do it rarely.

Some other possibilities:

1. You may store 2 copies of objects. One in rtree, second in some other

2. You may e.g. store your objects in std::vector and std::pair<Box,
Index> in the rtree. Assuming you won't be erasing some random objects
to not mess with indexes.

3. Another possibility is to use vector to store objects, pass indexes
as Values in the rtree and
index::translator::index<std::vector<MyObject> > as rtree's Translator:

using namespace boost::geometry::index;

typedef translator::index< std::vector<MyObject> > MyTranslator;

   bgi::quadratic<32, 8>,
> r(MyTranslator(my_vector));

4. You may store objects in some container which preserves iterators and
use pointers/iterators as rtree's Values.

It all depends on what do you want to do with your objects and how often.


Geometry list run by mateusz at