1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>Queries</title> 5<link rel="stylesheet" href="../../../../../../doc/src/boostbook.css" type="text/css"> 6<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 7<link rel="home" href="../../index.html" title="Chapter 1. Geometry"> 8<link rel="up" href="../spatial_indexes.html" title="Spatial Indexes"> 9<link rel="prev" href="creation_and_modification.html" title="Creation and Modification"> 10<link rel="next" href="rtree_examples.html" title="Examples"> 11</head> 12<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 13<table cellpadding="2" width="100%"><tr> 14<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td> 15<td align="center"><a href="../../../../../../index.html">Home</a></td> 16<td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td> 17<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 18<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 19<td align="center"><a href="../../../../../../more/index.htm">More</a></td> 20</tr></table> 21<hr> 22<div class="spirit-nav"> 23<a accesskey="p" href="creation_and_modification.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../spatial_indexes.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="rtree_examples.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a> 24</div> 25<div class="section"> 26<div class="titlepage"><div><div><h3 class="title"> 27<a name="geometry.spatial_indexes.queries"></a><a class="link" href="queries.html" title="Queries">Queries</a> 28</h3></div></div></div> 29<p> 30 Queries returns <code class="computeroutput">Value</code>s which meets some predicates. Currently 31 supported are three types of predicates: 32 </p> 33<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 34<li class="listitem"> 35 spatial predicates - spatial conditions that must be met by stored Value 36 and some Geometry, 37 </li> 38<li class="listitem"> 39 distance predicates - distance conditions that must be met by stored 40 Value and some Geometry, 41 </li> 42<li class="listitem"> 43 user-defined unary predicate - function, function object or lambda expression 44 checking user-defined condition. 45 </li> 46</ul></div> 47<p> 48 For example queries may be used to retrieve Values: 49 </p> 50<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 51<li class="listitem"> 52 intersecting some area but not within other area, 53 </li> 54<li class="listitem"> 55 are nearest to some point, 56 </li> 57<li class="listitem"> 58 overlapping a box and has user-defined property. 59 </li> 60</ul></div> 61<h5> 62<a name="geometry.spatial_indexes.queries.h0"></a> 63 <span class="phrase"><a name="geometry.spatial_indexes.queries.performing_a_query"></a></span><a class="link" href="queries.html#geometry.spatial_indexes.queries.performing_a_query">Performing 64 a query</a> 65 </h5> 66<p> 67 There are various ways to perform a query. They are presented below. All 68 of them returns <code class="computeroutput">Value</code>s intersecting some region defined as a 69 <code class="computeroutput">Box</code>. 70 </p> 71<p> 72 Member function call 73 </p> 74<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span>Value<span class="special">></span> <span class="identifier">returned_values</span><span class="special">;</span> 75Box <span class="identifier">box_region</span><span class="special">(...);</span> 76<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">bgi</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">box_region</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span> 77</pre> 78<p> 79 Free function call 80 </p> 81<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span>Value<span class="special">></span> <span class="identifier">returned_values</span><span class="special">;</span> 82Box <span class="identifier">box_region</span><span class="special">(...);</span> 83<span class="identifier">bgi</span><span class="special">::</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">bgi</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">box_region</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span> 84</pre> 85<p> 86 Range generated by <code class="computeroutput"><span class="keyword">operator</span><span class="special">|</span></code> 87 </p> 88<pre class="programlisting">Box <span class="identifier">box_region</span><span class="special">(...);</span> 89<span class="identifier">BOOST_FOREACH</span><span class="special">(</span>Value <span class="special">&</span> <span class="identifier">v</span><span class="special">,</span> <span class="identifier">rt</span> <span class="special">|</span> <span class="identifier">bgi</span><span class="special">::</span><span class="identifier">adaptors</span><span class="special">::</span><span class="identifier">queried</span><span class="special">(</span><span class="identifier">bgi</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">box_region</span><span class="special">)))</span> 90 <span class="special">;</span> <span class="comment">// do something with v</span> 91</pre> 92<p> 93 Query iterators returned by member functions 94 </p> 95<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span>Value<span class="special">></span> <span class="identifier">returned_values</span><span class="special">;</span> 96Box <span class="identifier">box_region</span><span class="special">(...);</span> 97<span class="identifier">std</span><span class="special">::</span><span class="identifier">copy</span><span class="special">(</span><span class="identifier">rt</span><span class="special">.</span><span class="identifier">qbegin</span><span class="special">(</span><span class="identifier">bgi</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">box_region</span><span class="special">)),</span> <span class="identifier">rt</span><span class="special">.</span><span class="identifier">qend</span><span class="special">(),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span> 98</pre> 99<p> 100 Query iterators returned by free functions 101 </p> 102<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span>Value<span class="special">></span> <span class="identifier">returned_values</span><span class="special">;</span> 103Box <span class="identifier">box_region</span><span class="special">(...);</span> 104<span class="identifier">std</span><span class="special">::</span><span class="identifier">copy</span><span class="special">(</span><span class="identifier">bgi</span><span class="special">::</span><span class="identifier">qbegin</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">bgi</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">box_region</span><span class="special">)),</span> <span class="identifier">bgi</span><span class="special">::</span><span class="identifier">qend</span><span class="special">(</span><span class="identifier">rt</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span> 105</pre> 106<h5> 107<a name="geometry.spatial_indexes.queries.h1"></a> 108 <span class="phrase"><a name="geometry.spatial_indexes.queries.spatial_queries"></a></span><a class="link" href="queries.html#geometry.spatial_indexes.queries.spatial_queries">Spatial 109 queries</a> 110 </h5> 111<p> 112 Queries using spatial predicates returns <code class="computeroutput">Value</code>s which are related 113 somehow to some Geometry - box, polygon, etc. Names of spatial predicates 114 correspond to names of Boost.Geometry algorithms (boolean operations). Examples 115 of some basic queries may be found in the tables below. The query region 116 and result <code class="computeroutput"><span class="identifier">Value</span></code>s are orange. 117 </p> 118<div class="informaltable"><table class="table"> 119<colgroup> 120<col> 121<col> 122<col> 123<col> 124<col> 125</colgroup> 126<thead><tr> 127<th> 128 <p> 129 intersects(Box) 130 </p> 131 </th> 132<th> 133 <p> 134 covered_by(Box) 135 </p> 136 </th> 137<th> 138 <p> 139 disjoint(Box) 140 </p> 141 </th> 142<th> 143 <p> 144 overlaps(Box) 145 </p> 146 </th> 147<th> 148 <p> 149 within(Box) 150 </p> 151 </th> 152</tr></thead> 153<tbody><tr> 154<td> 155 <p> 156 <span class="inlinemediaobject"><img src="../../img/index/rtree/intersects.png" alt="intersects"></span> 157 </p> 158 </td> 159<td> 160 <p> 161 <span class="inlinemediaobject"><img src="../../img/index/rtree/within.png" alt="within"></span> 162 </p> 163 </td> 164<td> 165 <p> 166 <span class="inlinemediaobject"><img src="../../img/index/rtree/disjoint.png" alt="disjoint"></span> 167 </p> 168 </td> 169<td> 170 <p> 171 <span class="inlinemediaobject"><img src="../../img/index/rtree/overlaps.png" alt="overlaps"></span> 172 </p> 173 </td> 174<td> 175 <p> 176 <span class="inlinemediaobject"><img src="../../img/index/rtree/within.png" alt="within"></span> 177 </p> 178 </td> 179</tr></tbody> 180</table></div> 181<div class="informaltable"><table class="table"> 182<colgroup> 183<col> 184<col> 185<col> 186<col> 187<col> 188</colgroup> 189<thead><tr> 190<th> 191 <p> 192 intersects(Segment) 193 </p> 194 </th> 195<th> 196 <p> 197 intersects(Box) 198 </p> 199 </th> 200<th> 201 <p> 202 disjoint(Box) 203 </p> 204 </th> 205<th> 206 <p> 207 intersects(Box) 208 </p> 209 </th> 210<th> 211 <p> 212 disjoint(Box) 213 </p> 214 </th> 215</tr></thead> 216<tbody><tr> 217<td> 218 <p> 219 <span class="inlinemediaobject"><img src="../../img/index/rtree/intersects_segment.png" alt="intersects_segment"></span> 220 </p> 221 </td> 222<td> 223 <p> 224 <span class="inlinemediaobject"><img src="../../img/index/rtree/rtree_pt_intersects_box.png" alt="rtree_pt_intersects_box"></span> 225 </p> 226 </td> 227<td> 228 <p> 229 <span class="inlinemediaobject"><img src="../../img/index/rtree/rtree_pt_disjoint_box.png" alt="rtree_pt_disjoint_box"></span> 230 </p> 231 </td> 232<td> 233 <p> 234 <span class="inlinemediaobject"><img src="../../img/index/rtree/rtree_seg_intersects_box.png" alt="rtree_seg_intersects_box"></span> 235 </p> 236 </td> 237<td> 238 <p> 239 <span class="inlinemediaobject"><img src="../../img/index/rtree/rtree_seg_disjoint_box.png" alt="rtree_seg_disjoint_box"></span> 240 </p> 241 </td> 242</tr></tbody> 243</table></div> 244<p> 245 Spatial predicates are generated by functions defined in <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">geometry</span><span class="special">::</span><span class="identifier">index</span></code> 246 namespace. 247 </p> 248<pre class="programlisting"><span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">contains</span><span class="special">(</span><span class="identifier">box</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span> 249<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">covered_by</span><span class="special">(</span><span class="identifier">box</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span> 250<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">covers</span><span class="special">(</span><span class="identifier">box</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span> 251<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">disjont</span><span class="special">(</span><span class="identifier">box</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span> 252<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">box</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span> 253<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">overlaps</span><span class="special">(</span><span class="identifier">box</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span> 254<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">within</span><span class="special">(</span><span class="identifier">box</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span> 255</pre> 256<p> 257 All spatial predicates may be negated, e.g.: 258 </p> 259<pre class="programlisting"><span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(!</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">box</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span> 260<span class="comment">// the same as</span> 261<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">disjoint</span><span class="special">(</span><span class="identifier">box</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span> 262</pre> 263<h5> 264<a name="geometry.spatial_indexes.queries.h2"></a> 265 <span class="phrase"><a name="geometry.spatial_indexes.queries.nearest_neighbours_queries"></a></span><a class="link" href="queries.html#geometry.spatial_indexes.queries.nearest_neighbours_queries">Nearest 266 neighbours queries</a> 267 </h5> 268<p> 269 Nearest neighbours queries returns <code class="computeroutput">Value</code>s which are closest 270 to some Geometry. The examples of k-NN queries are presented below. 5 <code class="computeroutput">Value</code>s 271 nearest to the Geometry are orange. 272 </p> 273<div class="informaltable"><table class="table"> 274<colgroup> 275<col> 276<col> 277<col> 278<col> 279</colgroup> 280<thead><tr> 281<th> 282 <p> 283 nearest(Point, k) 284 </p> 285 </th> 286<th> 287 <p> 288 nearest(Box, k) 289 </p> 290 </th> 291<th> 292 <p> 293 nearest(Point, k) 294 </p> 295 </th> 296<th> 297 <p> 298 nearest(Box, k) 299 </p> 300 </th> 301</tr></thead> 302<tbody><tr> 303<td> 304 <p> 305 <span class="inlinemediaobject"><img src="../../img/index/rtree/knn_pt_box.png" alt="knn_pt_box"></span> 306 </p> 307 </td> 308<td> 309 <p> 310 <span class="inlinemediaobject"><img src="../../img/index/rtree/knn_box_box.png" alt="knn_box_box"></span> 311 </p> 312 </td> 313<td> 314 <p> 315 <span class="inlinemediaobject"><img src="../../img/index/rtree/rtree_pt_knn_pt.png" alt="rtree_pt_knn_pt"></span> 316 </p> 317 </td> 318<td> 319 <p> 320 <span class="inlinemediaobject"><img src="../../img/index/rtree/rtree_pt_knn_box.png" alt="rtree_pt_knn_box"></span> 321 </p> 322 </td> 323</tr></tbody> 324</table></div> 325<div class="informaltable"><table class="table"> 326<colgroup> 327<col> 328<col> 329<col> 330<col> 331<col> 332</colgroup> 333<thead><tr> 334<th> 335 <p> 336 nearest(Segment, k) 337 </p> 338 </th> 339<th> 340 <p> 341 nearest(Point, k) 342 </p> 343 </th> 344<th> 345 <p> 346 nearest(Box, k) 347 </p> 348 </th> 349<th> 350 <p> 351 nearest(Segment, k) 352 </p> 353 </th> 354<th> 355 <p> 356 nearest(Segment, k) 357 </p> 358 </th> 359</tr></thead> 360<tbody><tr> 361<td> 362 <p> 363 <span class="inlinemediaobject"><img src="../../img/index/rtree/knn_seg_box.png" alt="knn_seg_box"></span> 364 </p> 365 </td> 366<td> 367 <p> 368 <span class="inlinemediaobject"><img src="../../img/index/rtree/rtree_seg_knn_pt.png" alt="rtree_seg_knn_pt"></span> 369 </p> 370 </td> 371<td> 372 <p> 373 <span class="inlinemediaobject"><img src="../../img/index/rtree/rtree_seg_knn_box.png" alt="rtree_seg_knn_box"></span> 374 </p> 375 </td> 376<td> 377 <p> 378 <span class="inlinemediaobject"><img src="../../img/index/rtree/rtree_seg_knn_seg.png" alt="rtree_seg_knn_seg"></span> 379 </p> 380 </td> 381<td> 382 <p> 383 <span class="inlinemediaobject"><img src="../../img/index/rtree/rtree_pt_knn_seg.png" alt="rtree_pt_knn_seg"></span> 384 </p> 385 </td> 386</tr></tbody> 387</table></div> 388<p> 389 To perform the knn query one must pass the nearest predicate generated by 390 the <code class="computeroutput"><span class="identifier">nearest</span><span class="special">()</span></code> 391 function defined in <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">geometry</span><span class="special">::</span><span class="identifier">index</span></code> 392 namespace. For non-point <code class="computeroutput">Indexable</code>s the shortest distance is 393 calculated using <code class="computeroutput"><span class="identifier">bg</span><span class="special">::</span><span class="identifier">comparable_distance</span><span class="special">()</span></code> 394 function. The following query returns <code class="computeroutput"><span class="identifier">k</span></code> 395 <code class="computeroutput">Value</code>s closest to some Point in space. 396 </p> 397<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span>Value<span class="special">></span> <span class="identifier">returned_values</span><span class="special">;</span> 398Point <span class="identifier">pt</span><span class="special">(/*...*/);</span> 399<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">bgi</span><span class="special">::</span><span class="identifier">nearest</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="identifier">k</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span> 400</pre> 401<p> 402 The same way different query Geometries can be used: 403 </p> 404<pre class="programlisting">Box <span class="identifier">box</span><span class="special">(/*...*/);</span> 405<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">bgi</span><span class="special">::</span><span class="identifier">nearest</span><span class="special">(</span><span class="identifier">box</span><span class="special">,</span> <span class="identifier">k</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span> 406 407<span class="identifier">Segment</span> <span class="identifier">seg</span><span class="special">(/*...*/);</span> 408<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">bgi</span><span class="special">::</span><span class="identifier">nearest</span><span class="special">(</span><span class="identifier">seg</span><span class="special">,</span> <span class="identifier">k</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span> 409</pre> 410<div class="note"><table border="0" summary="Note"> 411<tr> 412<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../../../../doc/src/images/note.png"></td> 413<th align="left">Note</th> 414</tr> 415<tr><td align="left" valign="top"><p> 416 In case of k-NN queries performed with <code class="computeroutput"><span class="identifier">query</span><span class="special">()</span></code> function it's not guaranteed that the 417 returned values will be sorted according to the distance. It's different 418 in case of k-NN queries performed with query iterator returned by <code class="computeroutput"><span class="identifier">qbegin</span><span class="special">()</span></code> 419 function which guarantees the iteration over the closest <code class="computeroutput">Value</code>s 420 first. 421 </p></td></tr> 422</table></div> 423<h5> 424<a name="geometry.spatial_indexes.queries.h3"></a> 425 <span class="phrase"><a name="geometry.spatial_indexes.queries.user_defined_unary_predicate"></a></span><a class="link" href="queries.html#geometry.spatial_indexes.queries.user_defined_unary_predicate">User-defined 426 unary predicate</a> 427 </h5> 428<p> 429 The user may pass a <code class="computeroutput"><span class="identifier">UnaryPredicate</span></code> 430 - function, function object or lambda expression taking const reference to 431 Value and returning bool. This object may be passed to the query in order 432 to check if <code class="computeroutput">Value</code> should be returned by the query. To do it 433 one may use <code class="computeroutput"><span class="identifier">index</span><span class="special">::</span><span class="identifier">satisfies</span><span class="special">()</span></code> 434 function like on the example below: 435 </p> 436<pre class="programlisting"><span class="keyword">bool</span> <span class="identifier">is_red</span><span class="special">(</span>Value <span class="keyword">const</span><span class="special">&</span> <span class="identifier">v</span><span class="special">)</span> 437<span class="special">{</span> 438 <span class="keyword">return</span> <span class="identifier">v</span><span class="special">.</span><span class="identifier">is_red</span><span class="special">();</span> 439<span class="special">}</span> 440 441<span class="keyword">struct</span> <span class="identifier">is_red_o</span> 442<span class="special">{</span> 443 <span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">Value</span><span class="special">></span> 444 <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">()(</span>Value <span class="keyword">const</span><span class="special">&</span> <span class="identifier">v</span><span class="special">)</span> 445 <span class="special">{</span> 446 <span class="keyword">return</span> <span class="identifier">v</span><span class="special">.</span><span class="identifier">is_red</span><span class="special">();</span> 447 <span class="special">}</span> 448<span class="special">}</span> 449 450<span class="comment">// ...</span> 451 452<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">box</span><span class="special">)</span> <span class="special">&&</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">satisfies</span><span class="special">(</span><span class="identifier">is_red</span><span class="special">),</span> 453 <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span> 454 455<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">box</span><span class="special">)</span> <span class="special">&&</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">satisfies</span><span class="special">(</span><span class="identifier">is_red_o</span><span class="special">()),</span> 456 <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span> 457 458<span class="preprocessor">#ifndef</span> <span class="identifier">BOOST_NO_CXX11_LAMBDAS</span> 459<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">box</span><span class="special">)</span> <span class="special">&&</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">satisfies</span><span class="special">([](</span>Value <span class="keyword">const</span><span class="special">&</span> <span class="identifier">v</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">v</span><span class="special">.</span><span class="identifier">is_red</span><span class="special">();</span> <span class="special">}),</span> 460 <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span> 461<span class="preprocessor">#endif</span> 462</pre> 463<p> 464 <code class="computeroutput"><span class="identifier">satisfies</span><span class="special">()</span></code> 465 may be negated, e.g.: 466 </p> 467<pre class="programlisting"><span class="keyword">bool</span> <span class="identifier">is_red</span><span class="special">(</span>Value <span class="keyword">const</span><span class="special">&</span> <span class="identifier">v</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">v</span><span class="special">.</span><span class="identifier">is_red</span><span class="special">();</span> <span class="special">}</span> 468<span class="keyword">bool</span> <span class="identifier">is_not_red</span><span class="special">(</span>Value <span class="keyword">const</span><span class="special">&</span> <span class="identifier">v</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="special">!</span><span class="identifier">v</span><span class="special">.</span><span class="identifier">is_red</span><span class="special">();</span> <span class="special">}</span> 469 470<span class="comment">// ...</span> 471 472<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">box</span><span class="special">)</span> <span class="special">&&</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">satisfies</span><span class="special">(</span><span class="identifier">is_red</span><span class="special">),</span> 473 <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span> 474<span class="comment">// the same as</span> 475<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">box</span><span class="special">)</span> <span class="special">&&</span> <span class="special">!</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">satisfies</span><span class="special">(</span><span class="identifier">is_not_red</span><span class="special">),</span> 476 <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span> 477</pre> 478<h5> 479<a name="geometry.spatial_indexes.queries.h4"></a> 480 <span class="phrase"><a name="geometry.spatial_indexes.queries.passing_set_of_predicates"></a></span><a class="link" href="queries.html#geometry.spatial_indexes.queries.passing_set_of_predicates">Passing 481 set of predicates</a> 482 </h5> 483<p> 484 It's possible to use some number of predicates in one query by connecting 485 them with <code class="computeroutput"><span class="keyword">operator</span><span class="special">&&</span></code> 486 e.g. <code class="computeroutput"><span class="identifier">Pred1</span> <span class="special">&&</span> 487 <span class="identifier">Pred2</span> <span class="special">&&</span> 488 <span class="identifier">Pred3</span> <span class="special">&&</span> 489 <span class="special">...</span></code>. 490 </p> 491<p> 492 These predicates are connected by logical AND. Passing all predicates together 493 not only makes possible to construct advanced queries but is also faster 494 than separate calls because the tree is traversed only once. Traversing is 495 continued and <code class="computeroutput"><span class="identifier">Value</span></code>s are 496 returned only if all predicates are met. Predicates are checked left-to-right 497 so placing most restrictive predicates first should accelerate the search. 498 </p> 499<pre class="programlisting"><span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">box1</span><span class="special">)</span> <span class="special">&&</span> <span class="special">!</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">within</span><span class="special">(</span><span class="identifier">box2</span><span class="special">),</span> 500 <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span> 501 502<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">box1</span><span class="special">)</span> <span class="special">&&</span> <span class="special">!</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">within</span><span class="special">(</span><span class="identifier">box2</span><span class="special">)</span> <span class="special">&&</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">overlaps</span><span class="special">(</span><span class="identifier">box3</span><span class="special">),</span> 503 <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span> 504</pre> 505<p> 506 It's possible to connect different types of predicates together. 507 </p> 508<pre class="programlisting"><span class="identifier">index</span><span class="special">::</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="identifier">k</span><span class="special">)</span> <span class="special">&&</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">within</span><span class="special">(</span><span class="identifier">b</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span> 509 510<span class="identifier">BOOST_FOREACH</span><span class="special">(</span><span class="identifier">Value</span> <span class="special">&</span> <span class="identifier">v</span><span class="special">,</span> <span class="identifier">rt</span> <span class="special">|</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">adaptors</span><span class="special">::</span><span class="identifier">queried</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="identifier">k</span><span class="special">)</span> <span class="special">&&</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">covered_by</span><span class="special">(</span><span class="identifier">b</span><span class="special">)))</span> 511 <span class="special">;</span> <span class="comment">// do something with v</span> 512</pre> 513<h5> 514<a name="geometry.spatial_indexes.queries.h5"></a> 515 <span class="phrase"><a name="geometry.spatial_indexes.queries.iterative_queries"></a></span><a class="link" href="queries.html#geometry.spatial_indexes.queries.iterative_queries">Iterative 516 queries</a> 517 </h5> 518<p> 519 The query performed using query iterators may be paused and resumed if needed, 520 e.g. when the query takes too long, or may be stopped at some point, when 521 all interesting values were gathered. The query iterator is returned by 522 <code class="computeroutput"><span class="identifier">qbegin</span><span class="special">()</span></code> 523 member function which requires passing predicates, like <code class="computeroutput"><span class="identifier">query</span><span class="special">()</span></code> member function. 524 </p> 525<pre class="programlisting"><span class="keyword">for</span> <span class="special">(</span> <span class="identifier">Rtree</span><span class="special">::</span><span class="identifier">const_query_iterator</span> <span class="identifier">it</span> <span class="special">=</span> <span class="identifier">tree</span><span class="special">.</span><span class="identifier">qbegin</span><span class="special">(</span><span class="identifier">bgi</span><span class="special">::</span><span class="identifier">nearest</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="number">10000</span><span class="special">))</span> <span class="special">;</span> 526 <span class="identifier">it</span> <span class="special">!=</span> <span class="identifier">tree</span><span class="special">.</span><span class="identifier">qend</span><span class="special">()</span> <span class="special">;</span> <span class="special">++</span><span class="identifier">it</span> <span class="special">)</span> 527<span class="special">{</span> 528 <span class="comment">// do something with value</span> 529 <span class="keyword">if</span> <span class="special">(</span> <span class="identifier">has_enough_nearest_values</span><span class="special">()</span> <span class="special">)</span> 530 <span class="keyword">break</span><span class="special">;</span> 531<span class="special">}</span> 532</pre> 533<div class="warning"><table border="0" summary="Warning"> 534<tr> 535<td rowspan="2" align="center" valign="top" width="25"><img alt="[Warning]" src="../../../../../../doc/src/images/warning.png"></td> 536<th align="left">Warning</th> 537</tr> 538<tr><td align="left" valign="top"><p> 539 The modification of the <code class="computeroutput"><span class="identifier">rtree</span></code>, 540 e.g. insertion or removal of <code class="computeroutput">Value</code>s may invalidate the iterators. 541 </p></td></tr> 542</table></div> 543<h5> 544<a name="geometry.spatial_indexes.queries.h6"></a> 545 <span class="phrase"><a name="geometry.spatial_indexes.queries.inserting_query_results_into_another_r_tree"></a></span><a class="link" href="queries.html#geometry.spatial_indexes.queries.inserting_query_results_into_another_r_tree">Inserting 546 query results into another R-tree</a> 547 </h5> 548<p> 549 There are several ways of inserting Values returned by a query into another 550 R-tree container. The most basic way is creating a temporary container for 551 Values and insert them later. 552 </p> 553<pre class="programlisting"><span class="keyword">namespace</span> <span class="identifier">bgi</span> <span class="special">=</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">geometry</span><span class="special">::</span><span class="identifier">index</span><span class="special">;</span> 554<span class="keyword">typedef</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span><span class="identifier">Box</span><span class="special">,</span> <span class="keyword">int</span><span class="special">></span> Value<span class="special">;</span> 555<span class="keyword">typedef</span> <span class="identifier">bgi</span><span class="special">::</span><span class="identifier">rtree</span><span class="special"><</span> Value<span class="special">,</span> <span class="identifier">bgi</span><span class="special">::</span><span class="identifier">linear</span><span class="special"><</span><span class="number">32</span><span class="special">,</span> <span class="number">8</span><span class="special">></span> <span class="special">></span> <span class="identifier">RTree</span><span class="special">;</span> 556 557<span class="identifier">RTree</span> <span class="identifier">rt1</span><span class="special">;</span> 558<span class="comment">/* some inserting into the tree */</span> 559 560<span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">Value</span><span class="special">></span> <span class="identifier">result</span><span class="special">;</span> 561<span class="identifier">rt1</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">bgi</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">Box</span><span class="special">(/*...*/)),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span> 562<span class="identifier">RTree</span> <span class="identifier">rt2</span><span class="special">(</span><span class="identifier">result</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">result</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span> 563</pre> 564<p> 565 However there are other ways. One of these methods is mentioned in the "Creation 566 and modification" section. The insert iterator may be passed directly 567 into the query. 568 </p> 569<pre class="programlisting"><span class="identifier">RTree</span> <span class="identifier">rt3</span><span class="special">;</span> 570<span class="identifier">rt1</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">bgi</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">Box</span><span class="special">(/*...*/))),</span> <span class="identifier">bgi</span><span class="special">::</span><span class="identifier">inserter</span><span class="special">(</span><span class="identifier">rt3</span><span class="special">));</span> 571</pre> 572<p> 573 You may also pass the resulting Range directly into the constructor or <code class="computeroutput"><span class="identifier">insert</span><span class="special">()</span></code> 574 member function using Boost.Range adaptor syntax. 575 </p> 576<pre class="programlisting"><span class="identifier">RTree</span> <span class="identifier">rt4</span><span class="special">(</span><span class="identifier">rt1</span> <span class="special">|</span> <span class="identifier">bgi</span><span class="special">::</span><span class="identifier">adaptors</span><span class="special">::</span><span class="identifier">queried</span><span class="special">(</span><span class="identifier">bgi</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">Box</span><span class="special">(/*...*/)))));</span> 577</pre> 578</div> 579<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 580<td align="left"></td> 581<td align="right"><div class="copyright-footer">Copyright © 2009-2019 Barend Gehrels, Bruno Lalande, Mateusz Loskot, Adam 582 Wulkiewicz, Oracle and/or its affiliates<p> 583 Distributed under the Boost Software License, Version 1.0. (See accompanying 584 file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) 585 </p> 586</div></td> 587</tr></table> 588<hr> 589<div class="spirit-nav"> 590<a accesskey="p" href="creation_and_modification.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../spatial_indexes.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="rtree_examples.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a> 591</div> 592</body> 593</html> 594
