Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r81539 - in sandbox-branches/geometry/index_dev: doc/html doc/html/geometry_index doc/html/geometry_index/r_tree doc/images doc/rtree doc/rtree/images doc/src/examples/rtree tests
From: adam.wulkiewicz_at_[hidden]
Date: 2012-11-25 15:56:42

Author: awulkiew
Date: 2012-11-25 15:56:38 EST (Sun, 25 Nov 2012)
New Revision: 81539
URL: http://svn.boost.org/trac/boost/changeset/81539

Log:
Rtree docs and sample modified.

Rtree introduction expanded.
Quickstart improved.
Added:
   sandbox-branches/geometry/index_dev/doc/images/
   sandbox-branches/geometry/index_dev/doc/images/disjoint.png (contents, props changed)
   sandbox-branches/geometry/index_dev/doc/images/intersects.png (contents, props changed)
   sandbox-branches/geometry/index_dev/doc/images/knn.png (contents, props changed)
   sandbox-branches/geometry/index_dev/doc/images/knn_cover.png (contents, props changed)
   sandbox-branches/geometry/index_dev/doc/images/knn_inters.png (contents, props changed)
   sandbox-branches/geometry/index_dev/doc/images/linear.png (contents, props changed)
   sandbox-branches/geometry/index_dev/doc/images/overlaps.png (contents, props changed)
   sandbox-branches/geometry/index_dev/doc/images/quadratic.png (contents, props changed)
   sandbox-branches/geometry/index_dev/doc/images/rstar.png (contents, props changed)
   sandbox-branches/geometry/index_dev/doc/images/within.png (contents, props changed)
Removed:
   sandbox-branches/geometry/index_dev/doc/rtree/images/
Text files modified:
   sandbox-branches/geometry/index_dev/doc/html/geometry_index/introduction.html | 2
   sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree.html | 2
   sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/creation_and_modification.html | 6
   sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/exception_safety.html | 12 +-
   sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/introduction.html | 191 ++++++++++++++++++++++++++++++++++++++-
   sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/nearest_neighbours_queries.html | 2
   sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/rtree_quickstart.html | 89 +++++++++++++-----
   sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/spatial_queries.html | 2
   sandbox-branches/geometry/index_dev/doc/html/index.html | 4
   sandbox-branches/geometry/index_dev/doc/rtree/introduction.qbk | 44 ++++++++
   sandbox-branches/geometry/index_dev/doc/rtree/quickstart.qbk | 26 +++-
   sandbox-branches/geometry/index_dev/doc/src/examples/rtree/quick_start.cpp | 42 ++++++--
   sandbox-branches/geometry/index_dev/tests/additional_speed.cpp | 2
   13 files changed, 356 insertions(+), 68 deletions(-)

Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/introduction.html
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/html/geometry_index/introduction.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/geometry_index/introduction.html 2012-11-25 15:56:38 EST (Sun, 25 Nov 2012)
@@ -3,7 +3,7 @@
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Introduction</title>
<link rel="stylesheet" href="http://www.boost.org/doc/libs/release/doc/src/boostbook.css" type="text/css">
-<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
<link rel="home" href="../index.html" title="Chapter 1. Geometry Index">
<link rel="up" href="../index.html" title="Chapter 1. Geometry Index">
<link rel="prev" href="../index.html" title="Chapter 1. Geometry Index">

Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree.html
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree.html 2012-11-25 15:56:38 EST (Sun, 25 Nov 2012)
@@ -3,7 +3,7 @@
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>R-tree</title>
<link rel="stylesheet" href="http://www.boost.org/doc/libs/release/doc/src/boostbook.css" type="text/css">
-<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
<link rel="home" href="../index.html" title="Chapter 1. Geometry Index">
<link rel="up" href="../index.html" title="Chapter 1. Geometry Index">
<link rel="prev" href="introduction.html" title="Introduction">

Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/creation_and_modification.html
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/creation_and_modification.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/creation_and_modification.html 2012-11-25 15:56:38 EST (Sun, 25 Nov 2012)
@@ -3,7 +3,7 @@
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Creation and modification</title>
<link rel="stylesheet" href="http://www.boost.org/doc/libs/release/doc/src/boostbook.css" type="text/css">
-<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
<link rel="home" href="../../index.html" title="Chapter 1. Geometry Index">
<link rel="up" href="../r_tree.html" title="R-tree">
<link rel="prev" href="rtree_quickstart.html" title="Quick Start">
@@ -51,7 +51,7 @@
 
