libs/geometry/doc/html/geometry/spatial_indexes/queries.html

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   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.78.1">
   7 <link rel="home" href="../../index.html" title="Chapter&#160;1.&#160;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">&lt;</span>Value<span class="special">&gt;</span> <span class="identifier">returned_values</span><span class="special">;</span>
  75 Box <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">&lt;</span>Value<span class="special">&gt;</span> <span class="identifier">returned_values</span><span class="special">;</span>
  82 Box <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">&amp;</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">&lt;</span>Value<span class="special">&gt;</span> <span class="identifier">returned_values</span><span class="special">;</span>
  96 Box <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">&lt;</span>Value<span class="special">&gt;</span> <span class="identifier">returned_values</span><span class="special">;</span>
 103 Box <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_predicates"></a></span><a class="link" href="queries.html#geometry.spatial_indexes.queries.spatial_predicates">Spatial
 109         predicates</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(Ring)
 193                 </p>
 194               </th>
 195 <th>
 196                 <p>
 197                   intersects(Polygon)
 198                 </p>
 199               </th>
 200 <th>
 201                 <p>
 202                   intersects(MultiPolygon)
 203                 </p>
 204               </th>
 205 <th>
 206                 <p>
 207                   intersects(Segment)
 208                 </p>
 209               </th>
 210 <th>
 211                 <p>
 212                   intersects(Linestring)
 213                 </p>
 214               </th>
 215 </tr></thead>
 216 <tbody><tr>
 217 <td>
 218                 <p>
 219                   <span class="inlinemediaobject"><img src="../../img/index/rtree/intersects_ring.png" alt="intersects_ring"></span>
 220                 </p>
 221               </td>
 222 <td>
 223                 <p>
 224                   <span class="inlinemediaobject"><img src="../../img/index/rtree/intersects_poly.png" alt="intersects_poly"></span>
 225                 </p>
 226               </td>
 227 <td>
 228                 <p>
 229                   <span class="inlinemediaobject"><img src="../../img/index/rtree/intersects_mpoly.png" alt="intersects_mpoly"></span>
 230                 </p>
 231               </td>
 232 <td>
 233                 <p>
 234                   <span class="inlinemediaobject"><img src="../../img/index/rtree/intersects_segment.png" alt="intersects_segment"></span>
 235                 </p>
 236               </td>
 237 <td>
 238                 <p>
 239                   <span class="inlinemediaobject"><img src="../../img/index/rtree/intersects_linestring.png" alt="intersects_linestring"></span>
 240                 </p>
 241               </td>
 242 </tr></tbody>
 243 </table></div>
 244 <div class="informaltable"><table class="table">
 245 <colgroup>
 246 <col>
 247 <col>
 248 <col>
 249 <col>
 250 </colgroup>
 251 <thead><tr>
 252 <th>
 253                 <p>
 254                   intersects(Box)
 255                 </p>
 256               </th>
 257 <th>
 258                 <p>
 259                   disjoint(Box)
 260                 </p>
 261               </th>
 262 <th>
 263                 <p>
 264                   intersects(Box)
 265                 </p>
 266               </th>
 267 <th>
 268                 <p>
 269                   disjoint(Box)
 270                 </p>
 271               </th>
 272 </tr></thead>
 273 <tbody><tr>
 274 <td>
 275                 <p>
 276                   <span class="inlinemediaobject"><img src="../../img/index/rtree/rtree_pt_intersects_box.png" alt="rtree_pt_intersects_box"></span>
 277                 </p>
 278               </td>
 279 <td>
 280                 <p>
 281                   <span class="inlinemediaobject"><img src="../../img/index/rtree/rtree_pt_disjoint_box.png" alt="rtree_pt_disjoint_box"></span>
 282                 </p>
 283               </td>
 284 <td>
 285                 <p>
 286                   <span class="inlinemediaobject"><img src="../../img/index/rtree/rtree_seg_intersects_box.png" alt="rtree_seg_intersects_box"></span>
 287                 </p>
 288               </td>
 289 <td>
 290                 <p>
 291                   <span class="inlinemediaobject"><img src="../../img/index/rtree/rtree_seg_disjoint_box.png" alt="rtree_seg_disjoint_box"></span>
 292                 </p>
 293               </td>
 294 </tr></tbody>
 295 </table></div>
 296 <p>
 297         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>
 298         namespace.
 299       </p>
 300 <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>
 301 <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>
 302 <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>
 303 <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>
 304 <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>
 305 <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>
 306 <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>
 307 </pre>
 308 <p>
 309         All spatial predicates may be negated, e.g.:
 310       </p>
 311 <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>
 312 <span class="comment">// the same as</span>
 313 <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>
 314 </pre>
 315 <h5>
 316 <a name="geometry.spatial_indexes.queries.h2"></a>
 317         <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
 318         neighbours queries</a>
 319       </h5>
 320 <p>
 321         Nearest neighbours queries returns <code class="computeroutput">Value</code>s which are closest
 322         to some Geometry. The examples of k-NN queries are presented below. 5 <code class="computeroutput">Value</code>s
 323         nearest to the Geometry are orange.
 324       </p>
 325 <div class="informaltable"><table class="table">
 326 <colgroup>
 327 <col>
 328 <col>
 329 <col>
 330 <col>
 331 </colgroup>
 332 <thead><tr>
 333 <th>
 334                 <p>
 335                   nearest(Point, k)
 336                 </p>
 337               </th>
 338 <th>
 339                 <p>
 340                   nearest(Box, k)
 341                 </p>
 342               </th>
 343 <th>
 344                 <p>
 345                   nearest(Point, k)
 346                 </p>
 347               </th>
 348 <th>
 349                 <p>
 350                   nearest(Box, k)
 351                 </p>
 352               </th>
 353 </tr></thead>
 354 <tbody><tr>
 355 <td>
 356                 <p>
 357                   <span class="inlinemediaobject"><img src="../../img/index/rtree/knn_pt_box.png" alt="knn_pt_box"></span>
 358                 </p>
 359               </td>
 360 <td>
 361                 <p>
 362                   <span class="inlinemediaobject"><img src="../../img/index/rtree/knn_box_box.png" alt="knn_box_box"></span>
 363                 </p>
 364               </td>
 365 <td>
 366                 <p>
 367                   <span class="inlinemediaobject"><img src="../../img/index/rtree/rtree_pt_knn_pt.png" alt="rtree_pt_knn_pt"></span>
 368                 </p>
 369               </td>
 370 <td>
 371                 <p>
 372                   <span class="inlinemediaobject"><img src="../../img/index/rtree/rtree_pt_knn_box.png" alt="rtree_pt_knn_box"></span>
 373                 </p>
 374               </td>
 375 </tr></tbody>
 376 </table></div>
 377 <div class="informaltable"><table class="table">
 378 <colgroup>
 379 <col>
 380 <col>
 381 <col>
 382 <col>
 383 <col>
 384 </colgroup>
 385 <thead><tr>
 386 <th>
 387                 <p>
 388                   nearest(Segment, k)
 389                 </p>
 390               </th>
 391 <th>
 392                 <p>
 393                   nearest(Point, k)
 394                 </p>
 395               </th>
 396 <th>
 397                 <p>
 398                   nearest(Box, k)
 399                 </p>
 400               </th>
 401 <th>
 402                 <p>
 403                   nearest(Segment, k)
 404                 </p>
 405               </th>
 406 <th>
 407                 <p>
 408                   nearest(Segment, k)
 409                 </p>
 410               </th>
 411 </tr></thead>
 412 <tbody><tr>
 413 <td>
 414                 <p>
 415                   <span class="inlinemediaobject"><img src="../../img/index/rtree/knn_seg_box.png" alt="knn_seg_box"></span>
 416                 </p>
 417               </td>
 418 <td>
 419                 <p>
 420                   <span class="inlinemediaobject"><img src="../../img/index/rtree/rtree_seg_knn_pt.png" alt="rtree_seg_knn_pt"></span>
 421                 </p>
 422               </td>
 423 <td>
 424                 <p>
 425                   <span class="inlinemediaobject"><img src="../../img/index/rtree/rtree_seg_knn_box.png" alt="rtree_seg_knn_box"></span>
 426                 </p>
 427               </td>
 428 <td>
 429                 <p>
 430                   <span class="inlinemediaobject"><img src="../../img/index/rtree/rtree_seg_knn_seg.png" alt="rtree_seg_knn_seg"></span>
 431                 </p>
 432               </td>
 433 <td>
 434                 <p>
 435                   <span class="inlinemediaobject"><img src="../../img/index/rtree/rtree_pt_knn_seg.png" alt="rtree_pt_knn_seg"></span>
 436                 </p>
 437               </td>
 438 </tr></tbody>
 439 </table></div>
 440 <p>
 441         To perform the knn query one must pass the nearest predicate generated by
 442         the <code class="computeroutput"><span class="identifier">nearest</span><span class="special">()</span></code>
 443         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>
 444         namespace. For non-point <code class="computeroutput">Indexable</code>s the shortest distance is
 445         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>
 446         function. The following query returns <code class="computeroutput"><span class="identifier">k</span></code>
 447         <code class="computeroutput">Value</code>s closest to some Point in space.
 448       </p>
 449 <pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span>Value<span class="special">&gt;</span> <span class="identifier">returned_values</span><span class="special">;</span>
 450 Point <span class="identifier">pt</span><span class="special">(/*...*/);</span>
 451 <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>
 452 </pre>
 453 <p>
 454         The same way different query Geometries can be used:
 455       </p>
 456 <pre class="programlisting">Box <span class="identifier">box</span><span class="special">(/*...*/);</span>
 457 <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>
 458
 459 <span class="identifier">Segment</span> <span class="identifier">seg</span><span class="special">(/*...*/);</span>
 460 <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>
 461 </pre>
 462 <h5>
 463 <a name="geometry.spatial_indexes.queries.h3"></a>
 464         <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
 465         unary predicate</a>
 466       </h5>
 467 <p>
 468         The user may pass a <code class="computeroutput"><span class="identifier">UnaryPredicate</span></code>
 469         - function, function object or lambda expression taking const reference to
 470         Value and returning bool. This object may be passed to the query in order
 471         to check if <code class="computeroutput">Value</code> should be returned by the query. To do it
 472         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>
 473         function like on the example below:
 474       </p>
 475 <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">&amp;</span> <span class="identifier">v</span><span class="special">)</span>
 476 <span class="special">{</span>
 477   <span class="keyword">return</span> <span class="identifier">v</span><span class="special">.</span><span class="identifier">is_red</span><span class="special">();</span>
 478 <span class="special">}</span>
 479
 480 <span class="keyword">struct</span> <span class="identifier">is_red_o</span>
 481 <span class="special">{</span>
 482   <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">Value</span><span class="special">&gt;</span>
 483   <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">()(</span>Value <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">v</span><span class="special">)</span>
 484   <span class="special">{</span>
 485     <span class="keyword">return</span> <span class="identifier">v</span><span class="special">.</span><span class="identifier">is_red</span><span class="special">();</span>
 486   <span class="special">}</span>
 487 <span class="special">}</span>
 488
 489 <span class="comment">// ...</span>
 490
 491 <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">&amp;&amp;</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>
 492          <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>
 493
 494 <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">&amp;&amp;</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>
 495          <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>
 496
 497 <span class="preprocessor">#ifndef</span> <span class="identifier">BOOST_NO_CXX11_LAMBDAS</span>
 498 <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">&amp;&amp;</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">&amp;</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>
 499          <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>
 500 <span class="preprocessor">#endif</span>
 501 </pre>
 502 <p>
 503         <code class="computeroutput"><span class="identifier">satisfies</span><span class="special">()</span></code>
 504         may be negated, e.g.:
 505       </p>
 506 <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">&amp;</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>
 507 <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">&amp;</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>
 508
 509 <span class="comment">// ...</span>
 510
 511 <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">&amp;&amp;</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>
 512          <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>
 513 <span class="comment">// the same as</span>
 514 <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">&amp;&amp;</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>
 515          <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>
 516 </pre>
 517 <h5>
 518 <a name="geometry.spatial_indexes.queries.h4"></a>
 519         <span class="phrase"><a name="geometry.spatial_indexes.queries.passing_a_set_of_predicates"></a></span><a class="link" href="queries.html#geometry.spatial_indexes.queries.passing_a_set_of_predicates">Passing
 520         a set of predicates</a>
 521       </h5>
 522 <p>
 523         It's possible to use some number of predicates in one query by connecting
 524         them with <code class="computeroutput"><span class="keyword">operator</span><span class="special">&amp;&amp;</span></code>
 525         e.g. <code class="computeroutput"><span class="identifier">Pred1</span> <span class="special">&amp;&amp;</span>
 526         <span class="identifier">Pred2</span> <span class="special">&amp;&amp;</span>
 527         <span class="identifier">Pred3</span> <span class="special">&amp;&amp;</span>
 528         <span class="special">...</span></code>.
 529       </p>
 530 <p>
 531         These predicates are connected by logical AND. Passing all predicates together
 532         not only makes possible to construct advanced queries but is also faster
 533         than separate calls because the tree is traversed only once. Traversing is
 534         continued and <code class="computeroutput"><span class="identifier">Value</span></code>s are
 535         returned only if all predicates are met. Predicates are checked left-to-right
 536         so placing most restrictive predicates first should accelerate the search.
 537       </p>
 538 <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">&amp;&amp;</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>
 539          <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>
 540
 541 <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">&amp;&amp;</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">&amp;&amp;</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>
 542          <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>
 543 </pre>
 544 <p>
 545         Of course it's possible to connect different types of predicates together.
 546       </p>
 547 <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">&amp;&amp;</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>
 548
 549 <span class="identifier">BOOST_FOREACH</span><span class="special">(</span><span class="identifier">Value</span> <span class="special">&amp;</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">&amp;&amp;</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>
 550   <span class="special">;</span> <span class="comment">// do something with v</span>
 551 </pre>
 552 <h5>
 553 <a name="geometry.spatial_indexes.queries.h5"></a>
 554         <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
 555         queries</a>
 556       </h5>
 557 <p>
 558         The query performed using query iterators may be paused and resumed if needed,
 559         e.g. when the query takes too long, or may be stopped at some point, when
 560         all interesting values were gathered. The query iterator is returned by
 561         <code class="computeroutput"><span class="identifier">qbegin</span><span class="special">()</span></code>
 562         member function which requires passing predicates, like <code class="computeroutput"><span class="identifier">query</span><span class="special">()</span></code> member function.
 563       </p>
 564 <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>
 565       <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>
 566 <span class="special">{</span>
 567     <span class="comment">// do something with value</span>
 568     <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>
 569         <span class="keyword">break</span><span class="special">;</span>
 570 <span class="special">}</span>
 571 </pre>
 572 <div class="note"><table border="0" summary="Note">
 573 <tr>
 574 <td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../../../../doc/src/images/note.png"></td>
 575 <th align="left">Note</th>
 576 </tr>
 577 <tr><td align="left" valign="top"><p>
 578           In the case of iterative k-NN queries it's guaranteed to iterate over the
 579           closest <code class="computeroutput">Value</code>s first.
 580         </p></td></tr>
 581 </table></div>
 582 <div class="warning"><table border="0" summary="Warning">
 583 <tr>
 584 <td rowspan="2" align="center" valign="top" width="25"><img alt="[Warning]" src="../../../../../../doc/src/images/warning.png"></td>
 585 <th align="left">Warning</th>
 586 </tr>
 587 <tr><td align="left" valign="top"><p>
 588           The modification of the <code class="computeroutput"><span class="identifier">rtree</span></code>,
 589           e.g. insertion or removal of <code class="computeroutput">Value</code>s may invalidate the iterators.
 590         </p></td></tr>
 591 </table></div>
 592 <h5>
 593 <a name="geometry.spatial_indexes.queries.h6"></a>
 594         <span class="phrase"><a name="geometry.spatial_indexes.queries.inserting_query_results_into_the_other_r_tree"></a></span><a class="link" href="queries.html#geometry.spatial_indexes.queries.inserting_query_results_into_the_other_r_tree">Inserting
 595         query results into the other R-tree</a>
 596       </h5>
 597 <p>
 598         There are several ways of inserting Values returned by a query to the other
 599         R-tree container. The most basic way is creating a temporary container for
 600         Values and insert them later.
 601       </p>
 602 <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>
 603 <span class="keyword">typedef</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special">&lt;</span><span class="identifier">Box</span><span class="special">,</span> <span class="keyword">int</span><span class="special">&gt;</span> Value<span class="special">;</span>
 604 <span class="keyword">typedef</span> <span class="identifier">bgi</span><span class="special">::</span><span class="identifier">rtree</span><span class="special">&lt;</span> Value<span class="special">,</span> <span class="identifier">bgi</span><span class="special">::</span><span class="identifier">linear</span><span class="special">&lt;</span><span class="number">32</span><span class="special">,</span> <span class="number">8</span><span class="special">&gt;</span> <span class="special">&gt;</span> <span class="identifier">RTree</span><span class="special">;</span>
 605
 606 <span class="identifier">RTree</span> <span class="identifier">rt1</span><span class="special">;</span>
 607 <span class="comment">/* some inserting into the tree */</span>
 608
 609 <span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">Value</span><span class="special">&gt;</span> <span class="identifier">result</span><span class="special">;</span>
 610 <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>
 611 <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>
 612 </pre>
 613 <p>
 614         However there are better ways. One of these methods is mentioned in the "Creation
 615         and modification" section. The insert iterator may be passed directly
 616         into the query.
 617       </p>
 618 <pre class="programlisting"><span class="identifier">RTree</span> <span class="identifier">rt3</span><span class="special">;</span>
 619 <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>
 620 </pre>
 621 <p>
 622         If you're a user of Boost.Range you'll appreciate the third option. You may
 623         pass the result Range directly into the constructor or <code class="computeroutput"><span class="identifier">insert</span><span class="special">()</span></code> member function.
 624       </p>
 625 <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>
 626 </pre>
 627 </div>
 628 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 629 <td align="left"></td>
 630 <td align="right"><div class="copyright-footer">Copyright &#169; 2009-2014 Barend Gehrels, Bruno Lalande, Mateusz Loskot, Adam
 631       Wulkiewicz, Oracle and/or its affiliates<p>
 632         Distributed under the Boost Software License, Version 1.0. (See accompanying
 633         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>)
 634       </p>
 635 </div></td>
 636 </tr></table>
 637 <hr>
 638 <div class="spirit-nav">
 639 <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>
 640 </div>
 641 </body>
 642 </html>