Boost logo

Boost-Commit :

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"><span class="identifier">index</span><span class="special">::</span><span class="identifier">translator</span><span class="special">::</span><span class="identifier">def</span><span class="special">&lt;</span><span class="identifier">Value</span><span class="special">&gt;</span></code>
- is able to handle <code class="computeroutput">Point</code>,
- <code class="computeroutput">Box</code>,
- <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special">&lt;...&gt;</span></code>,
- pointer, iterator or smart pointer.
+ <code class="computeroutput"><span class="identifier">index</span><span class="special">::</span><span class="identifier">translator</span><span class="special">::</span><span class="identifier">def</span><span class="special">&lt;</span>Value<span class="special">&gt;</span></code> is able to handle <code class="computeroutput">Point</code>,
+ <code class="computeroutput">Box</code>
+ or <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special">&lt;...&gt;</span></code>
+ <code class="computeroutput">Value</code>s.
         </p>
 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
 <li class="listitem">
@@ -95,17 +94,17 @@
               <span class="special">|</span> Box</code>
             </li>
 <li class="listitem">
- <code class="computeroutput"><span class="identifier">BasicValue</span> <span class="special">=</span>
- <span class="identifier">Indexable</span> <span class="special">|</span>
- <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special">&lt;</span>Indexable<span class="special">,</span> <span class="identifier">T</span><span class="special">&gt;</span> <span class="special">|</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> Indexable<span class="special">&gt;</span></code>
- </li>
-<li class="listitem">
- <code class="computeroutput">Value <span class="special">=</span> <span class="identifier">BasicValue</span>
- <span class="special">|</span> <span class="identifier">BasicValue</span><span class="special">*</span> <span class="special">|</span> <span class="identifier">Iterator</span><span class="special">&lt;</span><span class="identifier">BasicValue</span><span class="special">&gt;</span>
- <span class="special">|</span> <span class="identifier">SmartPtr</span><span class="special">&lt;</span><span class="identifier">BasicValue</span><span class="special">&gt;</span></code>
+ <code class="computeroutput">Value <span class="special">=</span> <span class="identifier">Indexable</span>
+ <span class="special">|</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special">&lt;</span>Indexable<span class="special">,</span>
+ <span class="identifier">T</span><span class="special">&gt;</span></code>
             </li>
 </ul></div>
 <p>
+ If comparison of two <code class="computeroutput">Value</code>s is required, the default translator
+ compares both components of the <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special">&lt;...&gt;</span></code>. If the second one is a <code class="computeroutput"><span class="identifier">Geometry</span></code>, <code class="computeroutput"><span class="identifier">geometry</span><span class="special">::</span><span class="identifier">equals</span><span class="special">()</span></code> function is used. For other types it
+ uses <code class="computeroutput"><span class="keyword">operator</span><span class="special">==()</span></code>.
+ </p>
+<p>
           Examples of <code class="computeroutput">Value</code> types:
         </p>
 <pre class="programlisting"><span class="identifier">geometry</span><span class="special">::</span><span class="identifier">model</span><span class="special">::</span><span class="identifier">point</span><span class="special">&lt;...&gt;</span>

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"><span class="identifier">CoordinateType</span></code>.
+ Exception-safe copy constructor of the <code class="computeroutput"><span class="identifier">CoordinateType</span></code>
+ used in the <code class="computeroutput"><span class="identifier">Indexable</span></code>.
+ </li>
+<li class="listitem">
+ Nonthrowing copy constructor of the <code class="computeroutput"><span class="identifier">Translator</span></code>.
           </li>
 </ul></div>
 <div class="informaltable"><table class="table">
@@ -65,8 +69,7 @@
               </td>
 <td>
                 <p>
- <span class="emphasis"><em>nothrow (default)</em></span> or <span class="bold"><strong>strong</strong></span>
- [a]</sup></a>
+ <span class="emphasis"><em>nothrow</em></span>
                 </p>
               </td>
 </tr>
@@ -139,8 +142,7 @@
               </td>
 <td>
                 <p>
