Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r84778 - trunk/boost/geometry/index/detail/rtree/rstar
From: adam.wulkiewicz_at_[hidden]
Date: 2013-06-14 09:05:30


Author: awulkiew
Date: 2013-06-14 09:05:30 EDT (Fri, 14 Jun 2013)
New Revision: 84778
URL: http://svn.boost.org/trac/boost/changeset/84778

Log:
[geometry][index]: added small optimization of overlap difference calculation in r* choose_next_node.

Text files modified:
   trunk/boost/geometry/index/detail/rtree/rstar/choose_next_node.hpp | 26 +++++++++++++-------------
   1 files changed, 13 insertions(+), 13 deletions(-)

Modified: trunk/boost/geometry/index/detail/rtree/rstar/choose_next_node.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/rtree/rstar/choose_next_node.hpp Fri Jun 14 08:42:36 2013 (r84777)
+++ trunk/boost/geometry/index/detail/rtree/rstar/choose_next_node.hpp 2013-06-14 09:05:30 EDT (Fri, 14 Jun 2013) (r84778)
@@ -91,9 +91,8 @@
             content_type content = index::detail::content(box_exp);
             content_type content_diff = content - index::detail::content(ch_i.first);
 
- content_type overlap = 0;
- content_type overlap_exp = 0;
-
+ content_type overlap_diff = 0;
+
             // calculate overlap
             for ( size_t j = 0 ; j < children_count ; ++j )
             {
@@ -101,13 +100,14 @@
                 {
                     child_type const& ch_j = children[j];
 
- overlap += index::detail::intersection_content(ch_i.first, ch_j.first);
- overlap_exp += index::detail::intersection_content(box_exp, ch_j.first);
+ content_type overlap_exp = index::detail::intersection_content(box_exp, ch_j.first);
+ if ( overlap_exp < -std::numeric_limits<content_type>::epsilon() || std::numeric_limits<content_type>::epsilon() < overlap_exp )
+ {
+ overlap_diff += overlap_exp - index::detail::intersection_content(ch_i.first, ch_j.first);
+ }
                 }
             }
 
- content_type overlap_diff = overlap_exp - overlap;
-
             // update result
             if ( overlap_diff < smallest_overlap_diff ||
                  ( overlap_diff == smallest_overlap_diff && ( content_diff < smallest_content_diff ||
@@ -170,8 +170,7 @@
             // calculate expanded box of child node ch_i
             geometry::expand(box_exp, indexable);
 
- content_type overlap = 0;
- content_type overlap_exp = 0;
+ content_type overlap_diff = 0;
 
             // calculate overlap
             for ( size_t j = 0 ; j < children_count ; ++j )
@@ -180,13 +179,14 @@
                 {
                     child_type const& ch_j = children[j];
 
- overlap += index::detail::intersection_content(ch_i.first, ch_j.first);
- overlap_exp += index::detail::intersection_content(box_exp, ch_j.first);
+ content_type overlap_exp = index::detail::intersection_content(box_exp, ch_j.first);
+ if ( overlap_exp < -std::numeric_limits<content_type>::epsilon() || std::numeric_limits<content_type>::epsilon() < overlap_exp )
+ {
+ overlap_diff += overlap_exp - index::detail::intersection_content(ch_i.first, ch_j.first);
+ }
                 }
             }
 
- content_type overlap_diff = overlap_exp - overlap;
-
             // update result
             if ( overlap_diff < smallest_overlap_diff )
             {


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