Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r81542 - in sandbox-branches/geometry/index: . boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/visitors boost/geometry/extensions/index/translator doc/html doc/html/geometry_index/r_tree doc/images doc/rtree doc/src/examples/rtree test/rtree tests
From: adam.wulkiewicz_at_[hidden]
Date: 2012-11-25 16:38:33

Author: awulkiew
Date: 2012-11-25 16:38:31 EST (Sun, 25 Nov 2012)
New Revision: 81542
URL: http://svn.boost.org/trac/boost/changeset/81542

Log:
Merged from index_dev.

Docs improved (images added). Some samples and tests modified.
Added:
   sandbox-branches/geometry/index/doc/images/
      - copied from r81541, /sandbox-branches/geometry/index_dev/doc/images/
Properties modified:
   sandbox-branches/geometry/index/ (props changed)
Text files modified:
   sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp | 42 +++++--
   sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp | 20 ++-
   sandbox-branches/geometry/index/boost/geometry/extensions/index/translator/def.hpp | 204 ++++++++++++++++++++++++++-------------
   sandbox-branches/geometry/index/boost/geometry/extensions/index/translator/helpers.hpp | 1
   sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/creation_and_modification.html | 25 ++--
   sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/exception_safety.html | 47 +++++----
   sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/introduction.html | 189 ++++++++++++++++++++++++++++++++++++
   sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/nearest_neighbours_queries.html | 49 +++++++++
   sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/rtree_quickstart.html | 85 ++++++++++++----
   sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/spatial_queries.html | 70 +++++++++++++
   sandbox-branches/geometry/index/doc/html/index.html | 2
   sandbox-branches/geometry/index/doc/rtree/creation.qbk | 12 +
   sandbox-branches/geometry/index/doc/rtree/exception_safety.qbk | 15 +-
   sandbox-branches/geometry/index/doc/rtree/introduction.qbk | 44 +++++++
   sandbox-branches/geometry/index/doc/rtree/nearest_query.qbk | 11 ++
   sandbox-branches/geometry/index/doc/rtree/quickstart.qbk | 26 +++-
   sandbox-branches/geometry/index/doc/rtree/spatial_query.qbk | 9 +
   sandbox-branches/geometry/index/doc/src/examples/rtree/quick_start.cpp | 42 ++++++--
   sandbox-branches/geometry/index/test/rtree/test_rtree.hpp | 36 +++++-
   sandbox-branches/geometry/index/tests/additional_glut_vis.cpp | 59 +++++++++-
   sandbox-branches/geometry/index/tests/additional_speed.cpp | 2
   21 files changed, 784 insertions(+), 206 deletions(-)

Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp 2012-11-25 16:38:31 EST (Sun, 25 Nov 2012)
@@ -103,15 +103,14 @@
 /*!
 The constructor.

- \note Exception-safety: nothrow (if translator has nonthrowing copy ctor),
- strong (if translator has throwing copy ctor)
+ \note Exception-safety: nothrow

 \param parameters The parameters object.
 \param translator The translator object.
 \param allocator The allocator object.
 */
 inline explicit rtree(Parameters parameters = Parameters(), translator_type const& translator = translator_type(), Allocator allocator = Allocator())
- : m_translator(translator) // MAY THROW (copy)
+ : m_translator(translator) // SHOULDN'T THROW
 , m_parameters(parameters)
 , m_allocators(allocator)
 , m_values_count(0)
@@ -132,7 +131,7 @@
 */
 template<typename Iterator>
 inline rtree(Iterator first, Iterator last, Parameters parameters = Parameters(), translator_type const& translator = translator_type(), Allocator allocator = std::allocator<value_type>())
- : m_translator(translator) // MAY THROW (copy)
+ : m_translator(translator) // SHOULDN'T THROW
 , m_parameters(parameters)
 , m_allocators(allocator)
 , m_values_count(0)
@@ -166,7 +165,7 @@
 \note Exception-safety: strong
 */
 inline rtree(rtree const& src)
- : m_translator(src.m_translator) // MAY THROW (copy)
+ : m_translator(src.m_translator) // SHOULDN'T THROW
 , m_parameters(src.m_parameters)
 , m_allocators(src.m_allocators)
 , m_values_count(0)
@@ -184,7 +183,7 @@
 \note Exception-safety: strong
 */
 inline rtree(rtree const& src, Allocator const& allocator)
- : m_translator(src.m_translator) // MAY THROW (copy)
+ : m_translator(src.m_translator) // SHOULDN'T THROW
 , m_parameters(src.m_parameters)
 , m_allocators(allocator)
 , m_values_count(0)
@@ -197,11 +196,10 @@
 /*!
 The moving constructor.

- \note Exception-safety: nothrow (if translator has nonthrowing copy ctor),
- strong (if translator has throwing copy ctor)
+ \note Exception-safety: nothrow
 */
 inline rtree(BOOST_RV_REF(rtree) src)
- : m_translator(src.m_translator) // MAY THROW (copy)
+ : m_translator(src.m_translator) // SHOULDN'T THROW
 , m_parameters(src.m_parameters)
 , m_allocators(src.m_allocators)
 , m_values_count(src.m_values_count)
