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;
}