|
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"><</span><span class="identifier">Value</span><span class="special">></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"><...></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"><</span>Value<span class="special">></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"><...></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"><</span>Indexable<span class="special">,</span> <span class="identifier">T</span><span class="special">></span> <span class="special">|</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span><span class="identifier">T</span><span class="special">,</span> Indexable<span class="special">></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"><</span><span class="identifier">BasicValue</span><span class="special">></span>
- <span class="special">|</span> <span class="identifier">SmartPtr</span><span class="special"><</span><span class="identifier">BasicValue</span><span class="special">></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"><</span>Indexable<span class="special">,</span>
+ <span class="identifier">T</span><span class="special">></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"><...></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"><...></span>
Modified: sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/exception_safety.html
Modified: sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/introduction.html
Modified: sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/nearest_neighbours_queries.html
Modified: sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/rtree_quickstart.html
Modified: sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/spatial_queries.html
Modified: sandbox-branches/geometry/index/doc/html/index.html
Modified: sandbox-branches/geometry/index/doc/rtree/creation.qbk
Modified: sandbox-branches/geometry/index/doc/rtree/exception_safety.qbk
Modified: sandbox-branches/geometry/index/doc/rtree/introduction.qbk
Modified: sandbox-branches/geometry/index/doc/rtree/nearest_query.qbk
Modified: sandbox-branches/geometry/index/doc/rtree/quickstart.qbk
Modified: sandbox-branches/geometry/index/doc/rtree/spatial_query.qbk
Modified: sandbox-branches/geometry/index/doc/src/examples/rtree/quick_start.cpp
Modified: sandbox-branches/geometry/index/test/rtree/test_rtree.hpp
Modified: sandbox-branches/geometry/index/tests/additional_glut_vis.cpp
Modified: sandbox-branches/geometry/index/tests/additional_speed.cpp
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
==============================================================================
--- 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">&)</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>
==============================================================================
--- 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>
==============================================================================
--- 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
==============================================================================
--- 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"><</span><span class="identifier">vector</span><span class="special">></span>
-
-<span class="preprocessor">#include</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">hpp</span><span class="special">></span>
+<pre class="programlisting"><span class="preprocessor">#include</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">hpp</span><span class="special">></span>
<span class="preprocessor">#include</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">geometries</span><span class="special">/</span><span class="identifier">point_xy</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span>
<span class="preprocessor">#include</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">geometries</span><span class="special">/</span><span class="identifier">box</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span>
<span class="preprocessor">#include</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">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">></span>
+<span class="comment">// to store queries results</span>
+<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">vector</span><span class="special">></span>
+
+<span class="comment">// just for output</span>
+<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">iostream</span><span class="special">></span>
+<span class="preprocessor">#include</span> <span class="special"><</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">></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"><</span><span class="identifier">Box</span><span class="special">,</span> <span class="identifier">MyGeometryId</span><span class="special">></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"><</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"><</span><span class="number">32</span><span class="special">,</span> <span class="number">8</span><span class="special">></span> <span class="special">></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"><</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"><</span><span class="number">32</span><span class="special">,</span> <span class="number">8</span><span class="special">></span> <span class="special">></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"><</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"><</span><span class="identifier">value</span><span class="special">></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"><</span><span class="identifier">value</span><span class="special">></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"><</span><span class="identifier">value</span><span class="special">></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"><<</span> <span class="string">"spatial query result:"</span> <span class="special"><<</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">&</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"><<</span> <span class="identifier">bg</span><span class="special">::</span><span class="identifier">wkt</span><span class="special"><</span><span class="identifier">box</span><span class="special">>(</span><span class="identifier">v</span><span class="special">.</span><span class="identifier">first</span><span class="special">)</span> <span class="special"><<</span> <span class="string">" - "</span> <span class="special"><<</span> <span class="identifier">v</span><span class="special">.</span><span class="identifier">second</span> <span class="special"><<</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"><<</span> <span class="string">"knn query result:"</span> <span class="special"><<</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">&</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"><<</span> <span class="identifier">bg</span><span class="special">::</span><span class="identifier">wkt</span><span class="special"><</span><span class="identifier">box</span><span class="special">>(</span><span class="identifier">v</span><span class="special">.</span><span class="identifier">first</span><span class="special">)</span> <span class="special"><<</span> <span class="string">" - "</span> <span class="special"><<</span> <span class="identifier">v</span><span class="special">.</span><span class="identifier">second</span> <span class="special"><<</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span><span class="special">;</span>
</pre>
<p>
</p>
==============================================================================
--- 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
==============================================================================
--- 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>
==============================================================================
--- 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:
==============================================================================
--- 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/ ]]
==============================================================================
--- 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]
+
+
==============================================================================
--- 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
==============================================================================
--- 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.
==============================================================================
--- 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
==============================================================================
--- 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;
==============================================================================
--- 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
==============================================================================
--- 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);
==============================================================================
--- 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;