Boost logo

Boost-Commit :

From: mariano.consoni_at_[hidden]
Date: 2008-06-13 14:05:38


Author: mconsoni
Date: 2008-06-13 14:05:38 EDT (Fri, 13 Jun 2008)
New Revision: 46378
URL: http://svn.boost.org/trac/boost/changeset/46378

Log:

- Inserts working.

Text files modified:
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp | 114 ++++++++++++++++++++++++++++++++++-----
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp | 49 +++++++++++++++--
   sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp | 19 ++++++
   3 files changed, 159 insertions(+), 23 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-13 14:05:38 EDT (Fri, 13 Jun 2008)
@@ -64,17 +64,16 @@
         boost::shared_ptr< rtree_node<Point, Value> > n2(new rtree_leaf<Point,Value>(l->get_parent(), l->get_capacity()));
 
         split_node(l, n1, n2);
-
-
+ std::cerr << "Node splited." << std::endl;
+ n1->print();
+ n2->print();
+ adjust_tree(l, n1, n2);
 
       } else {
         l->insert(e, v);
+ adjust_tree(l);
       }
 
-
-
- adjust_tree(l);
-
       element_count++;
     }
 
@@ -101,18 +100,55 @@
 
   private:
 
- void adjust_tree(boost::shared_ptr<rtree_node<Point, Value> > &l)
+ void adjust_tree(boost::shared_ptr<rtree_node<Point, Value> > &n)
     {
- boost::shared_ptr<rtree_node<Point,Value> > N = l;
- if(N->is_root()) {
+ if(n->is_root()) {
+ // we finished the adjust
         return;
       }
+ // as there are no splits just adjust the box of the parent and go on
+ boost::shared_ptr<rtree_node<Point,Value> > parent = n->get_parent();
+ parent->adjust_box(n);
+ adjust_tree(parent);
+ }
 
+ void adjust_tree(boost::shared_ptr<rtree_node<Point, Value> > &l,
+ boost::shared_ptr<rtree_node<Point, Value> > &n1,
+ boost::shared_ptr<rtree_node<Point, Value> > &n2)
+ {
+ boost::shared_ptr<rtree_node<Point,Value> > N = n1;
+ boost::shared_ptr<rtree_node<Point,Value> > NN = n2;
+ if(l->is_root()) {
+ std::cerr << "Root ---------> split."<< std::endl;
+ boost::shared_ptr< rtree_node<Point,Value> > new_root(new rtree_node<Point,Value>(boost::shared_ptr<rtree_node<Point,Value> >(), l->get_level()+1, m_, M_));
+ new_root->set_root();
+ new_root->add_node(n1->compute_box(), n1);
+ new_root->add_node(n2->compute_box(), n2);
+ root_ = new_root;
+ return;
+ }
+ boost::shared_ptr<rtree_node<Point,Value> > parent = l->get_parent();
+ parent->replace_node(l, n1);
+ if(parent->is_full()) {
+ parent->add_node(n2->compute_box(), n2);
+ std::cerr << "parent is full" << std::endl;
+
+ boost::shared_ptr< rtree_node<Point, Value> > p1(new rtree_node<Point,Value>(parent->get_parent(), parent->get_level(), m_, M_));
+ boost::shared_ptr< rtree_node<Point, Value> > p2(new rtree_node<Point,Value>(parent->get_parent(), parent->get_level(), m_, M_));
+
+ split_node(parent, p1, p2);
+ adjust_tree(parent, p1, p2);
+ } else {
+ parent->add_node(n2->compute_box(), n2);
+ adjust_tree(parent);
+ }
     }
 
+
     void split_node(const boost::shared_ptr<rtree_node<Point, Value> > &n, boost::shared_ptr<rtree_node<Point, Value> > &n1
                     , boost::shared_ptr<rtree_node<Point, Value> > &n2) const
     {
+ // TODO: unify
       std::cerr << "Split Node." << std::endl;
 
       unsigned int seed1, seed2;
@@ -124,9 +160,6 @@
          n1->add_value(boxes[seed1], n->get_value(seed1));
         n2->add_value(boxes[seed2], n->get_value(seed2));
 
- n1->print();
- n2->print();
-
         unsigned int index = 0;
         typename rtree_leaf<Point,Value>::leaves_map nodes = n->get_leaves();
         for(typename rtree_leaf<Point,Value>::leaves_map::const_iterator it = nodes.begin(); it != nodes.end(); ++it, index++) {
@@ -172,14 +205,61 @@
               }
             }
 
- n1->print();
- n2->print();
-
           }
         }
       } else {
- // TODO
- std::cerr << "TODO: implement node split" << std::endl;
+ n1->add_node(boxes[seed1], n->get_node(seed1));
+ n2->add_node(boxes[seed2], n->get_node(seed2));
+
+ unsigned int index = 0;
+ typename rtree_node<Point,Value>::node_map nodes = n->get_nodes();
+ for(typename rtree_node<Point,Value>::node_map::const_iterator it = nodes.begin(); it != nodes.end(); ++it, index++) {
+ if(index != seed1 && index != seed2) {
+ // TODO: check if the remaining elements should be in one group because of the minimum
+
+ std::cerr << "1" << std::endl;
+ /// current boxes of each group
+ geometry::box<Point> b1, b2;
+
+ /// enlarged boxes of each group
+ geometry::box<Point> eb1, eb2;
+ b1 = n1->compute_box();
+ b2 = n2->compute_box();
+
+ /// areas
+ double b1_area, b2_area;
+ double eb1_area, eb2_area;
+ b1_area = geometry::area(b1);
+ b2_area = geometry::area(b2);
+
+ eb1_area = compute_union_area(b1, it->first);
+ eb2_area = compute_union_area(b2, it->first);
+
+ if(eb1_area - b1_area > eb2_area - b2_area) {
+ n2->add_node(it->first, it->second);
+ }
+ if(eb1_area - b1_area < eb2_area - b2_area) {
+ n1->add_node(it->first, it->second);
+ }
+ if(eb1_area - b1_area == eb2_area - b2_area) {
+ if(b1_area < b2_area) {
+ n1->add_node(it->first, it->second);
+ }
+ if(b1_area > b2_area) {
+ n2->add_node(it->first, it->second);
+ }
+ if(b1_area == b2_area) {
+ if(n1->elements() > n2->elements()) {
+ n2->add_node(it->first, it->second);
+ } else {
+ n1->add_node(it->first, it->second);
+ }
+ }
+ }
+
+ }
+ }
+ std::cerr << "s" << std::endl;
       }
     }
 

