|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r81585 - in sandbox-branches/geometry/index_dev/doc: html html/geometry_index/r_tree rtree
From: adam.wulkiewicz_at_[hidden]
Date: 2012-11-27 07:10:58
Author: awulkiew
Date: 2012-11-27 07:10:56 EST (Tue, 27 Nov 2012)
New Revision: 81585
URL: http://svn.boost.org/trac/boost/changeset/81585
Log:
knn reference added + small change in docs.
Text files modified:
sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/introduction.html | 15 ++++++++++-----
sandbox-branches/geometry/index_dev/doc/html/index.html | 2 +-
sandbox-branches/geometry/index_dev/doc/rtree/introduction.qbk | 5 +++--
3 files changed, 14 insertions(+), 8 deletions(-)
Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/introduction.html
Modified: sandbox-branches/geometry/index_dev/doc/html/index.html
Modified: sandbox-branches/geometry/index_dev/doc/rtree/introduction.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/introduction.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/introduction.html 2012-11-27 07:10:56 EST (Tue, 27 Nov 2012)
@@ -31,7 +31,7 @@
by Antonin Guttman in 1984 [1]</sup></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.
+ close to some point in space [2]</sup></a>.
</p>
<p>
The R-tree structure is presented on the image below. Each R-tree's node
@@ -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 [3]</sup></a> [4]</sup></a>. 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
@@ -192,8 +192,9 @@
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.
+ advanced queries - e.g. search for 5 nearest values further than some
+ minimal distance and intersecting some region but not within the other
+ one.
</li>
</ul></div>
<div class="footnotes">
@@ -203,10 +204,14 @@
Searching</em></span>
</p></div>
<div id="ftn.geometry_index.r_tree.introduction.f1" class="footnote"><p>[2]
+ Cheung, K.; Fu, A. (1998). <span class="emphasis"><em>Enhanced Nearest Neighbour Search
+ on the R-tree</em></span>
+ </p></div>
+<div id="ftn.geometry_index.r_tree.introduction.f2" class="footnote"><p>[3]
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 id="ftn.geometry_index.r_tree.introduction.f3" class="footnote"><p>[4]
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/index.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/index.html 2012-11-27 07:10:56 EST (Tue, 27 Nov 2012)
@@ -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 22:11:47 GMT</small></p></td>
+<td align="left"><p><small>Last revised: November 27, 2012 at 12:09:04 GMT</small></p></td>
<td align="right"><div class="copyright-footer"></div></td>
</tr></table>
<hr>
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/rtree/introduction.qbk (original)
+++ sandbox-branches/geometry/index_dev/doc/rtree/introduction.qbk 2012-11-27 07:10:56 EST (Tue, 27 Nov 2012)
@@ -13,7 +13,8 @@
__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/]
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.
+perform a spatial query later. This query may return objects that are inside some area or are close to some point in space
+[footnote Cheung, K.; Fu, A. (1998). /Enhanced Nearest Neighbour Search on the R-tree/].
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
@@ -46,7 +47,7 @@
* 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.
+* advanced queries - e.g. search for 5 nearest values further than some minimal distance and intersecting some region but not within the other one.
[endsect]