|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r81549 - in sandbox-branches/geometry/index_dev/doc: html html/geometry_index html/geometry_index/r_tree rtree
From: adam.wulkiewicz_at_[hidden]
Date: 2012-11-26 07:44:54
Author: awulkiew
Date: 2012-11-26 07:44:53 EST (Mon, 26 Nov 2012)
New Revision: 81549
URL: http://svn.boost.org/trac/boost/changeset/81549
Log:
Docs modified. Creation expanded. Quickstart fixed.
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 | 10 +-
sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/creation_and_modification.html | 110 +++++++++++++++++++++++++++------------
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 | 16 ++--
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 | 6 +-
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/creation.qbk | 70 +++++++++++++++++--------
sandbox-branches/geometry/index_dev/doc/rtree/quickstart.qbk | 2
11 files changed, 152 insertions(+), 84 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-26 07:44:53 EST (Mon, 26 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.77.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.76.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-26 07:44:53 EST (Mon, 26 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.77.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.76.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">
@@ -36,12 +36,12 @@
parameters</a></span></dt>
<dt><span class="section"><a href="r_tree/creation_and_modification.html#geometry_index.r_tree.creation_and_modification.values__indexables_and_default_translator">Values,
Indexables and default Translator</a></span></dt>
-<dt><span class="section"><a href="r_tree/creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_splitting_algorithms">Inserting
- and splitting algorithms</a></span></dt>
+<dt><span class="section"><a href="r_tree/creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_splitting_algorithms__compile_time_">Inserting
+ and splitting algorithms (compile-time)</a></span></dt>
<dt><span class="section"><a href="r_tree/creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_splitting_algorithms__run_time_">Inserting
and splitting algorithms (run-time)</a></span></dt>
-<dt><span class="section"><a href="r_tree/creation_and_modification.html#geometry_index.r_tree.creation_and_modification.copying_and_moving">Copying
- and moving</a></span></dt>
+<dt><span class="section"><a href="r_tree/creation_and_modification.html#geometry_index.r_tree.creation_and_modification.copying__moving_and_swapping">Copying,
+ moving and swapping</a></span></dt>
<dt><span class="section"><a href="r_tree/creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_removing_values">Inserting
and removing Values</a></span></dt>
</dl></dd>
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-26 07:44:53 EST (Mon, 26 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.77.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.76.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">
@@ -32,12 +32,12 @@
parameters</a></span></dt>
<dt><span class="section"><a href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.values__indexables_and_default_translator">Values,
Indexables and default Translator</a></span></dt>
-<dt><span class="section"><a href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_splitting_algorithms">Inserting
- and splitting algorithms</a></span></dt>
+<dt><span class="section"><a href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_splitting_algorithms__compile_time_">Inserting
+ and splitting algorithms (compile-time)</a></span></dt>
<dt><span class="section"><a href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_splitting_algorithms__run_time_">Inserting
and splitting algorithms (run-time)</a></span></dt>
-<dt><span class="section"><a href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.copying_and_moving">Copying
- and moving</a></span></dt>
+<dt><span class="section"><a href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.copying__moving_and_swapping">Copying,
+ moving and swapping</a></span></dt>
<dt><span class="section"><a href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_removing_values">Inserting
and removing Values</a></span></dt>
</dl></div>
@@ -49,22 +49,21 @@
<p>
R-tree has 4 parameters:
</p>
-<pre class="programlisting"><span class="identifier">rtree</span><span class="special"><</span><span class="identifier">Value</span><span class="special">,</span> <span class="identifier">Parameters</span><span class="special">,</span> <span class="identifier">Translator</span><span class="special">,</span> <span class="identifier">Allocator</span><span class="special">></span>
+<pre class="programlisting"><span class="identifier">rtree</span><span class="special"><</span><span class="identifier">Value</span><span class="special">,</span> <span class="identifier">Parameters</span><span class="special">,</span> <span class="identifier">Translator</span> <span class="special">=</span> <span class="identifier">translator</span><span class="special">::</span><span class="identifier">def</span><span class="special"><</span><span class="identifier">Value</span><span class="special">>,</span> <span class="identifier">Allocator</span><span class="special">></span> <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">allocator</span><span class="special"><</span><span class="identifier">Value</span><span class="special">></span> <span class="special">></span>
</pre>
-<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
+<div class="itemizedlist"><ul class="itemizedlist" type="disc">
<li class="listitem">
- <code class="computeroutput">Value</code> - type of object which will be stored in the container.
+ <code class="computeroutput">Value</code> - type of object which will be stored in the container,
</li>
<li class="listitem">
- <code class="computeroutput"><span class="identifier">Parameters</span></code> - compile-time
- parameters, e.g. inserting/splitting algorithm with min and max nodes'
- elements numbers.
+ <code class="computeroutput"><span class="identifier">Parameters</span></code> - parameters
+ type, inserting/splitting algorithm,
</li>
<li class="listitem">
<code class="computeroutput">Translator</code> - type of object translating <code class="computeroutput"><span class="identifier">Value</span></code> objects to <code class="computeroutput">Indexable</code>
objects (<code class="computeroutput">Point</code>
or <code class="computeroutput">Box</code>)
- which R-tree can handle.
+ which R-tree can handle,
</li>
<li class="listitem">
<code class="computeroutput"><span class="identifier">Allocator</span></code> - the allocator.
@@ -78,9 +77,9 @@
</h4></div></div></div>
<p>
R-tree may store <code class="computeroutput">Value</code>s of any type as long the <code class="computeroutput">Translator</code>
- is passed as parameter. It knows how to interpret those <code class="computeroutput">Value</code>s
- and extract an object understandable by the R-tree. Those objects are called
- <code class="computeroutput">Indexable</code>s. Each type adapted to <code class="computeroutput">Point</code>
+ knows how to interpret those <code class="computeroutput">Value</code>s and extract an object
+ that the R-tree can handle. Those objects are called <code class="computeroutput">Indexable</code>s
+ in this documentation. Each type adapted to <code class="computeroutput">Point</code>
or <code class="computeroutput">Box</code>
concept is an <code class="computeroutput">Indexable</code>. Default <code class="computeroutput">Translator</code>
<code class="computeroutput"><span class="identifier">index</span><span class="special">::</span><span class="identifier">translator</span><span class="special">::</span><span class="identifier">def</span><span class="special"><</span>Value<span class="special">></span></code> is able to handle <code class="computeroutput">Point</code>,
@@ -88,7 +87,7 @@
or <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><...></span></code>
<code class="computeroutput">Value</code>s.
</p>
-<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
+<div class="itemizedlist"><ul class="itemizedlist" type="disc">
<li class="listitem">
<code class="computeroutput">Indexable <span class="special">=</span> Point
<span class="special">|</span> Box</code>
@@ -100,29 +99,48 @@
</li>
</ul></div>
<p>
- If comparison of two <code class="computeroutput">Value</code>s is required, the default translator
- compares both components of the <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><...></span></code>. If the second one is a <code class="computeroutput"><span class="identifier">Geometry</span></code>, <code class="computeroutput"><span class="identifier">geometry</span><span class="special">::</span><span class="identifier">equals</span><span class="special">()</span></code> function is used. For other types it
- uses <code class="computeroutput"><span class="keyword">operator</span><span class="special">==()</span></code>.
- </p>
-<p>
- Examples of <code class="computeroutput">Value</code> types:
+ Examples of default <code class="computeroutput">Value</code> types:
</p>
<pre class="programlisting"><span class="identifier">geometry</span><span class="special">::</span><span class="identifier">model</span><span class="special">::</span><span class="identifier">point</span><span class="special"><...></span>
<span class="identifier">geometry</span><span class="special">::</span><span class="identifier">model</span><span class="special">::</span><span class="identifier">point_xy</span><span class="special"><...></span>
<span class="identifier">geometry</span><span class="special">::</span><span class="identifier">model</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">pair</span><span class="special"><</span><span class="identifier">geometry</span><span class="special">::</span><span class="identifier">model</span><span class="special">::</span><span class="identifier">box</span><span class="special"><...>,</span> <span class="identifier">size_t</span><span class="special">></span>
</pre>
+<p>
+ A <code class="computeroutput">Translator</code> is a type which knows how to handle <code class="computeroutput">Value</code>s.
+ It has two purposes:
+ </p>
+<div class="itemizedlist"><ul class="itemizedlist" type="disc">
+<li class="listitem">
+ it translates <code class="computeroutput">Value</code> to a more suitable <code class="computeroutput">Indexable</code>
+ type which is needed by most of operations,
+ </li>
+<li class="listitem">
+ performs a comparison of <code class="computeroutput">Value</code> which is needed by the
+ removing process.
+ </li>
+</ul></div>
+<p>
+ A <code class="computeroutput">Translator</code> translates the <code class="computeroutput">Value</code> each time the
+ R-tree needs it. For this reason it should rather return const reference
+ to the <code class="computeroutput">Indexable</code> than a copy.
+ </p>
+<p>
+ If comparison of two <code class="computeroutput">Value</code>s is required, the default translator
+ compares both components of the <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><...></span></code>. If the second one is a <code class="computeroutput"><span class="identifier">Geometry</span></code>, <code class="computeroutput"><span class="identifier">geometry</span><span class="special">::</span><span class="identifier">equals</span><span class="special">()</span></code> function is used. For other types it
+ uses <code class="computeroutput"><span class="keyword">operator</span><span class="special">==()</span></code>.
+ </p>
</div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
-<a name="geometry_index.r_tree.creation_and_modification.inserting_and_splitting_algorithms"></a><a class="link" href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_splitting_algorithms" title="Inserting and splitting algorithms">Inserting
- and splitting algorithms</a>
+<a name="geometry_index.r_tree.creation_and_modification.inserting_and_splitting_algorithms__compile_time_"></a><a class="link" href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_splitting_algorithms__compile_time_" title="Inserting and splitting algorithms (compile-time)">Inserting
+ and splitting algorithms (compile-time)</a>
</h4></div></div></div>
<p>
<code class="computeroutput">Value</code>s may be inserted to the R-tree in many various ways.
Final internal structure of the R-tree depends on algorithms used in the
- insertion process. The most important is nodes' splitting algorithm. Currently,
- three well-known types of R-trees may be created.
+ insertion process and parameters. The most important is nodes' splitting
+ algorithm. Currently, three well-known types of R-trees may be created.
</p>
<p>
Linear - classic R-tree using splitting algorithm of linear complexity
@@ -146,37 +164,50 @@
and splitting algorithms (run-time)</a>
</h4></div></div></div>
<p>
- By default splitting algorithm parameters are passed to the R-tree in compile
+ Splitting algorithm parameters may be also passed to the R-tree in run
time. To use run-time versions of the R-tree one may pass parameters defined
in index::runtime namespace.
</p>
<pre class="programlisting"><span class="comment">// linear</span>
<span class="identifier">index</span><span class="special">::</span><span class="identifier">rtree</span><span class="special"><</span>Value<span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">runtime</span><span class="special">::</span><span class="identifier">linear</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">runtime</span><span class="special">::</span><span class="identifier">linear</span><span class="special">(</span><span class="number">32</span><span class="special">,</span> <span class="number">8</span><span class="special">));</span>
+
<span class="comment">// quadratic</span>
<span class="identifier">index</span><span class="special">::</span><span class="identifier">rtree</span><span class="special"><</span>Value<span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">runtime</span><span class="special">::</span><span class="identifier">quadratic</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">runtime</span><span class="special">::</span><span class="identifier">quadratic</span><span class="special">(</span><span class="number">32</span><span class="special">,</span> <span class="number">8</span><span class="special">));</span>
+
<span class="comment">// rstar</span>
<span class="identifier">index</span><span class="special">::</span><span class="identifier">rtree</span><span class="special"><</span>Value<span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">runtime</span><span class="special">::</span><span class="identifier">rstar</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">runtime</span><span class="special">::</span><span class="identifier">rstar</span><span class="special">(</span><span class="number">32</span><span class="special">,</span> <span class="number">8</span><span class="special">));</span>
</pre>
+<p>
+ The obvious drawback is a slightly slower R-tree.
+ </p>
</div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
-<a name="geometry_index.r_tree.creation_and_modification.copying_and_moving"></a><a class="link" href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.copying_and_moving" title="Copying and moving">Copying
- and moving</a>
+<a name="geometry_index.r_tree.creation_and_modification.copying__moving_and_swapping"></a><a class="link" href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.copying__moving_and_swapping" title="Copying, moving and swapping">Copying,
+ moving and swapping</a>
</h4></div></div></div>
<p>
The R-tree is copyable and movable container. Move semantics is implemented
using Boost.Move library which also supports compilers not supporting rvalue
references.
</p>
-<pre class="programlisting"><span class="identifier">index</span><span class="special">::</span><span class="identifier">rtree</span><span class="special"><</span> Value<span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">quadratic</span><span class="special"><</span><span class="number">32</span><span class="special">,</span> <span class="number">8</span><span class="special">></span> <span class="special">></span> <span class="identifier">rt1</span><span class="special">;</span>
+<pre class="programlisting"><span class="comment">// default constructor</span>
+<span class="identifier">index</span><span class="special">::</span><span class="identifier">rtree</span><span class="special"><</span> Value<span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">quadratic</span><span class="special"><</span><span class="number">32</span><span class="special">,</span> <span class="number">8</span><span class="special">></span> <span class="special">></span> <span class="identifier">rt1</span><span class="special">;</span>
+
<span class="comment">// copy constructor</span>
-<span class="identifier">index</span><span class="special">::</span><span class="identifier">rtree</span><span class="special"><</span> Value<span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">quadratic</span><span class="special"><</span><span class="number">32</span><span class="special">,</span> <span class="number">8</span><span class="special">></span> <span class="special">></span> <span class="identifier">rt2</span><span class="special">;</span>
+<span class="identifier">index</span><span class="special">::</span><span class="identifier">rtree</span><span class="special"><</span> Value<span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">quadratic</span><span class="special"><</span><span class="number">32</span><span class="special">,</span> <span class="number">8</span><span class="special">></span> <span class="special">></span> <span class="identifier">rt2</span><span class="special">(</span><span class="identifier">r1</span><span class="special">);</span>
+
<span class="comment">// copy assignment</span>
<span class="identifier">rt2</span> <span class="special">=</span> <span class="identifier">r1</span><span class="special">;</span>
+
<span class="comment">// move constructor</span>
<span class="identifier">index</span><span class="special">::</span><span class="identifier">rtree</span><span class="special"><</span> Value<span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">quadratic</span><span class="special"><</span><span class="number">32</span><span class="special">,</span> <span class="number">8</span><span class="special">></span> <span class="special">></span> <span class="identifier">rt3</span><span class="special">(</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">move</span><span class="special">(</span><span class="identifier">rt1</span><span class="special">));</span>
+
<span class="comment">// move assignment</span>
<span class="identifier">rt3</span> <span class="special">=</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">move</span><span class="special">(</span><span class="identifier">rt2</span><span class="special">);</span>
+
+<span class="comment">// swap</span>
+<span class="identifier">rt3</span><span class="special">.</span><span class="identifier">swap</span><span class="special">(</span><span class="identifier">rt2</span><span class="special">);</span>
</pre>
</div>
<div class="section">
@@ -185,27 +216,38 @@
and removing Values</a>
</h4></div></div></div>
<p>
- Following code creates an R-tree using quadratic algorithm.
+ The following code creates an R-tree using quadratic algorithm.
</p>
<pre class="programlisting"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">geometry</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span><span class="identifier">Box</span><span class="special">,</span> <span class="keyword">int</span><span class="special">></span> Value<span class="special">;</span>
<span class="identifier">index</span><span class="special">::</span><span class="identifier">rtree</span><span class="special"><</span> Value<span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">quadratic</span><span class="special"><</span><span class="number">32</span><span class="special">,</span> <span class="number">8</span><span class="special">></span> <span class="special">></span> <span class="identifier">rt</span><span class="special">;</span>
</pre>
<p>
- To insert or remove Value's by method calls one may use the following code.
+ To insert or remove a `Value' by method call one may use the following
+ code.
</p>
<pre class="programlisting">Value <span class="identifier">v</span> <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">make_pair</span><span class="special">(</span>Box<span class="special">(...),</span> <span class="number">0</span><span class="special">);</span>
+
<span class="identifier">rt</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">v</span><span class="special">);</span>
+
<span class="identifier">rt</span><span class="special">.</span><span class="identifier">remove</span><span class="special">(</span><span class="identifier">v</span><span class="special">);</span>
</pre>
<p>
- To insert or remove Value's by function calls one may use the following
+ To insert or remove a `Value' by function call one may use the following
code.
</p>
<pre class="programlisting">Value <span class="identifier">v</span> <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">make_pair</span><span class="special">(</span>Box<span class="special">(...),</span> <span class="number">0</span><span class="special">);</span>
+
<span class="identifier">index</span><span class="special">::</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">v</span><span class="special">);</span>
+
<span class="identifier">index</span><span class="special">::</span><span class="identifier">remove</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">v</span><span class="special">);</span>
</pre>
+<p>
+ Typically you will perform those operations in a loop in order to e.g.
+ insert some number of <code class="computeroutput">Value</code>s corresponding to geometrical
+ objects (e.g. <code class="computeroutput"><span class="identifier">Polygons</span></code>)
+ stored in another container.
+ </p>
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/exception_safety.html
Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/introduction.html
Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/nearest_neighbours_queries.html
Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/rtree_quickstart.html
Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/spatial_queries.html
Modified: sandbox-branches/geometry/index_dev/doc/html/index.html
Modified: sandbox-branches/geometry/index_dev/doc/rtree/creation.qbk
Modified: sandbox-branches/geometry/index_dev/doc/rtree/quickstart.qbk
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
==============================================================================
--- 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-26 07:44:53 EST (Mon, 26 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.77.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.76.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 @@
<p>
In order to be exception-safe the R-tree requires:
</p>
-<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
+<div class="itemizedlist"><ul class="itemizedlist" type="disc">
<li class="listitem">
Nonthrowing destructor of the <code class="computeroutput">Value</code>.
</li>
@@ -155,7 +155,7 @@
<td>
<p>
<span class="emphasis"><em>nothrow</em></span> or <span class="bold"><strong>strong</strong></span>
- [a]</sup></a>
+ <sup>[<a name="geometry_index.r_tree.exception_safety.f0" href="#ftn.geometry_index.r_tree.exception_safety.f0" class="footnote">a</a>]</sup>
</p>
</td>
</tr>
@@ -308,7 +308,7 @@
<td>
<p>
<span class="emphasis"><em>nothrow</em></span> or <span class="bold"><strong>strong</strong></span>
- [b]</sup></a>
+ <sup>[<a name="geometry_index.r_tree.exception_safety.f1" href="#ftn.geometry_index.r_tree.exception_safety.f1" class="footnote">b</a>]</sup>
</p>
</td>
</tr>
@@ -350,10 +350,10 @@
</tr>
</tbody>
<tbody class="footnotes"><tr><td colspan="2">
-<div id="ftn.geometry_index.r_tree.exception_safety.f0" class="footnote"><p>[a]
+<div class="footnote"><p><sup>[<a id="ftn.geometry_index.r_tree.exception_safety.f0" href="#geometry_index.r_tree.exception_safety.f0" class="para">a</a>] </sup>
<span class="emphasis"><em>nothrow</em></span> - if allocators are equal, <span class="bold"><strong>strong</strong></span> - otherwise
</p></div>
-<div id="ftn.geometry_index.r_tree.exception_safety.f1" class="footnote"><p>[b]
+<div class="footnote"><p><sup>[<a id="ftn.geometry_index.r_tree.exception_safety.f1" href="#geometry_index.r_tree.exception_safety.f1" class="para">b</a>] </sup>
<span class="emphasis"><em>nothrow</em></span> - if <code class="computeroutput"><span class="identifier">CoordinateType</span></code>
has nonthrowing copy constructor, <span class="bold"><strong>strong</strong></span>
- otherwise
==============================================================================
--- 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-26 07:44:53 EST (Mon, 26 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.77.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.76.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">
@@ -28,7 +28,7 @@
</h3></div></div></div>
<p>
R-tree is a tree data structure used for spatial searching. It was proposed
- by Antonin Guttman in 1984 [1]</sup></a> as an expansion of B-tree for multi-dimensional data. It may
+ by Antonin Guttman in 1984 <sup>[<a name="geometry_index.r_tree.introduction.f0" href="#ftn.geometry_index.r_tree.introduction.f0" class="footnote">1</a>]</sup> 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.
@@ -51,7 +51,7 @@
</p>
<p>
The R-tree is a self-balanced data structure. The key part of balancing algorithm
- is node splitting algorithm [2]</sup></a> [3]</sup></a>. Each algorithm produces different splits so the internal structure
+ is node splitting algorithm <sup>[<a name="geometry_index.r_tree.introduction.f1" href="#ftn.geometry_index.r_tree.introduction.f1" class="footnote">2</a>]</sup> <sup>[<a name="geometry_index.r_tree.introduction.f2" href="#ftn.geometry_index.r_tree.introduction.f2" class="footnote">3</a>]</sup>. Each algorithm produces 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.
In the searching process less nodes must be traversed in order to find desired
@@ -180,7 +180,7 @@
<p>
Key features of this implementation of the R-tree are:
</p>
-<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
+<div class="itemizedlist"><ul class="itemizedlist" type="disc">
<li class="listitem">
three different creation algorithms - linear, quadratic or rstar,
</li>
@@ -197,16 +197,16 @@
</li>
</ul></div>
<div class="footnotes">
-<br><hr style="width:100; align:left;">
-<div id="ftn.geometry_index.r_tree.introduction.f0" class="footnote"><p>[1]
+<br><hr width="100" align="left">
+<div class="footnote"><p><sup>[<a id="ftn.geometry_index.r_tree.introduction.f0" href="#geometry_index.r_tree.introduction.f0" class="para">1</a>] </sup>
Guttman, A. (1984). <span class="emphasis"><em>R-Trees: A Dynamic Index Structure for Spatial
Searching</em></span>
</p></div>
-<div id="ftn.geometry_index.r_tree.introduction.f1" class="footnote"><p>[2]
+<div class="footnote"><p><sup>[<a id="ftn.geometry_index.r_tree.introduction.f1" href="#geometry_index.r_tree.introduction.f1" class="para">2</a>] </sup>
Greene, D. (1989). <span class="emphasis"><em>An implementation and performance analysis
of spatial data access methods</em></span>
</p></div>
-<div id="ftn.geometry_index.r_tree.introduction.f2" class="footnote"><p>[3]
+<div class="footnote"><p><sup>[<a id="ftn.geometry_index.r_tree.introduction.f2" href="#geometry_index.r_tree.introduction.f2" class="para">3</a>] </sup>
Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). <span class="emphasis"><em>The
R*-tree: an efficient and robust access method for points and rectangles</em></span>
</p></div>
==============================================================================
--- 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-26 07:44:53 EST (Mon, 26 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.77.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.76.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">
==============================================================================
--- 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-26 07:44:53 EST (Mon, 26 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.77.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.76.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">
@@ -87,7 +87,7 @@
Typically <code class="computeroutput"><span class="identifier">Value</span></code>s will be
generated in a loop from e.g. <code class="computeroutput"><span class="identifier">Polygon</span></code>s
stored in some other container. In this case <code class="computeroutput"><span class="identifier">Box</span></code>
- objects will probably be created with <code class="computeroutput"><span class="identifier">geometry</span><span class="special">::</span><span class="identifier">make_envelope</span><span class="special">()</span></code> function. But to keep it simple lets just
+ 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
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>
method.
</p>
@@ -150,7 +150,7 @@
</p>
<h4>
<a name="geometry_index.r_tree.rtree_quickstart.h0"></a>
- <span class="phrase"><a name="geometry_index.r_tree.rtree_quickstart.more"></a></span><a class="link" href="rtree_quickstart.html#geometry_index.r_tree.rtree_quickstart.more">More</a>
+ <span><a name="geometry_index.r_tree.rtree_quickstart.more"></a></span><a class="link" href="rtree_quickstart.html#geometry_index.r_tree.rtree_quickstart.more">More</a>
</h4>
<p>
More information about the R-tree implementation, other algorithms and queries
==============================================================================
--- 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-26 07:44:53 EST (Mon, 26 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.77.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.76.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">
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/html/index.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/index.html 2012-11-26 07:44:53 EST (Mon, 26 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.77.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.76.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"><p><small>Last revised: November 26, 2012 at 02:22:46 GMT</small></p></td>
+<td align="left"><p><small>Last revised: November 26, 2012 at 12:43:19 GMT</small></p></td>
<td align="right"><div class="copyright-footer"></div></td>
</tr></table>
<hr>
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/rtree/creation.qbk (original)
+++ sandbox-branches/geometry/index_dev/doc/rtree/creation.qbk 2012-11-26 07:44:53 EST (Mon, 26 Nov 2012)
@@ -14,46 +14,52 @@
__rtree__ has 4 parameters:
- rtree<Value, Parameters, Translator, Allocator>
+ rtree<Value, Parameters, Translator = translator::def<Value>, Allocator> = std::allocator<Value> >
-* `__value__` - type of object which will be stored in the container.
-* `Parameters` - compile-time parameters, e.g. inserting/splitting
- algorithm with min and max nodes' elements numbers.
+* `__value__` - type of object which will be stored in the container,
+* `Parameters` - parameters type, inserting/splitting algorithm,
* `__translator__` - type of object translating `Value` objects to
- `__indexable__` objects (`__point__` or `__box__`) which __rtree__ can handle.
+ `__indexable__` objects (`__point__` or `__box__`) which __rtree__ can handle,
* `Allocator` - the allocator.
[endsect]
[section Values, Indexables and default Translator]
-__rtree__ may store `__value__`s of any type as long the `__translator__`
-is passed as parameter. It knows how to interpret those `__value__`s
-and extract an object understandable by the __rtree__. Those objects are called
-`__indexable__`s. Each type adapted to `__point__` or `__box__` concept is an `__indexable__`.
+__rtree__ may store `__value__`s of any type as long the `__translator__` knows how to interpret those `__value__`s
+and extract an object that the __rtree__ can handle. Those objects are called
+`__indexable__`s in this documentation. Each type adapted to `__point__` or `__box__` concept is an `__indexable__`.
Default `__translator__` `index::translator::def<__value__>`
is able to handle `__point__`, `__box__` or `std::pair<...>` `__value__`s.
* `__indexable__ = __point__ | __box__`
* `__value__ = Indexable | std::pair<__indexable__, T>`
-If comparison of two `__value__`s is required, the default translator compares
-both components of the `std::pair<...>`. If the second one is a `Geometry`,
-`geometry::equals()` function is used. For other types it uses `operator==()`.
-
-Examples of `__value__` types:
+Examples of default `__value__` types:
geometry::model::point<...>
geometry::model::point_xy<...>
geometry::model::box<...>
std::pair<geometry::model::box<...>, size_t>
+A `__translator__` is a type which knows how to handle `__value__`s. It has two purposes:
+
+* it translates `__value__` to a more suitable `__indexable__` type which is needed by most of operations,
+* performs a comparison of `__value__` which is needed by the removing process.
+
+A `__translator__` translates the `__value__` each time the __rtree__ needs it. For this reason
+it should rather return const reference to the `__indexable__` than a copy.
+
+If comparison of two `__value__`s is required, the default translator compares
+both components of the `std::pair<...>`. If the second one is a `Geometry`,
+`geometry::equals()` function is used. For other types it uses `operator==()`.
+
[endsect]
-[section Inserting and splitting algorithms]
+[section Inserting and splitting algorithms (compile-time)]
`__value__`s may be inserted to the __rtree__ in many various ways. Final internal structure
-of the __rtree__ depends on algorithms used in the insertion process. The most important is
+of the __rtree__ depends on algorithms used in the insertion process and parameters. The most important is
nodes' splitting algorithm. Currently, three well-known types of R-trees may be created.
Linear - classic __rtree__ using splitting algorithm of linear complexity
@@ -72,58 +78,78 @@
[section Inserting and splitting algorithms (run-time)]
-By default splitting algorithm parameters are passed to the __rtree__ in compile time.
+Splitting algorithm parameters may be also passed to the __rtree__ in run time.
To use run-time versions of the __rtree__ one may pass parameters defined in index::runtime
namespace.
// linear
index::rtree<__value__, index::runtime::linear> rt(index::runtime::linear(32, 8));
+
// quadratic
index::rtree<__value__, index::runtime::quadratic> rt(index::runtime::quadratic(32, 8));
+
// rstar
index::rtree<__value__, index::runtime::rstar> rt(index::runtime::rstar(32, 8));
+The obvious drawback is a slightly slower __rtree__.
+
[endsect]
-[section Copying and moving]
+[section Copying, moving and swapping]
The __rtree__ is copyable and movable container. Move semantics is implemented using Boost.Move library
which also supports compilers not supporting rvalue references.
+ // default constructor
index::rtree< __value__, index::quadratic<32, 8> > rt1;
+
// copy constructor
- index::rtree< __value__, index::quadratic<32, 8> > rt2;
+ index::rtree< __value__, index::quadratic<32, 8> > rt2(r1);
+
// copy assignment
rt2 = r1;
+
// move constructor
index::rtree< __value__, index::quadratic<32, 8> > rt3(boost::move(rt1));
+
// move assignment
rt3 = boost::move(rt2);
+ // swap
+ rt3.swap(rt2);
+
[endsect]
[section Inserting and removing Values]
-Following code creates an __rtree__ using quadratic algorithm.
+The following code creates an __rtree__ using quadratic algorithm.
using namespace boost::geometry;
typedef std::pair<Box, int> __value__;
index::rtree< __value__, index::quadratic<32, 8> > rt;
-To insert or remove __value__'s by method calls one may use the following
+To insert or remove a `__value__' by method call one may use the following
code.
__value__ v = std::make_pair(__box__(...), 0);
+
rt.insert(v);
+
rt.remove(v);
-To insert or remove __value__'s by function calls one may use the following
+To insert or remove a `__value__' by function call one may use the following
code.
__value__ v = std::make_pair(__box__(...), 0);
+
index::insert(rt, v);
+
index::remove(rt, v);
+Typically you will perform those operations in a loop in order to e.g. insert
+some number of `__value__`s corresponding to geometrical objects (e.g. `Polygons`)
+stored in another container.
+
[endsect]
[endsect] [/ Creation and modification /]
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/rtree/quickstart.qbk (original)
+++ sandbox-branches/geometry/index_dev/doc/rtree/quickstart.qbk 2012-11-26 07:44:53 EST (Mon, 26 Nov 2012)
@@ -31,7 +31,7 @@
[rtree_quickstart_create]
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.
+In this case `Box` objects will probably be created with `geometry::envelope()` function.
But to keep it simple lets just generate some boxes manually and insert them into the R-tree by
using `insert()` method.