<pre class="programlisting">rtree<Value, Parameters, Translator, Allocator>
</pre>
-<div class="itemizedlist"><ul class="itemizedlist" type="disc">
+<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
 <code class="computeroutput">Value</code> - type of object which will be stored in the container.
 </li>
@@ -88,7 +88,7 @@
 or <code class="computeroutput">std::pair<...></code>
 <code class="computeroutput">Value</code>s.
 
-<div class="itemizedlist"><ul class="itemizedlist" type="disc">
+<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
 <code class="computeroutput">Indexable = Point
 | Box</code>

Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/exception_safety.html
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/exception_safety.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/exception_safety.html 2012-11-25 15:56:38 EST (Sun, 25 Nov 2012)
@@ -3,7 +3,7 @@
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Exception safety</title>
<link rel="stylesheet" href="http://www.boost.org/doc/libs/release/doc/src/boostbook.css" type="text/css">
-<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
<link rel="home" href="../../index.html" title="Chapter 1. Geometry Index">
<link rel="up" href="../r_tree.html" title="R-tree">
<link rel="prev" href="nearest_neighbours_queries.html" title="Nearest neighbours queries">
@@ -28,7 +28,7 @@

 In order to be exception-safe the R-tree requires:
 
-<div class="itemizedlist"><ul class="itemizedlist" type="disc">
+<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
 Nonthrowing destructor of the <code class="computeroutput">Value</code>.
 </li>
@@ -155,7 +155,7 @@
<td>
 
 nothrow or strong
- [<a name="geometry_index.r_tree.exception_safety.f0" href="#ftn.geometry_index.r_tree.exception_safety.f0" class="footnote">a</a>]
+ [a]</a>
 
 </td>
</tr>
@@ -308,7 +308,7 @@
<td>
 
 nothrow or strong
- [<a name="geometry_index.r_tree.exception_safety.f1" href="#ftn.geometry_index.r_tree.exception_safety.f1" class="footnote">b</a>]
+ [b]</a>
 
 </td>
</tr>
@@ -350,10 +350,10 @@
</tr>
</tbody>
<tbody class="footnotes"><tr><td colspan="2">
-<div class="footnote">[<a id="ftn.geometry_index.r_tree.exception_safety.f0" href="#geometry_index.r_tree.exception_safety.f0" class="para">a</a>] 
+<div id="ftn.geometry_index.r_tree.exception_safety.f0" class="footnote">^[a]
 nothrow - if allocators are equal, strong - otherwise
 </div>
-<div class="footnote">[<a id="ftn.geometry_index.r_tree.exception_safety.f1" href="#geometry_index.r_tree.exception_safety.f1" class="para">b</a>] 
+<div id="ftn.geometry_index.r_tree.exception_safety.f1" class="footnote">^[b]
 nothrow - if <code class="computeroutput">CoordinateType</code>
 has nonthrowing copy constructor, strong
 - otherwise

Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/introduction.html
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/introduction.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/introduction.html 2012-11-25 15:56:38 EST (Sun, 25 Nov 2012)
@@ -3,7 +3,7 @@
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Introduction</title>
<link rel="stylesheet" href="http://www.boost.org/doc/libs/release/doc/src/boostbook.css" type="text/css">
-<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
<link rel="home" href="../../index.html" title="Chapter 1. Geometry Index">
<link rel="up" href="../r_tree.html" title="R-tree">
<link rel="prev" href="../r_tree.html" title="R-tree">
@@ -27,12 +27,191 @@
<a name="geometry_index.r_tree.introduction"></a><a class="link" href="introduction.html" title="Introduction">Introduction</a>
</h3></div></div></div>

- R-tree is a self-balancing search tree. Each tree's node store a box descring
- the space occupied by children nodes. At the bottom of the structure, there
- are leaf-nodes which contains values (geometric objects representations).
- Minimal and maximal numbers of values/children which may be stored inside
- each node are user defined.
+ R-tree is a tree data structure used for spatial searching. It was proposed
+ by Antonin Guttman in 1984 [1]</a> as an expansion of B-tree for multi-dimensional data. It may
+ be used to store points or volumetric data in order to perform a spatial
+ query later. This query may return objects that are inside some area or are
+ close to some point in space.

