[Boost-commit] svn:boost r84783 - in trunk/boost/geometry/index/detail/rtree: linear rstar

Subject: [Boost-commit] svn:boost r84783 - in trunk/boost/geometry/index/detail/rtree: linear rstar
From: adam.wulkiewicz_at_[hidden]
Date: 2013-06-14 19:03:38

Author: awulkiew
Date: 2013-06-14 19:03:37 EDT (Fri, 14 Jun 2013)
New Revision: 84783
URL: http://svn.boost.org/trac/boost/changeset/84783

Log:
[geometry][index]: R*tree choose_next_node significantly optimized.

Text files modified: 
   trunk/boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp |    13 -                                       
   trunk/boost/geometry/index/detail/rtree/rstar/choose_next_node.hpp       |   261 +++++++++++++++++++++++++++++++++------ 
   2 files changed, 222 insertions(+), 52 deletions(-)

Modified: trunk/boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp	Fri Jun 14 16:08:40 2013	(r84782)
+++ trunk/boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp	2013-06-14 19:03:37 EDT (Fri, 14 Jun 2013)	(r84783)
@@ -32,10 +32,8 @@
 
 // TODO: Implement separate version for Points
 
-// [DONE] What if width calculated inside find_greatest_normalized_separation::apply() is near 0?
-// [DONE] What epsilon should be taken to calculation and what would be the value of resulting separation?
-
-// from void find_normalized_separations(std::vector<Box> const& boxes, T& separation, unsigned int& first, unsigned int& second) const
+// The following struct/method was adapted for the preliminary version of the R-tree. Then it was called:
+// void find_normalized_separations(std::vector<Box> const& boxes, T& separation, unsigned int& first, unsigned int& second) const
 
 template <typename Elements, typename Parameters, typename Translator, size_t DimensionIndex>
 struct find_greatest_normalized_separation
@@ -104,12 +102,7 @@
         }
 
         coordinate_type const width = highest_high - lowest_low;
-
-        // TODO: awulkiew - following separation calculation has two flaws:
-        // 1. [DONE] for floating point numbers width should be compared witn some EPS
-        // 2. [DONE] separation calculation won't work for unsigned numbers
-        //    but there should be possible to calculate negative value (cast to some floating point type?)
-
+        
         separation = difference(highest_low, lowest_high, is_coordinate_type_unsigned());
         // BOOST_ASSERT(0 <= width);
         if ( std::numeric_limits<coordinate_type>::epsilon() < width )

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 16:08:40 2013	(r84782)
+++ trunk/boost/geometry/index/detail/rtree/rstar/choose_next_node.hpp	2013-06-14 19:03:37 EDT (Fri, 14 Jun 2013)	(r84783)
@@ -52,11 +52,13 @@
         // children are leafs
         if ( node_relative_level <= 1 )
         {
-            if ( 0 < parameters.get_overlap_cost_threshold() &&
+            /*if ( 0 < parameters.get_overlap_cost_threshold() &&
                  parameters.get_overlap_cost_threshold() < children.size() )
                 return choose_by_nearly_minimum_overlap_cost(children, indexable, parameters.get_overlap_cost_threshold());
             else
-                return choose_by_minimum_overlap_cost(children, indexable);
+                return choose_by_minimum_overlap_cost(children, indexable);*/
+
+            return choose_by_minimum_overlap_cost(children, indexable, parameters.get_overlap_cost_threshold());
         }
         // children are internal nodes
         else
@@ -68,9 +70,73 @@
 private:
     template <typename Indexable>
     static inline size_t choose_by_minimum_overlap_cost(children_type const& children,
-                                                        Indexable const& indexable)
+                                                        Indexable const& indexable,
+                                                        size_t overlap_cost_threshold)
     {
-        size_t children_count = children.size();
+        const size_t children_count = children.size();
+
+        content_type min_content_diff = (std::numeric_limits<content_type>::max)();
+        content_type min_content = (std::numeric_limits<content_type>::max)();
+        size_t choosen_index = 0;
+
+        // create container of children sorted by content enlargement needed to include the new value
+        typedef boost::tuple<size_t, content_type, content_type> child_contents;
+        typename rtree::container_from_elements_type<children_type, child_contents>::type
+            children_contents(children_count);
+
+        for ( size_t i = 0 ; i < children_count ; ++i )
+        {
+            child_type const& ch_i = children[i];
+
+            // expanded child node's box
+            Box box_exp(ch_i.first);
+            geometry::expand(box_exp, indexable);
+
+            // areas difference
+            content_type content = index::detail::content(box_exp);
+            content_type content_diff = content - index::detail::content(ch_i.first);
+
+            children_contents[i] = boost::make_tuple(i, content_diff, content);
+
+            if ( content_diff < min_content_diff ||
+                 (content_diff == min_content_diff && content < min_content) )
+            {
+                min_content_diff = content_diff;
+                min_content = content;
+                choosen_index = i;
+            }
+        }
+
+        // is this assumption ok? if min_content_diff == 0 there is no overlap increase?
+
+        if ( min_content_diff < -std::numeric_limits<double>::epsilon() || std::numeric_limits<double>::epsilon() < min_content_diff )
+        {
+            if ( 0 < overlap_cost_threshold && overlap_cost_threshold < children.size() )
+            {
+                // calculate nearly minimum overlap cost
+
+                // sort by content_diff
+                std::partial_sort(children_contents.begin(), children_contents.begin() + overlap_cost_threshold, children_contents.end(), content_diff_less);
+                choosen_index = choose_by_minimum_overlap_cost_sorted_by_content(children, indexable, children_count, overlap_cost_threshold, children_contents);
+            }
+            else
+            {
+                // calculate minimum overlap cost
+
+                choosen_index = choose_by_minimum_overlap_cost_unsorted_by_content(children, indexable, children_count, children_contents);
+            }
+        }
+
+        return choosen_index;
+    }
+
+    template <typename Indexable, typename ChildrenContents>
+    static inline size_t choose_by_minimum_overlap_cost_unsorted_by_content(children_type const& children,
+                                                                            Indexable const& indexable,
+                                                                            size_t children_count,
+                                                                            ChildrenContents const& children_contents)
+    {
+        BOOST_GEOMETRY_INDEX_ASSERT(children_contents.size() == children_count, "unexpected number of elements");
 
         // choose index with smallest overlap change value, or content change or smallest content
         size_t choosen_index = 0;
@@ -87,12 +153,8 @@
             // calculate expanded box of child node ch_i
             geometry::expand(box_exp, indexable);
 
-            // calculate content and content diff
-            content_type content = index::detail::content(box_exp);
-            content_type content_diff = content - index::detail::content(ch_i.first);
-
             content_type overlap_diff = 0;
-            
+
             // calculate overlap
             for ( size_t j = 0 ; j < children_count ; ++j )
             {
@@ -108,11 +170,14 @@
                 }
             }
 
