[Boost-commit] svn:boost r46308 - sandbox/SOC/2008/spacial_indexing/boost/spatial_index

From: mariano.consoni_at_[hidden]
Date: 2008-06-10 17:19:54

Author: mconsoni
Date: 2008-06-10 17:19:53 EDT (Tue, 10 Jun 2008)
New Revision: 46308
URL: http://svn.boost.org/trac/boost/changeset/46308

Log:

- more on the rtree.

Text files modified: 
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp |   127 ++++++++++++++++++++++++++++++++++----- 
   1 files changed, 109 insertions(+), 18 deletions(-)

Modified: sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp	(original)
+++ sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp	2008-06-10 17:19:53 EDT (Tue, 10 Jun 2008)
@@ -7,6 +7,8 @@
 #ifndef BOOST_SPATIAL_INDEX_RTREE_HPP
 #define BOOST_SPATIAL_INDEX_RTREE_HPP
 
+#include <geometry/area.hpp>
+
 // #include "quadtree_node.hpp"
 
 // #include <boost/thread/xtime.hpp>
@@ -25,9 +27,17 @@
     rtree_node(const unsigned int &level, const unsigned int &m, const unsigned int &M) 
       : level_(level), m_(m), M_(M) {}
 
+    virtual bool is_full(void) const { return nodes_.size() == M_; }
+
     /// true if it is a leaf node
     virtual bool is_leaf(void) { return false; }
 
+    virtual void insert(const geometry::box<Point> &e, const Value &v) 
+    {
+      std::cerr << "Insert in node!" << std::endl;
+    }
+
+
     void add_leaf_node(const geometry::box<Point> &b, const boost::shared_ptr<rtree_leaf<Point, Value> > &l)
     {
       
@@ -39,11 +49,54 @@
 
     }
 
-    virtual ~rtree_node(void) {}
+    boost::shared_ptr<rtree_node<Point, Value> > choose_node(const geometry::box<Point> e)
+    {
+      std::cerr << "Choose node" << std::endl;
 
+      if(nodes_.size() == 0) {
+	throw std::logic_error("Empty node trying to choose the least enlargment node.");
+      }
+      bool first = true;
+      double min_area;
+      double min_diff_area;
+      boost::shared_ptr<rtree_node<Point,Value> > chosen_node;
+
+      for(typename node_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
+
+	double diff_area = compute_union_area(e, it->first) - geometry::area(it->first);
+
+	if(first) {
+	  // it's the first time, we keep the first
+	  min_diff_area = diff_area;
+	  min_area = geometry::area(it->first);
+	  chosen_node = it->second;
+
+	  first = false;
+	} else {
+	  if(diff_area < min_diff_area) {
+	    min_diff_area = diff_area;
+	    min_area = geometry::area(it->first);
+	    chosen_node = it->second;	    
+	  } else {
+	    if(diff_area == min_diff_area) {
+	      if(geometry::area(it->first) < min_area) {
+		min_diff_area = diff_area;
+		min_area = geometry::area(it->first);
+		chosen_node = it->second;	    
+	      }
+	    }
+	  }
+
+	}
+      }
+      std::cerr << "We have a node." << std::endl;
+      return chosen_node;
+    }
 
 
 
+    virtual ~rtree_node(void) {}
+
     // level of this node
     unsigned int level_;
 
@@ -52,7 +105,32 @@
     // maximum number of elements per node
     unsigned int M_;
 
-    std::map<geometry::box<Point>, boost::shared_ptr<rtree_node> > nodes_;
+    typedef std::map<geometry::box<Point>, boost::shared_ptr<rtree_node> > node_map;
+    node_map nodes_;
+
+  private:
+
+    geometry::box<Point> enlarge_box(const geometry::box<Point> &b1, const geometry::box<Point> &b2) const
+    {
+      Point min(
+		geometry::get<0>(b1.min()) < geometry::get<0>(b2.min()) ? geometry::get<0>(b1.min()) : geometry::get<0>(b2.min()),
+		geometry::get<1>(b1.min()) < geometry::get<1>(b2.min()) ? geometry::get<1>(b1.min()) : geometry::get<1>(b2.min())
+		);
+
+      Point max(
+		geometry::get<0>(b1.max()) > geometry::get<0>(b2.max()) ? geometry::get<0>(b1.max()) : geometry::get<0>(b2.max()),
+		geometry::get<1>(b1.max()) > geometry::get<1>(b2.max()) ? geometry::get<1>(b1.max()) : geometry::get<1>(b2.max())
+		);
+
+      return geometry::box<Point>(min, max);
+    }
+
+    double compute_union_area(const geometry::box<Point> &b1, const geometry::box<Point> &b2) const
+    {
+      geometry::box<Point> enlarged_box = enlarge_box(b1, b2);
+      return geometry::area(enlarged_box);
+    }
+
 
   };
 
@@ -67,6 +145,13 @@
     /// yes, we are a leaf
     virtual bool is_leaf(void) { return true; }
 
+    virtual bool is_full(void) const { return nodes_.size() == L_; }
+
+    virtual void insert(const geometry::box<Point> &e, const Value &v) 
+    {
+      nodes_[e] = v;
+    }
+
   private:
 
     // maximum number of elements per leaf
@@ -75,8 +160,8 @@
     // level of this node
     unsigned int level_;
 
-
-    std::map<geometry::box<Point>, Value > nodes_;
+    typedef std::map<geometry::box<Point>, Value > leaves_map;
+    leaves_map nodes_;
   };
 
 
@@ -114,7 +199,15 @@
 
     void insert(const geometry::box<Point> &e, const Value &v)
     {
-      boost::shared_ptr<rtree_node<Point, Value> > l = choose_leaf(e);
+      boost::shared_ptr<rtree_node<Point, Value> > l(choose_leaf(e));
+
+      if(l->is_full()) {
+	// split!
+      } else {
+	l->insert(e, v);
+      }
+
+      adjust_tree(l);
 
       element_count++;
     }
@@ -142,25 +235,23 @@
 
   private:
 
+    void adjust_tree(boost::shared_ptr<rtree_node<Point, Value> > &l)
+    {
+      
+    }
+
     boost::shared_ptr<rtree_node<Point, Value> > choose_leaf(const geometry::box<Point> e)
     {
       boost::shared_ptr< rtree_node<Point, Value> > N = root_;
 
       std::cerr << "Choosing." << std::endl;
 
-//       while() {
-	if(N->is_leaf()) {
-	  return N;
-	} else {
-	  /// traverse N's map to see which node we should select
-	  std::cerr << "Not a leaf." << std::endl;
-
-	  
-	}
-//       }
-	// FIXME
-	return root_;
-    
+      while(!N->is_leaf()) {
+	/// traverse N's map to see which node we should select
+	std::cerr << "Not a leaf." << std::endl;
+	N = N->choose_node(e);
+      }
+      return N;
     }