+
+ The R-tree structure is presented on the image below. Each R-tree's node
+ store a box descring the space occupied by its children nodes. At the bottom
+ of the structure, there are leaf-nodes which contains values (geometric objects
+ representations).
+ 
+
+ <img src="../../../images/rstar.png" alt="rstar">
+ 
+
+ The number of maximum and mininimum node's elements must be specified by
+ the user. If the number of elements reaches it's maximum the new node is
+ created and elements are split between nodes. If the number of elements in
+ node is too small, the node is deleted and elements are reinserted into the
+ tree.
+ 
+
+ The R-tree is a self-balanced data structure. The key part of balancing algorithm
+ is node splitting algorithm mentioned before [2]</a> [3]</a>. Each algorithm would produce different splits so the internal
+ structure of a tree may be different for each one of them. In general more
+ complex algorithms analyses elements better and produces less overlapping
+ nodes. This is a "better" split because later, in the searching
+ process less nodes must be traversed in order to find desired obejcts. On
+ the other hand more complex analysis takes more time. In general faster inserting
+ will result in slower searching and vice versa. Example structures of trees
+ created by use of three different algorithms and operations time are presented
+ below.
+ 
+<div class="informaltable"><table class="table">
+<colgroup>
+<col>
+<col>
+<col>
+<col>
+</colgroup>
+<thead><tr>
+<th>
+ </th>
+<th>
+ 
+ linear algorithm
+ 
+ </th>
+<th>
+ 
+ quadratic algorithm
+ 
+ </th>
+<th>
+ 
+ R*-tree
+ 
+ </th>
+</tr></thead>
+<tbody>
+<tr>
+<td>
+ 
+ Structure
+ 
+ </td>
+<td>
+ 
+ <img src="../../../images/linear.png" alt="linear">
+ 
+ </td>
+<td>
+ 
+ <img src="../../../images/quadratic.png" alt="quadratic">
+ 
+ </td>
+<td>
+ 
+ <img src="../../../images/rstar.png" alt="rstar">
+ 
+ </td>
+</tr>
+<tr>
+<td>
+ 
+ 1M Values inserts
+ 
+ </td>
+<td>
+ 
+ 1.85s
+ 
+ </td>
+<td>
+ 
+ 3.10s
+ 
+ </td>
+<td>
+ 
+ 24.52s
+ 
+ </td>
+</tr>
+<tr>
+<td>
+ 
+ 1M spatial queries
+ 
+ </td>
+<td>
+ 
+ 8.60s
+ 
+ </td>
+<td>
+ 
+ 2.74s
+ 
+ </td>
+<td>
+ 
+ 1.31s
+ 
+ </td>
+</tr>
+<tr>
+<td>
+ 
+ 100k knn queries
+ 
+ </td>
+<td>
+ 
+ 3.49s
+ 
+ </td>
+<td>
+ 
+ 1.59s
+ 
+ </td>
+<td>
+ 
+ 0.84s
+ 
+ </td>
+</tr>
+</tbody>
+</table></div>
+
+ Key features of this implementation of the R-tree are:
+ 
+<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
+<li class="listitem">
+ three different creation algorithms - linear, quadratic or rstar,
+ </li>
+<li class="listitem">
+ parameters (including maximal and minimal number of elements) may be
+ passed as compile- or run-time parameters - compile-time version is faster,
+ </li>
+<li class="listitem">
+ capable to store arbitrary Value type,
+ </li>
+<li class="listitem">
+ sophisticated queries - e.g. search for 5 nearest values intersecting
+ some region but not within the other one.
+ </li>
+</ul></div>
+<div class="footnotes">
+ <hr style="width:100; align:left;">
+<div id="ftn.geometry_index.r_tree.introduction.f0" class="footnote">^[1]
+ Guttman, A. (1984). R-Trees: A Dynamic Index Structure for Spatial
+ Searching footnote
+ </div>
+<div id="ftn.geometry_index.r_tree.introduction.f1" class="footnote">^[2]
+ Greene, D. (1989). An implementation and performance analysis
+ of spatial data access methods
+ </div>
+<div id="ftn.geometry_index.r_tree.introduction.f2" class="footnote">^[3]
+ Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). The
+ R*-tree: an efficient and robust access method for points and rectangles
+ </div>
+</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>

Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/nearest_neighbours_queries.html
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/nearest_neighbours_queries.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/nearest_neighbours_queries.html 2012-11-25 15:56:38 EST (Sun, 25 Nov 2012)
@@ -3,7 +3,7 @@
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Nearest neighbours queries</title>
<link rel="stylesheet" href="http://www.boost.org/doc/libs/release/doc/src/boostbook.css" type="text/css">
-<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
<link rel="home" href="../../index.html" title="Chapter 1. Geometry Index">
<link rel="up" href="../r_tree.html" title="R-tree">
<link rel="prev" href="spatial_queries.html" title="Spatial queries">

Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/rtree_quickstart.html
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/rtree_quickstart.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/rtree_quickstart.html 2012-11-25 15:56:38 EST (Sun, 25 Nov 2012)
@@ -3,7 +3,7 @@
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Quick Start</title>
<link rel="stylesheet" href="http://www.boost.org/doc/libs/release/doc/src/boostbook.css" type="text/css">
-<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
<link rel="home" href="../../index.html" title="Chapter 1. Geometry Index">
<link rel="up" href="../r_tree.html" title="R-tree">
<link rel="prev" href="introduction.html" title="Introduction">
@@ -35,23 +35,32 @@
 


