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;