7b1e4bd601
Add a tip about usage of Boost.Range adaptors with the rtree. Add an example of usage of Boost.Range adaptors. Replace invalid main(void) with main() in examples. Fix MSVC type conversion warnings in examples.
234 lines
8.5 KiB
Plaintext
234 lines
8.5 KiB
Plaintext
[/============================================================================
|
|
Boost.Geometry Index
|
|
|
|
Copyright (c) 2011-2012 Adam Wulkiewicz.
|
|
|
|
Use, modification and distribution is subject to the Boost Software License,
|
|
Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
|
|
http://www.boost.org/LICENSE_1_0.txt)
|
|
=============================================================================/]
|
|
|
|
[section Creation and Modification]
|
|
|
|
[h4 Template parameters]
|
|
|
|
__rtree__ has 5 parameters but only 2 are required:
|
|
|
|
rtree<Value,
|
|
Parameters,
|
|
IndexableGetter = index::indexable<Value>,
|
|
EqualTo = index::equal_to<Value>,
|
|
Allocator = std::allocator<Value> >
|
|
|
|
* `__value__` - type of object which will be stored in the container,
|
|
* `Parameters` - parameters type, inserting/splitting algorithm,
|
|
* `IndexableGetter` - function object translating `__value__` to `__indexable__` (`__point__` or `__box__`) which __rtree__ can handle,
|
|
* `EqualTo` - function object comparing `__value__`s,
|
|
* `Allocator` - `Value`s allocator, all allocators needed by the container are created from it.
|
|
|
|
[h4 Values and Indexables]
|
|
|
|
__rtree__ may store `__value__`s of any type as long as passed function objects know how to interpret those `__value__`s, that is
|
|
extract an `__indexable__` that the __rtree__ can handle and compare `__value__`s.
|
|
The `__indexable__` is a type adapted to Point, Box or Segment concept.
|
|
The examples of rtrees storing `__value__`s translatable to various `__indexable__`s are presented below.
|
|
|
|
[table
|
|
[[rtree<Point, ...>] [rtree<Box, ...>] [rtree<Segment, ...>]]
|
|
[[[$img/index/rtree/rtree_pt.png]] [[$img/index/rtree/rstar.png]] [[$img/index/rtree/rtree_seg.png]]]
|
|
]
|
|
|
|
By default function objects `index::indexable<Value>` and `index::equal_to<Value>` are defined for some typically used `__value__`
|
|
types which may be stored without defining any additional classes. By default the rtree may store pure `__indexable__`s, pairs
|
|
and tuples. In the case of those two collection types, the `__indexable__` must be the first stored type.
|
|
|
|
* `__indexable__ = __point__ | __box__ | Segment`
|
|
* `__value__ = Indexable | std::pair<__indexable__, T> | boost::tuple<__indexable__, ...> [ | std::tuple<__indexable__, ...> ]`
|
|
|
|
By default `boost::tuple<...>` is supported on all compilers. If the compiler supports C++11 tuples and variadic templates
|
|
then `std::tuple<...>` may be used "out of the box" as well.
|
|
|
|
Examples of default `__value__` types:
|
|
|
|
geometry::model::point<...>
|
|
geometry::model::point_xy<...>
|
|
geometry::model::box<...>
|
|
geometry::model::segment<...>
|
|
std::pair<geometry::model::box<...>, unsigned>
|
|
boost::tuple<geometry::model::point<...>, int, float>
|
|
|
|
The predefined `index::indexable<Value>` returns const reference to the `__indexable__` stored in the `__value__`.
|
|
|
|
[important The translation is done quite frequently inside the container - each time the rtree needs it. ]
|
|
|
|
The predefined `index::equal_to<Value>`:
|
|
|
|
* for `__point__`, `__box__` and `Segment` - compares `__value__`s with geometry::equals().
|
|
* for `std::pair<...>` - compares both components of the `__value__`. The first value stored in the pair is compared before the second one.
|
|
If the value stored in the pair is a Geometry, `geometry::equals()` is used. For other types it uses `operator==()`.
|
|
* for `tuple<...>` - compares all components of the `__value__`. If the component is a `Geometry`, `geometry::equals()`
|
|
function is used. For other types it uses `operator==()`.
|
|
|
|
[h4 Balancing algorithms compile-time parameters]
|
|
|
|
`__value__`s may be inserted to the __rtree__ in many various ways. Final internal structure
|
|
of the __rtree__ depends on algorithms used in the insertion process and parameters. The most important is
|
|
nodes' balancing algorithm. Currently, three well-known types of R-trees may be created.
|
|
|
|
Linear - classic __rtree__ using balancing algorithm of linear complexity
|
|
|
|
index::rtree< __value__, index::linear<16> > rt;
|
|
|
|
Quadratic - classic __rtree__ using balancing algorithm of quadratic complexity
|
|
|
|
index::rtree< __value__, index::quadratic<16> > rt;
|
|
|
|
R*-tree - balancing algorithm minimizing nodes' overlap with forced reinsertions
|
|
|
|
index::rtree< __value__, index::rstar<16> > rt;
|
|
|
|
[h4 Balancing algorithms run-time parameters]
|
|
|
|
Balancing algorithm parameters may be passed to the __rtree__ in run-time.
|
|
To use run-time versions of the __rtree__ one may pass parameters which
|
|
names start with `dynamic_`.
|
|
|
|
// linear
|
|
index::rtree<__value__, index::dynamic_linear> rt(index::dynamic_linear(16));
|
|
|
|
// quadratic
|
|
index::rtree<__value__, index::dynamic_quadratic> rt(index::dynamic_quadratic(16));
|
|
|
|
// rstar
|
|
index::rtree<__value__, index::dynamic_rstar> rt(index::dynamic_rstar(16));
|
|
|
|
The obvious drawback is a slightly slower __rtree__.
|
|
|
|
[h4 Non-default parameters]
|
|
|
|
Non-default R-tree parameters are described in the reference.
|
|
|
|
[h4 Copying, moving and swapping]
|
|
|
|
The __rtree__ is copyable and movable container. Move semantics is implemented using Boost.Move library
|
|
so it's possible to move the container on a compilers without rvalue references support.
|
|
|
|
// default constructor
|
|
index::rtree< __value__, index::rstar<8> > rt1;
|
|
|
|
// copy constructor
|
|
index::rtree< __value__, index::rstar<8> > rt2(r1);
|
|
|
|
// copy assignment
|
|
rt2 = r1;
|
|
|
|
// move constructor
|
|
index::rtree< __value__, index::rstar<8> > rt3(boost::move(rt1));
|
|
|
|
// move assignment
|
|
rt3 = boost::move(rt2);
|
|
|
|
// swap
|
|
rt3.swap(rt2);
|
|
|
|
[h4 Inserting and removing Values]
|
|
|
|
The following code creates an __rtree__ using quadratic balancing algorithm.
|
|
|
|
using namespace boost::geometry;
|
|
typedef std::pair<Box, int> __value__;
|
|
index::rtree< __value__, index::quadratic<16> > rt;
|
|
|
|
To insert or remove a `__value__' by method call one may use the following
|
|
code.
|
|
|
|
__value__ v = std::make_pair(__box__(...), 0);
|
|
|
|
rt.insert(v);
|
|
|
|
rt.remove(v);
|
|
|
|
To insert or remove a `__value__' by function call one may use the following
|
|
code.
|
|
|
|
__value__ v = std::make_pair(__box__(...), 0);
|
|
|
|
index::insert(rt, v);
|
|
|
|
index::remove(rt, v);
|
|
|
|
Typically you will perform those operations in a loop in order to e.g. insert
|
|
some number of `__value__`s corresponding to geometrical objects (e.g. `Polygons`)
|
|
stored in another container.
|
|
|
|
[h4 Additional interface]
|
|
|
|
The __rtree__ allows creation, inserting and removing of Values from a range. The range may be passed as
|
|
`[first, last)` Iterators pair or as a Range adapted to one of the Boost.Range Concepts.
|
|
|
|
namespace bgi = boost::geometry::index;
|
|
typedef std::pair<Box, int> __value__;
|
|
typedef bgi::rtree< __value__, bgi::linear<32> > RTree;
|
|
|
|
std::vector<__value__> values;
|
|
/* vector filling code, here */
|
|
|
|
// create R-tree with default constructor and insert values with insert(Value const&)
|
|
RTree rt1;
|
|
BOOST_FOREACH(__value__ const& v, values)
|
|
rt1.insert(v);
|
|
|
|
// create R-tree with default constructor and insert values with insert(Iter, Iter)
|
|
RTree rt2;
|
|
rt2.insert(values.begin(), values.end());
|
|
|
|
// create R-tree with default constructor and insert values with insert(Range)
|
|
RTree rt3;
|
|
rt3.insert(values_range);
|
|
|
|
// create R-tree with constructor taking Iterators
|
|
RTree rt4(values.begin(), values.end());
|
|
|
|
// create R-tree with constructor taking Range
|
|
RTree rt5(values_range);
|
|
|
|
// remove values with remove(Value const&)
|
|
BOOST_FOREACH(__value__ const& v, values)
|
|
rt1.remove(v);
|
|
|
|
// remove values with remove(Iter, Iter)
|
|
rt2.remove(values.begin(), values.end());
|
|
|
|
// remove values with remove(Range)
|
|
rt3.remove(values_range);
|
|
|
|
Furthermore, it's possible to pass a Range adapted by one of the Boost.Range adaptors into the rtree (more complete example can be found in the *Examples* section).
|
|
|
|
// create Rtree containing `std::pair<Box, int>` from a container of Boxes on the fly.
|
|
RTree rt6(boxes | boost::adaptors::indexed()
|
|
| boost::adaptors::transformed(pair_maker()));
|
|
|
|
[h4 Insert iterator]
|
|
|
|
There are functions like `std::copy()`, or __rtree__'s queries that copy values to an output iterator.
|
|
In order to insert values to a container in this kind of function insert iterators may be used.
|
|
Geometry.Index provide its own `bgi::insert_iterator<Container>` which is generated by
|
|
`bgi::inserter()` function.
|
|
|
|
namespace bgi = boost::geometry::index;
|
|
typedef std::pair<Box, int> __value__;
|
|
typedef bgi::rtree< __value__, bgi::linear<32> > RTree;
|
|
|
|
std::vector<__value__> values;
|
|
/* vector filling code, here */
|
|
|
|
// create R-tree and insert values from the vector
|
|
RTree rt1;
|
|
std::copy(values.begin(), values.end(), bgi::inserter(rt1));
|
|
|
|
// create R-tree and insert values returned by a query
|
|
RTree rt2;
|
|
rt1.spatial_query(Box(/*...*/), bgi::inserter(rt2));
|
|
|
|
[endsect] [/ Creation and Modification /]
|