- <span class="emphasis"><em>nothrow (default)</em></span> or <span class="bold"><strong>strong</strong></span>
- [b]</sup></a>
+ <span class="emphasis"><em>nothrow</em></span>
                 </p>
               </td>
 </tr>
@@ -153,7 +155,19 @@
 <td>
                 <p>
                   <span class="emphasis"><em>nothrow</em></span> or <span class="bold"><strong>strong</strong></span>
- [c]</sup></a>
+ [a]</sup></a>
+ </p>
+ </td>
+</tr>
+<tr>
+<td>
+ <p>
+ <code class="computeroutput"><span class="identifier">swap</span><span class="special">(</span><span class="identifier">rtree</span> <span class="special">&amp;)</span></code>
+ </p>
+ </td>
+<td>
+ <p>
+ <span class="emphasis"><em>nothrow</em></span>
                 </p>
               </td>
 </tr>
@@ -293,7 +307,8 @@
               </td>
 <td>
                 <p>
- <span class="emphasis"><em>nothrow</em></span>
+ <span class="emphasis"><em>nothrow</em></span> or <span class="bold"><strong>strong</strong></span>
+ [b]</sup></a>
                 </p>
               </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"><p>[a]
- <span class="emphasis"><em>nothrow</em></span> - if <code class="computeroutput"><span class="identifier">Translator</span></code>
- has nonthrowing copy constructor (default), <span class="bold"><strong>strong</strong></span>
- - if <code class="computeroutput"><span class="identifier">Translator</span></code>
- has throwing copy constructor
+ <span class="emphasis"><em>nothrow</em></span> - if allocators are equal, <span class="bold"><strong>strong</strong></span> - otherwise
                   </p></div>
 <div id="ftn.geometry_index.r_tree.exception_safety.f1" class="footnote"><p>[b]
- <span class="emphasis"><em>nothrow</em></span> - if <code class="computeroutput"><span class="identifier">Translator</span></code>
- has nonthrowing copy constructor (default), <span class="bold"><strong>strong</strong></span>
- - if <code class="computeroutput"><span class="identifier">Translator</span></code>
- has throwing copy constructor
- </p></div>
-<div id="ftn.geometry_index.r_tree.exception_safety.f2" class="footnote"><p>[c]
- <span class="emphasis"><em>nothrow</em></span> - if allocators are equal and <code class="computeroutput"><span class="identifier">Translator</span></code> has nonthrowing
- copy constructor (default), <span class="bold"><strong>strong</strong></span>
- - if allocators aren't equal or <code class="computeroutput"><span class="identifier">Translator</span></code>
- has throwing copy constructor
+ <span class="emphasis"><em>nothrow</em></span> - if <code class="computeroutput"><span class="identifier">CoordinateType</span></code>
+ has nonthrowing copy constructor, <span class="bold"><strong>strong</strong></span>
+ - otherwise
                   </p></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>
 <p>
- 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]</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.
       </p>
