libs/geometry/doc/index/introduction.qbk

   1 [/============================================================================
   2   Boost.Geometry Index
   3
   4   Copyright (c) 2011-2013 Adam Wulkiewicz.
   5
   6   Use, modification and distribution is subject to the Boost Software License,
   7   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   8   http://www.boost.org/LICENSE_1_0.txt)
   9 =============================================================================/]
  10
  11 [section Introduction]
  12
  13 The __boost_geometry_index__ is intended to gather data structures called spatial
  14 indexes which may be used to accelerate searching for objects in space. In general,
  15 spatial indexes stores geometric objects' representations and allows searching for
  16 objects occupying some space or close to some point in space.
  17
  18 Currently, only one spatial index is implemented - __rtree__.
  19
  20 [heading __rtree__]
  21
  22 __rtree__ is a tree data structure used for spatial searching. It was proposed by
  23 Antonin Guttman in 1984 [footnote Guttman, A. (1984). /R-Trees: A Dynamic Index Structure for Spatial Searching/]
  24 as an expansion of B-tree for multi-dimensional data. It may be used to store points or volumetric data in order to
  25 perform a spatial query. This query may for example return objects that are inside some area or are close to some point in space
  26 [footnote Cheung, K.; Fu, A. (1998). /Enhanced Nearest Neighbour Search on the R-tree/].
  27 It's possible to insert new objects or to remove the ones already stored.
  28
  29 The __rtree__ structure is presented on the image below. Each __rtree__'s node store a box describing the space occupied by
  30 its children nodes. At the bottom of the structure, there are leaf-nodes which contains values
  31 (geometric objects representations).
  32
  33 [$img/index/rtree/rstar.png]
  34
  35 The __rtree__ is a self-balanced data structure. The key part of balancing algorithm is node splitting algorithm
  36 [footnote Greene, D. (1989). /An implementation and performance analysis of spatial data access methods/]
  37 [footnote Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). /The R*-tree: an efficient and robust access method for points and rectangles/].
  38 Each algorithm produces different splits so the internal structure of a tree may be different for each one of them.
  39 In general, more complex algorithms analyses elements better and produces less overlapping nodes. In the searching process less nodes must be traversed
  40 in order to find desired objects. On the other hand more complex analysis takes more time. In general faster inserting will result in slower searching
  41 and vice versa. The performance of the R-tree depends on balancing algorithm, parameters and data inserted into the container.
  42
  43 Additionally there are also algorithms creating R-tree containing some, number of objects. This technique is called bulk loading and is
  44 done by use of packing algorithm
  45 [footnote Leutenegger, Scott T.; Edgington, Jeffrey M.; Lopez, Mario A. (1997). /STR: A Simple and Efficient Algorithm for R-Tree Packing/]
  46 [footnote Garcia, Yvan J.; Lopez, Mario A.; Leutenegger, Scott T. (1997). /A Greedy Algorithm for Bulk Loading R-trees/].
  47 This method is faster and results in R-trees with better internal structure. This means that the query performance is increased.
  48
  49 The examples of structures of trees created by use of different algorithms and exemplary operations times are presented below.
  50
  51 [table
  52 [[]                         [Linear algorithm] [Quadratic algorithm] [R*-tree] [Packing algorithm]]
  53 [[*Example structure*]      [[$img/index/rtree/linear.png]] [[$img/index/rtree/quadratic.png]] [[$img/index/rtree/rstar.png]] [[$img/index/rtree/bulk.png]]]
  54 [[*1M Values inserts*]      [1.76s] [2.47s] [6.19s] [0.64s]]
  55 [[*100k spatial queries*]   [2.21s] [0.51s] [0.12s] [0.07s]]
  56 [[*100k knn queries*]       [6.37s] [2.09s] [0.64s] [0.52s]]
  57 ]
  58
  59 The performance of the R-tree for different values of Max parameter and Min=0.5*Max is presented in the table below.
  60 The configuration of the machine used for testing is: /Intel(R) Core(TM) i7 870 @ 2.93GHz, 8GB RAM, MS Windows 7 x64/.
  61 In the two upper figures you can see the performance of the __rtree__ storing random, relatively small, non-overlapping, 2d boxes.
  62 In the lower ones, the performance of the __rtree__ also storing random, 2d boxes, but this time quite big and possibly overlapping.
  63 As you can see, the __rtree__ performance is different in both cases.
  64
  65 [table
  66 [[]                  [building] [querying]]
  67 [[*non overlapping*] [[$img/index/rtree/build_non_ovl.png]] [[$img/index/rtree/query_non_ovl.png]]]
  68 [[*overlapping*]      [[$img/index/rtree/build_ovl.png]] [[$img/index/rtree/query_ovl.png]]]
  69 ]
  70
  71 [heading Implementation details]
  72
  73 Key features of this implementation of the __rtree__ are:
  74
  75 * capable to store arbitrary __value__ type,
  76 * three different balancing algorithms - linear, quadratic or rstar,
  77 * creation using packing algorithm,
  78 * parameters (including maximal and minimal number of elements) may be passed as compile- or run-time parameters, in compile-time
  79   version nodes elements are stored in static-size containers,
  80 * advanced queries, e.g. search for 5 nearest Values to some point and intersecting some Geometry but not within the other one,
  81 * iterative queries by use of iterators,
  82 * C++11 conformant - move semantics, stateful allocators,
  83 * capable to store __value__ type with no default constructor,
  84 * in-memory storage by use of the default std::allocator<>,
  85 * other storage options - shared memory and mapped file by use of Boost.Interprocess allocators.
  86
  87 [/
  88 [heading Planned features]
  89
  90 Below you can find features that will (or probably will) be added in the future releases:
  91 /]
  92 [/ Done
  93 * rstar optimization (planned for release in Boost 1.55),
  94 * bulk loading (planned for release in Boost 1.55),
  95 * 'reversed' spatial predicates or additional spatial predicates like contains(),
  96 * iterative queries - query iterators / type-erased query iterators,
  97 /]
  98 [/
  99 * path/ray query predicate - search for Values along Segment or LineString, closest to the starting point,
 100 * user-defined distance calculation in nearest() predicate,
 101 * serialization,
 102 * persistent storage.
 103 /]
 104 [/ Maybe
 105 * other geometries as Indexables, e.g. NSpheres. Rings would probably require using move semantics instead of copying
 106 * bounding tree - rtree variation capable to use other Geometries as bounds, e.g. NSpheres, Rings/convex polygons/ (moving required), Capsules, Elipses, Variants etc.
 107 * moving instead of copying + optimizations for movable/nonthrowing/trivialy copied elements
 108 * passing more than one nearest/path predicate - "returned value is one of k1 nearest values to p1 and ... and one of kN nearest values to pN"
 109 /]
 110
 111 [heading Dependencies]
 112
 113 R-tree depends on Boost.Container, Boost.Core, Boost.Move, Boost.MPL, Boost.Range, Boost.Tuple.
 114
 115 [heading Contributors]
 116
 117 The spatial index was originally started by Federico J. Fernandez during the Google Summer of Code 2008 program, mentored by Hartmut Kaiser.
 118
 119 [heading Spatial thanks]
 120
 121 I'd like to thank Barend Gehrels, Bruno Lalande, Mateusz Łoskot, Lucanus J. Simonson for their support and ideas.
 122
 123 [endsect]
 124