Boost logo

Geometry :

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:

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.


Geometry list run by mateusz at