Modified: sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp (original)
+++ sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp 2008-06-13 14:05:38 EDT (Fri, 13 Jun 2008)
@@ -24,16 +24,23 @@
   class rtree_node
   {
   public:
+ /// type for the node map
+ typedef std::vector< std::pair<geometry::box<Point>, boost::shared_ptr<rtree_node<Point, Value> > > > node_map;
+
+ public:
     /// default constructor (needed for the containers)
- rtree_node(void) : m_(4), M_(8) {}
+ rtree_node(void) : m_(4), M_(8), root_(false) {}
 
     /// normal constructor
     rtree_node(const boost::shared_ptr<rtree_node<Point, Value> > &parent, const unsigned int &level, const unsigned int &m, const unsigned int &M)
- : parent_(parent), level_(level), m_(m), M_(M) {}
+ : parent_(parent), level_(level), m_(m), M_(M), root_(false) {}
 
     /// true if the node is full
     virtual bool is_full(void) const { return nodes_.size() >= M_; }
 
+ /// level projector
+ virtual unsigned int get_level(void) const { return level_; }
+
     /// element count
     virtual unsigned int elements(void) const
     {
@@ -96,6 +103,34 @@
       return r;
     }
 
+ /// recompute the box
+ void adjust_box(const boost::shared_ptr<rtree_node<Point, Value> > &n)
+ {
+ unsigned int index = 0;
+ for(typename node_map::iterator it = nodes_.begin(); it != nodes_.end(); ++it, index++) {
+ if(it->second.get() == n.get()) {
+ std::cerr << "Node found!" << std::endl;
+ nodes_[index] = std::make_pair(n->compute_box(), n);
+ return;
+ }
+ }
+ std::cerr << "adjust_node: node not found." << std::endl;
+ }
+
+ /// replace the node in the nodes_ vector and recompute the box
+ void replace_node(const boost::shared_ptr<rtree_node<Point, Value> > &l, boost::shared_ptr<rtree_node<Point, Value> > &new_l)
+ {
+ unsigned int index = 0;
+ for(typename node_map::iterator it = nodes_.begin(); it != nodes_.end(); ++it, index++) {
+ if(it->second.get() == l.get()) {
+ std::cerr << "Node found!" << std::endl;
+ nodes_[index] = std::make_pair(new_l->compute_box(), new_l);
+ return;
+ }
+ }
+ std::cerr << "replace_node: node not found." << std::endl;
+ }
+
     /// add a node
     virtual void add_node(const geometry::box<Point> &b, const boost::shared_ptr<rtree_node<Point, Value> > &n)
     {
@@ -172,6 +207,9 @@
     /// value projector for leaf_node (not allowed here)
     virtual Value get_value(const unsigned int i) const { throw std::logic_error("No values in a non-leaf node."); }
 
+ /// value projector for the nodes
+ node_map get_nodes(void) const { return nodes_; }
+
     /// print node
     virtual void print(void) const
     {
@@ -200,8 +238,6 @@
 
   private:
 
- // true if it is the root
- bool root_;
 
     // parent node
     boost::shared_ptr< rtree_node<Point, Value> > parent_;
@@ -215,8 +251,9 @@
     // maximum number of elements per node
     unsigned int M_;
 
- /// type for the node map
- typedef std::vector< std::pair<geometry::box<Point>, boost::shared_ptr<rtree_node> > > node_map;
+ // true if it is the root
+ bool root_;
+
 
     /// child nodes
     node_map nodes_;

Modified: sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp (original)
+++ sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp 2008-06-13 14:05:38 EDT (Fri, 13 Jun 2008)
@@ -51,13 +51,32 @@
         geometry::box<geometry::point_xy<double> > e3(geometry::point_xy<double>(5.0, 4.0), geometry::point_xy<double>(6.0, 6.0));
         geometry::box<geometry::point_xy<double> > e4(geometry::point_xy<double>(5.0, 5.0), geometry::point_xy<double>(8.0, 8.0));
         geometry::box<geometry::point_xy<double> > e5(geometry::point_xy<double>(7.0, 4.0), geometry::point_xy<double>(12.0, 7.0));
+
+
+ geometry::box<geometry::point_xy<double> > e6(geometry::point_xy<double>(5.0, 5.0), geometry::point_xy<double>(9.0, 10.0));
+ geometry::box<geometry::point_xy<double> > e7(geometry::point_xy<double>(7.0, 7.0), geometry::point_xy<double>(12.0, 12.0));
+
+ geometry::box<geometry::point_xy<double> > e8(geometry::point_xy<double>(1.0, 5.0), geometry::point_xy<double>(2.0, 10.0));
+ geometry::box<geometry::point_xy<double> > e9(geometry::point_xy<double>(1.0, 1.0), geometry::point_xy<double>(3.0, 3.0));
+ geometry::box<geometry::point_xy<double> > e10(geometry::point_xy<double>(1.5, 1.0), geometry::point_xy<double>(2.5, 3.0));
+ geometry::box<geometry::point_xy<double> > e11(geometry::point_xy<double>(1.0, 0.0), geometry::point_xy<double>(2.0, 3.0));
+
          std::cerr << " --> insert env" << std::endl;
          q->insert(e1, 1);
          q->insert(e2, 2);
          q->insert(e3, 3);
          q->insert(e4, 4);
          q->insert(e5, 5);
+ q->print();
+
+ q->insert(e6, 6);
+ q->insert(e7, 7);
+ q->print();
 
+ q->insert(e8, 8);
+ q->insert(e9, 9);
+ q->insert(e10, 10);
+ q->insert(e11, 11);
          q->print();
 
 // std::cerr << " --> insert" << std::endl;


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