Subject: [Boost-commit] svn:boost r74610 - in sandbox-branches/geometry/index: boost/geometry/extensions/index/rtree/visitors tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-09-29 09:38:03
Author: awulkiew
Date: 2011-09-29 09:38:03 EDT (Thu, 29 Sep 2011)
New Revision: 74610
URL: http://svn.boost.org/trac/boost/changeset/74610
Log:
nearest query optimized by rejecting distant nodes before adding them to the active branches list.
Text files modified:
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp | 21 ++++++++++++++++++---
sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp | 24 +++++++++++++++++++++++-
2 files changed, 41 insertions(+), 4 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 09:38:03 EDT (Thu, 29 Sep 2011)
@@ -167,7 +167,7 @@
, m_result(r)
{}
- //TODO: awulkiew - check this approach: store one, global vector of active branches, add branches only if mindist is ok
+ //TODO: awulkiew - consider this approach: store one, global vector of active branches, add branches only if mindist is ok
inline void operator()(internal_node const& n)
{
@@ -191,6 +191,17 @@
// calculate node's distance(s) for distance predicate
node_distances_type node_dist_data = node_distances_calc::apply(m_dist_pred, it->first);
+ // TODO: awulkiew - consider at first calculating just near distance,
+ // comparing it with m_result.comparable_distance if it's valid,
+ // after that calculate the rest of distances and check predicates
+
+ // if current node is further than found neighbors - don't analyze it
+ if ( m_result.is_comparable_distance_valid() &&
+ is_node_prunable(m_result.comparable_distance(), node_dist_data) )
+ {
+ continue;
+ }
+
// if current node distance(s) meets distance predicate
if ( node_distances_predicates_check::apply(m_dist_pred, node_dist_data) )
{
@@ -235,6 +246,10 @@
// calculate values distance for distance predicate
value_distances_type distances = value_distances_calc::apply(m_dist_pred, m_tr(*it));
+ // TODO: awulkiew - consider at first calculating just point relation distance,
+ // comparing it with m_result.comparable_distance if it's valid,
+ // after that calculate the rest of distances and check predicates
+
// if distance meets distance predicate
if ( value_distances_predicates_check::apply(m_dist_pred, distances) )
{
@@ -261,7 +276,7 @@
{
// prune if box's mindist is further than value's mindist
while ( !abl.empty() &&
- prune_node(m_result.comparable_distance(), abl.back().first) )
+ is_node_prunable(m_result.comparable_distance(), abl.back().first) )
{
abl.pop_back();
}
@@ -279,7 +294,7 @@
}
template <typename Distance>
- static inline bool prune_node(Distance const& smallest_dist, node_distances_type const& d)
+ static inline bool is_node_prunable(Distance const& smallest_dist, node_distances_type const& d)
{
return smallest_dist
< index::detail::cdist_value<node_distances_type>
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-29 09:38:03 EDT (Thu, 29 Sep 2011)
@@ -221,7 +221,7 @@
// searching test
{
- std::cout << "query(B) and value(odd index) searching time test... ("
+ std::cout << "pair: query(B) and value(odd index) searching time test... ("
<< queries_count << ")\n";
tim.restart();
size_t temp = 0;
@@ -243,6 +243,28 @@
// searching test
{
+ std::cout << "tuple: query(B) and value(odd index) searching time test... ("
+ << queries_count << ")\n";
+ tim.restart();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ std::deque< std::pair<B, size_t> > result;
+ t.query(
+ boost::make_tuple(
+ B(P(x - 10, y - 10), P(x + 10, y + 10)),
+ bgi::value(test_pred< std::pair<B, size_t> >())
+ ), std::back_inserter(result));
+ temp += result.size();
+ }
+ std::cout << "time: " << tim.elapsed() << "s\n";
+ std::cout << "found: " << temp << "\n";
+ }
+
+ // searching test
+ {
std::cout << "vector searching time test... ("
<< queries_count / 1000 << ")\n";
tim.restart();