+            content_type content = boost::get<2>(children_contents[i]);
+            content_type content_diff = boost::get<1>(children_contents[i]);
+
             // update result
             if ( overlap_diff < smallest_overlap_diff ||
-                 ( overlap_diff == smallest_overlap_diff && ( content_diff < smallest_content_diff ||
-                   ( content_diff == smallest_content_diff && content < smallest_content ) )
-                 ) )
+                ( overlap_diff == smallest_overlap_diff && ( content_diff < smallest_content_diff ||
+                ( content_diff == smallest_content_diff && content < smallest_content ) )
+                ) )
             {
                 smallest_overlap_diff = overlap_diff;
                 smallest_content_diff = content_diff;
@@ -123,36 +188,16 @@
 
         return choosen_index;
     }
-
-    template <typename Indexable>
-    static inline size_t choose_by_nearly_minimum_overlap_cost(children_type const& children,
-                                                               Indexable const& indexable,
-                                                               size_t overlap_cost_threshold)
+    
+    template <typename Indexable, typename ChildrenContents>
+    static inline size_t choose_by_minimum_overlap_cost_sorted_by_content(children_type const& children,
+                                                                          Indexable const& indexable,
+                                                                          size_t children_count,
+                                                                          size_t overlap_cost_threshold,
+                                                                          ChildrenContents const& children_contents)
     {
-        const size_t children_count = children.size();
-
-        // create container of children sorted by content enlargement needed to include the new value
-        std::vector< boost::tuple<size_t, content_type, content_type> > sorted_children(children_count);
-        for ( size_t i = 0 ; i < children_count ; ++i )
-        {
-            child_type const& ch_i = children[i];
-
-            // expanded child node's box
-            Box box_exp(ch_i.first);
-            geometry::expand(box_exp, indexable);
-
-            // areas difference
-            content_type content = index::detail::content(box_exp);
-            content_type content_diff = content - index::detail::content(ch_i.first);
-
-            sorted_children[i] = boost::make_tuple(i, content_diff, content);
-        }
-
-        BOOST_GEOMETRY_INDEX_ASSERT(overlap_cost_threshold <= children_count, "there is not enough children");
-
-        // sort by content_diff
-        //std::sort(sorted_children.begin(), sorted_children.end(), content_diff_less);
-        std::partial_sort(sorted_children.begin(), sorted_children.begin() + overlap_cost_threshold, sorted_children.end(), content_diff_less);
+        BOOST_GEOMETRY_INDEX_ASSERT(overlap_cost_threshold < children_count, "unexpected value");
+        BOOST_GEOMETRY_INDEX_ASSERT(children_count == children_contents.size(), "unexpected number of elements");
 
         // for overlap_cost_threshold child nodes find the one with smallest overlap value
         size_t choosen_index = 0;
@@ -161,7 +206,7 @@
         // for each node
         for (size_t i = 0 ; i < overlap_cost_threshold ; ++i )
         {
-            size_t child_index = boost::get<0>(sorted_children[i]);
+            size_t child_index = boost::get<0>(children_contents[i]);
 
             typedef typename children_type::value_type child_type;
             child_type const& ch_i = children[child_index];
@@ -198,6 +243,138 @@
         return choosen_index;
     }
 
+    //template <typename Indexable>
+    //static inline size_t choose_by_minimum_overlap_cost(children_type const& children,
+    //                                                    Indexable const& indexable)
+    //{
+    //    size_t children_count = children.size();
+
+    //    // choose index with smallest overlap change value, or content change or smallest content
+    //    size_t choosen_index = 0;
+    //    content_type smallest_overlap_diff = (std::numeric_limits<content_type>::max)();
+    //    content_type smallest_content_diff = (std::numeric_limits<content_type>::max)();
+    //    content_type smallest_content = (std::numeric_limits<content_type>::max)();
+
+    //    // for each child node
+    //    for (size_t i = 0 ; i < children_count ; ++i )
+    //    {
+    //        child_type const& ch_i = children[i];
+
+    //        Box box_exp(ch_i.first);
+    //        // calculate expanded box of child node ch_i
+    //        geometry::expand(box_exp, indexable);
+
+    //        // calculate content and content diff
+    //        content_type content = index::detail::content(box_exp);
+    //        content_type content_diff = content - index::detail::content(ch_i.first);
+
+    //        content_type overlap_diff = 0;
+    //        
+    //        // calculate overlap
+    //        for ( size_t j = 0 ; j < children_count ; ++j )
+    //        {
+    //            if ( i != j )
+    //            {
+    //                child_type const& ch_j = children[j];
+
+    //                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);
+    //                }
+    //            }
+    //        }
+
+    //        // update result
+    //        if ( overlap_diff < smallest_overlap_diff ||
+    //             ( overlap_diff == smallest_overlap_diff && ( content_diff < smallest_content_diff ||
+    //               ( content_diff == smallest_content_diff && content < smallest_content ) )
+    //             ) )
+    //        {
+    //            smallest_overlap_diff = overlap_diff;
+    //            smallest_content_diff = content_diff;
+    //            smallest_content = content;
+    //            choosen_index = i;
+    //        }
+    //    }
+
+    //    return choosen_index;
+    //}
+
+    //template <typename Indexable>
+    //static inline size_t choose_by_nearly_minimum_overlap_cost(children_type const& children,
+    //                                                           Indexable const& indexable,
+    //                                                           size_t overlap_cost_threshold)
+    //{
+    //    const size_t children_count = children.size();
+
+    //    // create container of children sorted by content enlargement needed to include the new value
+    //    std::vector< boost::tuple<size_t, content_type, content_type> > sorted_children(children_count);
+    //    for ( size_t i = 0 ; i < children_count ; ++i )
+    //    {
+    //        child_type const& ch_i = children[i];
+
+    //        // expanded child node's box
+    //        Box box_exp(ch_i.first);
+    //        geometry::expand(box_exp, indexable);
+
+    //        // areas difference
+    //        content_type content = index::detail::content(box_exp);
+    //        content_type content_diff = content - index::detail::content(ch_i.first);
+
+    //        sorted_children[i] = boost::make_tuple(i, content_diff, content);
+    //    }
+
+    //    BOOST_GEOMETRY_INDEX_ASSERT(overlap_cost_threshold <= children_count, "there is not enough children");
+
+    //    // sort by content_diff
+    //    //std::sort(sorted_children.begin(), sorted_children.end(), content_diff_less);
+    //    std::partial_sort(sorted_children.begin(), sorted_children.begin() + overlap_cost_threshold, sorted_children.end(), content_diff_less);
+
+    //    // for overlap_cost_threshold child nodes find the one with smallest overlap value
+    //    size_t choosen_index = 0;
+    //    content_type smallest_overlap_diff = (std::numeric_limits<content_type>::max)();
+
+    //    // for each node
+    //    for (size_t i = 0 ; i < overlap_cost_threshold ; ++i )
+    //    {
+    //        size_t child_index = boost::get<0>(sorted_children[i]);
+
+    //        typedef typename children_type::value_type child_type;
+    //        child_type const& ch_i = children[child_index];
+
+    //        Box box_exp(ch_i.first);
+    //        // calculate expanded box of child node ch_i
+    //        geometry::expand(box_exp, indexable);
+
+    //        content_type overlap_diff = 0;
+
+    //        // calculate overlap
+    //        for ( size_t j = 0 ; j < children_count ; ++j )
+    //        {
+    //            if ( child_index != j )
+    //            {
+    //                child_type const& ch_j = children[j];
+
+    //                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);
+    //                }
+    //            }
+    //        }
+
+    //        // update result
+    //        if ( overlap_diff < smallest_overlap_diff )
+    //        {
+    //            smallest_overlap_diff = overlap_diff;
+    //            choosen_index = child_index;
+    //        }
+    //    }
+
+    //    return choosen_index;
+    //}
+
     static inline bool content_diff_less(boost::tuple<size_t, content_type, content_type> const& p1, boost::tuple<size_t, content_type, content_type> const& p2)
     {
         return boost::get<1>(p1) < boost::get<1>(p2) ||