[Boost-commit] svn:boost r84259 - trunk/libs/geometry/doc/index

Subject: [Boost-commit] svn:boost r84259 - trunk/libs/geometry/doc/index
From: adam.wulkiewicz_at_[hidden]
Date: 2013-05-12 19:48:55

Author: awulkiew
Date: 2013-05-12 19:48:54 EDT (Sun, 12 May 2013)
New Revision: 84259
URL: http://svn.boost.org/trac/boost/changeset/84259

Log:
geometry.index docs: index general introduction modified, not included yet
Text files modified: 
   trunk/libs/geometry/doc/index/introduction.qbk |    66 +++++++++++++++++++++++++++++++++++++-- 
   1 files changed, 62 insertions(+), 4 deletions(-)

Modified: trunk/libs/geometry/doc/index/introduction.qbk
==============================================================================
--- trunk/libs/geometry/doc/index/introduction.qbk	(original)
+++ trunk/libs/geometry/doc/index/introduction.qbk	2013-05-12 19:48:54 EDT (Sun, 12 May 2013)
@@ -1,7 +1,7 @@
 [/============================================================================
   Boost.Geometry Index
 
-  Copyright (c) 2011-2012 Adam Wulkiewicz.
+  Copyright (c) 2011-2013 Adam Wulkiewicz.
 
   Use, modification and distribution is subject to the Boost Software License,
   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
@@ -10,10 +10,68 @@
 
 [section Introduction]
 
-The __boost_geometry_index__ is intetended to gather containers (spatial indexes) which may be used to accelerate spatial searching.
-It is a part of the __boost_geometry__ library. In general, spatial indexes stores geometric objects' representations and
-allows searching for objects occupying some space or close to some point in space.
+The __boost_geometry_index__ is intetended to gather data structures called spatial
+indexes which may be used to accelerate searching for objects in space. In general,
+spatial indexes stores geometric objects' representations and allows searching for
+objects occupying some space or close to some point in space.
 
 Currently, only one spatial index is implemented - __rtree__.
 
+[section __rtree__]
+
+__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. This query may for example 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/]. It's possible to insert new objects or
+to remove the ones already stored.
+
+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). 
+
+[$img/index/rtree/rstar.png]
+
+The __rtree__ is a self-balanced data structure. The key part of balancing algorithm is node splitting algorithm
+[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 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 obejcts. On the other hand more complex analysis takes more time. In general faster inserting will result in slower searching
+and vice versa. The performance of the R-tree depends on balancing algorithm, parameters and data inserted into the container.
+Example structures of trees created by use of three different algorithms and operations time are presented below. Data used in benchmark was random,
+non-overlapping boxes.
+
+[table
+[[]                         [linear algorithm] [quadratic algorithm] [R*-tree]]
+[[*Example structure*]      [[$img/index/rtree/linear.png]] [[$img/index/rtree/quadratic.png]] [[$img/index/rtree/rstar.png]]]
+[[*1M Values inserts*]      [1.65s] [2.51s] [4.96s]]
+[[*100k spatial queries*]   [0.87s] [0.25s] [0.09s]]
+[[*100k knn queries*]       [3.25s] [1.41s] [0.51s]]
+]
+
+[heading Implementation details]
+
+Key features of this implementation of the __rtree__ are:
+
+* capable to store arbitrary __value__ type,
+* 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,
+* advanced queries - e.g. search for 5 nearest values to some point and intersecting some region but not within the other one,
+* C++11 conformant: move semantics, stateful allocators,
+* capable to store __value__ type with no default constructor.
+
+[heading Dependencies]
+
+R-tree depends on *Boost.Move*, *Boost.Container*, *Boost.Tuple*, *Boost.Utility*, *Boost.MPL*.
+
+[heading Contributors]
+
+The spatial index was originally started by Federico J. Fernandez during the Google Summer of Code 2008 program, mentored by Hartmut Kaiser.
+
+[heading Spatial thanks]
+
+I'd like to thank Barend Gehrels, Bruno Lalande, Mateusz Łoskot, Lucanus J. Simonson for their support and ideas.
+
 [endsect]
+