Subject: [Boost-commit] svn:boost r74422 - in sandbox-branches/geometry/index: boost/geometry/extensions/index boost/geometry/extensions/index/algorithms boost/geometry/extensions/index/algorithms/detail boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/visitors tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-09-16 15:44:05
Author: awulkiew
Date: 2011-09-16 15:44:04 EDT (Fri, 16 Sep 2011)
New Revision: 74422
URL: http://svn.boost.org/trac/boost/changeset/74422
Log:
k nearest neighbors search implemented, empty predicate added, pop_back() added to pushable_array, glFlush() and glClear() calls removed from gl_draw(), number of found objects added to spatial query, find visitor and corresponding rtree's method removed.
Added:
sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/detail/
sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/detail/smallest_for_indexable.hpp (contents, props changed)
sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/detail/sum_for_indexable.hpp (contents, props changed)
sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/mindist.hpp (contents, props changed)
sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/minmaxdist.hpp (contents, props changed)
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp (contents, props changed)
Removed:
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/find.hpp
Text files modified:
sandbox-branches/geometry/index/boost/geometry/extensions/index/predicates.hpp | 27 +++++++
sandbox-branches/geometry/index/boost/geometry/extensions/index/pushable_array.hpp | 6 +
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/predicates.hpp | 30 ++++++++
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp | 134 ++++++++++++++++++++++++++++++++-------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp | 4 -
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/query.hpp | 5 +
sandbox-branches/geometry/index/tests/additional_glut_vis.cpp | 71 +++++++++++++++++---
sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp | 46 +++++++++---
8 files changed, 268 insertions(+), 55 deletions(-)
Added: sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/detail/smallest_for_indexable.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/detail/smallest_for_indexable.hpp 2011-09-16 15:44:04 EDT (Fri, 16 Sep 2011)
@@ -0,0 +1,83 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - Get smallest value calculated for indexable's dimensions, used in R-tree k nearest neighbors query
+//
+// Copyright 2011 Adam Wulkiewicz.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_DETAIL_SMALLEST_FOR_INDEXABLE_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_DETAIL_SMALLEST_FOR_INDEXABLE_HPP
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail {
+
+template <
+ typename Geometry,
+ typename Indexable,
+ typename IndexableTag,
+ typename AlgoTag,
+ size_t DimensionIndex>
+struct smallest_for_indexable_dimension
+{
+ BOOST_MPL_ASSERT_MSG(
+ (false),
+ NOT_IMPLEMENTED_FOR_THIS_INDEXABLE_TAG_TYPE,
+ (smallest_for_indexable_dimension));
+};
+
+template <
+ typename Geometry,
+ typename Indexable,
+ typename IndexableTag,
+ typename AlgoTag,
+ size_t N>
+struct smallest_for_indexable
+{
+ typedef typename smallest_for_indexable_dimension<
+ Geometry, Indexable, IndexableTag, AlgoTag, N - 1
+ >::result_type result_type;
+
+ template <typename Data>
+ inline static result_type apply(Geometry const& g, Indexable const& i, Data const& data)
+ {
+ result_type r1 = smallest_for_indexable<
+ Geometry, Indexable, IndexableTag, AlgoTag, N - 1
+ >::apply(g, i, data);
+
+ result_type r2 = smallest_for_indexable_dimension<
+ Geometry, Indexable, IndexableTag, AlgoTag, N - 1
+ >::apply(g, i, data);
+
+ return r1 < r2 ? r1 : r2;
+ }
+};
+
+template <
+ typename Geometry,
+ typename Indexable,
+ typename IndexableTag,
+ typename AlgoTag>
+struct smallest_for_indexable<Geometry, Indexable, IndexableTag, AlgoTag, 1>
+{
+ typedef typename smallest_for_indexable_dimension<
+ Geometry, Indexable, IndexableTag, AlgoTag, 0
+ >::result_type result_type;
+
+ template <typename Data>
+ inline static result_type apply(Geometry const& g, Indexable const& i, Data const& data)
+ {
+ return
+ smallest_for_indexable_dimension<
+ Geometry, Indexable, IndexableTag, AlgoTag, 0
+ >::apply(g, i, data);
+ }
+};
+
+} // namespace detail
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_DETAIL_SMALLEST_FOR_INDEXABLE_HPP
Added: sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/detail/sum_for_indexable.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/detail/sum_for_indexable.hpp 2011-09-16 15:44:04 EDT (Fri, 16 Sep 2011)
@@ -0,0 +1,79 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - Sum values calculated for indexable's dimensions, used e.g. in R-tree k nearest neighbors query
+//
+// Copyright 2011 Adam Wulkiewicz.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_DETAIL_SUM_FOR_INDEXABLE_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_DETAIL_SUM_FOR_INDEXABLE_HPP
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail {
+
+template <
+ typename Geometry,
+ typename Indexable,
+ typename IndexableTag,
+ typename AlgoTag,
+ size_t DimensionIndex>
+struct sum_for_indexable_dimension
+{
+ BOOST_MPL_ASSERT_MSG(
+ (false),
+ NOT_IMPLEMENTED_FOR_THIS_INDEXABLE_TAG_TYPE,
+ (sum_for_indexable_dimension));
+};
+
+template <
+ typename Geometry,
+ typename Indexable,
+ typename IndexableTag,
+ typename AlgoTag,
+ size_t N>
+struct sum_for_indexable
+{
+ typedef typename sum_for_indexable_dimension<
+ Geometry, Indexable, IndexableTag, AlgoTag, N - 1
+ >::result_type result_type;
+
+ inline static result_type apply(Geometry const& g, Indexable const& i)
+ {
+ return
+ sum_for_indexable<
+ Geometry, Indexable, IndexableTag, AlgoTag, N - 1
+ >::apply(g, i) +
+ sum_for_indexable_dimension<
+ Geometry, Indexable, IndexableTag, AlgoTag, N - 1
+ >::apply(g, i);
+ }
+};
+
+template <
+ typename Geometry,
+ typename Indexable,
+ typename IndexableTag,
+ typename AlgoTag>
+struct sum_for_indexable<Geometry, Indexable, IndexableTag, AlgoTag, 1>
+{
+ typedef typename sum_for_indexable_dimension<
+ Geometry, Indexable, IndexableTag, AlgoTag, 0
+ >::result_type result_type;
+
+ inline static result_type apply(Geometry const& g, Indexable const& i)
+ {
+ return
+ sum_for_indexable_dimension<
+ Geometry, Indexable, IndexableTag, AlgoTag, 0
+ >::apply(g, i);
+ }
+};
+
+} // namespace detail
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_DETAIL_SUM_FOR_INDEXABLE_HPP
Added: sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/mindist.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/mindist.hpp 2011-09-16 15:44:04 EDT (Fri, 16 Sep 2011)
@@ -0,0 +1,80 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - mindist used in R-tree k nearest neighbors query
+//
+// Copyright 2011 Adam Wulkiewicz.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_MINDIST_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_MINDIST_HPP
+
+#include <boost/geometry/extensions/index/algorithms/detail/sum_for_indexable.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail {
+
+struct mindist_tag {};
+
+template <
+ typename Point,
+ typename PointIndexable,
+ size_t N>
+struct sum_for_indexable<Point, PointIndexable, point_tag, mindist_tag, N>
+{
+ typedef typename geometry::default_distance_result<Point, PointIndexable>::type result_type;
+
+ inline static result_type apply(Point const& pt, PointIndexable const& i)
+ {
+ return geometry::comparable_distance(pt, i);
+ }
+};
+
+template <
+ typename Point,
+ typename BoxIndexable,
+ size_t DimensionIndex>
+struct sum_for_indexable_dimension<Point, BoxIndexable, box_tag, mindist_tag, DimensionIndex>
+{
+ typedef typename geometry::default_distance_result<Point, BoxIndexable>::type result_type;
+
+ inline static result_type apply(Point const& pt, BoxIndexable const& i)
+ {
+ typedef typename index::traits::coordinate_type<Point>::type point_coord_t;
+ typedef typename index::traits::coordinate_type<BoxIndexable>::type indexable_coord_t;
+
+ point_coord_t pt_c = geometry::get<DimensionIndex>(pt);
+ indexable_coord_t ind_c_min = geometry::get<geometry::min_corner, DimensionIndex>(i);
+ indexable_coord_t ind_c_max = geometry::get<geometry::max_corner, DimensionIndex>(i);
+
+ result_type diff = 0;
+
+ if ( pt_c < ind_c_min )
+ diff = ind_c_min - pt_c;
+ else if ( ind_c_max < pt_c )
+ diff = pt_c - ind_c_max;
+
+ return diff * diff;
+ }
+};
+
+} // namespace detail
+
+template <typename Point, typename Indexable>
+typename geometry::default_distance_result<Point, Indexable>::type
+mindist(Point const& pt, Indexable const& i)
+{
+ return detail::sum_for_indexable<
+ Point,
+ Indexable,
+ typename index::traits::tag<Indexable>::type,
+ detail::mindist_tag,
+ index::traits::dimension<Indexable>::value
+ >::apply(pt, i);
+}
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_MINDIST_HPP
Added: sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/minmaxdist.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/minmaxdist.hpp 2011-09-16 15:44:04 EDT (Fri, 16 Sep 2011)
@@ -0,0 +1,168 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - minmaxdist used in R-tree k nearest neighbors query
+//
+// Copyright 2011 Adam Wulkiewicz.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_MINMAXDIST_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_MINMAXDIST_HPP
+
+#include <boost/geometry/extensions/index/algorithms/detail/sum_for_indexable.hpp>
+#include <boost/geometry/extensions/index/algorithms/detail/smallest_for_indexable.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail {
+
+// awulkiew - use if unsigned values may be used as coordinates
+template <typename T>
+inline T diff_abs(T const& v1, T const& v2)
+{
+ return v1 < v2 ? v2 - v1 : v1 - v2;
+}
+
+// minmaxdist component
+
+struct minmaxdist_comp_tag {};
+
+template <
+ typename Point,
+ typename BoxIndexable,
+ size_t DimensionIndex>
+struct sum_for_indexable_dimension<Point, BoxIndexable, box_tag, minmaxdist_comp_tag, DimensionIndex>
+{
+ typedef typename geometry::default_distance_result<Point, BoxIndexable>::type result_type;
+
+ inline static result_type apply(Point const& pt, BoxIndexable const& i)
+ {
+ typedef typename index::traits::coordinate_type<Point>::type point_coord_t;
+ typedef typename index::traits::coordinate_type<BoxIndexable>::type indexable_coord_t;
+
+ point_coord_t pt_c = geometry::get<DimensionIndex>(pt);
+ indexable_coord_t ind_c_min = geometry::get<geometry::min_corner, DimensionIndex>(i);
+ indexable_coord_t ind_c_max = geometry::get<geometry::max_corner, DimensionIndex>(i);
+
+ result_type further_diff = 0;
+
+ if ( (ind_c_min + ind_c_max) / 2 <= pt_c )
+ further_diff = pt_c - ind_c_min;
+ else
+ further_diff = diff_abs(pt_c, ind_c_max); // unsigned values protection
+
+ return further_diff * further_diff;
+ }
+};
+
+template <typename Point, typename Indexable>
+typename geometry::default_distance_result<Point, Indexable>::type
+minmaxdist_comp(Point const& pt, Indexable const& i)
+{
+ return sum_for_indexable<
+ Point,
+ Indexable,
+ typename index::traits::tag<Indexable>::type,
+ minmaxdist_comp_tag,
+ index::traits::dimension<Indexable>::value
+ >::apply(pt, i);
+}
+
+// minmaxdist
+
+struct minmaxdist_tag {};
+
+template <
+ typename Point,
+ typename BoxIndexable,
+ size_t DimensionIndex>
+struct smallest_for_indexable_dimension<Point, BoxIndexable, box_tag, minmaxdist_tag, DimensionIndex>
+{
+ typedef typename geometry::default_distance_result<Point, BoxIndexable>::type result_type;
+
+ inline static result_type apply(Point const& pt, BoxIndexable const& i, result_type const& comp)
+ {
+ typedef typename index::traits::coordinate_type<Point>::type point_coord_t;
+ typedef typename index::traits::coordinate_type<BoxIndexable>::type indexable_coord_t;
+
+ point_coord_t pt_c = geometry::get<DimensionIndex>(pt);
+ indexable_coord_t ind_c_min = geometry::get<geometry::min_corner, DimensionIndex>(i);
+ indexable_coord_t ind_c_max = geometry::get<geometry::max_corner, DimensionIndex>(i);
+
+ indexable_coord_t ind_c_avg = (ind_c_min + ind_c_max) / 2;
+
+ // TODO: awulkiew - optimize! don't calculate 2x pt_c <= ind_c_avg
+ // take particular case pt_c == ind_c_avg into account
+
+ result_type closer_comp = 0;
+ if ( pt_c <= ind_c_avg )
+ closer_comp = diff_abs(pt_c, ind_c_min); // unsigned values protection
+ else
+ closer_comp = diff_abs(pt_c, ind_c_max); // unsigned values protection
+
+ result_type further_comp = 0;
+ if ( ind_c_avg <= pt_c )
+ further_comp = pt_c - ind_c_min;
+ else
+ further_comp = diff_abs(pt_c, ind_c_max); // unsigned values protection
+
+ return (comp + closer_comp * closer_comp) - further_comp * further_comp;
+ }
+};
+
+template <typename Point, typename Indexable, typename IndexableTag>
+struct minmaxdist_impl
+{
+ BOOST_MPL_ASSERT_MSG(
+ (false),
+ NOT_IMPLEMENTED_FOR_THIS_INDEXABLE_TAG_TYPE,
+ (minmaxdist_impl));
+};
+
+template <typename Point, typename Indexable>
+struct minmaxdist_impl<Point, Indexable, point_tag>
+{
+ typedef typename geometry::default_distance_result<Point, Indexable>::type result_type;
+
+ inline static result_type apply(Point const& pt, Indexable const& i)
+ {
+ return geometry::comparable_distance(pt, i);
+ }
+};
+
+template <typename Point, typename Indexable>
+struct minmaxdist_impl<Point, Indexable, box_tag>
+{
+ typedef typename geometry::default_distance_result<Point, Indexable>::type result_type;
+
+ inline static result_type apply(Point const& pt, Indexable const& i)
+ {
+ result_type comp = minmaxdist_comp(pt, i);
+
+ return smallest_for_indexable<
+ Point,
+ Indexable,
+ box_tag,
+ minmaxdist_tag,
+ index::traits::dimension<Indexable>::value
+ >::apply(pt, i, comp);
+ }
+};
+
+} // namespace detail
+
+template <typename Point, typename Indexable>
+typename geometry::default_distance_result<Point, Indexable>::type
+minmaxdist(Point const& pt, Indexable const& i)
+{
+ return detail::minmaxdist_impl<
+ Point,
+ Indexable,
+ typename index::traits::tag<Indexable>::type
+ >::apply(pt, i);
+}
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_MINMAXDIST_HPP
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/predicates.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/predicates.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/predicates.hpp 2011-09-16 15:44:04 EDT (Fri, 16 Sep 2011)
@@ -23,8 +23,11 @@
namespace detail {
+struct empty {};
+
template <typename Geometry>
struct covered_by
+ : nonassignable
{
covered_by(Geometry const& g) : geometry(g) {}
Geometry const& geometry;
@@ -32,6 +35,7 @@
template <typename Geometry>
struct intersects
+ : nonassignable
{
intersects(Geometry const& g) : geometry(g) {}
Geometry const& geometry;
@@ -39,6 +43,7 @@
template <typename Geometry>
struct overlaps
+ : nonassignable
{
overlaps(Geometry const& g) : geometry(g) {}
Geometry const& geometry;
@@ -46,6 +51,7 @@
template <typename Geometry>
struct within
+ : nonassignable
{
within(Geometry const& g) : geometry(g) {}
Geometry const& geometry;
@@ -53,6 +59,11 @@
} // namespace detail
+inline detail::empty empty()
+{
+ return detail::empty();
+}
+
template <typename Geometry>
inline detail::covered_by<Geometry> covered_by(Geometry const& g)
{
@@ -77,11 +88,11 @@
return detail::within<Geometry>(g);
}
-// predicates checks
-
namespace detail
{
+// predicate check
+
template <typename Geometry, typename Tag>
struct predicate_check
{
@@ -92,6 +103,16 @@
}
};
+template <typename Tag>
+struct predicate_check<empty, Tag>
+{
+ template <typename Geometry, typename Indexable>
+ static inline bool apply(Geometry const&, Indexable const&)
+ {
+ return true;
+ }
+};
+
template <typename Geometry, typename Tag>
struct predicate_check<covered_by<Geometry>, Tag>
{
@@ -132,6 +153,8 @@
}
};
+// predicates check
+
template <typename TuplePredicates, typename Tag, unsigned int N>
struct predicates_check_tuple
{
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/pushable_array.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/pushable_array.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/pushable_array.hpp 2011-09-16 15:44:04 EDT (Fri, 16 Sep 2011)
@@ -141,6 +141,12 @@
m_array[m_size++] = v;
}
+ inline void pop_back()
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
+ --m_size;
+ }
+
inline bool empty() const
{
return m_size == 0;
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/predicates.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/predicates.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/predicates.hpp 2011-09-16 15:44:04 EDT (Fri, 16 Sep 2011)
@@ -23,6 +23,16 @@
} // namespace rtree
+//template <typename Geometry>
+//struct predicate_check<Geometry, rtree::node_predicates_tag>
+//{
+// template <typename Indexable>
+// static inline bool apply(Geometry const& g, Indexable const& i)
+// {
+// return geometry::intersects(i, g);
+// }
+//};
+
template <typename Geometry>
struct predicate_check<covered_by<Geometry>, rtree::node_predicates_tag>
{
@@ -33,6 +43,26 @@
}
};
+//template <typename Geometry>
+//struct predicate_check<intersects<Geometry>, rtree::node_predicates_tag>
+//{
+// template <typename Indexable>
+// static inline bool apply(intersects<Geometry> const& p, Indexable const& i)
+// {
+// return geometry::intersects(i, p.geometry);
+// }
+//};
+//
+//template <typename Geometry>
+//struct predicate_check<overlaps<Geometry>, rtree::node_predicates_tag>
+//{
+// template <typename Indexable>
+// static inline bool apply(overlaps<Geometry> const& p, Indexable const& i)
+// {
+// return geometry::overlaps(i, p.geometry);
+// }
+//};
+
template <typename Geometry>
struct predicate_check<within<Geometry>, rtree::node_predicates_tag>
{
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 2011-09-16 15:44:04 EDT (Fri, 16 Sep 2011)
@@ -20,15 +20,15 @@
#include <boost/geometry/extensions/index/nonassignable.hpp>
#include <boost/geometry/extensions/index/translator/translator.hpp>
-
#include <boost/geometry/extensions/index/rtree/options.hpp>
+
#include <boost/geometry/extensions/index/rtree/predicates.hpp>
//#include <boost/geometry/extensions/index/rtree/filters.hpp>
#include <boost/geometry/extensions/index/rtree/node/node.hpp>
-#include <boost/geometry/extensions/index/rtree/visitors/find.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/query.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/nearest.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/destroy.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/insert.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/remove.hpp>
@@ -78,25 +78,44 @@
}
template <typename Predicates, typename OutIter>
- inline void query(Predicates const& pred, OutIter out_it) const
+ inline size_t query(Predicates const& pred, OutIter out_it) const
{
detail::rtree::visitors::query<value_type, options_type, translator_type, box_type, Predicates, OutIter>
find_v(m_translator, pred, out_it);
detail::rtree::apply_visitor(find_v, *m_root);
+
+ return find_v.found_count;
}
- // TODO: delete find method
- template <typename Geometry, typename OutIter>
- inline void find(Geometry const& geom, OutIter out_it) const
+ // TODO: awulkiew - change Point to Geometry?
+ // return number of elements instead of bool?
+
+ template <typename Point>
+ inline size_t nearest(Point const& pt, value_type & v) const
{
- detail::rtree::visitors::find<value_type, options_type, translator_type, box_type, Geometry, OutIter>
- find_v(m_translator, geom, out_it);
+ return nearest_one(pt, detail::empty(), v);
+ }
- detail::rtree::apply_visitor(find_v, *m_root);
+ template <typename Point, typename Predicates>
+ inline size_t nearest(Point const& pt, Predicates const& pred, value_type & v) const
+ {
+ return nearest_one(pt, pred, v);
+ }
+
+ template <typename Point, typename OutIter>
+ inline size_t nearest(Point const& pt, size_t k, OutIter out_it) const
+ {
+ return nearest_k(pt, k, detail::empty(), out_it);
}
- void insert(value_type const& value)
+ template <typename Point, typename Predicates, typename OutIter>
+ inline size_t nearest(Point const& pt, size_t k, Predicates const& pred, OutIter out_it) const
+ {
+ return nearest_k(pt, k, pred, out_it);
+ }
+
+ inline void insert(value_type const& value)
{
// TODO: awulkiew - assert for correct value
@@ -108,7 +127,7 @@
++m_values_count;
}
- void remove(value_type const& value)
+ inline void remove(value_type const& value)
{
// TODO: awulkiew - assert for correct value
@@ -122,40 +141,77 @@
--m_values_count;
}
- size_t size() const
+ inline size_t size() const
{
return m_values_count;
}
- bool empty() const
+ inline bool empty() const
{
- // TODO: awulkiew - take root into consideration
return 0 == m_values_count;
}
- void clear()
- {
- // TODO: awulkiew - implement
- BOOST_GEOMETRY_INDEX_ASSERT(false, "not implemented");
- }
+ // TODO: awulkiew
+ // clear()
+ // aabb/box/get_box/etc.
+ // iterators, begin/end/etc.
+
+ //inline void clear()
+ //{
+ // // TODO: awulkiew - implement
+ // BOOST_GEOMETRY_INDEX_ASSERT(false, "not implemented");
+ //}
template <typename Visitor>
- void apply_visitor(Visitor & visitor) const
+ inline void apply_visitor(Visitor & visitor) const
{
detail::rtree::apply_visitor(visitor, *m_root);
}
- translator_type const& get_translator() const
+ inline translator_type const& get_translator() const
{
return m_translator;
}
- size_t values_count() const
+ inline size_t values_count() const
{
return m_values_count;
}
+ inline size_t depth() const
+ {
+ return m_leafs_level;
+ }
+
private:
+ template <typename Point, typename Predicates>
+ inline size_t nearest_one(Point const& pt, Predicates const& pred, value_type & v) const
+ {
+ typedef detail::rtree::visitors::nearest_one<value_type, translator_type, Point> result_type;
+ result_type result;
+
+ detail::rtree::visitors::nearest<value_type, options_type, translator_type, box_type, Point, Predicates, result_type>
+ nearest_v(m_translator, pt, pred, result);
+
+ detail::rtree::apply_visitor(nearest_v, *m_root);
+
+ return result.get(v);
+ }
+
+ template <typename Point, typename Predicates, typename OutIter>
+ inline size_t nearest_k(Point const& pt, size_t k, Predicates const& pred, OutIter out_it) const
+ {
+ typedef detail::rtree::visitors::nearest_k<value_type, translator_type, Point> result_type;
+ result_type result(k);
+
+ detail::rtree::visitors::nearest<value_type, options_type, translator_type, box_type, Point, Predicates, result_type>
+ nearest_v(m_translator, pt, pred, result);
+
+ detail::rtree::apply_visitor(nearest_v, *m_root);
+
+ return result.get(out_it);
+ }
+
size_t m_values_count;
node *m_root;
size_t m_leafs_level;
@@ -163,17 +219,47 @@
};
template <typename Value, typename Options, typename Translator>
-void insert(rtree<Value, Options, Translator> & tree, Value const& v)
+inline void insert(rtree<Value, Options, Translator> & tree, Value const& v)
{
tree.insert(v);
}
template <typename Value, typename Options, typename Translator>
-void remove(rtree<Value, Options, Translator> & tree, Value const& v)
+inline void remove(rtree<Value, Options, Translator> & tree, Value const& v)
{
tree.remove(v);
}
+template <typename Value, typename Options, typename Translator, typename Predicates, typename OutIter>
+inline size_t query(rtree<Value, Options, Translator> const& tree, Predicates const& pred, OutIter out_it)
+{
+ return tree.query(pred, out_it);
+}
+
+template <typename Value, typename Options, typename Translator, typename Point>
+inline size_t nearest(rtree<Value, Options, Translator> const& tree, Point const& pt, Value & v)
+{
+ return tree.nearest(pt, v);
+}
+
+template <typename Value, typename Options, typename Translator, typename Point, typename Predicates>
+inline size_t nearest(rtree<Value, Options, Translator> const& tree, Point const& pt, Predicates const& pred, Value & v)
+{
+ return tree.nearest(pt, pred, v);
+}
+
+template <typename Value, typename Options, typename Translator, typename Point, typename OutIter>
+inline size_t nearest(rtree<Value, Options, Translator> const& tree, Point const& pt, size_t k, OutIter out_it)
+{
+ return tree.nearest(pt, k, out_it);
+}
+
+template <typename Value, typename Options, typename Translator, typename Point, typename Predicates, typename OutIter>
+inline size_t nearest(rtree<Value, Options, Translator> const& tree, Point const& pt, size_t k, Predicates const& pred, OutIter out_it)
+{
+ return tree.nearest(pt, k, pred, out_it);
+}
+
}}} // namespace boost::geometry::index
#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RTREE_HPP
Deleted: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/find.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/find.hpp 2011-09-16 15:44:04 EDT (Fri, 16 Sep 2011)
+++ (empty file)
@@ -1,232 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Boost.Index - R-tree find
-//
-// Copyright 2011 Adam Wulkiewicz.
-// Use, modification and distribution is subject to the Boost Software License,
-// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
-// http://www.boost.org/LICENSE_1_0.txt)
-
-#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_FIND_HPP
-#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_FIND_HPP
-
-#include <boost/geometry/extensions/index/rtree/node/node.hpp>
-
-//#include <boost/geometry/extensions/index/rtree/visitors/is_leaf.hpp>
-
-namespace boost { namespace geometry { namespace index {
-
-namespace detail { namespace rtree { namespace visitors {
-
-//template <size_t N, typename T>
-//class array
-//{
-//public:
-// inline array()
-// : arr_elements(0)
-// {}
-//
-// inline void push(T const& v)
-// {
-// arr[arr_elements++] = v;
-// }
-//
-// inline T pop()
-// {
-// assert(0 < arr_elements);
-// return arr[--arr_elements];
-// }
-//
-// inline bool empty() const
-// {
-// return 0 == arr_elements;
-// }
-//
-// inline size_t size() const
-// {
-// return arr_elements;
-// }
-//
-//private:
-// boost::array<T, N> arr;
-// size_t arr_elements;
-//};
-//
-//template <typename Cont>
-//class dynamic
-//{
-//public:
-// typedef typename Cont::value_type value_type;
-//
-// inline void push(value_type const& v)
-// {
-// cont.push_back(v);
-// }
-//
-// inline value_type pop()
-// {
-// value_type v = cont.back();
-// cont.pop_back();
-// return v;
-// }
-//
-// inline bool empty() const
-// {
-// return cont.empty();
-// }
-//
-// inline size_t size() const
-// {
-// return cont.size();
-// }
-//
-// inline void clear()
-// {
-// cont.clear();
-// }
-//
-//private:
-// Cont cont;
-//};
-//
-//template <size_t N, typename Cont>
-//class array_semi_dynamic
-//{
-//public:
-// typedef typename Cont::value_type value_type;
-//
-// inline array_semi_dynamic()
-// : arr_elements(0)
-// {}
-//
-// inline void push(value_type const& v)
-// {
-// if ( arr_elements < N )
-// arr[arr_elements++] = v;
-// else
-// cont.push_back(v);
-// }
-//
-// inline value_type pop()
-// {
-// if ( !cont.empty() )
-// {
-// value_type v = cont.back();
-// cont.pop_back();
-// return v;
-// }
-// else
-// {
-// assert(0 < arr_elements);
-// return arr[--arr_elements];
-// }
-// }
-//
-// inline bool empty() const
-// {
-// return cont.empty() && 0 == arr_elements;
-// }
-//
-// inline size_t size() const
-// {
-// return arr_elements + cont.size();
-// }
-//
-//private:
-// boost::array<value_type, N> arr;
-// size_t arr_elements;
-// Cont cont;
-//};
-
-// rtree spatial query visitor
-
-template <typename Value, typename Options, typename Translator, typename Box, typename Geometry, typename OutIter>
-struct find
- : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, true>::type
- , index::nonassignable
-{
- typedef typename rtree::node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type node;
- typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
-
- inline find(Translator const& t, Geometry const& g, OutIter out_it)
- : tr(t), geom(g), out_iter(out_it)
- {}
-
- inline void operator()(internal_node const& n)
- {
- //typedef typename internal_node::children_type children_type;
-
- //array_semi_dynamic<1024, std::deque<node*> > nodes;
- ////array<1024, node*> nodes;
- ////dynamic< std::deque<node*> > nodes;
- //
- //for (typename children_type::const_iterator it = n.children.begin();
- // it != n.children.end(); ++it)
- //{
- // if ( geometry::intersects(it->first, geom) )
- // {
- // nodes.push(it->second);
- // }
- //}
-
- //while ( !nodes.empty() )
- //{
- // node *n = nodes.pop();
-
- // if ( !boost::apply_visitor(visitors::is_leaf<Value, Box, Tag>(), *n) )
- // {
- // internal_node &in = boost::get<internal_node>(*n);
-
- // for (typename children_type::const_iterator it = in.children.begin();
- // it != in.children.end(); ++it)
- // {
- // if ( geometry::intersects(it->first, geom) )
- // {
- // nodes.push(it->second);
- // }
- // }
- // }
- // else
- // {
- // operator()(boost::get<leaf>(*n));
- // }
- //}
-
- typedef typename rtree::elements_type<internal_node>::type elements_type;
- elements_type const& elements = rtree::elements(n);
-
- for (typename elements_type::const_iterator it = elements.begin();
- it != elements.end(); ++it)
- {
- if ( geometry::intersects(it->first, geom) )
- rtree::apply_visitor(*this, *it->second);
- }
- }
-
- inline void operator()(leaf const& n)
- {
- typedef typename rtree::elements_type<leaf>::type elements_type;
- elements_type const& elements = rtree::elements(n);
-
- for (typename elements_type::const_iterator it = elements.begin();
- it != elements.end(); ++it)
- {
- if ( geometry::intersects(tr(*it), geom) )
- {
- out_iter = *it;
- ++out_iter;
- }
- }
- }
-
- Translator const& tr;
- Geometry const& geom;
- OutIter out_iter;
-};
-
-}}} // namespace detail::rtree::visitors
-
-}}} // namespace boost::geometry::index
-
-#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_VISITORS_FIND_HPP
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 2011-09-16 15:44:04 EDT (Fri, 16 Sep 2011)
@@ -200,14 +200,10 @@
typedef typename rtree<Value, Options, Translator>::translator_type translator_type;
typedef typename rtree<Value, Options, Translator>::box_type box_type;
- glClear(GL_COLOR_BUFFER_BIT);
-
detail::rtree::visitors::gl_draw<value_type, options_type, translator_type, box_type>
gl_draw_v(tree.get_translator(), level_first, level_last, z_coord_level_multiplier);
tree.apply_visitor(gl_draw_v);
-
- glFlush();
}
}}} // namespace boost::geometry::index
Added: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp 2011-09-16 15:44:04 EDT (Fri, 16 Sep 2011)
@@ -0,0 +1,246 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree k nearest neighbors query
+//
+// Copyright 2011 Adam Wulkiewicz.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_NEAREST_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_NEAREST_HPP
+
+#include <boost/geometry/extensions/index/algorithms/mindist.hpp>
+#include <boost/geometry/extensions/index/algorithms/minmaxdist.hpp>
+
+#include <boost/geometry/extensions/index/rtree/node/node.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail { namespace rtree { namespace visitors {
+
+template <typename Value, typename Translator, typename Point>
+struct nearest_one
+{
+public:
+ typedef typename Translator::indexable_type indexable_type;
+ typedef typename geometry::default_distance_result<Point, indexable_type>::type distance_type;
+
+ inline nearest_one()
+ : comp_mindist(std::numeric_limits<distance_type>::max())
+ {}
+
+ inline void store(Value const& val, distance_type const& curr_mindist)
+ {
+ if ( curr_mindist < comp_mindist )
+ {
+ comp_mindist = curr_mindist;
+ value = val;
+ }
+ }
+
+ inline bool is_mindist_valid() const
+ {
+ return comp_mindist < std::numeric_limits<distance_type>::max();
+ }
+
+ inline distance_type mindist() const
+ {
+ return comp_mindist;
+ }
+
+ inline size_t get(Value & v)
+ {
+ v = value;
+ return is_mindist_valid() ? 1 : 0;
+ }
+
+private:
+ Value value;
+ distance_type comp_mindist;
+};
+
+template <typename Value, typename Translator, typename Point>
+struct nearest_k
+{
+public:
+ typedef typename Translator::indexable_type indexable_type;
+ typedef typename geometry::default_distance_result<Point, indexable_type>::type distance_type;
+
+ inline explicit nearest_k(size_t k)
+ : m_count(k)
+ {
+ // TEMP?
+ m_neighbors.reserve(m_count + 1);
+ }
+
+ inline void store(Value const& val, distance_type const& curr_mindist)
+ {
+ m_neighbors.push_back(std::make_pair(curr_mindist, val));
+ std::sort(m_neighbors.begin(), m_neighbors.end(), neighbors_less);
+
+ if ( m_count < m_neighbors.size() )
+ m_neighbors.pop_back();
+
+ // TODO: awulkiew - test other methods:
+ // heap, manual inserting
+ // don't sort if size < k ?
+ }
+
+ inline bool is_mindist_valid() const
+ {
+ return m_neighbors.size() == m_count;
+ }
+
+ inline distance_type mindist() const
+ {
+ return m_neighbors.size() < m_count ?
+ std::numeric_limits<distance_type>::max() :
+ m_neighbors.back().first;
+ }
+
+ template <typename OutIter>
+ inline size_t get(OutIter & out_it)
+ {
+ typedef typename std::vector< std::pair<distance_type, Value> >::const_iterator neighbors_iterator;
+ for ( neighbors_iterator it = m_neighbors.begin() ; it != m_neighbors.end() ; ++it )
+ *out_it = it->second;
+
+ return m_neighbors.size();
+ }
+
+private:
+ inline static bool neighbors_less(
+ std::pair<distance_type, Value> const& p1,
+ std::pair<distance_type, Value> const& p2)
+ {
+ return p1.first < p2.first;
+ }
+
+ size_t m_count;
+ std::vector< std::pair<distance_type, Value> > m_neighbors;
+};
+
+template <
+ typename Value,
+ typename Options,
+ typename Translator,
+ typename Box,
+ typename Point,
+ typename Predicates,
+ typename Result = typename geometry::default_distance_result<
+ Point,
+ typename Translator::indexable_type
+ >::type
+>
+class nearest
+ : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, true>::type
+ , index::nonassignable
+{
+public:
+ typedef typename rtree::node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type node;
+ typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
+
+ typedef typename geometry::default_distance_result<Point, Box>::type node_distance_type;
+
+ inline nearest(Translator const& t, Point const& pt, Predicates const& pr, Result & r)
+ : m_tr(t), m_point(pt), m_pred(pr)
+ , m_result(r)
+ {}
+
+ inline void operator()(internal_node const& n)
+ {
+ // array of active nodes
+ index::pushable_array<
+ std::pair<node_distance_type, const node *>,
+ Options::parameters_type::max_elements
+ > active_branch_list;
+
+ typedef typename rtree::elements_type<internal_node>::type elements_type;
+ elements_type const& elements = rtree::elements(n);
+
+ // fill array of nodes meeting predicates
+ for (typename elements_type::const_iterator it = elements.begin();
+ it != elements.end(); ++it)
+ {
+ if ( index::predicates_check<rtree::node_predicates_tag>(m_pred, it->first) )
+ {
+ active_branch_list.push_back(
+ std::make_pair(index::mindist(m_point, it->first), it->second)
+ );
+ }
+ }
+
+ // if there aren't any nodes in ABL - return
+ if ( active_branch_list.empty() )
+ return;
+
+ // sort array
+ std::sort(active_branch_list.begin(), active_branch_list.end(), abl_mindist_less);
+
+ // recursively visit nodes
+ for ( size_t i = 0 ;; ++i )
+ {
+ // prune nodes
+ prune_nodes(active_branch_list);
+
+ if ( active_branch_list.size() <= i )
+ break;
+
+ rtree::apply_visitor(*this, *active_branch_list[i].second);
+ }
+ }
+
+ inline void operator()(leaf const& n)
+ {
+ typedef typename rtree::elements_type<leaf>::type elements_type;
+ elements_type const& elements = rtree::elements(n);
+
+ // search leaf for closest value meeting predicates
+ for (typename elements_type::const_iterator it = elements.begin();
+ it != elements.end(); ++it)
+ {
+ if ( index::predicates_check<rtree::value_predicates_tag>(m_pred, m_tr(*it)) )
+ {
+ // store value
+ m_result.store(*it, index::mindist(m_point, m_tr(*it)));
+ }
+ }
+ }
+
+private:
+ inline static bool abl_mindist_less(
+ std::pair<node_distance_type, const node *> const& p1,
+ std::pair<node_distance_type, const node *> const& p2)
+ {
+ return p1.first < p2.first;
+ }
+
+ template <typename ActiveBranchList>
+ inline void prune_nodes(ActiveBranchList & abl) const
+ {
+ // if some value were found
+ if ( m_result.is_mindist_valid() )
+ {
+ // prune if box's mindist is further than value's mindist
+ while ( !abl.empty() &&
+ m_result.mindist() < abl.back().first )
+ {
+ abl.pop_back();
+ }
+ }
+ }
+
+ Translator const& m_tr;
+ Point const& m_point;
+ Predicates const& m_pred;
+
+ Result & m_result;
+};
+
+}}} // namespace detail::rtree::visitors
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_NEAREST_HPP
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/query.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/query.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/query.hpp 2011-09-16 15:44:04 EDT (Fri, 16 Sep 2011)
@@ -26,7 +26,7 @@
typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
inline query(Translator const& t, Predicates const& p, OutIter out_it)
- : tr(t), pred(p), out_iter(out_it)
+ : tr(t), pred(p), out_iter(out_it), found_count(0)
{}
inline void operator()(internal_node const& n)
@@ -54,6 +54,8 @@
{
out_iter = *it;
++out_iter;
+
+ ++found_count;
}
}
}
@@ -61,6 +63,7 @@
Translator const& tr;
Predicates const& pred;
OutIter out_iter;
+ size_t found_count;
};
}}} // namespace detail::rtree::visitors
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 2011-09-16 15:44:04 EDT (Fri, 16 Sep 2011)
@@ -20,14 +20,36 @@
typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
typedef boost::geometry::model::box<P> B;
//boost::geometry::index::rtree<B> t(2, 1);
+
boost::geometry::index::rtree<
B,
boost::geometry::index::rstar<4, 2> > t;
std::vector<B> vect;
+bool is_nearest = false;
+P search_point;
+std::vector<B> nearest_boxes;
+
void render_scene(void)
{
+ glClear(GL_COLOR_BUFFER_BIT);
+
boost::geometry::index::gl_draw(t);
+
+ if ( is_nearest )
+ {
+ glColor3f(1.0f, 0.5f, 0.0f);
+ glBegin(GL_TRIANGLES);
+ glVertex3f(boost::geometry::get<0>(search_point), boost::geometry::get<1>(search_point), t.depth());
+ glVertex3f(boost::geometry::get<0>(search_point) + 1, boost::geometry::get<1>(search_point), t.depth());
+ glVertex3f(boost::geometry::get<0>(search_point) + 1, boost::geometry::get<1>(search_point) + 1, t.depth());
+ glEnd();
+
+ for ( size_t i = 0 ; i < nearest_boxes.size() ; ++i )
+ boost::geometry::index::detail::rtree::visitors::detail::gl_draw_indexable(nearest_boxes[i], t.depth());
+ }
+
+ glFlush();
}
void resize(int w, int h)
@@ -65,16 +87,14 @@
boost::geometry::index::insert(t, b);
vect.push_back(b);
- std::cout << t << "\n\n";
-
std::cout << "inserted: ";
boost::geometry::index::detail::rtree::visitors::detail::print_indexable(std::cout, b);
std::cout << '\n';
- std::cout << ( boost::geometry::index::are_boxes_ok(t) ? "boxes OK\n" : "WRONG BOXES!\n" );
- std::cout << ( boost::geometry::index::are_levels_ok(t) ? "levels OK\n" : "WRONG LEVELS!\n" );
- std::cout << "\n\n";
- glutPostRedisplay();
+ std::cout << "\n" << t << "\n";
+ std::cout << ( boost::geometry::index::are_boxes_ok(t) ? "boxes OK\n" : "WRONG BOXES!\n" );
+ std::cout << ( boost::geometry::index::are_levels_ok(t) ? "levels OK\n" : "WRONG LEVELS!\n" );
+ std::cout << "\n";
}
else if ( button == GLUT_RIGHT_BUTTON && state == GLUT_DOWN )
{
@@ -87,16 +107,45 @@
boost::geometry::index::remove(t, b);
vect.erase(vect.begin() + i);
- std::cout << '\n' << t << "\n\n";
std::cout << "removed: ";
boost::geometry::index::detail::rtree::visitors::detail::print_indexable(std::cout, b);
std::cout << '\n';
- std::cout << ( boost::geometry::index::are_boxes_ok(t) ? "boxes OK\n" : "WRONG BOXES!\n" );
- std::cout << ( boost::geometry::index::are_levels_ok(t) ? "levels OK\n" : "WRONG LEVELS!\n" );
- std::cout << "\n\n";
- glutPostRedisplay();
+ std::cout << "\n" << t << "\n";
+ std::cout << ( boost::geometry::index::are_boxes_ok(t) ? "boxes OK\n" : "WRONG BOXES!\n" );
+ std::cout << ( boost::geometry::index::are_levels_ok(t) ? "levels OK\n" : "WRONG LEVELS!\n" );
+ std::cout << "\n";
+ }
+ else if ( button == GLUT_MIDDLE_BUTTON && state == GLUT_DOWN )
+ {
+ float x = ( rand() % 1000 ) / 10.0f;
+ float y = ( rand() % 1000 ) / 10.0f;
+
+ search_point = P(x, y);
+ nearest_boxes.clear();
+ is_nearest = t.nearest(search_point, 3, std::back_inserter(nearest_boxes));
+
+ if ( is_nearest )
+ {
+ std::cout << "search point: ";
+ boost::geometry::index::detail::rtree::visitors::detail::print_indexable(std::cout, search_point);
+ std::cout << "\nfound: ";
+ for ( size_t i = 0 ; i < nearest_boxes.size() ; ++i )
+ {
+ boost::geometry::index::detail::rtree::visitors::detail::print_indexable(std::cout, nearest_boxes[i]);
+ std::cout << '\n';
+ }
+ }
+ else
+ std::cout << "nearest not found\n";
+
+ std::cout << "\n" << t << "\n";
+ std::cout << ( boost::geometry::index::are_boxes_ok(t) ? "boxes OK\n" : "WRONG BOXES!\n" );
+ std::cout << ( boost::geometry::index::are_levels_ok(t) ? "levels OK\n" : "WRONG LEVELS!\n" );
+ std::cout << "\n";
}
+
+ glutPostRedisplay();
}
int main(int argc, char **argv)
Modified: sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp
==============================================================================
--- sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp (original)
+++ sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp 2011-09-16 15:44:04 EDT (Fri, 16 Sep 2011)
@@ -90,16 +90,21 @@
{
boost::mt19937 rng;
//rng.seed(static_cast<unsigned int>(std::time(0)));
-
float max_val = static_cast<float>(values_count / 2);
boost::uniform_real<float> range(-max_val, max_val);
-
boost::variate_generator<boost::mt19937&, boost::uniform_real<float> > rnd(rng, range);
+ //::srand( ::time(NULL) );
+ //float factor = values_count / float(RAND_MAX);
+ //float comp = values_count / 2;
+
std::cout << "randomizing data\n";
for ( size_t i = 0 ; i < values_count ; ++i )
{
coords.push_back(std::make_pair(rnd(), rnd()));
+ //float x = rand() * factor + comp;
+ //float y = rand() * factor + comp;
+ //coords.push_back( std::make_pair( x, y ));
}
std::cout << "randomized\n";
}
@@ -134,7 +139,7 @@
// searching test
{
- std::cout << "find(B) searching time test...\n";
+ std::cout << "query(intersects(B)) searching time test...\n";
tim.restart();
size_t temp = 0;
for (size_t i = 0 ; i < queries_count ; ++i )
@@ -142,7 +147,7 @@
float x = coords[i].first;
float y = coords[i].second;
std::deque< std::pair<B, size_t> > result;
- t.find(B(P(x - 10, y - 10), P(x + 10, y + 10)), std::back_inserter(result));
+ t.query(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))), std::back_inserter(result));
temp += result.size();
}
std::cout << "time: " << tim.elapsed() << "s\n";
@@ -151,7 +156,7 @@
// searching test
{
- std::cout << "query(intersects(B)) searching time test...\n";
+ std::cout << "query(B) searching time test...\n";
tim.restart();
size_t temp = 0;
for (size_t i = 0 ; i < queries_count ; ++i )
@@ -159,7 +164,7 @@
float x = coords[i].first;
float y = coords[i].second;
std::deque< std::pair<B, size_t> > result;
- t.query(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))), std::back_inserter(result));
+ t.query(B(P(x - 10, y - 10), P(x + 10, y + 10)), std::back_inserter(result));
temp += result.size();
}
std::cout << "time: " << tim.elapsed() << "s\n";
@@ -168,16 +173,31 @@
// searching test
{
- std::cout << "query(B) searching time test...\n";
+ std::cout << "nearest searching time test...\n";
tim.restart();
size_t temp = 0;
- for (size_t i = 0 ; i < queries_count ; ++i )
+ for (size_t i = 0 ; i < queries_count / 10 ; ++i )
{
- float x = coords[i].first;
- float y = coords[i].second;
- std::deque< std::pair<B, size_t> > result;
- t.query(B(P(x - 10, y - 10), P(x + 10, y + 10)), std::back_inserter(result));
- temp += result.size();
+ float x = coords[i].first + 100;
+ float y = coords[i].second + 100;
+ std::pair<B, size_t> result;
+ temp += t.nearest(P(x, y), result);
+ }
+ std::cout << "time: " << tim.elapsed() << "s\n";
+ std::cout << "found: " << temp << "\n";
+ }
+
+ // searching test
+ {
+ std::cout << "nearest searching time test...\n";
+ tim.restart();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count / 10 ; ++i )
+ {
+ float x = coords[i].first + 100;
+ float y = coords[i].second + 100;
+ std::vector< std::pair<B, size_t> > result;
+ temp += t.nearest(P(x, y), 5, std::back_inserter(result));
}
std::cout << "time: " << tim.elapsed() << "s\n";
std::cout << "found: " << temp << "\n";