@@ -234,8 +232,8 @@
 /*!
 The moving assignment.

- \note Exception-safety: nothrow (if allocators are equal and translator has nonthrowing copy ctor),
- strong (if allocators aren't equal or translator has throwing copy ctor)
+ \note Exception-safety: nothrow (if allocators are equal),
+ strong (if allocators aren't equal)
 */
 inline rtree & operator=(BOOST_RV_REF(rtree) src)
 {
@@ -246,7 +244,7 @@

 if ( m_allocators.allocator == src.m_allocators.allocator )
 {
- m_translator = src.m_translator; // MAY THROW (copy)
+ m_translator = src.m_translator; // SHOULDN'T THROW
 m_parameters = src.m_parameters;
 //m_allocators = src.m_allocators;

@@ -268,6 +266,24 @@
 }

 /*!
+ Swaps two rtrees.
+
+ \note Exception-safety: nothrow
+
+ \param other The other rtree.
+ */
+ void swap(rtree & other)
+ {
+ std::swap(m_translator, other.m_translator); // SHOULDN'T THROW
+ std::swap(m_parameters, other.m_parameters);
+ std::swap(m_allocators, other.m_allocators);
+
+ std::swap(m_values_count, other.m_values_count);
+ std::swap(m_leafs_level, other.m_leafs_level);
+ std::swap(m_root, other.m_root);
+ }
+
+ /*!
 Insert a value to the index.

 \note Exception-safety: basic
@@ -732,7 +748,7 @@

 if ( copy_all_internals )
 {
- dst.m_translator = src.m_translator; // MAY THROW
+ dst.m_translator = src.m_translator; // SHOULDN'T THROW

 dst.m_parameters = src.m_parameters;
 //dst.m_allocators = dst.m_allocators;

Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp 2012-11-25 16:38:31 EST (Sun, 25 Nov 2012)
@@ -122,17 +122,17 @@
 size_t level_rel = level - level_f;

 if ( level_rel == 0 )
- glColor3f(1.0f, 0.0f, 0.0f);
+ glColor3f(0.75f, 0.0f, 0.0f);
 else if ( level_rel == 1 )
- glColor3f(0.0f, 1.0f, 0.0f);
+ glColor3f(0.0f, 0.75f, 0.0f);
 else if ( level_rel == 2 )
- glColor3f(0.0f, 0.0f, 1.0f);
+ glColor3f(0.0f, 0.0f, 0.75f);
 else if ( level_rel == 3 )
- glColor3f(1.0f, 1.0f, 0.0f);
+ glColor3f(0.75f, 0.75f, 0.0f);
 else if ( level_rel == 4 )
- glColor3f(1.0f, 0.0f, 1.0f);
+ glColor3f(0.75f, 0.0f, 0.75f);
 else if ( level_rel == 5 )
- glColor3f(0.0f, 1.0f, 1.0f);
+ glColor3f(0.0f, 0.75f, 0.75f);
 else
 glColor3f(0.5f, 0.5f, 0.5f);

@@ -167,7 +167,7 @@
 {
 size_t level_rel = level - level_f;

- glColor3f(1.0f, 1.0f, 1.0f);
+ glColor3f(0.25f, 0.25f, 0.25f);

 for (typename elements_type::const_iterator it = elements.begin();
 it != elements.end(); ++it)
@@ -204,6 +204,12 @@
 typedef typename rtree_type::box_type box_type;
 typedef typename rtree_type::allocators_type allocators_type;

+ if ( !tree.empty() )
+ {
+ glColor3f(0.75f, 0.75f, 0.75f);
+ detail::rtree::visitors::detail::gl_draw_indexable(tree.box(), 0);
+ }
+
 detail::rtree::visitors::gl_draw<value_type, options_type, translator_type, box_type, allocators_type>
 gl_draw_v(tree.translator(), level_first, level_last, z_coord_level_multiplier);

Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/translator/def.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/translator/def.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/translator/def.hpp 2012-11-25 16:38:31 EST (Sun, 25 Nov 2012)
@@ -15,100 +15,164 @@

namespace boost { namespace geometry { namespace index { namespace translator {

-namespace dispatch {
+//namespace dispatch {
+//
+//// Distinguish between def<Geometry>, def<Iterator> and def<SmartPtr>
+//
+//// Geometry
+//template <typename Value, bool IsIterator, bool IsSmartPtr>
+//struct def
+//{
+// typedef typename detail::extract_indexable<Value>::type const& result_type;
+//
+// result_type operator()(Value const& v) const
+// {
+// return detail::extract_indexable<Value>::get(v);
+// }
+//
+// bool equals(Value const& v1, Value const& v2) const
+// {
+// return detail::equals<Value>::apply(v1, v2);
+// }
+//};
+//
+//// Iterator
+//template <typename Value, bool IsSmartPtr>
+//struct def<Value, true, IsSmartPtr>
+//{
+// typedef typename detail::extract_indexable<typename Value::value_type>::type const& result_type;
+//
+// result_type operator()(Value const& v) const
+// {
+// return detail::extract_indexable<typename Value::value_type>::get(*v);
+// }
+//
+// bool equals(Value const& v1, Value const& v2) const
+// {
+// return v1 == v2;
+// }
+//};
+//
+//// SmartPtr
+//template <typename Value>
+//struct def<Value, false, true>
+//{
+// typedef typename detail::extract_indexable<typename Value::element_type>::type const& result_type;
+//
+// result_type operator()(Value const& v) const
+// {
+// return detail::extract_indexable<typename Value::element_type>::get(*v);
+// }
+//
+// bool equals(Value const& v1, Value const& v2) const
+// {
+// return v1 == v2;
+// }
+//};
+//
+//} // namespace dispatch
+//
+///*!
+//The default translator. It translates Value object to Indexable object. This is done in
+//operator() which takes const reference to Value and returns const reference to Indexable.
+//
+//\tparam Value The Value type which the translator translates to Indexable.
+//*/
+//template <typename Value>
+//struct def
+// : public dispatch::def
+// <
+// Value,
+// detail::is_iterator<Value>::value,
+// detail::is_smart_ptr<Value>::value
+// >
+//{
+//};
+//
+///*!
+//The default translator. It translates Value object to Indexable object. Since this is
+//a specialization for pointers to Values operator() takes const ptr to Value and returns
+//const reference to Indexable.
+//
+//\tparam Value The Value type which the translator translates to Indexable.
+//*/
+//template <typename Value>
+//struct def<Value*>
+//{
+// typedef typename detail::extract_indexable<Value>::type const& result_type;
+//
+// result_type operator()(const Value *v) const
+// {
+// return detail::extract_indexable<Value>::get(*v);
+// }
+//
+// bool equals(const Value* v1, const Value* v2) const
+// {
+// return v1 == v2;
+// }
+//};

-// Distinguish between def<Geometry>, def<Iterator> and def<SmartPtr>
+/*!
+The default translator. It translates Value object to Indexable object.

-// Geometry
-template <typename Value, bool IsIterator, bool IsSmartPtr>
+\tparam Value The Value type which may be translated directly to the Indexable.
+*/
+template <typename Value>
struct def
{
- typedef typename detail::extract_indexable<Value>::type const& result_type;
-
- result_type operator()(Value const& v) const
- {
- return detail::extract_indexable<Value>::get(v);
- }
-
- bool equals(Value const& v1, Value const& v2) const
- {
- return detail::equals<Value>::apply(v1, v2);
- }
-};
-
-// Iterator
-template <typename Value, bool IsSmartPtr>
-struct def<Value, true, IsSmartPtr>
-{
- typedef typename detail::extract_indexable<typename Value::value_type>::type const& result_type;
-
- result_type operator()(Value const& v) const
- {
- return detail::extract_indexable<typename Value::value_type>::get(*v);
- }
+ BOOST_MPL_ASSERT_MSG(
+ (!detail::indexable_not_found_error<
+ typename traits::indexable_type<Value>::type
+ >::value),
+ NOT_VALID_INDEXABLE_TYPE,
+ (Value)
+ );

- bool equals(Value const& v1, Value const& v2) const
- {
- return v1 == v2;
- }
-};
+ typedef Value const& result_type;

-// SmartPtr
-template <typename Value>
-struct def<Value, false, true>
-{
- typedef typename detail::extract_indexable<typename Value::element_type>::type const& result_type;
-
- result_type operator()(Value const& v) const
+ result_type operator()(Value const& value) const
 {
- return detail::extract_indexable<typename Value::element_type>::get(*v);
+ return value;
 }

 bool equals(Value const& v1, Value const& v2) const
 {
- return v1 == v2;
+ return geometry::equals(v1, v2);
 }
};

-} // namespace dispatch
-
/*!
-The default translator. It translates Value object to Indexable object. This is done in
-operator() which takes const reference to Value and returns const reference to Indexable.
+The default translator. This specialization translates from std::pair<Indexable, Second>.

-\tparam Value The Value type which the translator translates to Indexable.
+\tparam Indexable The Indexable type.
+\tparam Second The second type.
*/
-template <typename Value>
-struct def
- : public dispatch::def
- <
- Value,
- detail::is_iterator<Value>::value,
- detail::is_smart_ptr<Value>::value
- >
+template <typename Indexable, typename Second>
+struct def< std::pair<Indexable, Second> >
{
-};
-
-/*!
-The default translator. It translates Value object to Indexable object. Since this is
-a specialization for pointers to Values operator() takes const ptr to Value and returns
-const reference to Indexable.
+ BOOST_MPL_ASSERT_MSG(
+ (!detail::indexable_not_found_error<
+ typename traits::indexable_type<Indexable>::type
+ >::value),
+ NOT_VALID_INDEXABLE_TYPE,
+ (Indexable)
+ );

-\tparam Value The Value type which the translator translates to Indexable.
-*/
-template <typename Value>
-struct def<Value*>
-{
- typedef typename detail::extract_indexable<Value>::type const& result_type;
+ typedef Indexable const& result_type;

- result_type operator()(const Value *v) const
+ result_type operator()(std::pair<Indexable, Second> const& value) const
 {
- return detail::extract_indexable<Value>::get(*v);
+ return value.first;
 }

- bool equals(const Value* v1, const Value* v2) const
+ bool equals(std::pair<Indexable, Second> const& v1, std::pair<Indexable, Second> const& v2) const
 {
- return v1 == v2;
+ return geometry::equals(v1.first, v2.first)
+ &&
+ dispatch::equals<
+ Second,
+ typename geometry::traits::tag<Second>::type
+ >::apply(v1.second, v2.second);
 }
};

Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/translator/helpers.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/translator/helpers.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/translator/helpers.hpp 2012-11-25 16:38:31 EST (Sun, 25 Nov 2012)
@@ -15,6 +15,7 @@

