libs/geometry/doc/index/rtree/query.qbk

   1 [/============================================================================
   2   Boost.Geometry Index
   3
   4   Copyright (c) 2011-2017 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 Queries]
  12
  13 Queries returns `__value__`s which meets some predicates. Currently supported are three types of predicates:
  14
  15 * spatial predicates - spatial conditions that must be met by stored Value and some Geometry,
  16 * distance predicates - distance conditions that must be met by stored Value and some Geometry,
  17 * user-defined unary predicate - function, function object or lambda expression checking user-defined condition.
  18
  19 For example queries may be used to retrieve Values:
  20
  21 * intersecting some area but not within other area,
  22 * are nearest to some point,
  23 * overlapping a box and has user-defined property.
  24
  25 [h4 Performing a query]
  26
  27 There are various ways to perform a query. They are presented below.
  28 All of them returns `__value__`s intersecting some region defined as a `__box__`.
  29
  30 Member function call
  31
  32  std::vector<__value__> returned_values;
  33  __box__ box_region(...);
  34  rt.query(bgi::intersects(box_region), std::back_inserter(returned_values));
  35
  36 Free function call
  37
  38  std::vector<__value__> returned_values;
  39  __box__ box_region(...);
  40  bgi::query(rt, bgi::intersects(box_region), std::back_inserter(returned_values));
  41
  42 Range generated by `operator|`
  43
  44  __box__ box_region(...);
  45  BOOST_FOREACH(__value__ & v, rt | bgi::adaptors::queried(bgi::intersects(box_region)))
  46    ; // do something with v
  47
  48 Query iterators returned by member functions
  49
  50  std::vector<__value__> returned_values;
  51  __box__ box_region(...);
  52  std::copy(rt.qbegin(bgi::intersects(box_region)), rt.qend(), std::back_inserter(returned_values));
  53
  54 Query iterators returned by free functions
  55
  56  std::vector<__value__> returned_values;
  57  __box__ box_region(...);
  58  std::copy(bgi::qbegin(rt, bgi::intersects(box_region)), bgi::qend(rt), std::back_inserter(returned_values));
  59
  60 [h4 Spatial queries]
  61
  62 Queries using spatial predicates returns `__value__`s which are related somehow to some Geometry - box, polygon, etc.
  63 Names of spatial predicates correspond to names of __boost_geometry__ algorithms (boolean operations).
  64 Examples of some basic queries may be found in the tables below. The query region and result `Value`s are orange.
  65
  66 [table
  67 [[intersects(Box)] [covered_by(Box)] [disjoint(Box)] [overlaps(Box)] [within(Box)]]
  68 [[[$img/index/rtree/intersects.png]] [[$img/index/rtree/within.png]] [[$img/index/rtree/disjoint.png]] [[$img/index/rtree/overlaps.png]] [[$img/index/rtree/within.png]]]
  69 ]
  70
  71 [table
  72 [[intersects(Ring)] [intersects(Polygon)] [intersects(MultiPolygon)] [intersects(Segment)] [intersects(Linestring)]]
  73 [[[$img/index/rtree/intersects_ring.png]] [[$img/index/rtree/intersects_poly.png]] [[$img/index/rtree/intersects_mpoly.png]] [[$img/index/rtree/intersects_segment.png]] [[$img/index/rtree/intersects_linestring.png]]]
  74 ]
  75
  76 [table
  77 [[intersects(Box)] [disjoint(Box)] [intersects(Box)] [disjoint(Box)]]
  78 [[[$img/index/rtree/rtree_pt_intersects_box.png]] [[$img/index/rtree/rtree_pt_disjoint_box.png]] [[$img/index/rtree/rtree_seg_intersects_box.png]] [[$img/index/rtree/rtree_seg_disjoint_box.png]]]
  79 ]
  80
  81 Spatial predicates are generated by functions defined in `boost::geometry::index` namespace.
  82
  83  rt.query(index::contains(box), std::back_inserter(result));
  84  rt.query(index::covered_by(box), std::back_inserter(result));
  85  rt.query(index::covers(box), std::back_inserter(result));
  86  rt.query(index::disjont(box), std::back_inserter(result));
  87  rt.query(index::intersects(box), std::back_inserter(result));
  88  rt.query(index::overlaps(box), std::back_inserter(result));
  89  rt.query(index::within(box), std::back_inserter(result));
  90
  91 All spatial predicates may be negated, e.g.:
  92
  93  rt.query(!index::intersects(box), std::back_inserter(result));
  94  // the same as
  95  rt.query(index::disjoint(box), std::back_inserter(result));
  96
  97 [h4 Nearest neighbours queries]
  98
  99 Nearest neighbours queries returns `__value__`s which are closest to some Geometry.
 100 The examples of k-NN queries are presented below. 5 `__value__`s nearest to the Geometry are orange.
 101
 102 [table
 103 [[nearest(Point, k)] [nearest(Box, k)] [nearest(Point, k)] [nearest(Box, k)]]
 104 [[[$img/index/rtree/knn_pt_box.png]] [[$img/index/rtree/knn_box_box.png]] [[$img/index/rtree/rtree_pt_knn_pt.png]] [[$img/index/rtree/rtree_pt_knn_box.png]]]
 105 ]
 106 [table
 107 [[nearest(Segment, k)]
 108  [nearest(Point, k)] [nearest(Box, k)] [nearest(Segment, k)]
 109  [nearest(Segment, k)]]
 110 [[[$img/index/rtree/knn_seg_box.png]]
 111  [[$img/index/rtree/rtree_seg_knn_pt.png]] [[$img/index/rtree/rtree_seg_knn_box.png]] [[$img/index/rtree/rtree_seg_knn_seg.png]]
 112  [[$img/index/rtree/rtree_pt_knn_seg.png]]]
 113 ]
 114
 115 To perform the knn query one must pass the nearest predicate generated by the
 116 `nearest()` function defined in `boost::geometry::index` namespace.
 117 For non-point `__indexable__`s the shortest distance is calculated using `bg::comparable_distance()` function.
 118 The following query returns `k` `__value__`s closest to some Point in space.
 119
 120  std::vector<__value__> returned_values;
 121  __point__ pt(/*...*/);
 122  rt.query(bgi::nearest(pt, k), std::back_inserter(returned_values));
 123
 124 The same way different query Geometries can be used:
 125
 126  __box__ box(/*...*/);
 127  rt.query(bgi::nearest(box, k), std::back_inserter(returned_values));
 128
 129  Segment seg(/*...*/);
 130  rt.query(bgi::nearest(seg, k), std::back_inserter(returned_values));
 131
 132 [note In case of k-NN queries performed with `query()` function it's not guaranteed that the returned values will be sorted according to the distance.
 133       It's different in case of k-NN queries performed with query iterator returned by `qbegin()` function which guarantees the iteration over the closest `__value__`s first. ]
 134
 135 [h4 User-defined unary predicate]
 136
 137 The user may pass a `UnaryPredicate` - function, function object or lambda expression taking const reference to Value and returning bool.
 138 This object may be passed to the query in order to check if `__value__` should be returned by the query. To do it one
 139 may use `index::satisfies()` function like on the example below:
 140
 141  bool is_red(__value__ const& v)
 142  {
 143    return v.is_red();
 144  }
 145
 146  struct is_red_o
 147  {
 148    template <typename Value>
 149    bool operator()(__value__ const& v)
 150    {
 151      return v.is_red();
 152    }
 153  }
 154
 155  // ...
 156
 157  rt.query(index::intersects(box) && index::satisfies(is_red),
 158           std::back_inserter(result));
 159
 160  rt.query(index::intersects(box) && index::satisfies(is_red_o()),
 161           std::back_inserter(result));
 162
 163  #ifndef BOOST_NO_CXX11_LAMBDAS
 164  rt.query(index::intersects(box) && index::satisfies([](__value__ const& v) { return v.is_red(); }),
 165           std::back_inserter(result));
 166  #endif
 167
 168 `satisfies()` may be negated, e.g.:
 169
 170  bool is_red(__value__ const& v) { return v.is_red(); }
 171  bool is_not_red(__value__ const& v) { return !v.is_red(); }
 172
 173  // ...
 174
 175  rt.query(index::intersects(box) && index::satisfies(is_red),
 176           std::back_inserter(result));
 177  // the same as
 178  rt.query(index::intersects(box) && !index::satisfies(is_not_red),
 179           std::back_inserter(result));
 180
 181 [h4 Passing set of predicates]
 182
 183 It's possible to use some number of predicates in one query by connecting them with `operator&&` e.g. `Pred1 && Pred2 && Pred3 && ...`.
 184
 185 These predicates are connected by logical AND. Passing all predicates together not only makes possible
 186 to construct advanced queries but is also faster than separate calls because the tree is traversed only once.
 187 Traversing is continued and `Value`s are returned only if all predicates are met. Predicates are checked
 188 left-to-right so placing most restrictive predicates first should accelerate the search.
 189
 190  rt.query(index::intersects(box1) && !index::within(box2),
 191           std::back_inserter(result));
 192
 193  rt.query(index::intersects(box1) && !index::within(box2) && index::overlaps(box3),
 194           std::back_inserter(result));
 195
 196 It's possible to connect different types of predicates together.
 197
 198  index::query(rt, index::nearest(pt, k) && index::within(b), std::back_inserter(returned_values));
 199
 200  BOOST_FOREACH(Value & v, rt | index::adaptors::queried(index::nearest(pt, k) && index::covered_by(b)))
 201    ; // do something with v
 202
 203 [h4 Iterative queries]
 204
 205 The query performed using query iterators may be paused and resumed if needed, e.g. when the query takes too long,
 206 or may be stopped at some point, when all interesting values were gathered. The query iterator is returned by
 207 `qbegin()` member function which requires passing predicates, like `query()` member function.
 208
 209  for ( Rtree::const_query_iterator it = tree.qbegin(bgi::nearest(pt, 10000)) ;
 210        it != tree.qend() ; ++it )
 211  {
 212      // do something with value
 213      if ( has_enough_nearest_values() )
 214          break;
 215  }
 216
 217 [warning The modification of the `rtree`, e.g. insertion or removal of `__value__`s may invalidate the iterators. ]
 218
 219 [h4 Inserting query results into another R-tree]
 220
 221 There are several ways of inserting Values returned by a query into another R-tree container.
 222 The most basic way is creating a temporary container for Values and insert them later.
 223
 224  namespace bgi = boost::geometry::index;
 225  typedef std::pair<Box, int> __value__;
 226  typedef bgi::rtree< __value__, bgi::linear<32, 8> > RTree;
 227
 228  RTree rt1;
 229  /* some inserting into the tree */
 230
 231  std::vector<Value> result;
 232  rt1.query(bgi::intersects(Box(/*...*/)), std::back_inserter(result));
 233  RTree rt2(result.begin(), result.end());
 234
 235 However there are other ways. One of these methods is mentioned in the "Creation and modification" section.
 236 The insert iterator may be passed directly into the query.
 237
 238  RTree rt3;
 239  rt1.query(bgi::intersects(Box(/*...*/))), bgi::inserter(rt3));
 240
 241 You may also pass the resulting Range directly into the constructor or `insert()` member function using Boost.Range adaptor syntax.
 242
 243  RTree rt4(rt1 | bgi::adaptors::queried(bgi::intersects(Box(/*...*/)))));
 244
 245 [endsect] [/ Queries /]