+<p>
+ 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).
+ </p>
+<p>
+ <span class="inlinemediaobject"><img src="../../../images/rstar.png" alt="rstar"></span>
+ </p>
+<p>
+ 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.
+ </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 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.
+ </p>
+<div class="informaltable"><table class="table">
+<colgroup>
+<col>
+<col>
+<col>
+<col>
+</colgroup>
+<thead><tr>
+<th>
+ </th>
+<th>
+ <p>
+ linear algorithm
+ </p>
+ </th>
+<th>
+ <p>
+ quadratic algorithm
+ </p>
+ </th>
+<th>
+ <p>
+ R*-tree
+ </p>
+ </th>
+</tr></thead>
+<tbody>
+<tr>
+<td>
+ <p>
+ <span class="bold"><strong>Structure</strong></span>
+ </p>
+ </td>
+<td>
+ <p>
+ <span class="inlinemediaobject"><img src="../../../images/linear.png" alt="linear"></span>
+ </p>
+ </td>
+<td>
+ <p>
+ <span class="inlinemediaobject"><img src="../../../images/quadratic.png" alt="quadratic"></span>
+ </p>
+ </td>
+<td>
+ <p>
+ <span class="inlinemediaobject"><img src="../../../images/rstar.png" alt="rstar"></span>
+ </p>
+ </td>
+</tr>
+<tr>
+<td>
+ <p>
+ <span class="bold"><strong>1M Values inserts</strong></span>
+ </p>
+ </td>
+<td>
+ <p>
+ 1.85s
+ </p>
+ </td>
+<td>
+ <p>
+ 3.10s
+ </p>
+ </td>
+<td>
+ <p>
+ 24.52s
+ </p>
+ </td>
+</tr>
+<tr>
+<td>
+ <p>
+ <span class="bold"><strong>1M spatial queries</strong></span>
+ </p>
+ </td>
+<td>
+ <p>
+ 8.60s
+ </p>
+ </td>
+<td>
+ <p>
+ 2.74s
+ </p>
+ </td>
+<td>
+ <p>
+ 1.31s
+ </p>
+ </td>
+</tr>
+<tr>
+<td>
+ <p>
+ <span class="bold"><strong>100k knn queries</strong></span>
+ </p>
+ </td>
+<td>
+ <p>
+ 3.49s
+ </p>
+ </td>
+<td>
+ <p>
+ 1.59s
+ </p>
+ </td>
+<td>
+ <p>
+ 0.84s
+ </p>
+ </td>
+</tr>
+</tbody>
+</table></div>
+<p>
+ Key features of this implementation of the R-tree are:
+ </p>
+<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">
+<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>
+ </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
+ of spatial data access methods</em></span>
+ </p></div>
+<div id="ftn.geometry_index.r_tree.introduction.f2" class="footnote"><p>[3]
+ 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>
+</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><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/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 @@
       </p>
 <p>
 </p>
-<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">vector</span><span class="special">&gt;</span>
-
-<span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">geometry</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
+<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">geometry</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
 <span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">geometry</span><span class="special">/</span><span class="identifier">geometries</span><span class="special">/</span><span class="identifier">point_xy</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
 <span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">geometry</span><span class="special">/</span><span class="identifier">geometries</span><span class="special">/</span><span class="identifier">box</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
 
 <span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">geometry</span><span class="special">/</span><span class="identifier">extensions</span><span class="special">/</span><span class="identifier">index</span><span class="special">/</span><span class="identifier">rtree</span><span class="special">/</span><span class="identifier">rtree</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
 
+<span class="comment">// to store queries results</span>
+<span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">vector</span><span class="special">&gt;</span>
+
+<span class="comment">// just for output</span>
+<span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">iostream</span><span class="special">&gt;</span>
+<span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">foreach</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
+
 <span class="keyword">namespace</span> <span class="identifier">bg</span> <span class="special">=</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">geometry</span><span class="special">;</span>
 <span class="keyword">namespace</span> <span class="identifier">bgi</span> <span class="special">=</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">geometry</span><span class="special">::</span><span class="identifier">index</span><span class="special">;</span>
 </pre>
 <p>
       </p>
 <p>
- 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"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special">&lt;</span><span class="identifier">Box</span><span class="special">,</span> <span class="identifier">MyGeometryId</span><span class="special">&gt;</span></code> in the R-tree. <code class="computeroutput"><span class="identifier">MyGeometryId</span></code>
+ will be some indentifier of a complex <code class="computeroutput"><span class="identifier">Geometry</span></code>
+ stored in other container, e.g. index type of a <code class="computeroutput"><span class="identifier">Polygon</span></code>
+ stored in the vector or an iterator of list of <code class="computeroutput"><span class="identifier">Ring</span></code>s.
+ To keep it simple to define <code class="computeroutput"><span class="identifier">Value</span></code>
+ we will use predefined Box
+ and unsigned int.
       </p>
 <p>
 </p>
@@ -62,48 +71,80 @@
 <p>
       </p>
 <p>
- 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.
       </p>
 <p>
 </p>