-<pre class="programlisting">#include <vector>
-
-#include <boost/geometry.hpp>
+<pre class="programlisting">#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/box.hpp>

#include <boost/geometry/extensions/index/rtree/rtree.hpp>

+// to store queries results
+#include <vector>
+
+// just for output
+#include <iostream>
+#include <boost/foreach.hpp>
+
namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;
</pre>

 

- It is possible to store user-defined types in the R-tree. To keep it simple
- we will use predefined Point
- and Box.
+ Typically you'll store e.g. <code class="computeroutput">std::pair<Box, MyGeometryId></code> in the R-tree. <code class="computeroutput">MyGeometryId</code>
+ will be some indentifier of a complex <code class="computeroutput">Geometry</code>
+ stored in other container, e.g. index type of a <code class="computeroutput">Polygon</code>
+ stored in the vector or an iterator of list of <code class="computeroutput">Ring</code>s.
+ To keep it simple to define <code class="computeroutput">Value</code>
+ we will use predefined Box
+ and unsigned int.
 


@@ -62,54 +71,86 @@

 

- R-tree may be created using various algorithm and parameters. In this example
- we will use quadratic algorithm. Maximum number of elements in nodes are
- set to 32, minimum to 8.
+ R-tree may be created using various algorithm and parameters. You should
+ choose the algorithm you'll find the best for your purpose. In this example
+ we will use quadratic algorithm. Parameters are passed as template parameters.
+ Maximum number of elements in nodes are set to 32, minimum to 8.
 


-<pre class="programlisting">bgi::rtree< value, bgi::quadratic<32, 8> > rtree;
+<pre class="programlisting">// create the rtree using default constructor
+bgi::rtree< value, bgi::quadratic<32, 8> > rtree;
</pre>

 

- Inserting values into the R-tree may be done by calling insert() method.
+ Typically <code class="computeroutput">Value</code>s will be
+ generated in a loop from e.g. <code class="computeroutput">Polygon</code>s
+ stored in some other container. In this case <code class="computeroutput">Box</code>
+ objects will probably be created with <code class="computeroutput">geometry::make_envelope()</code> function. But to keep it simple lets just
+ generate some boxes manually and insert them into the R-tree by using <code class="computeroutput">insert()</code>
+ method.
 


-<pre class="programlisting">// create some box
-// this typically will be an envelope of some geometry
-box b(point(0, 0), point(10, 10));
-// insert new value
-rtree.insert(std::make_pair(b, 0));
+<pre class="programlisting">// create some values
+for ( unsigned i = 0 ; i < 10 ; ++i )
+{
+ // create a box
+ box b(point(i, i), point(i + 0.5f, i + 0.5f));
+ // insert new value
+ rtree.insert(std::make_pair(b, i));
+}
</pre>

 

 There are various types of spatial queries that may be performed, they can
- be even combined together in one call. For simplicity, default one is used.
+ be even combined together in one call. For simplicity, we use the default
+ one. The following query return values intersecting a box. The sequence of
+ <code class="computeroutput">Values</code> in the result is not
+ specified.
 


-<pre class="programlisting">// find values intersecting a box
-std::vector<value> result;
-rtree.spatial_query(b, std::back_inserter(result));
+<pre class="programlisting">// find values intersecting some area defined by a box
+box query_box(point(0, 0), point(5, 5));
+std::vector<value> result_s;
+rtree.spatial_query(query_box, std::back_inserter(result_s));
</pre>

 

