Subject: [Boost-commit] svn:boost r74608 - in sandbox-branches/geometry/index: boost/geometry/extensions/index/rtree/visitors tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-09-29 07:48:13
Author: awulkiew
Date: 2011-09-29 07:48:13 EDT (Thu, 29 Sep 2011)
New Revision: 74608
URL: http://svn.boost.org/trac/boost/changeset/74608
Log:
k-nearest query optimized by use of heap instead of sorting.
Text files modified:
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp | 37 +++++++++++++++++++++++--------------
sandbox-branches/geometry/index/tests/rtree_function.hpp | 39 ++++++++++++++++++++++++++++++++++++++-
2 files changed, 61 insertions(+), 15 deletions(-)
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp 2011-09-29 07:48:13 EDT (Thu, 29 Sep 2011)
@@ -73,22 +73,30 @@
inline explicit nearest_k(size_t k)
: m_count(k)
{
- // TEMP?
- m_neighbors.reserve(m_count + 1);
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < m_count, "Number of neighbors should be greater than 0");
+
+ m_neighbors.reserve(m_count);
}
inline void store(Value const& val, distance_type const& curr_comp_dist)
{
- m_neighbors.push_back(std::make_pair(curr_comp_dist, val));
- std::sort(m_neighbors.begin(), m_neighbors.end(), neighbors_less);
-
- if ( m_count < m_neighbors.size() )
- m_neighbors.pop_back();
+ if ( m_neighbors.size() < m_count )
+ {
+ m_neighbors.push_back(std::make_pair(curr_comp_dist, val));
- // TODO: awulkiew - test other methods:
- // heap, manual inserting
- // don't sort if size < k ?
- // check the furthest distance at the first place, before push_back()
+ if ( m_neighbors.size() == m_count )
+ std::make_heap(m_neighbors.begin(), m_neighbors.end(), neighbors_less);
+ }
+ else
+ {
+ if ( curr_comp_dist < m_neighbors.front().first )
+ {
+ std::pop_heap(m_neighbors.begin(), m_neighbors.end(), neighbors_less);
+ m_neighbors.back().first = curr_comp_dist;
+ m_neighbors.back().second = val;
+ std::push_heap(m_neighbors.begin(), m_neighbors.end(), neighbors_less);
+ }
+ }
}
inline bool is_comparable_distance_valid() const
@@ -98,9 +106,9 @@
inline distance_type comparable_distance() const
{
- return m_neighbors.size() < m_count ?
- std::numeric_limits<distance_type>::max() :
- m_neighbors.back().first;
+ return m_neighbors.size() < 0
+ ? std::numeric_limits<distance_type>::max()
+ : m_neighbors.front().first;
}
template <typename OutIter>
@@ -123,6 +131,7 @@
size_t m_count;
std::vector< std::pair<distance_type, Value> > m_neighbors;
+ distance_type m_biggest_comp_dist;
};
// TODO: awulkiew - add additional pruning before adding nodes to the ABL
Modified: sandbox-branches/geometry/index/tests/rtree_function.hpp
==============================================================================
--- sandbox-branches/geometry/index/tests/rtree_function.hpp (original)
+++ sandbox-branches/geometry/index/tests/rtree_function.hpp 2011-09-29 07:48:13 EDT (Thu, 29 Sep 2011)
@@ -148,6 +148,43 @@
return true;
}
+ template <typename Point, typename Cont, typename Translator>
+ bool nearest_results_compare(Point const& p, Cont const& c1, Cont const& c2, Translator const& tr)
+ {
+ namespace bg = boost::geometry;
+ namespace bgi = boost::geometry::index;
+
+ typedef typename Translator::indexable_type indexable_type;
+ typedef bg::default_distance_result<Point, indexable_type>::type distance_type;
+
+ if ( c1.size() != c2.size() )
+ return false;
+
+ if ( c1.size() == 0 && c2.size() == 0 )
+ return true;
+
+ distance_type biggest_distance1 = 0;
+
+ for ( typename Cont::const_iterator it = c1.begin() ; it != c1.end() ; ++it )
+ {
+ distance_type curr_distance = bgi::comparable_distance_near(p, tr(*it));
+
+ if ( biggest_distance1 < curr_distance )
+ biggest_distance1 = curr_distance;
+ }
+
+ distance_type biggest_distance2 = 0;
+ for ( typename Cont::const_iterator it = c2.begin() ; it != c2.end() ; ++it )
+ {
+ distance_type curr_distance = bgi::comparable_distance_near(p, tr(*it));
+
+ if ( biggest_distance2 < curr_distance )
+ biggest_distance2 = curr_distance;
+ }
+
+ return biggest_distance1 == biggest_distance2;
+ }
+
template <typename Predicate, typename Rtree, typename Cont, typename Randomizer>
void random_query_check(Rtree const& t, Cont const& c, size_t n, Randomizer r)
{
@@ -233,7 +270,7 @@
std::stringstream ss;
ss << "\nPredicate: " << typeid(Predicate).name() << "\nres1: " << res1.size() << ", res2: " << res2.size() << '\n';
- BOOST_CHECK_MESSAGE( helpers::results_compare(res1, res2, t.get_translator()), ss.str());
+ BOOST_CHECK_MESSAGE(helpers::nearest_results_compare(pt, res1, res2, t.get_translator()), ss.str());
}
}
}