-<pre class="programlisting"><span class="identifier">bgi</span><span class="special">::</span><span class="identifier">rtree</span><span class="special">&lt;</span> <span class="identifier">value</span><span class="special">,</span> <span class="identifier">bgi</span><span class="special">::</span><span class="identifier">quadratic</span><span class="special">&lt;</span><span class="number">32</span><span class="special">,</span> <span class="number">8</span><span class="special">&gt;</span> <span class="special">&gt;</span> <span class="identifier">rtree</span><span class="special">;</span>
+<pre class="programlisting"><span class="comment">// create the rtree using default constructor</span>
+<span class="identifier">bgi</span><span class="special">::</span><span class="identifier">rtree</span><span class="special">&lt;</span> <span class="identifier">value</span><span class="special">,</span> <span class="identifier">bgi</span><span class="special">::</span><span class="identifier">quadratic</span><span class="special">&lt;</span><span class="number">32</span><span class="special">,</span> <span class="number">8</span><span class="special">&gt;</span> <span class="special">&gt;</span> <span class="identifier">rtree</span><span class="special">;</span>
 </pre>
 <p>
       </p>
 <p>
- Inserting values into the R-tree may be done by calling insert() method.
+ Typically <code class="computeroutput"><span class="identifier">Value</span></code>s will be
+ generated in a loop from e.g. <code class="computeroutput"><span class="identifier">Polygon</span></code>s
+ stored in some other container. In this case <code class="computeroutput"><span class="identifier">Box</span></code>
+ objects will probably be created with <code class="computeroutput"><span class="identifier">geometry</span><span class="special">::</span><span class="identifier">make_envelope</span><span class="special">()</span></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"><span class="identifier">insert</span><span class="special">()</span></code>
+ method.
       </p>
 <p>
 </p>
-<pre class="programlisting"><span class="comment">// create some box</span>
-<span class="comment">// this typically will be an envelope of some geometry</span>
-<span class="identifier">box</span> <span class="identifier">b</span><span class="special">(</span><span class="identifier">point</span><span class="special">(</span><span class="number">0</span><span class="special">,</span> <span class="number">0</span><span class="special">),</span> <span class="identifier">point</span><span class="special">(</span><span class="number">10</span><span class="special">,</span> <span class="number">10</span><span class="special">));</span>
-<span class="comment">// insert new value</span>
-<span class="identifier">rtree</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">make_pair</span><span class="special">(</span><span class="identifier">b</span><span class="special">,</span> <span class="number">0</span><span class="special">));</span>
+<pre class="programlisting"><span class="comment">// create some values</span>
+<span class="keyword">for</span> <span class="special">(</span> <span class="keyword">unsigned</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span> <span class="special">;</span> <span class="identifier">i</span> <span class="special">&lt;</span> <span class="number">10</span> <span class="special">;</span> <span class="special">++</span><span class="identifier">i</span> <span class="special">)</span>
+<span class="special">{</span>
+ <span class="comment">// create a box</span>
+ <span class="identifier">box</span> <span class="identifier">b</span><span class="special">(</span><span class="identifier">point</span><span class="special">(</span><span class="identifier">i</span><span class="special">,</span> <span class="identifier">i</span><span class="special">),</span> <span class="identifier">point</span><span class="special">(</span><span class="identifier">i</span> <span class="special">+</span> <span class="number">0.5f</span><span class="special">,</span> <span class="identifier">i</span> <span class="special">+</span> <span class="number">0.5f</span><span class="special">));</span>
+ <span class="comment">// insert new value</span>
+ <span class="identifier">rtree</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">make_pair</span><span class="special">(</span><span class="identifier">b</span><span class="special">,</span> <span class="identifier">i</span><span class="special">));</span>
+<span class="special">}</span>
 </pre>
 <p>
       </p>
 <p>
         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"><span class="identifier">Values</span></code> in the result is not
+ specified.
       </p>
 <p>
 </p>
