[Boost-commit] svn:boost r70746 - in sandbox-branches/geometry/index_080_new: boost/geometry/extensions/index/rtree/rstar tests

Subject: [Boost-commit] svn:boost r70746 - in sandbox-branches/geometry/index_080_new: boost/geometry/extensions/index/rtree/rstar tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-03-30 06:16:04

Author: awulkiew
Date: 2011-03-30 06:16:03 EDT (Wed, 30 Mar 2011)
New Revision: 70746
URL: http://svn.boost.org/trac/boost/changeset/70746

Log:
choose_next_node algorithm changed
Text files modified: 
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp |   228 +++++++++++++++++++++++++++++---------- 
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert.hpp           |    26 ++-                                     
   sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp                                    |     3                                         
   3 files changed, 186 insertions(+), 71 deletions(-)

Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp	(original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp	2011-03-30 06:16:03 EDT (Wed, 30 Mar 2011)
@@ -12,6 +12,8 @@
 
 #include <algorithm>
 
+#include <boost/geometry/algorithms/expand.hpp>
+
 #include <boost/geometry/extensions/index/algorithms/area.hpp>
 #include <boost/geometry/extensions/index/algorithms/overlap.hpp>
 #include <boost/geometry/extensions/index/algorithms/union_area.hpp>
@@ -32,6 +34,9 @@
 
     typedef typename internal_node::children_type children_type;
 
+    typedef typename index::area_result<Box>::type area_type;
+    typedef typename index::overlap_result<Box>::type overlap_type;
+
 public:
     template <typename Indexable>
     static inline size_t apply(internal_node & n, Indexable const& indexable)
@@ -42,89 +47,192 @@
             visitors::is_leaf<Value, Box, rstar_tag>(),
             *n.children.front().second);
 
-        if ( !has_leaves )
-            return impl<internal_node_areas>(n, indexable);
+        if ( has_leaves )
+            return branch_impl(n, indexable);
+            //return impl<branch_areas>(n, indexable);
         else
-            return impl<branch_areas>(n, indexable);
+            return internal_node_impl(n, indexable);
+            //return impl<internal_node_areas>(n, indexable);
     }
 
 private:
-    template <typename Areas, typename Indexable>
-    static inline size_t impl(internal_node & n, Indexable const& indexable)
+    template <typename Indexable>
+    static inline size_t branch_impl(internal_node & n, Indexable const& indexable)
     {
-        typedef typename children_type::iterator children_iterator;
-
-        //assert(!n.children.empty());
+        size_t children_count = n.children.size();
+        // overlaps values of all nodes' boxes,
+        // overlaps and areas of extended boxes are stored at indexes i + children_count
+        std::vector<overlap_type> overlaps(children_count * 2, overlap_type(0));
+        std::vector<overlap_type> areas(children_count * 2);
+        // caculate overlaps and areas of all nodes' boxes
+        for (size_t i = 0 ; i < children_count ; ++i )
+        {
+            typedef typename children_type::value_type child_type;
+            child_type const& ch_i = n.children[i];
 
-        children_iterator temp_it = n.children.begin();
-        children_iterator child_it = temp_it;
-        Areas min_areas(n.children, child_it, indexable);
+            Box ch_ext;
+            // calculate expanded box fo node ch_i
+            geometry::convert(ch_i.first, ch_ext);
+            geometry::expand(ch_ext, indexable);
 
-        for (children_iterator it = ++temp_it;
-            it != n.children.end(); ++it)
-        {
-            Areas areas(n.children, it, indexable);
+            areas[i] = index::area(ch_i.first);
+            areas[i + children_count] = index::area(ch_ext);
 
-            if ( areas < min_areas )
+            for (size_t j = i + 1 ; j < children_count ; ++j )
             {
-                child_it = it;
-                min_areas = areas;
+                child_type const& ch_j = n.children[j];
+                
+                // add overlap of both boxes
+                overlap_type ovl = index::overlap(ch_i.first, ch_j.first);
+                overlaps[i] += ovl;
+                overlaps[j] += ovl;
+
+                // add overlap of expanded box i and box j
+                overlaps[i + children_count] = index::overlap(ch_ext, ch_j.first);
+                
+                // add overlap of expanded box j and box i
+                geometry::convert(ch_j.first, ch_ext);
+                geometry::expand(ch_ext, indexable);
+                overlaps[j + children_count] = index::overlap(ch_ext, ch_i.first);
             }
         }
 
-        // TODO: awulkiew - switch to indexes in the whole class?
-        return child_it - n.children.begin();
-    }
+        // choose index with smallest overlap change value, or area change or smallest area
+        size_t choosen_index = 0;
+        overlap_type smallest_overlap_change = std::numeric_limits<overlap_type>::max();
+        area_type smallest_area_change = std::numeric_limits<area_type>::max();
+        area_type smallest_area = std::numeric_limits<area_type>::max();
 
-    struct branch_areas
-    {
-        typedef typename index::area_result<Box>::type area_type;
-
-        template <typename Indexable>
-        inline branch_areas(children_type const& ch, typename children_type::iterator const& k_it, Indexable const& indexable)
+        for ( size_t i = 0 ; i < children_count ; ++i )
         {
-            overlap_area = 0;
-            for (typename children_type::const_iterator it = ch.begin(); it != ch.end(); ++it)
-                if ( it != k_it )
-                    overlap_area += index::overlap(k_it->first, it->first);
-
-            area = index::area(k_it->first);
-
-            diff_area = index::union_area(k_it->first, indexable) - area;
-        }
-
-        inline bool operator<(branch_areas &a) const
-        {
-            return overlap_area < a.overlap_area ||
-                ( overlap_area == a.overlap_area && diff_area < a.diff_area ) ||
-                ( diff_area == a.diff_area && area < a.area );
+            overlap_type overlap_change = overlaps[i + children_count] - overlaps[i];
+            area_type area_change = areas[i + children_count] - areas[i];
+            area_type area = areas[i + children_count];
+
+            if ( overlap_change < smallest_overlap_change ||
+                 ( overlap_change == smallest_overlap_change && area_change < smallest_area_change ) ||
+                 ( area_change == smallest_area_change && smallest_area < area ) )
+            {
+                smallest_overlap_change = overlap_change;
+                smallest_area_change = area_change;
+                smallest_area = area;
+                choosen_index = i;
+            }
         }
 
-        area_type overlap_area;
-        area_type diff_area;
-        area_type area;
-    };
+        return choosen_index;
+    }
 