#include <boost/static_assert.hpp>

+#include <boost/mpl/assert.hpp>
#include <boost/mpl/has_xxx.hpp>
#include <boost/mpl/and.hpp>

Modified: sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/creation_and_modification.html
==============================================================================
--- sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/creation_and_modification.html (original)
+++ sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/creation_and_modification.html 2012-11-25 16:38:31 EST (Sun, 25 Nov 2012)
@@ -83,11 +83,10 @@
 <code class="computeroutput">Indexable</code>s. 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">index::translator::def<Value></code>
- is able to handle <code class="computeroutput">Point</code>,
- <code class="computeroutput">Box</code>,
- <code class="computeroutput">std::pair<...></code>,
- pointer, iterator or smart pointer.
+ <code class="computeroutput">index::translator::def<Value></code> is able to handle <code class="computeroutput">Point</code>,
+ <code class="computeroutput">Box</code>
+ or <code class="computeroutput">std::pair<...></code>
+ <code class="computeroutput">Value</code>s.
 
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
@@ -95,17 +94,17 @@
 | Box</code>
 </li>
<li class="listitem">
- <code class="computeroutput">BasicValue =
- Indexable |
- std::pair<Indexable, T> | std::pair<T, Indexable></code>
- </li>
-<li class="listitem">
- <code class="computeroutput">Value = BasicValue
- | BasicValue* | Iterator<BasicValue>
- | SmartPtr<BasicValue></code>
+ <code class="computeroutput">Value = Indexable
+ | std::pair<Indexable,
+ T></code>
 </li>
</ul></div>

+ If comparison of two <code class="computeroutput">Value</code>s is required, the default translator
+ compares both components of the <code class="computeroutput">std::pair<...></code>. If the second one is a <code class="computeroutput">Geometry</code>, <code class="computeroutput">geometry::equals()</code> function is used. For other types it
+ uses <code class="computeroutput">operator==()</code>.
+ 
+
 Examples of <code class="computeroutput">Value</code> types:
 
<pre class="programlisting">geometry::model::point<...>

Modified: sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/exception_safety.html
==============================================================================
--- sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/exception_safety.html (original)
+++ sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/exception_safety.html 2012-11-25 16:38:31 EST (Sun, 25 Nov 2012)
@@ -36,7 +36,11 @@
 Exception-safe copy constructor of the <code class="computeroutput">Value</code>.
 </li>
<li class="listitem">
- Exception-safe copy constructor of the <code class="computeroutput">CoordinateType</code>.
+ Exception-safe copy constructor of the <code class="computeroutput">CoordinateType</code>
+ used in the <code class="computeroutput">Indexable</code>.
+ </li>
+<li class="listitem">
+ Nonthrowing copy constructor of the <code class="computeroutput">Translator</code>.
 </li>
</ul></div>
<div class="informaltable"><table class="table">
@@ -65,8 +69,7 @@
 </td>
<td>
 
- nothrow (default) or strong
- [a]</a>
+ nothrow
 
 </td>
</tr>
@@ -139,8 +142,7 @@
 </td>
<td>
 
- nothrow (default) or strong
- [b]</a>
+ nothrow
 
 </td>
</tr>
@@ -153,7 +155,19 @@
<td>
 
 nothrow or strong
- [c]</a>
+ [a]</a>
+ 
+ </td>
+</tr>
+<tr>
+<td>
+ 
+ <code class="computeroutput">swap(rtree &)</code>
+ 
+ </td>
+<td>
+ 
+ nothrow
 
 </td>
</tr>
@@ -293,7 +307,8 @@
 </td>
<td>
 
- nothrow
+ nothrow or strong
+ [b]</a>
 
 </td>