-<pre class="programlisting"><span class="comment">// find values intersecting a box</span>
-<span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">value</span><span class="special">&gt;</span> <span class="identifier">result</span><span class="special">;</span>
-<span class="identifier">rtree</span><span class="special">.</span><span class="identifier">spatial_query</span><span class="special">(</span><span class="identifier">b</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span>
+<pre class="programlisting"><span class="comment">// find values intersecting some area defined by a box</span>
+<span class="identifier">box</span> <span class="identifier">query_box</span><span class="special">(</span><span class="identifier">point</span><span class="special">(</span><span class="number">0</span><span class="special">,</span> <span class="number">0</span><span class="special">),</span> <span class="identifier">point</span><span class="special">(</span><span class="number">5</span><span class="special">,</span> <span class="number">5</span><span class="special">));</span>
+<span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">value</span><span class="special">&gt;</span> <span class="identifier">result_s</span><span class="special">;</span>
+<span class="identifier">rtree</span><span class="special">.</span><span class="identifier">spatial_query</span><span class="special">(</span><span class="identifier">query_box</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result_s</span><span class="special">));</span>
 </pre>
 <p>
       </p>
 <p>
- 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"><span class="identifier">Values</span></code>
+ in the result is not specified.
       </p>
 <p>
 </p>
 <pre class="programlisting"><span class="comment">// find 5 nearest values to a point</span>
-<span class="identifier">rtree</span><span class="special">.</span><span class="identifier">nearest_query</span><span class="special">(</span><span class="identifier">point</span><span class="special">(</span><span class="number">0</span><span class="special">,</span> <span class="number">0</span><span class="special">),</span> <span class="number">5</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span>
+<span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">value</span><span class="special">&gt;</span> <span class="identifier">result_n</span><span class="special">;</span>
+<span class="identifier">rtree</span><span class="special">.</span><span class="identifier">nearest_query</span><span class="special">(</span><span class="identifier">point</span><span class="special">(</span><span class="number">0</span><span class="special">,</span> <span class="number">0</span><span class="special">),</span> <span class="number">5</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result_n</span><span class="special">));</span>
+</pre>
+<p>
+ </p>
+<p>
+ At the end we'll print results.
+ </p>
+<p>
+</p>
+<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special">&lt;&lt;</span> <span class="string">"spatial query result:"</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span><span class="special">;</span>
+<span class="identifier">BOOST_FOREACH</span><span class="special">(</span><span class="identifier">value</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">v</span><span class="special">,</span> <span class="identifier">result_s</span><span class="special">)</span>
+ <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special">&lt;&lt;</span> <span class="identifier">bg</span><span class="special">::</span><span class="identifier">wkt</span><span class="special">&lt;</span><span class="identifier">box</span><span class="special">&gt;(</span><span class="identifier">v</span><span class="special">.</span><span class="identifier">first</span><span class="special">)</span> <span class="special">&lt;&lt;</span> <span class="string">" - "</span> <span class="special">&lt;&lt;</span> <span class="identifier">v</span><span class="special">.</span><span class="identifier">second</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span><span class="special">;</span>
+<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special">&lt;&lt;</span> <span class="string">"knn query result:"</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span><span class="special">;</span>
+<span class="identifier">BOOST_FOREACH</span><span class="special">(</span><span class="identifier">value</span> <span class="keyword">const</span><span class="special">&amp;</span> <span class="identifier">v</span><span class="special">,</span> <span class="identifier">result_n</span><span class="special">)</span>
+ <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special">&lt;&lt;</span> <span class="identifier">bg</span><span class="special">::</span><span class="identifier">wkt</span><span class="special">&lt;</span><span class="identifier">box</span><span class="special">&gt;(</span><span class="identifier">v</span><span class="special">.</span><span class="identifier">first</span><span class="special">)</span> <span class="special">&lt;&lt;</span> <span class="string">" - "</span> <span class="special">&lt;&lt;</span> <span class="identifier">v</span><span class="special">.</span><span class="identifier">second</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span><span class="special">;</span>
 </pre>
 <p>
       </p>

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><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/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"><p><small>Last revised: November 21, 2012 at 16:05:59 GMT</small></p></td>
+<td align="left"><p><small>Last revised: November 25, 2012 at 21:34:09 GMT</small></p></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<P>::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<P>::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<B> 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;
 


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