-    struct internal_node_areas
+    template <typename Indexable>
+    static inline size_t internal_node_impl(internal_node & n, Indexable const& indexable)
     {
-        typedef typename area_result<Box>::type area_type;
+        size_t children_count = n.children.size();
 
-        template <typename Indexable>
-        inline internal_node_areas(children_type const&, typename children_type::iterator const& k_it, Indexable const& indexable)
-        {
-            area = index::area(k_it->first);
-            diff_area = index::union_area(k_it->first, indexable) - area;
-        }
+        // choose index with smallest overlap change value, or area change or smallest area
+        size_t choosen_index = 0;
+        area_type smallest_area_change = std::numeric_limits<area_type>::max();
+        area_type smallest_area = std::numeric_limits<area_type>::max();
 
-        inline bool operator<(internal_node_areas &a) const
+        // caculate areas and areas of all nodes' boxes
+        for ( size_t i = 0 ; i < children_count ; ++i )
         {
-            return diff_area < a.diff_area ||
-                ( diff_area == a.diff_area && area < a.area );
+            typedef typename children_type::value_type child_type;
+            child_type const& ch_i = n.children[i];
+
+            Box ch_exp;
+            geometry::convert(ch_i.first, ch_exp);
+            geometry::expand(ch_exp, indexable);
+
+            area_type area = index::area(ch_exp);
+            area_type area_change = area - index::area(ch_i.first);
+            
+            if ( area_change < smallest_area_change ||
+                ( area_change == smallest_area_change && smallest_area < area ) )
+            {
+                smallest_area_change = area_change;
+                smallest_area = area;
+                choosen_index = i;
+            }
         }
 
-        area_type diff_area;
-        area_type area;
-    };
+        return choosen_index;
+    }
+
+    //template <typename Areas, typename Indexable>
+    //static inline size_t impl(internal_node & n, Indexable const& indexable)
+    //{
+    //    typedef typename children_type::iterator children_iterator;
+
+    //    //assert(!n.children.empty());
+
+    //    children_iterator temp_it = n.children.begin();
+    //    children_iterator child_it = temp_it;
+    //    Areas min_areas(n.children, child_it, indexable);
+
+    //    for (children_iterator it = ++temp_it;
+    //        it != n.children.end(); ++it)
+    //    {
+    //        Areas areas(n.children, it, indexable);
+
+    //        if ( areas < min_areas )
+    //        {
+    //            child_it = it;
+    //            min_areas = areas;
+    //        }
+    //    }
+
+    //    return child_it - n.children.begin();
+    //}
+
+    //struct branch_areas
+    //{
+    //    typedef typename index::area_result<Box>::type area_type;
+
+    //    template <typename Indexable>
+    //    inline branch_areas(children_type const& ch, typename children_type::iterator const& k_it, Indexable const& indexable)
+    //    {
+    //        overlap_area = 0;
+    //        for (typename children_type::const_iterator it = ch.begin(); it != ch.end(); ++it)
+    //            if ( it != k_it )
+    //                overlap_area += index::overlap(k_it->first, it->first);
+
+    //        area = index::area(k_it->first);
+
+    //        diff_area = index::union_area(k_it->first, indexable) - area;
+    //    }
+
+    //    inline bool operator<(branch_areas &a) const
+    //    {
+    //        return overlap_area < a.overlap_area ||
+    //            ( overlap_area == a.overlap_area && diff_area < a.diff_area ) ||
+    //            ( diff_area == a.diff_area && area < a.area );
+    //    }
+
+    //    area_type overlap_area;
+    //    area_type diff_area;
+    //    area_type area;
+    //};
+
+    //struct internal_node_areas
+    //{
+    //    typedef typename area_result<Box>::type area_type;
+
+    //    template <typename Indexable>
+    //    inline internal_node_areas(children_type const&, typename children_type::iterator const& k_it, Indexable const& indexable)
+    //    {
+    //        area = index::area(k_it->first);
+    //        diff_area = index::union_area(k_it->first, indexable) - area;
+    //    }
+
+    //    inline bool operator<(internal_node_areas &a) const
+    //    {
+    //        return diff_area < a.diff_area ||
+    //            ( diff_area == a.diff_area && area < a.area );
+    //    }
+
+    //    area_type diff_area;
+    //    area_type area;
+    //};
 };
 
 }}} // namespace detail::rtree:rstar

Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert.hpp	(original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert.hpp	2011-03-30 06:16:03 EDT (Wed, 30 Mar 2011)
@@ -41,7 +41,7 @@
     inline explicit insert(node* & root, Value const& v, size_t min_elements, size_t max_elements, Translator const& t)
         : m_value(v), m_tr(t), m_min_elems_per_node(min_elements), m_max_elems_per_node(max_elements)
         , m_root_node(root)
-        , m_parent(0), m_current_child_index(0)
+        , m_parent(0), m_current_child_index(0), m_current_level(0)
     {}
 
     inline void operator()(internal_node & n)
@@ -50,13 +50,14 @@
         internal_node * parent_bckup = m_parent;
         m_parent = &n;
         size_t current_child_index_bckup = m_current_child_index;
+        size_t current_level_bckup = m_current_level;
 
         // choose next node, where value insert traversing should go
         m_current_child_index =
             rstar::choose_next_node<Value, Box>::
             apply(n, m_tr(m_value));
 
-        // TODO: awulkiew - if reinsert is implemented this must be changed
+        // expand the node to contain value
         geometry::expand(n.children[m_current_child_index].first, m_tr(m_value));
 
         // next traversing step
@@ -65,12 +66,10 @@
         // restore previous traverse inputs
         m_parent = parent_bckup;
         m_current_child_index = current_child_index_bckup;
+        m_current_level = current_level_bckup;
 
         if ( m_max_elems_per_node < n.children.size() )
-        {
-            rstar::split<Value, Translator, Box>::
-                apply(n, m_parent, m_current_child_index, m_root_node, m_min_elems_per_node, m_max_elems_per_node, m_tr);
-        }
+            overflow_treatment(n);
     }
 
     inline void operator()(leaf & n)
