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