- Default k-nearest neighbors query may be performed as follows.
+ Other type of query is k-nearest neighbor search. It returns some number
+ of values nearest to some point in space. The default knn query may be performed
+ as follows. The sequence of <code class="computeroutput">Values</code>
+ in the result is not specified.
 


<pre class="programlisting">// find 5 nearest values to a point
-rtree.nearest_query(point(0, 0), 5, std::back_inserter(result));
+std::vector<value> result_n;
+rtree.nearest_query(point(0, 0), 5, std::back_inserter(result_n));
+</pre>
+
+ 
+
+ At the end we'll print results.
+ 
+
+
+<pre class="programlisting">std::cout << "spatial query result:" << std::endl;
+BOOST_FOREACH(value const& v, result_s)
+ std::cout << bg::wkt<box>(v.first) << " - " << v.second << std::endl;
+std::cout << "knn query result:" << std::endl;
+BOOST_FOREACH(value const& v, result_n)
+ std::cout << bg::wkt<box>(v.first) << " - " << v.second << std::endl;
</pre>

 
<h4>
<a name="geometry_index.r_tree.rtree_quickstart.h0"></a>
- <a name="geometry_index.r_tree.rtree_quickstart.more"></a><a class="link" href="rtree_quickstart.html#geometry_index.r_tree.rtree_quickstart.more">More</a>
+ <a name="geometry_index.r_tree.rtree_quickstart.more"></a><a class="link" href="rtree_quickstart.html#geometry_index.r_tree.rtree_quickstart.more">More</a>
 </h4>

 More information about the R-tree implementation, other algorithms and queries

Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/spatial_queries.html
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/spatial_queries.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/spatial_queries.html 2012-11-25 15:56:38 EST (Sun, 25 Nov 2012)
@@ -3,7 +3,7 @@
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Spatial queries</title>
<link rel="stylesheet" href="http://www.boost.org/doc/libs/release/doc/src/boostbook.css" type="text/css">
-<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
<link rel="home" href="../../index.html" title="Chapter 1. Geometry Index">
<link rel="up" href="../r_tree.html" title="R-tree">
<link rel="prev" href="creation_and_modification.html" title="Creation and modification">

Modified: sandbox-branches/geometry/index_dev/doc/html/index.html
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/html/index.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/index.html 2012-11-25 15:56:38 EST (Sun, 25 Nov 2012)
@@ -3,7 +3,7 @@
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Chapter 1. Geometry Index</title>
<link rel="stylesheet" href="http://www.boost.org/doc/libs/release/doc/src/boostbook.css" type="text/css">
-<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
<link rel="home" href="index.html" title="Chapter 1. Geometry Index">
<link rel="next" href="geometry_index/introduction.html" title="Introduction">
</head>
@@ -56,7 +56,7 @@
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
-<td align="left">Last revised: November 24, 2012 at 22:04:48 GMT</td>
+<td align="left">Last revised: November 25, 2012 at 20:52:29 GMT</td>
<td align="right"><div class="copyright-footer"></div></td>
</tr></table>
<hr>

Added: sandbox-branches/geometry/index_dev/doc/images/disjoint.png
==============================================================================
Binary file. No diff available.

Added: sandbox-branches/geometry/index_dev/doc/images/intersects.png
==============================================================================
Binary file. No diff available.

Added: sandbox-branches/geometry/index_dev/doc/images/knn.png
==============================================================================
Binary file. No diff available.

Added: sandbox-branches/geometry/index_dev/doc/images/knn_cover.png
==============================================================================
Binary file. No diff available.

Added: sandbox-branches/geometry/index_dev/doc/images/knn_inters.png
==============================================================================
Binary file. No diff available.

Added: sandbox-branches/geometry/index_dev/doc/images/linear.png
==============================================================================
Binary file. No diff available.

Added: sandbox-branches/geometry/index_dev/doc/images/overlaps.png
==============================================================================
Binary file. No diff available.

Added: sandbox-branches/geometry/index_dev/doc/images/quadratic.png
==============================================================================
Binary file. No diff available.

Added: sandbox-branches/geometry/index_dev/doc/images/rstar.png
==============================================================================
Binary file. No diff available.

