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

From: mariano.consoni_at_[hidden]
Date: 2008-06-12 16:18:38

Author: mconsoni
Date: 2008-06-12 16:18:37 EDT (Thu, 12 Jun 2008)
New Revision: 46361
URL: http://svn.boost.org/trac/boost/changeset/46361

Log:

- Seeds for Node Split.

Text files modified: 
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp |    66 +++++++++++++++++++++++++++++---------- 
   1 files changed, 49 insertions(+), 17 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-12 16:18:37 EDT (Thu, 12 Jun 2008)
@@ -36,6 +36,8 @@
     bool is_root(void) const { return root_; }
     void set_root(void) { root_ = true; }
 
+    boost::shared_ptr< rtree_node<Point, Value> > get_node(const unsigned int i) { return nodes_[i].second; }
+
     virtual void insert(const geometry::box<Point> &e, const Value &v) 
     {
       std::cerr << "Insert in node!" << std::endl;
@@ -55,17 +57,20 @@
       return r;
     }
 
-    void add_leaf_node(const geometry::box<Point> &b, const boost::shared_ptr<rtree_leaf<Point, Value> > &l)
+    virtual void add_node(const geometry::box<Point> &b, const boost::shared_ptr<rtree_node<Point, Value> > &n)
     {
-      
-//       if(nodes_.size() < M_) {
-	nodes_.push_back(std::make_pair(b, l));
-//       } else {
-// 	// split
-// 	boost::shared_ptr< rtree_node<Point,Value> > n1, n2;
-// 	split_node(l, n1, n2);
-//       }
+      nodes_.push_back(std::make_pair(b, n));
+    }
+
+    virtual void add_value(const geometry::box<Point> &b, const Value &v)
+    {
+      throw std::logic_error("Can't add value to non-leaf node."); 
+    }
+
 
+    void add_leaf_node(const geometry::box<Point> &b, const boost::shared_ptr<rtree_leaf<Point, Value> > &l)
+    {
+      nodes_.push_back(std::make_pair(b, l));
     }
 
     boost::shared_ptr<rtree_node<Point, Value> > choose_node(const geometry::box<Point> e)
@@ -120,6 +125,8 @@
       return parent_;
     }
 
+    virtual Value get_value(const unsigned int i) const { throw std::logic_error("No values in a non-leaf node."); }
+
     virtual void print(void) const
     {
       std::cerr << " --> Node --------" << std::endl;
@@ -142,8 +149,6 @@
       }
     }
 
-
-
     virtual ~rtree_node(void) {}
 
   private:
@@ -167,7 +172,6 @@
 
   private:
 
-
     geometry::box<Point> enlarge_box(const geometry::box<Point> &b1, const geometry::box<Point> &b2) const
     {
       Point min(
@@ -190,6 +194,7 @@
     }
 
 
+
   };
 
 
@@ -212,6 +217,16 @@
 //       std::cerr << "Node size: " << nodes_.size() << std::endl;
     }
 
+    virtual void add_node(const geometry::box<Point> &b, const boost::shared_ptr<rtree_node<Point, Value> > &n)
+    {
+      throw std::logic_error("Can't add node to leaf node."); 
+    }
+
+    virtual void add_value(const geometry::box<Point> &b, const Value &v)
+    {
+      nodes_.push_back(std::make_pair(b, v));
+    }
+
     virtual void empty_nodes(void) {
       nodes_.clear();
     }
@@ -221,6 +236,8 @@
       return L_;
     }
 
+    virtual Value get_value(const unsigned int i) const { return nodes_[i].second; }
+
     virtual std::vector< geometry::box<Point> > get_boxes(void) const
     {
       std::vector< geometry::box<Point> > r;
@@ -358,15 +375,22 @@
     {
       std::cerr << "Split Node." << std::endl;
 
-      boost::shared_ptr< rtree_node<Point,Value> > seed1, seed2;
+      unsigned int seed1, seed2;
+      std::vector< geometry::box<Point> > boxes = n->get_boxes();
 
       linear_pick_seeds(n, seed1, seed2);
+
+      if(n->is_leaf()) {
+	n->get_value(seed1);
+// 	n1->add_value(boxes[seed1], n->get_value(seed1));
+	// n2->add_node(boxes[seed2], n->get_node(seed2));
+      }
     }
 
 
     void linear_pick_seeds(const boost::shared_ptr< rtree_node<Point,Value> > &n, 
-			   boost::shared_ptr< rtree_node<Point,Value> > &seed1,
-			   boost::shared_ptr< rtree_node<Point,Value> > &seed2) const
+			   unsigned int &seed1,
+			   unsigned int &seed2) const
     {
       std::cerr << "Linear Pick Seeds." << std::endl;
 
@@ -386,8 +410,16 @@
       find_normalized_separations<0u>(boxes, separation_x, first_x, second_x);
       find_normalized_separations<1u>(boxes, separation_y, first_y, second_y);
 
-      std::cout << "Separation X: " << separation_x << " within " << first_x << " and " << second_x << std::endl;
-      std::cout << "Separation Y: " << separation_y << " within " << first_y << " and " << second_y << std::endl;
+      std::cout << "Separation X: " << separation_x << " between " << first_x << " and " << second_x << std::endl;
+      std::cout << "Separation Y: " << separation_y << " between " << first_y << " and " << second_y << std::endl;
+
+      if(separation_x > separation_y) {
+	seed1 = first_x;
+	seed2 = second_x;
+      } else {
+	seed1 = first_y;
+	seed2 = second_y;
+      }
     }
 
     template<unsigned int Dimension>