[Boost-commit] svn:boost r74610 - in sandbox-branches/geometry/index: boost/geometry/extensions/index/rtree/visitors tests

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();