</tr>
@@ -336,22 +351,12 @@
</tbody>
<tbody class="footnotes"><tr><td colspan="2">
<div id="ftn.geometry_index.r_tree.exception_safety.f0" class="footnote">^[a]
- nothrow - if <code class="computeroutput">Translator</code>
- has nonthrowing copy constructor (default), strong
- - if <code class="computeroutput">Translator</code>
- has throwing copy constructor
+ nothrow - if allocators are equal, strong - otherwise
 </div>
<div id="ftn.geometry_index.r_tree.exception_safety.f1" class="footnote">^[b]
- nothrow - if <code class="computeroutput">Translator</code>
- has nonthrowing copy constructor (default), strong
- - if <code class="computeroutput">Translator</code>
- has throwing copy constructor
- </div>
-<div id="ftn.geometry_index.r_tree.exception_safety.f2" class="footnote">^[c]
- nothrow - if allocators are equal and <code class="computeroutput">Translator</code> has nonthrowing
- copy constructor (default), strong
- - if allocators aren't equal or <code class="computeroutput">Translator</code>
- has throwing copy constructor
+ nothrow - if <code class="computeroutput">CoordinateType</code>
+ has nonthrowing copy constructor, strong
+ - otherwise
 </div>
</td></tr></tbody>
</table></div>

Modified: sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/introduction.html
==============================================================================
--- sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/introduction.html (original)
+++ sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/introduction.html 2012-11-25 16:38:31 EST (Sun, 25 Nov 2012)
@@ -27,12 +27,191 @@
<a name="geometry_index.r_tree.introduction"></a><a class="link" href="introduction.html" title="Introduction">Introduction</a>
</h3></div></div></div>

- R-tree is a self-balancing search tree. Each tree's node store a box descring
- the space occupied by children nodes. At the bottom of the structure, there
- are leaf-nodes which contains values (geometric objects representations).
- Minimal and maximal numbers of values/children which may be stored inside
- each node are user defined.
+ R-tree is a tree data structure used for spatial searching. It was proposed
+ by Antonin Guttman in 1984 [1]</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.

+
+ The R-tree structure is presented on the image below. Each R-tree'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 src="../../../images/rstar.png" alt="rstar">
+ 
+
+ The number of maximum and mininimum node's elements must be specified by
+ the user. If the number of elements reaches it's maximum the new node is
+ created and elements are split between nodes. If the number of elements in
+ node is too small, the node is deleted and elements are reinserted into the
+ tree.
+ 
+
+ The R-tree is a self-balanced data structure. The key part of balancing algorithm
+ is node splitting algorithm [2]</a> [3]</a>. 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 takes more time. In general faster inserting
+ will result in slower searching and vice versa. Example structures of trees
+ created by use of three different algorithms and operations time are presented
+ below.
+ 
+<div class="informaltable"><table class="table">
+<colgroup>
+<col>
+<col>
+<col>
+<col>
+</colgroup>
+<thead><tr>
+<th>
+ </th>
+<th>
+ 
+ linear algorithm
+ 
+ </th>
+<th>
+ 
+ quadratic algorithm
+ 
+ </th>
+<th>
+ 
+ R*-tree
+ 
+ </th>
+</tr></thead>
+<tbody>
+<tr>
+<td>
+ 
+ Structure
+ 
+ </td>
+<td>
+ 
+ <img src="../../../images/linear.png" alt="linear">
+ 
+ </td>
+<td>
+ 
+ <img src="../../../images/quadratic.png" alt="quadratic">
+ 
+ </td>
+<td>
+ 
+ <img src="../../../images/rstar.png" alt="rstar">
+ 
+ </td>
+</tr>
+<tr>
+<td>
+ 
+ 1M Values inserts
+ 
+ </td>
+<td>
+ 
+ 1.85s
+ 
+ </td>
+<td>
+ 
+ 3.10s
+ 
+ </td>
+<td>
+ 
+ 24.52s
+ 
+ </td>
+</tr>
+<tr>
+<td>
+ 
+ 1M spatial queries
+ 
+ </td>
+<td>
+ 
+ 8.60s
+ 
+ </td>
+<td>
+ 
+ 2.74s
+ 
+ </td>
+<td>
+ 
+ 1.31s
+ 
+ </td>
+</tr>
+<tr>
+<td>
+ 
+ 100k knn queries
+ 
+ </td>
+<td>
+ 
+ 3.49s
+ 
+ </td>
+<td>
+ 
+ 1.59s
+ 
+ </td>
+<td>
+ 
+ 0.84s
+ 
+ </td>
+</tr>
+</tbody>
+</table></div>
+
+ Key features of this implementation of the R-tree are:
+ 
+<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
+<li class="listitem">
+ three different creation algorithms - linear, quadratic or rstar,
+ </li>
+<li class="listitem">
+ parameters (including maximal and minimal number of elements) may be
+ passed as compile- or run-time parameters - compile-time version is faster,
+ </li>
+<li class="listitem">
+ 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.
+ </li>
+</ul></div>
+<div class="footnotes">
+ <hr style="width:100; align:left;">
+<div id="ftn.geometry_index.r_tree.introduction.f0" class="footnote">^[1]
+ Guttman, A. (1984). R-Trees: A Dynamic Index Structure for Spatial
+ Searching
+ </div>
+<div id="ftn.geometry_index.r_tree.introduction.f1" class="footnote">^[2]
+ Greene, D. (1989). An implementation and performance analysis
+ of spatial data access methods
+ </div>
+<div id="ftn.geometry_index.r_tree.introduction.f2" class="footnote">^[3]
+ Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). The
+ R*-tree: an efficient and robust access method for points and rectangles
+ </div>
+</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>

