Geometry Boost List: [ggl] Re: rtree ?

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 
predicates:

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 
container.

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;

rtree<
   size_t,
   bgi::quadratic<32, 8>,
   MyTranslator>
 > 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.

Regards,
Adam