123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233 |
- [/============================================================================
- 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 /]
|