Added: sandbox-branches/geometry/index_dev/doc/images/within.png
==============================================================================
Binary file. No diff available.

Modified: sandbox-branches/geometry/index_dev/doc/rtree/introduction.qbk
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/rtree/introduction.qbk (original)
+++ sandbox-branches/geometry/index_dev/doc/rtree/introduction.qbk 2012-11-25 15:56:38 EST (Sun, 25 Nov 2012)
@@ -10,9 +10,45 @@

[section Introduction]

-__rtree__ is a self-balancing search tree. Each tree's node store a box descring the space occupied by children nodes.
-At the bottom of the structure, there are leaf-nodes which contains values
-(geometric objects representations). Minimal and maximal numbers of values/children
-which may be stored inside each node are user defined.
+__rtree__ is a tree data structure used for spatial searching. It was proposed by
+Antonin Guttman in 1984 [footnote Guttman, A. (1984). /R-Trees: A Dynamic Index Structure for Spatial Searching/ footnote]
+as an expansion of B-tree for multi-dimensional data. It may be used to store points or volumetric data in order to
+perform a spatial query later. This query may return objects that are inside some area or are close to some point in space.
+
+The __rtree__ structure is presented on the image below. Each __rtree__'s node store a box descring the space occupied by
+its children nodes. At the bottom of the structure, there are leaf-nodes which contains values
+(geometric objects representations).
+
+[$../images/rstar.png]
+
+The number of maximum and mininimum node's elements must be specified by the user. If the number of elements reaches it's maximum
+the new node is created and elements are split between nodes. If the number of elements in node is too small, the node is deleted
+and elements are reinserted into the tree.
+
+The __rtree__ is a self-balanced data structure. The key part of balancing algorithm is node splitting algorithm mentioned before
+[footnote Greene, D. (1989). /An implementation and performance analysis of spatial data access methods/ ]
+[footnote Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). /The R*-tree: an efficient and robust access method for points and rectangles/ ].
+Each algorithm would produce different splits so the internal structure of a tree may be different for each one of them.
+In general more complex algorithms analyses elements better and produces less overlapping nodes. This is a "better" split because
+later, in the searching process less nodes must be traversed in order to find desired obejcts. On the other hand more complex analysis
+takes more time. In general faster inserting will result in slower searching and vice versa. Example structures of trees created by use
+of three different algorithms and operations time are presented below.
+
+[table
+[[] [linear algorithm] [quadratic algorithm] [R*-tree]]
+[[*Structure*][[$../images/linear.png]] [[$../images/quadratic.png]] [[$../images/rstar.png]]]
+[[*1M Values inserts*] [1.85s] [3.10s] [24.52s]]
+[[*1M spatial queries*][8.60s] [2.74s] [1.31s]]
+[[*100k knn queries*] [3.49s] [1.59s] [0.84s]]
+]
+
+Key features of this implementation of the __rtree__ are:
+
+* three different creation algorithms - linear, quadratic or rstar,
+* parameters (including maximal and minimal number of elements) may be passed as compile- or run-time parameters - compile-time version is faster,
+* capable to store arbitrary __value__ type,
+* sophisticated queries - e.g. search for 5 nearest values intersecting some region but not within the other one.

[endsect]
+
+

Modified: sandbox-branches/geometry/index_dev/doc/rtree/quickstart.qbk
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/rtree/quickstart.qbk (original)
+++ sandbox-branches/geometry/index_dev/doc/rtree/quickstart.qbk 2012-11-25 15:56:38 EST (Sun, 25 Nov 2012)
@@ -17,29 +17,41 @@

[rtree_quickstart_include]

-It is possible to store user-defined types in the R-tree. To keep it simple we will
-use predefined __point__ and __box__.
+Typically you'll store e.g. `std::pair<Box, MyGeometryId>` in the __rtree__. `MyGeometryId`
+will be some indentifier of a complex `Geometry` stored in other container, e.g. index type
+of a `Polygon` stored in the vector or an iterator of list of `Ring`s. To keep it simple to
+define `Value` we will use predefined __box__ and unsigned int.

[rtree_quickstart_valuetype]

-R-tree may be created using various algorithm and parameters. In this example we will
-use quadratic algorithm. Maximum number of elements in nodes are set to 32, minimum to 8.
+R-tree may be created using various algorithm and parameters. You should choose the algorithm you'll
+find the best for your purpose. In this example we will use quadratic algorithm. Parameters are
+passed as template parameters. Maximum number of elements in nodes are set to 32, minimum to 8.