@@ -78,13 +77,19 @@
         n.values.push_back(m_value);
 
         if ( m_max_elems_per_node < n.values.size() )
-        {
-            rstar::split<Value, Translator, Box>::
-                apply(n, m_parent, m_current_child_index, m_root_node, m_min_elems_per_node, m_max_elems_per_node, m_tr);
-        }
+            overflow_treatment(n);
     }
 
 private:
+    template <typename Node>
+    inline void overflow_treatment(Node & n)
+    {
+        // TODO: awulkiew - reinsert
+
+        rstar::split<Value, Translator, Box>::
+            apply(n, m_parent, m_current_child_index, m_root_node, m_min_elems_per_node, m_max_elems_per_node, m_tr);
+    }
+
     Value const& m_value;
     Translator const& m_tr;
     size_t m_min_elems_per_node;
@@ -95,6 +100,7 @@
     // traversing input parameters
     internal_node *m_parent;
     size_t m_current_child_index;
+    size_t m_current_level;
 };
 
 }}} // namespace detail::rtree::visitors

Modified: sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp	(original)
+++ sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp	2011-03-30 06:16:03 EDT (Wed, 30 Mar 2011)
@@ -9,7 +9,8 @@
 
 typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
 typedef boost::geometry::model::box<P> B;
-boost::geometry::index::rtree<B> t(2, 1);
+//boost::geometry::index::rtree<B> t(2, 1);
+boost::geometry::index::rtree<B> t(4, 2);
 
 void render_scene(void)
 {