|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r81540 - in sandbox-branches/geometry/index_dev/doc: html html/geometry_index/r_tree rtree
From: adam.wulkiewicz_at_[hidden]
Date: 2012-11-25 16:26:01
Author: awulkiew
Date: 2012-11-25 16:26:00 EST (Sun, 25 Nov 2012)
New Revision: 81540
URL: http://svn.boost.org/trac/boost/changeset/81540
Log:
Added basic description and images of spatial and knn queries
Text files modified:
sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/introduction.html | 2
sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/nearest_neighbours_queries.html | 49 ++++++++++++++++++++++++++++
sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/spatial_queries.html | 70 ++++++++++++++++++++++++++++++++++++++++
sandbox-branches/geometry/index_dev/doc/html/index.html | 2
sandbox-branches/geometry/index_dev/doc/rtree/introduction.qbk | 6 +-
sandbox-branches/geometry/index_dev/doc/rtree/nearest_query.qbk | 11 ++++++
sandbox-branches/geometry/index_dev/doc/rtree/spatial_query.qbk | 9 +++++
7 files changed, 144 insertions(+), 5 deletions(-)
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 16:26:00 EST (Sun, 25 Nov 2012)
@@ -201,7 +201,7 @@
<br><hr style="width:100; align:left;">
<div id="ftn.geometry_index.r_tree.introduction.f0" class="footnote"><p>[1]
Guttman, A. (1984). <span class="emphasis"><em>R-Trees: A Dynamic Index Structure for Spatial
- Searching</em></span> footnote
+ Searching</em></span>
</p></div>
<div id="ftn.geometry_index.r_tree.introduction.f1" class="footnote"><p>[2]
Greene, D. (1989). <span class="emphasis"><em>An implementation and performance analysis
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 16:26:00 EST (Sun, 25 Nov 2012)
@@ -37,6 +37,55 @@
<dt><span class="section"><a href="nearest_neighbours_queries.html#geometry_index.r_tree.nearest_neighbours_queries.using_spatial_predicates">Using
spatial predicates</a></span></dt>
</dl></div>
+<p>
+ Nearest neighbours queries returns <code class="computeroutput"><span class="identifier">Value</span></code>s
+ which are closest to some point in space. Additionally it is possible to
+ pass distance predicates in order to define how the distance to the <code class="computeroutput"><span class="identifier">Value</span></code> should be calculated or minimal and
+ maximal distances. The examples of some knn queries may be found in the table
+ below. All queries returns 5 closest <code class="computeroutput"><span class="identifier">Values</span></code>.
+ The query point, region and result Values are orange.
+ </p>
+<div class="informaltable"><table class="table">
+<colgroup>
+<col>
+<col>
+<col>
+</colgroup>
+<thead><tr>
+<th>
+ <p>
+ Basic knn query
+ </p>
+ </th>
+<th>
+ <p>
+ knn in a ring (Value's furthest point)
+ </p>
+ </th>
+<th>
+ <p>
+ knn in a ring (Value's closest point)
+ </p>
+ </th>
+</tr></thead>
+<tbody><tr>
+<td>
+ <p>
+ <span class="inlinemediaobject"><img src="../../../images/knn.png" alt="knn"></span>
+ </p>
+ </td>
+<td>
+ <p>
+ <span class="inlinemediaobject"><img src="../../../images/knn_inters.png" alt="knn_inters"></span>
+ </p>
+ </td>
+<td>
+ <p>
+ <span class="inlinemediaobject"><img src="../../../images/knn_cover.png" alt="knn_cover"></span>
+ </p>
+ </td>
+</tr></tbody>
+</table></div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="geometry_index.r_tree.nearest_neighbours_queries.k_nearest_neighbours"></a><a class="link" href="nearest_neighbours_queries.html#geometry_index.r_tree.nearest_neighbours_queries.k_nearest_neighbours" title="k nearest neighbours">k
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 16:26:00 EST (Sun, 25 Nov 2012)
@@ -32,6 +32,76 @@
<dt><span class="section"><a href="spatial_queries.html#geometry_index.r_tree.spatial_queries.spatial_predicates">Spatial
predicates</a></span></dt>
</dl></div>
+<p>
+ Spatial queries returns <code class="computeroutput"><span class="identifier">Value</span></code>s
+ which meets some predicates. For instance it may be used to retrieve Values
+ intersecting some area or are within some other area. The examples of some
+ basic queries may be found in the table below. The query region and result
+ <code class="computeroutput"><span class="identifier">Value</span></code>s are orange.
+ </p>
+<div class="informaltable"><table class="table">
+<colgroup>
+<col>
+<col>
+<col>
+<col>
+<col>
+</colgroup>
+<thead><tr>
+<th>
+ <p>
+ intersects (default)
+ </p>
+ </th>
+<th>
+ <p>
+ covered_by
+ </p>
+ </th>
+<th>
+ <p>
+ disjoint
+ </p>
+ </th>
+<th>
+ <p>
+ overlaps
+ </p>
+ </th>
+<th>
+ <p>
+ within
+ </p>
+ </th>
+</tr></thead>
+<tbody><tr>
+<td>
+ <p>
+ <span class="inlinemediaobject"><img src="../../../images/intersects.png" alt="intersects"></span>
+ </p>
+ </td>
+<td>
+ <p>
+ <span class="inlinemediaobject"><img src="../../../images/within.png" alt="within"></span>
+ </p>
+ </td>
+<td>
+ <p>
+ <span class="inlinemediaobject"><img src="../../../images/disjoint.png" alt="disjoint"></span>
+ </p>
+ </td>
+<td>
+ <p>
+ <span class="inlinemediaobject"><img src="../../../images/overlaps.png" alt="overlaps"></span>
+ </p>
+ </td>
+<td>
+ <p>
+ <span class="inlinemediaobject"><img src="../../../images/within.png" alt="within"></span>
+ </p>
+ </td>
+</tr></tbody>
+</table></div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="geometry_index.r_tree.spatial_queries.basic_queries"></a><a class="link" href="spatial_queries.html#geometry_index.r_tree.spatial_queries.basic_queries" title="Basic queries">Basic
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 16:26:00 EST (Sun, 25 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 25, 2012 at 20:52:29 GMT</small></p></td>
+<td align="left"><p><small>Last revised: November 25, 2012 at 21:23:52 GMT</small></p></td>
<td align="right"><div class="copyright-footer"></div></td>
</tr></table>
<hr>
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 16:26:00 EST (Sun, 25 Nov 2012)
@@ -11,7 +11,7 @@
[section Introduction]
__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]
+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.
@@ -26,8 +26,8 @@
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/ ].
+[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
Modified: sandbox-branches/geometry/index_dev/doc/rtree/nearest_query.qbk
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/rtree/nearest_query.qbk (original)
+++ sandbox-branches/geometry/index_dev/doc/rtree/nearest_query.qbk 2012-11-25 16:26:00 EST (Sun, 25 Nov 2012)
@@ -10,6 +10,17 @@
[section Nearest neighbours queries]
+Nearest neighbours queries returns `Value`s which are closest to some point in space.
+Additionally it is possible to pass distance predicates in order to define how the distance
+to the `Value` should be calculated or minimal and maximal distances. The examples of some knn
+queries may be found in the table below. All queries returns 5 closest `Values`.
+The query point, region and result Values are orange.
+
+[table
+[[Basic knn query] [knn in a ring (Value's furthest point)] [knn in a ring (Value's closest point)]]
+[[[$../images/knn.png]] [[$../images/knn_inters.png]] [[$../images/knn_cover.png]]]
+]
+
[section k nearest neighbours]
There are three ways of performing knn queries. Following queries returns
Modified: sandbox-branches/geometry/index_dev/doc/rtree/spatial_query.qbk
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/rtree/spatial_query.qbk (original)
+++ sandbox-branches/geometry/index_dev/doc/rtree/spatial_query.qbk 2012-11-25 16:26:00 EST (Sun, 25 Nov 2012)
@@ -10,6 +10,15 @@
[section Spatial queries]
+Spatial queries returns `Value`s which meets some predicates. For instance it may be used to
+retrieve Values intersecting some area or are within some other area. The examples of some
+basic queries may be found in the table below. The query region and result `Value`s are orange.
+
+[table
+[[intersects (default)] [covered_by] [disjoint] [overlaps] [within]]
+[[[$../images/intersects.png]] [[$../images/within.png]] [[$../images/disjoint.png]] [[$../images/overlaps.png]] [[$../images/within.png]]]
+]
+
[section Basic queries]
There are three ways to perform a spatial query. Following queries returns
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