Geometry Boost List: [ggl] rtree query interface

Subject: [ggl] rtree query interface
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-10-04 09:17:20

Mateusz Loskot wrote:
> On 28/09/11 12:16, Adam Wulkiewicz wrote:
>> Another small improvement. User may now pass a value predicate and add
>> values to the result only if they pass the test. It takes less time than
>> e.g. searching for all values in some region and then testing them.
>>
>> bool user_pred(Value const& v) { /* some condition */ }
>>
>> std::vector<Value> result;
>>
>> t.query(
>> std::make_pair(
>> Box(...),
>> bgi::value(user_pred)
>> ),
>> std::back_inserter(result)
>> );
>>
>> This will return all values intersecting the Box and meeting user_pred.
>
> Adam,
>
> It looks you are continuously pushing the development forward.
> Great effort!
>
> Shame on my, I haven't monitored this subject closely, so here comes
> basic question: where is the code and how can I start testing it?

Hi, you may find it here: 
https://svn.boost.org/svn/boost/sandbox-branches/geometry/index.

There are 2 folders:
/boost - code in boost-like directory structure
/tests - unit tests (main.cpp, *.hpp) and additional ones (times of 
execution and visualization using GLUT).

If you want to run additional_sizes_and_times.cpp (which shows times 
only btw) you should have config file config.txt with at least 3 values:

values_count remove_count queries_count

Try e.g. 1000000 100000 100000

Some definitions:
Value - type that is stored in the rtree (or if you like, in
         rtree's leafs)
Indexable - type that is used by the rtree's algorithms
             (some Point or Box)
Translator - type of an object translating from Value to Indexable

Geometry.Index is in /boost/geometry/extensions/index which contain:
./algorithms - various algorithms working on Indexables.
./filters - indexes filters facade.
./rtree - rtree's code.
./translator - some translators.
./indexable.hpp - indexables-related traits, functions etc.
./distance_predicates.hpp - default knn queries' distance predicates.
./predicates.hpp - default spatial queries' and values' predicates.
./*.hpp - other tools.

In the /boost/geometry/extensions/index/rtree there are:
./linear - specializations and algorithms used by linear insert
./node - various rtree's nodes (build on Boost.Variant and polymorphic
          nodes, with elements in std::vectors and in boost::array
          wrapper), visitors, allocators, creating and destroying
          of nodes.
./quadratic - specializations and algorithms used by quadratic insert.
./rstar - specializations and algorithms used by R*tree insert.
./visitors - various visitors doing most of the things in the rtree.
./distance_predicates.hpp - specializations of knn queries' distance
                             predicates for rtree's nodes.
./filters.hpp - filters specializations.
./options.hpp - definition of compile-time options passed to the rtree
                 (e.g. which algorithm, min, max elements, etc.).
./distance_predicates.hpp - specializations of spatial queries' and
                             values' predicates for rtree's nodes.
./rtree.hpp - the rtree.

Regards,
Adam