Modified: sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/nearest_neighbours_queries.html
==============================================================================
--- sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/nearest_neighbours_queries.html (original)
+++ sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/nearest_neighbours_queries.html 2012-11-25 16:38:31 EST (Sun, 25 Nov 2012)
@@ -37,6 +37,55 @@
<dt><a href="nearest_neighbours_queries.html#geometry_index.r_tree.nearest_neighbours_queries.using_spatial_predicates">Using
spatial predicates</a></dt>
</dl></div>
+
+ Nearest neighbours queries returns <code class="computeroutput">Value</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">Value</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">Values</code>.
+ The query point, region and result Values are orange.
+ 
+<div class="informaltable"><table class="table">
+<colgroup>
+<col>
+<col>
+<col>
+</colgroup>
+<thead><tr>
+<th>
+ 
+ Basic knn query
+ 
+ </th>
+<th>
+ 
+ knn in a ring (Value's furthest point)
+ 
+ </th>
+<th>
+ 
+ knn in a ring (Value's closest point)
+ 
+ </th>
+</tr></thead>
+<tbody><tr>
+<td>
+ 
+ <img src="../../../images/knn.png" alt="knn">
+ 
+ </td>
+<td>
+ 
+ <img src="../../../images/knn_inters.png" alt="knn_inters">
+ 
+ </td>
+<td>
+ 
+ <img src="../../../images/knn_cover.png" alt="knn_cover">
+ 
+ </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/doc/html/geometry_index/r_tree/rtree_quickstart.html
==============================================================================
--- sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/rtree_quickstart.html (original)
+++ sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/rtree_quickstart.html 2012-11-25 16:38:31 EST (Sun, 25 Nov 2012)
@@ -35,23 +35,32 @@
 


-<pre class="programlisting">#include <vector>
-
-#include <boost/geometry.hpp>
+<pre class="programlisting">#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/box.hpp>

#include <boost/geometry/extensions/index/rtree/rtree.hpp>

+// to store queries results
+#include <vector>
+
+// just for output
+#include <iostream>
+#include <boost/foreach.hpp>
+
namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;
</pre>

 

- It is possible to store user-defined types in the R-tree. To keep it simple
- we will use predefined Point
- and Box.
+ Typically you'll store e.g. <code class="computeroutput">std::pair<Box, MyGeometryId></code> in the R-tree. <code class="computeroutput">MyGeometryId</code>
+ will be some indentifier of a complex <code class="computeroutput">Geometry</code>
+ stored in other container, e.g. index type of a <code class="computeroutput">Polygon</code>
+ stored in the vector or an iterator of list of <code class="computeroutput">Ring</code>s.
+ To keep it simple to define <code class="computeroutput">Value</code>
+ we will use predefined Box
+ and unsigned int.
 


@@ -62,48 +71,80 @@

 

- R-tree may be created using various algorithm and parameters. In this example
- we will use quadratic algorithm. Maximum number of elements in nodes are
- set to 32, minimum to 8.
+ R-tree may be created using various algorithm and parameters. You should
+ choose the algorithm you'll find the best for your purpose. In this example
+ we will use quadratic algorithm. Parameters are passed as template parameters.
+ Maximum number of elements in nodes are set to 32, minimum to 8.
 


-<pre class="programlisting">bgi::rtree< value, bgi::quadratic<32, 8> > rtree;
+<pre class="programlisting">// create the rtree using default constructor
+bgi::rtree< value, bgi::quadratic<32, 8> > rtree;
</pre>

 

- Inserting values into the R-tree may be done by calling insert() method.
+ Typically <code class="computeroutput">Value</code>s will be
+ generated in a loop from e.g. <code class="computeroutput">Polygon</code>s
+ stored in some other container. In this case <code class="computeroutput">Box</code>
+ objects will probably be created with <code class="computeroutput">geometry::make_envelope()</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">insert()</code>
+ method.
 


-<pre class="programlisting">// create some box
-// this typically will be an envelope of some geometry
-box b(point(0, 0), point(10, 10));
-// insert new value
-rtree.insert(std::make_pair(b, 0));
+<pre class="programlisting">// create some values
+for ( unsigned i = 0 ; i < 10 ; ++i )
+{
+ // create a box
+ box b(point(i, i), point(i + 0.5f, i + 0.5f));
+ // insert new value
+ rtree.insert(std::make_pair(b, i));
+}
</pre>

 

 There are various types of spatial queries that may be performed, they can
- be even combined together in one call. For simplicity, default one is used.
+ be even combined together in one call. For simplicity, we use the default
+ one. The following query return values intersecting a box. The sequence of
+ <code class="computeroutput">Values</code> in the result is not
+ specified.
 


-<pre class="programlisting">// find values intersecting a box
-std::vector<value> result;
-rtree.spatial_query(b, std::back_inserter(result));
+<pre class="programlisting">// find values intersecting some area defined by a box
+box query_box(point(0, 0), point(5, 5));
+std::vector<value> result_s;
+rtree.spatial_query(query_box, std::back_inserter(result_s));
</pre>

 

- Default k-nearest neighbors query may be performed as follows.
+ Other type of query is k-nearest neighbor search. It returns some number
+ of values nearest to some point in space. The default knn query may be performed
+ as follows. The sequence of <code class="computeroutput">Values</code>
+ in the result is not specified.
 


<pre class="programlisting">// find 5 nearest values to a point
-rtree.nearest_query(point(0, 0), 5, std::back_inserter(result));
+std::vector<value> result_n;
+rtree.nearest_query(point(0, 0), 5, std::back_inserter(result_n));
+</pre>
+
+ 
+
+ At the end we'll print results.
+ 
+
+
+<pre class="programlisting">std::cout << "spatial query result:" << std::endl;
+BOOST_FOREACH(value const& v, result_s)
+ std::cout << bg::wkt<box>(v.first) << " - " << v.second << std::endl;
+std::cout << "knn query result:" << std::endl;
+BOOST_FOREACH(value const& v, result_n)
+ std::cout << bg::wkt<box>(v.first) << " - " << v.second << std::endl;
</pre>

Modified: sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/spatial_queries.html
==============================================================================
--- sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/spatial_queries.html (original)
+++ sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/spatial_queries.html 2012-11-25 16:38:31 EST (Sun, 25 Nov 2012)
@@ -32,6 +32,76 @@
<dt><a href="spatial_queries.html#geometry_index.r_tree.spatial_queries.spatial_predicates">Spatial
predicates</a></dt>
</dl></div>
+
+ Spatial queries returns <code class="computeroutput">Value</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">Value</code>s are orange.
+ 
+<div class="informaltable"><table class="table">
+<colgroup>
+<col>
+<col>
+<col>
+<col>
+<col>
+</colgroup>
+<thead><tr>
+<th>
+ 
+ intersects (default)
+ 
+ </th>
+<th>
+ 
+ covered_by
+ 
+ </th>
+<th>
+ 
+ disjoint
+ 
+ </th>
+<th>
+ 
+ overlaps
+ 
+ </th>
+<th>
+ 
+ within
+ 
+ </th>
+</tr></thead>
+<tbody><tr>
+<td>
+ 
+ <img src="../../../images/intersects.png" alt="intersects">
+ 
+ </td>
+<td>
+ 
+ <img src="../../../images/within.png" alt="within">
+ 
+ </td>
+<td>
+ 
+ <img src="../../../images/disjoint.png" alt="disjoint">
+ 
+ </td>
+<td>
+ 
+ <img src="../../../images/overlaps.png" alt="overlaps">
+ 
+ </td>
+<td>
+ 
+ <img src="../../../images/within.png" alt="within">
+ 
+ </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/doc/html/index.html
==============================================================================
--- sandbox-branches/geometry/index/doc/html/index.html (original)
+++ sandbox-branches/geometry/index/doc/html/index.html 2012-11-25 16:38:31 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">Last revised: November 21, 2012 at 16:05:59 GMT</td>
+<td align="left">Last revised: November 25, 2012 at 21:34:09 GMT</td>
<td align="right"><div class="copyright-footer"></div></td>
</tr></table>
<hr>

Modified: sandbox-branches/geometry/index/doc/rtree/creation.qbk
==============================================================================
--- sandbox-branches/geometry/index/doc/rtree/creation.qbk (original)
+++ sandbox-branches/geometry/index/doc/rtree/creation.qbk 2012-11-25 16:38:31 EST (Sun, 25 Nov 2012)
@@ -31,13 +31,15 @@
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__`.
-Default `__translator__` `index::translator::def<Value>`
-is able to handle `__point__`, `__box__`, `std::pair<...>`, pointer, iterator
-or smart pointer.
+Default `__translator__` `index::translator::def<__value__>`
+is able to handle `__point__`, `__box__` or `std::pair<...>` `__value__`s.

* `__indexable__ = __point__ | __box__`
-* `BasicValue = Indexable | std::pair<__indexable__, T> | std::pair<T, __indexable__>`
-* `__value__ = BasicValue | BasicValue* | Iterator<BasicValue> | SmartPtr<BasicValue>`
+* `__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:

Modified: sandbox-branches/geometry/index/doc/rtree/exception_safety.qbk
==============================================================================
--- sandbox-branches/geometry/index/doc/rtree/exception_safety.qbk (original)
+++ sandbox-branches/geometry/index/doc/rtree/exception_safety.qbk 2012-11-25 16:38:31 EST (Sun, 25 Nov 2012)
@@ -14,22 +14,22 @@

* Nonthrowing destructor of the `__value__`.
* Exception-safe copy constructor of the `__value__`.
-* Exception-safe copy constructor of the `CoordinateType`.
+* Exception-safe copy constructor of the `CoordinateType` used in the `Indexable`.
+* Nonthrowing copy constructor of the `Translator`.

[table
[[Operation] [exception-safety]]
-[[`rtree()`] [ /nothrow (default)/ or *strong*
-[footnote /nothrow/ - if `Translator` has nonthrowing copy constructor (default), *strong* - if `Translator` has throwing copy constructor]]]
+[[`rtree()`] [ /nothrow/ ]]
[[`rtree(first, last)`] [ *strong* ]]
[[`~rtree()`] [ /nothrow/ ]]
[[][]]
[[`rtree(rtree const&)`] [ *strong* ]]
[[`operator=(rtree const&)`] [ *strong* ]]
[[][]]
-[[`rtree(rtree &&)`] [ /nothrow (default)/ or *strong*
-[footnote /nothrow/ - if `Translator` has nonthrowing copy constructor (default), *strong* - if `Translator` has throwing copy constructor]]]
+[[`rtree(rtree &&)`] [ /nothrow/ ]]
[[`operator=(rtree &&)`] [ /nothrow/ or *strong*
-[footnote /nothrow/ - if allocators are equal and `Translator` has nonthrowing copy constructor (default), *strong* - if allocators aren't equal or `Translator` has throwing copy constructor]]]
+[footnote /nothrow/ - if allocators are equal, *strong* - otherwise]]]
+[[`swap(rtree &)`] [ /nothrow/ ]]
[[][]]
[[`insert(__value__)`] [ basic ]]
[[`insert(first, last)`] [ basic ]]
@@ -42,7 +42,8 @@
[[`size()`] [ /nothrow/ ]]
[[`empty()`] [ /nothrow/ ]]
[[`clear()`] [ /nothrow/ ]]
-[[`box()`] [ /nothrow/ ]]
+[[`box()`] [ /nothrow/ or *strong*
+[footnote /nothrow/ - if `CoordinateType` has nonthrowing copy constructor, *strong* - otherwise]]]
[[`get_allocator()`] [ /nothrow/ ]]
[[`parameters()`] [ /nothrow/ ]]
[[`translator()`] [ /nothrow/ ]]

Modified: sandbox-branches/geometry/index/doc/rtree/introduction.qbk
==============================================================================
--- sandbox-branches/geometry/index/doc/rtree/introduction.qbk (original)
+++ sandbox-branches/geometry/index/doc/rtree/introduction.qbk 2012-11-25 16:38:31 EST (Sun, 25 Nov 2012)
@@ -10,9 +10,45 @@

[section Introduction]

-__rtree__ is a self-balancing search tree. Each tree's node store a box descring the space occupied by children nodes.
-At the bottom of the structure, there are leaf-nodes which contains values
-(geometric objects representations). Minimal and maximal numbers of values/children
-which may be stored inside each node are user defined.
+__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.
+
+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).
+
+[$../images/rstar.png]
+
+The number of maximum and mininimum node's elements must be specified by the user. If the number of elements reaches it's maximum
+the new node is created and elements are split between nodes. If the number of elements in node is too small, the node is deleted
+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
+[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
+takes more time. In general faster inserting will result in slower searching and vice versa. Example structures of trees created by use
+of three different algorithms and operations time are presented below.
+
+[table
+[[] [linear algorithm] [quadratic algorithm] [R*-tree]]
+[[*Structure*][[$../images/linear.png]] [[$../images/quadratic.png]] [[$../images/rstar.png]]]
+[[*1M Values inserts*] [1.85s] [3.10s] [24.52s]]
+[[*1M spatial queries*][8.60s] [2.74s] [1.31s]]
+[[*100k knn queries*] [3.49s] [1.59s] [0.84s]]
+]
+
+Key features of this implementation of the __rtree__ are:
+
+* 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.

[endsect]
+
+

Modified: sandbox-branches/geometry/index/doc/rtree/nearest_query.qbk
==============================================================================
--- sandbox-branches/geometry/index/doc/rtree/nearest_query.qbk (original)
+++ sandbox-branches/geometry/index/doc/rtree/nearest_query.qbk 2012-11-25 16:38:31 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/doc/rtree/quickstart.qbk
==============================================================================
--- sandbox-branches/geometry/index/doc/rtree/quickstart.qbk (original)
+++ sandbox-branches/geometry/index/doc/rtree/quickstart.qbk 2012-11-25 16:38:31 EST (Sun, 25 Nov 2012)
@@ -17,29 +17,41 @@

[rtree_quickstart_include]

-It is possible to store user-defined types in the R-tree. To keep it simple we will
-use predefined __point__ and __box__.
+Typically you'll store e.g. `std::pair<Box, MyGeometryId>` in the __rtree__. `MyGeometryId`
+will be some indentifier of a complex `Geometry` stored in other container, e.g. index type
+of a `Polygon` stored in the vector or an iterator of list of `Ring`s. To keep it simple to
+define `Value` we will use predefined __box__ and unsigned int.

[rtree_quickstart_valuetype]

-R-tree may be created using various algorithm and parameters. In this example we will
-use quadratic algorithm. Maximum number of elements in nodes are set to 32, minimum to 8.
+R-tree may be created using various algorithm and parameters. You should choose the algorithm you'll
+find the best for your purpose. In this example we will use quadratic algorithm. Parameters are
+passed as template parameters. Maximum number of elements in nodes are set to 32, minimum to 8.

[rtree_quickstart_create]

-Inserting values into the R-tree may be done by calling insert() method.
+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.
+But to keep it simple lets just generate some boxes manually and insert them into the R-tree by
+using `insert()` method.

[rtree_quickstart_insert]

There are various types of spatial queries that may be performed, they can be even combined together
-in one call. For simplicity, default one is used.
+in one call. For simplicity, we use the default one. The following query return values intersecting
+a box. The sequence of `Values` in the result is not specified.

[rtree_quickstart_spatial_query]

-Default k-nearest neighbors query may be performed as follows.
+Other type of query is k-nearest neighbor search. It returns some number of values nearest to some point
+in space. The default knn query may be performed as follows. The sequence of `Values` in the result is not specified.

[rtree_quickstart_nearest_query]

+At the end we'll print results.
+
+[rtree_quickstart_output]
+
[h3 More]
More information about the R-tree implementation, other algorithms and queries may be found in
other parts of this documentation.

Modified: sandbox-branches/geometry/index/doc/rtree/spatial_query.qbk
==============================================================================
--- sandbox-branches/geometry/index/doc/rtree/spatial_query.qbk (original)
+++ sandbox-branches/geometry/index/doc/rtree/spatial_query.qbk 2012-11-25 16:38:31 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

Modified: sandbox-branches/geometry/index/doc/src/examples/rtree/quick_start.cpp
==============================================================================
--- sandbox-branches/geometry/index/doc/src/examples/rtree/quick_start.cpp (original)
+++ sandbox-branches/geometry/index/doc/src/examples/rtree/quick_start.cpp 2012-11-25 16:38:31 EST (Sun, 25 Nov 2012)
@@ -10,14 +10,19 @@

//[rtree_quickstart_include

-#include <vector>
-
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/box.hpp>

#include <boost/geometry/extensions/index/rtree/rtree.hpp>

+// to store queries results
+#include <vector>
+
+// just for output
+#include <iostream>
+#include <boost/foreach.hpp>
+
namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;
//]
@@ -31,26 +36,41 @@
 //]

 //[rtree_quickstart_create
+ // create the rtree using default constructor
 bgi::rtree< value, bgi::quadratic<32, 8> > rtree;
 //]

 //[rtree_quickstart_insert
- // create some box
- // this typically will be an envelope of some geometry
- box b(point(0, 0), point(10, 10));
- // insert new value
- rtree.insert(std::make_pair(b, 0));
+ // create some values
+ for ( unsigned i = 0 ; i < 10 ; ++i )
+ {
+ // create a box
+ box b(point(i, i), point(i + 0.5f, i + 0.5f));
+ // insert new value
+ rtree.insert(std::make_pair(b, i));
+ }
 //]

 //[rtree_quickstart_spatial_query
- // find values intersecting a box
- std::vector<value> result;
- rtree.spatial_query(b, std::back_inserter(result));
+ // find values intersecting some area defined by a box
+ box query_box(point(0, 0), point(5, 5));
+ std::vector<value> result_s;
+ rtree.spatial_query(query_box, std::back_inserter(result_s));
 //]

 //[rtree_quickstart_nearest_query
 // find 5 nearest values to a point
- rtree.nearest_query(point(0, 0), 5, std::back_inserter(result));
+ std::vector<value> result_n;
+ rtree.nearest_query(point(0, 0), 5, std::back_inserter(result_n));
+ //]
+
+ //[rtree_quickstart_output
+ std::cout << "spatial query result:" << std::endl;
+ BOOST_FOREACH(value const& v, result_s)
+ std::cout << bg::wkt<box>(v.first) << " - " << v.second << std::endl;
+ std::cout << "knn query result:" << std::endl;
+ BOOST_FOREACH(value const& v, result_n)
+ std::cout << bg::wkt<box>(v.first) << " - " << v.second << std::endl;
 //]

 return 0;

Modified: sandbox-branches/geometry/index/test/rtree/test_rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index/test/rtree/test_rtree.hpp (original)
+++ sandbox-branches/geometry/index/test/rtree/test_rtree.hpp 2012-11-25 16:38:31 EST (Sun, 25 Nov 2012)
@@ -533,7 +533,7 @@
// rtree copying and moving

template <typename Value, typename Algo, typename Box>
-void test_copy_assignment_move(bgi::rtree<Value, Algo> const& tree, Box const& qbox)
+void test_copy_assignment_swap_move(bgi::rtree<Value, Algo> const& tree, Box const& qbox)
{
 size_t s = tree.size();

@@ -560,25 +560,43 @@
 t1.spatial_query(qbox, std::back_inserter(output));
 test_exactly_the_same_outputs(t1, output, expected_output);

- // moving constructor
- bgi::rtree<Value, Algo> t2(boost::move(t1));
+ bgi::rtree<Value, Algo> t2(tree.parameters());
+ t2.swap(t1);
+ BOOST_CHECK(tree.empty() == t2.empty());
+ BOOST_CHECK(tree.size() == t2.size());
+ BOOST_CHECK(true == t1.empty());
+ BOOST_CHECK(0 == t1.size());

- BOOST_CHECK(t2.size() == s);
- BOOST_CHECK(t1.size() == 0);
+ output.clear();
+ t1.spatial_query(qbox, std::back_inserter(output));
+ BOOST_CHECK(output.empty());

 output.clear();
 t2.spatial_query(qbox, std::back_inserter(output));
 test_exactly_the_same_outputs(t2, output, expected_output);
+ t2.swap(t1);
+
+ // moving constructor
+ bgi::rtree<Value, Algo> t3(boost::move(t1));
+
+ BOOST_CHECK(t3.size() == s);
+ BOOST_CHECK(t1.size() == 0);
+
+ output.clear();
+ t3.spatial_query(qbox, std::back_inserter(output));
+ test_exactly_the_same_outputs(t3, output, expected_output);

 // moving assignment operator
- t1 = boost::move(t2);
+ t1 = boost::move(t3);

 BOOST_CHECK(t1.size() == s);
- BOOST_CHECK(t2.size() == 0);
+ BOOST_CHECK(t3.size() == 0);

 output.clear();
 t1.spatial_query(qbox, std::back_inserter(output));
 test_exactly_the_same_outputs(t1, output, expected_output);
+
+ //TODO - test SWAP
}

// rtree removing
@@ -634,7 +652,7 @@
 test_nearest_query_k(tree, input, pt, 10);
 test_nearest_query_not_found(tree, generate_outside_point::apply(), 1, 3);

- test_copy_assignment_move(tree, qbox);
+ test_copy_assignment_swap_move(tree, qbox);

 test_remove(tree, qbox);

@@ -651,7 +669,7 @@
 test_nearest_query(empty_tree, empty_input, pt);
 test_nearest_query_k(empty_tree, empty_input, pt, 10);
 test_nearest_query_not_found(empty_tree, generate_outside_point::apply(), 1, 3);
- test_copy_assignment_move(empty_tree, qbox);
+ test_copy_assignment_swap_move(empty_tree, qbox);
}

// run all tests for one Algorithm for some number of rtrees

Modified: sandbox-branches/geometry/index/tests/additional_glut_vis.cpp
==============================================================================
--- sandbox-branches/geometry/index/tests/additional_glut_vis.cpp (original)
+++ sandbox-branches/geometry/index/tests/additional_glut_vis.cpp 2012-11-25 16:38:31 EST (Sun, 25 Nov 2012)
@@ -9,6 +9,8 @@

#include <gl/glut.h>

+#define BOOST_GEOMETRY_INDEX_ENABLE_DEBUG_INTERFACE
+
#include <boost/geometry/extensions/index/rtree/rtree.hpp>

#include <boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp>
@@ -31,9 +33,9 @@

size_t found_count = 0;
P search_point;
-float min_distance = 20;
+float min_distance = 10;
float max_distance = 30;
-size_t count = 10;
+size_t count = 5;
std::vector nearest_boxes;
B search_box;

@@ -50,11 +52,11 @@

 search_point = P(x, y);
 nearest_boxes.clear();
- found_count = t.nearest(
+ found_count = t.nearest_query(
 bgi::bounded(
 search_point,
- bgi::far(min_distance),
- bgi::near(max_distance)
+ bgi::to_furthest(min_distance),
+ bgi::to_nearest(max_distance)
 ),
 count,
 std::back_inserter(nearest_boxes)
@@ -87,13 +89,13 @@

 search_box = B(P(x - w, y - h), P(x + w, y + h));
 nearest_boxes.clear();
- found_count = t.query(Predicate(search_box), std::back_inserter(nearest_boxes) );
+ found_count = t.spatial_query(Predicate(search_box), std::back_inserter(nearest_boxes) );
 }
 else
 {
 search_box = t.box();
 nearest_boxes.clear();
- found_count = t.query(Predicate(search_box), std::back_inserter(nearest_boxes) );
+ found_count = t.spatial_query(Predicate(search_box), std::back_inserter(nearest_boxes) );
 }

 if ( found_count > 0 )
@@ -220,13 +222,23 @@

 glViewport(0, 0, w, h);

- gluPerspective(45, ratio, 1, 1000);
+ //gluPerspective(45, ratio, 1, 1000);
+ glOrtho(-150, 150, -150, 150, -150, 150);
 glMatrixMode(GL_MODELVIEW);
 glLoadIdentity();
- gluLookAt(
+ /*gluLookAt(
 120.0f, 120.0f, 120.0f,
 50.0f, 50.0f, -1.0f,
+ 0.0f, 1.0f, 0.0f);*/
+ gluLookAt(
+ 50.0f, 50.0f, 75.0f,
+ 50.0f, 50.0f, -1.0f,
 0.0f, 1.0f, 0.0f);
+
+ glClearColor(1.0f, 1.0f, 1.0f, 1.0f);
+ glLineWidth(1.5f);
+
+ srand(1);
}

void mouse(int button, int state, int x, int y)
@@ -292,6 +304,33 @@
 {
 std::cout << "\n" << t << "\n";
 }
+ else if ( current_line == "rand" )
+ {
+ for ( size_t i = 0 ; i < 35 ; ++i )
+ {
+ float x = ( rand() % 100 );
+ float y = ( rand() % 100 );
+ float w = ( rand() % 2 ) + 1;
+ float h = ( rand() % 2 ) + 1;
+
+ B b(P(x - w, y - h),P(x + w, y + h));
+
+ boost::geometry::index::insert(t, b);
+ vect.push_back(b);
+
+ std::cout << "inserted: ";
+ bgi::detail::rtree::visitors::detail::print_indexable(std::cout, b);
+ std::cout << '\n';
+ }
+
+ std::cout << ( bgi::are_boxes_ok(t) ? "boxes OK\n" : "WRONG BOXES!\n" );
+ std::cout << ( bgi::are_levels_ok(t) ? "levels OK\n" : "WRONG LEVELS!\n" );
+ std::cout << "\n";
+
+ search_valid = false;
+
+ glutPostRedisplay();
+ }
 else
 {
 if ( current_line == "knn" )
@@ -338,7 +377,7 @@
 glutInit(&argc, argv);
 glutInitDisplayMode(GLUT_DEPTH | GLUT_SINGLE | GLUT_RGBA);
 glutInitWindowPosition(100,100);
- glutInitWindowSize(800, 600);
+ glutInitWindowSize(600, 600);
 glutCreateWindow("boost::geometry::index::rtree GLUT test");

 glutDisplayFunc(render_scene);

Modified: sandbox-branches/geometry/index/tests/additional_speed.cpp
==============================================================================
--- sandbox-branches/geometry/index/tests/additional_speed.cpp (original)
+++ sandbox-branches/geometry/index/tests/additional_speed.cpp 2012-11-25 16:38:31 EST (Sun, 25 Nov 2012)
@@ -21,7 +21,7 @@
 namespace bgi = bg::index;

 size_t values_count = 1000000;
- size_t queries_count = 100000;
+ size_t queries_count = 1000000;

 std::vector< std::pair<float, float> > coords;

Date view	Thread view	Subject view	Author view

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