ceph/src/boost/libs/geometry/doc/index/rtree/creation.qbk

   1 [/============================================================================
   2   Boost.Geometry Index
   3
   4   Copyright (c) 2011-2012 Adam Wulkiewicz.
   5
   6   Use, modification and distribution is subject to the Boost Software License,
   7   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   8   http://www.boost.org/LICENSE_1_0.txt)
   9 =============================================================================/]
  10
  11 [section Creation and Modification]
  12
  13 [h4 Template parameters]
  14
  15 __rtree__ has 5 parameters but only 2 are required:
  16
  17  rtree<Value,
  18        Parameters,
  19        IndexableGetter = index::indexable<Value>,
  20        EqualTo = index::equal_to<Value>,
  21        Allocator = std::allocator<Value> >
  22
  23 * `__value__` - type of object which will be stored in the container,
  24 * `Parameters` - parameters type, inserting/splitting algorithm,
  25 * `IndexableGetter` - function object translating `__value__` to `__indexable__` (`__point__` or `__box__`) which __rtree__ can handle,
  26 * `EqualTo` - function object comparing `__value__`s,
  27 * `Allocator` - `Value`s allocator, all allocators needed by the container are created from it.
  28
  29 [h4 Values and Indexables]
  30
  31 __rtree__ may store `__value__`s of any type as long as passed function objects know how to interpret those `__value__`s, that is
  32 extract an `__indexable__` that the __rtree__ can handle and compare `__value__`s.
  33 The `__indexable__` is a type adapted to Point, Box or Segment concept.
  34 The examples of rtrees storing `__value__`s translatable to various `__indexable__`s are presented below.
  35
  36 [table
  37 [[rtree<Point, ...>] [rtree<Box, ...>] [rtree<Segment, ...>]]
  38 [[[$img/index/rtree/rtree_pt.png]] [[$img/index/rtree/rstar.png]] [[$img/index/rtree/rtree_seg.png]]]
  39 ]
  40
  41 By default function objects `index::indexable<Value>` and `index::equal_to<Value>` are defined for some typically used `__value__`
  42 types which may be stored without defining any additional classes. By default the rtree may store pure `__indexable__`s, pairs
  43 and tuples. In the case of those two collection types, the `__indexable__` must be the first stored type.
  44
  45 * `__indexable__ = __point__ | __box__ | Segment`
  46 * `__value__ = Indexable | std::pair<__indexable__, T> | boost::tuple<__indexable__, ...> [ | std::tuple<__indexable__, ...> ]`
  47
  48 By default `boost::tuple<...>` is supported on all compilers. If the compiler supports C++11 tuples and variadic templates
  49 then `std::tuple<...>` may be used "out of the box" as well.
  50
  51 Examples of default `__value__` types:
  52
  53  geometry::model::point<...>
  54  geometry::model::point_xy<...>
  55  geometry::model::box<...>
  56  geometry::model::segment<...>
  57  std::pair<geometry::model::box<...>, unsigned>
  58  boost::tuple<geometry::model::point<...>, int, float>
  59
  60 The predefined `index::indexable<Value>` returns const reference to the `__indexable__` stored in the `__value__`.
  61
  62 [important The translation is done quite frequently inside the container - each time the rtree needs it. ]
  63
  64 The predefined `index::equal_to<Value>`:
  65
  66 * for `__point__`, `__box__` and `Segment` - compares `__value__`s with geometry::equals().
  67 * for `std::pair<...>` - compares both components of the `__value__`. The first value stored in the pair is compared before the second one.
  68   If the value stored in the pair is a Geometry, `geometry::equals()` is used. For other types it uses `operator==()`.
  69 * for `tuple<...>` - compares all components of the `__value__`. If the component is a `Geometry`, `geometry::equals()`
  70   function is used. For other types it uses `operator==()`.
  71
  72 [h4 Balancing algorithms compile-time parameters]
  73
  74 `__value__`s may be inserted to the __rtree__ in many various ways. Final internal structure
  75 of the __rtree__ depends on algorithms used in the insertion process and parameters. The most important is
  76 nodes' balancing algorithm. Currently, three well-known types of R-trees may be created.
  77
  78 Linear - classic __rtree__ using balancing algorithm of linear complexity
  79
  80  index::rtree< __value__, index::linear<16> > rt;
  81
  82 Quadratic - classic __rtree__ using balancing algorithm of quadratic complexity
  83
  84  index::rtree< __value__, index::quadratic<16> > rt;
  85
  86 R*-tree - balancing algorithm minimizing nodes' overlap with forced reinsertions
  87
  88  index::rtree< __value__, index::rstar<16> > rt;
  89
  90 [h4 Balancing algorithms run-time parameters]
  91
  92 Balancing algorithm parameters may be passed to the __rtree__ in run-time.
  93 To use run-time versions of the __rtree__ one may pass parameters which
  94 names start with `dynamic_`.
  95
  96  // linear
  97  index::rtree<__value__, index::dynamic_linear> rt(index::dynamic_linear(16));
  98
  99  // quadratic
 100  index::rtree<__value__, index::dynamic_quadratic> rt(index::dynamic_quadratic(16));
 101
 102  // rstar
 103  index::rtree<__value__, index::dynamic_rstar> rt(index::dynamic_rstar(16));
 104
 105 The obvious drawback is a slightly slower __rtree__.
 106
 107 [h4 Non-default parameters]
 108
 109 Non-default R-tree parameters are described in the reference.
 110
 111 [h4 Copying, moving and swapping]
 112
 113 The __rtree__ is copyable and movable container. Move semantics is implemented using Boost.Move library
 114 so it's possible to move the container on a compilers without rvalue references support.
 115
 116  // default constructor
 117  index::rtree< __value__, index::rstar<8> > rt1;
 118
 119  // copy constructor
 120  index::rtree< __value__, index::rstar<8> > rt2(r1);
 121
 122  // copy assignment
 123  rt2 = r1;
 124
 125  // move constructor
 126  index::rtree< __value__, index::rstar<8> > rt3(boost::move(rt1));
 127
 128  // move assignment
 129  rt3 = boost::move(rt2);
 130
 131  // swap
 132  rt3.swap(rt2);
 133
 134 [h4 Inserting and removing Values]
 135
 136 The following code creates an __rtree__ using quadratic balancing algorithm.
 137
 138  using namespace boost::geometry;
 139  typedef std::pair<Box, int> __value__;
 140  index::rtree< __value__, index::quadratic<16> > rt;
 141
 142 To insert or remove a `__value__' by method call one may use the following
 143 code.
 144
 145  __value__ v = std::make_pair(__box__(...), 0);
 146
 147  rt.insert(v);
 148
 149  rt.remove(v);
 150
 151 To insert or remove a `__value__' by function call one may use the following
 152 code.
 153
 154  __value__ v = std::make_pair(__box__(...), 0);
 155
 156  index::insert(rt, v);
 157
 158  index::remove(rt, v);
 159
 160 Typically you will perform those operations in a loop in order to e.g. insert
 161 some number of `__value__`s corresponding to geometrical objects (e.g. `Polygons`)
 162 stored in another container.
 163
 164 [h4 Additional interface]
 165
 166 The __rtree__ allows creation, inserting and removing of Values from a range. The range may be passed as
 167 `[first, last)` Iterators pair or as a Range adapted to one of the Boost.Range Concepts.
 168
 169  namespace bgi = boost::geometry::index;
 170  typedef std::pair<Box, int> __value__;
 171  typedef bgi::rtree< __value__, bgi::linear<32> > RTree;
 172
 173  std::vector<__value__> values;
 174  /* vector filling code, here */
 175
 176  // create R-tree with default constructor and insert values with insert(Value const&)
 177  RTree rt1;
 178  BOOST_FOREACH(__value__ const& v, values)
 179     rt1.insert(v);
 180
 181  // create R-tree with default constructor and insert values with insert(Iter, Iter)
 182  RTree rt2;
 183  rt2.insert(values.begin(), values.end());
 184
 185  // create R-tree with default constructor and insert values with insert(Range)
 186  RTree rt3;
 187  rt3.insert(values_range);
 188
 189  // create R-tree with constructor taking Iterators
 190  RTree rt4(values.begin(), values.end());
 191
 192  // create R-tree with constructor taking Range
 193  RTree rt5(values_range);
 194
 195  // remove values with remove(Value const&)
 196  BOOST_FOREACH(__value__ const& v, values)
 197     rt1.remove(v);
 198
 199  // remove values with remove(Iter, Iter)
 200  rt2.remove(values.begin(), values.end());
 201
 202  // remove values with remove(Range)
 203  rt3.remove(values_range);
 204
 205 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).
 206
 207  // create Rtree containing `std::pair<Box, int>` from a container of Boxes on the fly.
 208  RTree rt6(boxes | boost::adaptors::indexed()
 209                  | boost::adaptors::transformed(pair_maker()));
 210
 211 [h4 Insert iterator]
 212
 213 There are functions like `std::copy()`, or __rtree__'s queries that copy values to an output iterator.
 214 In order to insert values to a container in this kind of function insert iterators may be used.
 215 Geometry.Index provide its own `bgi::insert_iterator<Container>` which is generated by
 216 `bgi::inserter()` function.
 217
 218  namespace bgi = boost::geometry::index;
 219  typedef std::pair<Box, int> __value__;
 220  typedef bgi::rtree< __value__, bgi::linear<32> > RTree;
 221
 222  std::vector<__value__> values;
 223  /* vector filling code, here */
 224
 225  // create R-tree and insert values from the vector
 226  RTree rt1;
 227  std::copy(values.begin(), values.end(), bgi::inserter(rt1));
 228
 229  // create R-tree and insert values returned by a query
 230  RTree rt2;
 231  rt1.spatial_query(Box(/*...*/), bgi::inserter(rt2));
 232
 233 [endsect] [/ Creation and Modification /]