libs/geometry/doc/html/geometry/spatial_indexes/rtree_quickstart.html

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   4 <title>Quick Start</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="introduction.html" title="Introduction">
  10 <link rel="next" href="creation_and_modification.html" title="Creation and Modification">
  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="introduction.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="creation_and_modification.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.rtree_quickstart"></a><a class="link" href="rtree_quickstart.html" title="Quick Start">Quick Start</a>
  28 </h3></div></div></div>
  29 <p>
  30         This Quick Start section shows simple way to creating a typical R-tree and
  31         perform spatial query.
  32       </p>
  33 <p>
  34         The code below assumes that following files are included and namespaces used.
  35       </p>
  36 <p>
  37 </p>
  38 <pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">geometry</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
  39 <span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">geometry</span><span class="special">/</span><span class="identifier">geometries</span><span class="special">/</span><span class="identifier">point</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
  40 <span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">geometry</span><span class="special">/</span><span class="identifier">geometries</span><span class="special">/</span><span class="identifier">box</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
  41
  42 <span class="preprocessor">#include</span> <span class="special">&lt;</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><span class="identifier">rtree</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
  43
  44 <span class="comment">// to store queries results</span>
  45 <span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">vector</span><span class="special">&gt;</span>
  46
  47 <span class="comment">// just for output</span>
  48 <span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">iostream</span><span class="special">&gt;</span>
  49 <span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">foreach</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
  50
  51 <span class="keyword">namespace</span> <span class="identifier">bg</span> <span class="special">=</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">geometry</span><span class="special">;</span>
  52 <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>
  53 </pre>
  54 <p>
  55       </p>
  56 <p>
  57         Typically you'll store e.g. <code class="computeroutput"><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="identifier">MyGeometryId</span><span class="special">&gt;</span></code> in the R-tree. <code class="computeroutput"><span class="identifier">MyGeometryId</span></code>
  58         will be some identifier of a complex <code class="computeroutput"><span class="identifier">Geometry</span></code>
  59         stored in other container, e.g. index type of a <code class="computeroutput"><span class="identifier">Polygon</span></code>
  60         stored in the vector or an iterator of list of <code class="computeroutput"><span class="identifier">Ring</span></code>s.
  61         To keep it simple to define <code class="computeroutput"><span class="identifier">Value</span></code>
  62         we will use predefined Box and unsigned int.
  63       </p>
  64 <p>
  65 </p>
  66 <pre class="programlisting"><span class="keyword">typedef</span> <span class="identifier">bg</span><span class="special">::</span><span class="identifier">model</span><span class="special">::</span><span class="identifier">point</span><span class="special">&lt;</span><span class="keyword">float</span><span class="special">,</span> <span class="number">2</span><span class="special">,</span> <span class="identifier">bg</span><span class="special">::</span><span class="identifier">cs</span><span class="special">::</span><span class="identifier">cartesian</span><span class="special">&gt;</span> <span class="identifier">point</span><span class="special">;</span>
  67 <span class="keyword">typedef</span> <span class="identifier">bg</span><span class="special">::</span><span class="identifier">model</span><span class="special">::</span><span class="identifier">box</span><span class="special">&lt;</span><span class="identifier">point</span><span class="special">&gt;</span> <span class="identifier">box</span><span class="special">;</span>
  68 <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">unsigned</span><span class="special">&gt;</span> <span class="identifier">value</span><span class="special">;</span>
  69 </pre>
  70 <p>
  71       </p>
  72 <p>
  73         R-tree may be created using various algorithm and parameters. You should
  74         choose the algorithm you'll find the best for your purpose. In this example
  75         we will use quadratic algorithm. Parameters are passed as template parameters.
  76         Maximum number of elements in nodes is set to 16.
  77       </p>
  78 <p>
  79 </p>
  80 <pre class="programlisting"><span class="comment">// create the rtree using default constructor</span>
  81 <span class="identifier">bgi</span><span class="special">::</span><span class="identifier">rtree</span><span class="special">&lt;</span> <span class="identifier">value</span><span class="special">,</span> <span class="identifier">bgi</span><span class="special">::</span><span class="identifier">quadratic</span><span class="special">&lt;</span><span class="number">16</span><span class="special">&gt;</span> <span class="special">&gt;</span> <span class="identifier">rtree</span><span class="special">;</span>
  82 </pre>
  83 <p>
  84       </p>
  85 <p>
  86         Typically <code class="computeroutput"><span class="identifier">Value</span></code>s will be
  87         generated in a loop from e.g. <code class="computeroutput"><span class="identifier">Polygon</span></code>s
  88         stored in some other container. In this case <code class="computeroutput"><span class="identifier">Box</span></code>
  89         objects will probably be created with <code class="computeroutput"><span class="identifier">geometry</span><span class="special">::</span><span class="identifier">envelope</span><span class="special">()</span></code> function. But to keep it simple lets just
  90         generate some boxes manually and insert them into the R-tree by using <code class="computeroutput"><span class="identifier">insert</span><span class="special">()</span></code>
  91         method.
  92       </p>
  93 <p>
  94 </p>
  95 <pre class="programlisting"><span class="comment">// create some values</span>
  96 <span class="keyword">for</span> <span class="special">(</span> <span class="keyword">unsigned</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span> <span class="special">;</span> <span class="identifier">i</span> <span class="special">&lt;</span> <span class="number">10</span> <span class="special">;</span> <span class="special">++</span><span class="identifier">i</span> <span class="special">)</span>
  97 <span class="special">{</span>
  98     <span class="comment">// create a box</span>
  99     <span class="identifier">box</span> <span class="identifier">b</span><span class="special">(</span><span class="identifier">point</span><span class="special">(</span><span class="identifier">i</span> <span class="special">+</span> <span class="number">0.0f</span><span class="special">,</span> <span class="identifier">i</span> <span class="special">+</span> <span class="number">0.0f</span><span class="special">),</span> <span class="identifier">point</span><span class="special">(</span><span class="identifier">i</span> <span class="special">+</span> <span class="number">0.5f</span><span class="special">,</span> <span class="identifier">i</span> <span class="special">+</span> <span class="number">0.5f</span><span class="special">));</span>
 100     <span class="comment">// insert new value</span>
 101     <span class="identifier">rtree</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">make_pair</span><span class="special">(</span><span class="identifier">b</span><span class="special">,</span> <span class="identifier">i</span><span class="special">));</span>
 102 <span class="special">}</span>
 103 </pre>
 104 <p>
 105       </p>
 106 <p>
 107         There are various types of spatial queries that may be performed, they can
 108         be even combined together in one call. For simplicity, we use the default
 109         one. The following query return values intersecting a box. The sequence of
 110         <code class="computeroutput"><span class="identifier">Values</span></code> in the result is not
 111         specified.
 112       </p>
 113 <p>
 114 </p>
 115 <pre class="programlisting"><span class="comment">// find values intersecting some area defined by a box</span>
 116 <span class="identifier">box</span> <span class="identifier">query_box</span><span class="special">(</span><span class="identifier">point</span><span class="special">(</span><span class="number">0</span><span class="special">,</span> <span class="number">0</span><span class="special">),</span> <span class="identifier">point</span><span class="special">(</span><span class="number">5</span><span class="special">,</span> <span class="number">5</span><span class="special">));</span>
 117 <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_s</span><span class="special">;</span>
 118 <span class="identifier">rtree</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">query_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_s</span><span class="special">));</span>
 119 </pre>
 120 <p>
 121       </p>
 122 <p>
 123         Other type of query is k-nearest neighbor search. It returns some number
 124         of values nearest to some point in space. The default knn query may be performed
 125         as follows. The sequence of <code class="computeroutput"><span class="identifier">Values</span></code>
 126         in the result is not specified.
 127       </p>
 128 <p>
 129 </p>
 130 <pre class="programlisting"><span class="comment">// find 5 nearest values to a point</span>
 131 <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_n</span><span class="special">;</span>
 132 <span class="identifier">rtree</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">point</span><span class="special">(</span><span class="number">0</span><span class="special">,</span> <span class="number">0</span><span class="special">),</span> <span class="number">5</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_n</span><span class="special">));</span>
 133 </pre>
 134 <p>
 135       </p>
 136 <p>
 137         At the end we'll print results.
 138       </p>
 139 <p>
 140 </p>
 141 <pre class="programlisting"><span class="comment">// display results</span>
 142 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special">&lt;&lt;</span> <span class="string">"spatial query box:"</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span><span class="special">;</span>
 143 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special">&lt;&lt;</span> <span class="identifier">bg</span><span class="special">::</span><span class="identifier">wkt</span><span class="special">&lt;</span><span class="identifier">box</span><span class="special">&gt;(</span><span class="identifier">query_box</span><span class="special">)</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span><span class="special">;</span>
 144 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special">&lt;&lt;</span> <span class="string">"spatial query result:"</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span><span class="special">;</span>
 145 <span class="identifier">BOOST_FOREACH</span><span class="special">(</span><span class="identifier">value</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">v</span><span class="special">,</span> <span class="identifier">result_s</span><span class="special">)</span>
 146     <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special">&lt;&lt;</span> <span class="identifier">bg</span><span class="special">::</span><span class="identifier">wkt</span><span class="special">&lt;</span><span class="identifier">box</span><span class="special">&gt;(</span><span class="identifier">v</span><span class="special">.</span><span class="identifier">first</span><span class="special">)</span> <span class="special">&lt;&lt;</span> <span class="string">" - "</span> <span class="special">&lt;&lt;</span> <span class="identifier">v</span><span class="special">.</span><span class="identifier">second</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span><span class="special">;</span>
 147
 148 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special">&lt;&lt;</span> <span class="string">"knn query point:"</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span><span class="special">;</span>
 149 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special">&lt;&lt;</span> <span class="identifier">bg</span><span class="special">::</span><span class="identifier">wkt</span><span class="special">&lt;</span><span class="identifier">point</span><span class="special">&gt;(</span><span class="identifier">point</span><span class="special">(</span><span class="number">0</span><span class="special">,</span> <span class="number">0</span><span class="special">))</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span><span class="special">;</span>
 150 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special">&lt;&lt;</span> <span class="string">"knn query result:"</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span><span class="special">;</span>
 151 <span class="identifier">BOOST_FOREACH</span><span class="special">(</span><span class="identifier">value</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">v</span><span class="special">,</span> <span class="identifier">result_n</span><span class="special">)</span>
 152     <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special">&lt;&lt;</span> <span class="identifier">bg</span><span class="special">::</span><span class="identifier">wkt</span><span class="special">&lt;</span><span class="identifier">box</span><span class="special">&gt;(</span><span class="identifier">v</span><span class="special">.</span><span class="identifier">first</span><span class="special">)</span> <span class="special">&lt;&lt;</span> <span class="string">" - "</span> <span class="special">&lt;&lt;</span> <span class="identifier">v</span><span class="special">.</span><span class="identifier">second</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span><span class="special">;</span>
 153 </pre>
 154 <p>
 155       </p>
 156 <h4>
 157 <a name="geometry.spatial_indexes.rtree_quickstart.h0"></a>
 158         <span class="phrase"><a name="geometry.spatial_indexes.rtree_quickstart.more"></a></span><a class="link" href="rtree_quickstart.html#geometry.spatial_indexes.rtree_quickstart.more">More</a>
 159       </h4>
 160 <p>
 161         More information about the R-tree implementation, other algorithms and queries
 162         may be found in other parts of this documentation.
 163       </p>
 164 </div>
 165 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 166 <td align="left"></td>
 167 <td align="right"><div class="copyright-footer">Copyright &#169; 2009-2014 Barend Gehrels, Bruno Lalande, Mateusz Loskot, Adam
 168       Wulkiewicz, Oracle and/or its affiliates<p>
 169         Distributed under the Boost Software License, Version 1.0. (See accompanying
 170         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>)
 171       </p>
 172 </div></td>
 173 </tr></table>
 174 <hr>
 175 <div class="spirit-nav">
 176 <a accesskey="p" href="introduction.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="creation_and_modification.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
 177 </div>
 178 </body>
 179 </html>