[rtree_quickstart_create]

-Inserting values into the R-tree may be done by calling insert() method.
+Typically `Value`s will be generated in a loop from e.g. `Polygon`s stored in some other container.
+In this case `Box` objects will probably be created with `geometry::make_envelope()` function.
+But to keep it simple lets just generate some boxes manually and insert them into the R-tree by
+using `insert()` method.

[rtree_quickstart_insert]

There are various types of spatial queries that may be performed, they can be even combined together
-in one call. For simplicity, default one is used.
+in one call. For simplicity, we use the default one. The following query return values intersecting
+a box. The sequence of `Values` in the result is not specified.

[rtree_quickstart_spatial_query]

-Default k-nearest neighbors query may be performed as follows.
+Other type of query is k-nearest neighbor search. It returns some number of values nearest to some point
+in space. The default knn query may be performed as follows. The sequence of `Values` in the result is not specified.

[rtree_quickstart_nearest_query]

+At the end we'll print results.
+
+[rtree_quickstart_output]
+
[h3 More]
More information about the R-tree implementation, other algorithms and queries may be found in
other parts of this documentation.

Modified: sandbox-branches/geometry/index_dev/doc/src/examples/rtree/quick_start.cpp
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/src/examples/rtree/quick_start.cpp (original)
+++ sandbox-branches/geometry/index_dev/doc/src/examples/rtree/quick_start.cpp 2012-11-25 15:56:38 EST (Sun, 25 Nov 2012)
@@ -10,14 +10,19 @@

//[rtree_quickstart_include

-#include <vector>
-
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/box.hpp>

#include <boost/geometry/extensions/index/rtree/rtree.hpp>

+// to store queries results
+#include <vector>
+
+// just for output
+#include <iostream>
+#include <boost/foreach.hpp>
+
namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;
//]
@@ -31,26 +36,41 @@
 //]

 //[rtree_quickstart_create
+ // create the rtree using default constructor
 bgi::rtree< value, bgi::quadratic<32, 8> > rtree;
 //]

 //[rtree_quickstart_insert
- // create some box
- // this typically will be an envelope of some geometry
- box b(point(0, 0), point(10, 10));
- // insert new value
- rtree.insert(std::make_pair(b, 0));
+ // create some values
+ for ( unsigned i = 0 ; i < 10 ; ++i )
+ {
+ // create a box
+ box b(point(i, i), point(i + 0.5f, i + 0.5f));
+ // insert new value
+ rtree.insert(std::make_pair(b, i));
+ }
 //]

 //[rtree_quickstart_spatial_query
- // find values intersecting a box
- std::vector<value> result;
- rtree.spatial_query(b, std::back_inserter(result));
+ // find values intersecting some area defined by a box
+ box query_box(point(0, 0), point(5, 5));
+ std::vector<value> result_s;
+ rtree.spatial_query(query_box, std::back_inserter(result_s));
 //]

 //[rtree_quickstart_nearest_query
 // find 5 nearest values to a point
- rtree.nearest_query(point(0, 0), 5, std::back_inserter(result));
+ std::vector<value> result_n;
+ rtree.nearest_query(point(0, 0), 5, std::back_inserter(result_n));
+ //]
+
+ //[rtree_quickstart_output
+ std::cout << "spatial query result:" << std::endl;
+ BOOST_FOREACH(value const& v, result_s)
+ std::cout << bg::wkt<box>(v.first) << " - " << v.second << std::endl;
+ std::cout << "knn query result:" << std::endl;
+ BOOST_FOREACH(value const& v, result_n)
+ std::cout << bg::wkt<box>(v.first) << " - " << v.second << std::endl;
 //]

 return 0;

Modified: sandbox-branches/geometry/index_dev/tests/additional_speed.cpp
==============================================================================
--- sandbox-branches/geometry/index_dev/tests/additional_speed.cpp (original)
+++ sandbox-branches/geometry/index_dev/tests/additional_speed.cpp 2012-11-25 15:56:38 EST (Sun, 25 Nov 2012)
@@ -21,7 +21,7 @@
 namespace bgi = bg::index;

 size_t values_count = 1000000;
- size_t queries_count = 100000;
+ size_t queries_count = 1000000;

 std::vector< std::pair<float, float> > coords;

Date view	Thread view	Subject view	Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk