Boost logo

Boost-Commit :

Date view Thread view Subject view Author view

From: mariano.consoni_at_[hidden]
Date: 2008-07-23 13:32:05

Author: mconsoni
Date: 2008-07-23 13:32:04 EDT (Wed, 23 Jul 2008)
New Revision: 47731
URL: http://svn.boost.org/trac/boost/changeset/47731

Log:
- Code indented according to Boost Guidelines.

Text files modified:
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index.hpp | 1
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/helpers.hpp | 112 ++-
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree.hpp | 186 +++--
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree_node.hpp | 644 +++++++++++----------
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp | 1175 ++++++++++++++++++++-------------------
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_leaf.hpp | 231 ++++---
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp | 680 ++++++++++++----------
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/spatial_index.hpp | 244 +++++---
   8 files changed, 1773 insertions(+), 1500 deletions(-)

Modified: sandbox/SOC/2008/spacial_indexing/boost/spatial_index.hpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/boost/spatial_index.hpp (original)
+++ sandbox/SOC/2008/spacial_indexing/boost/spatial_index.hpp 2008-07-23 13:32:04 EDT (Wed, 23 Jul 2008)
@@ -13,4 +13,3 @@
 #include <boost/spatial_index/rtree.hpp>
 
 #endif // BOOST_SPATIAL_INDEX_HPP
-

Modified: sandbox/SOC/2008/spacial_indexing/boost/spatial_index/helpers.hpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/boost/spatial_index/helpers.hpp (original)
+++ sandbox/SOC/2008/spacial_indexing/boost/spatial_index/helpers.hpp 2008-07-23 13:32:04 EDT (Wed, 23 Jul 2008)
@@ -7,63 +7,79 @@
 #ifndef BOOST_SPATIAL_INDEX_HELPERS_HPP
 #define BOOST_SPATIAL_INDEX_HELPERS_HPP
 
-namespace boost {
-namespace spatial_index {
-
-
- /// given two boxes, create the minimal box that contains them
- template<typename Point>
- geometry::box<Point> enlarge_box(const geometry::box<Point> &b1, const geometry::box<Point> &b2)
- {
- 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);
- }
-
- /// compute the area of the union of b1 and b2
- template<typename Point>
- double compute_union_area(const geometry::box<Point> &b1, const geometry::box<Point> &b2)
+namespace boost
+{
+ namespace spatial_index
   {
- geometry::box<Point> enlarged_box = enlarge_box(b1, b2);
- return geometry::area(enlarged_box);
- }
 
 
+ /// given two boxes, create the minimal box that contains them
+ template < typename Point >
+ geometry::box < Point > enlarge_box(const geometry::box < Point > &b1,
+ const geometry::box < Point > &b2)
+ {
+ 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()));
 
- template<typename Point>
- bool overlaps(const geometry::box<Point> &b1, const geometry::box<Point> &b2)
- {
-
- bool overlaps_x, overlaps_y;
- overlaps_x = overlaps_y = false;
-
- if(geometry::get<0>(b1.min()) >= geometry::get<0>(b2.min()) && geometry::get<0>(b1.min()) <= geometry::get<0>(b2.max())) {
- overlaps_x = true;
- }
- if(geometry::get<0>(b1.max()) >= geometry::get<0>(b2.min()) && geometry::get<0>(b1.min()) <= geometry::get<0>(b2.max())) {
- overlaps_x = true;
+ return geometry::box < Point > (min, max);
     }
 
- if(geometry::get<1>(b1.min()) >= geometry::get<1>(b2.min()) && geometry::get<1>(b1.min()) <= geometry::get<1>(b2.max())) {
- overlaps_y = true;
- }
- if(geometry::get<1>(b1.max()) >= geometry::get<1>(b2.min()) && geometry::get<1>(b1.min()) <= geometry::get<1>(b2.max())) {
- overlaps_y = true;
+ /// compute the area of the union of b1 and b2
+ template < typename Point >
+ double compute_union_area(const geometry::box < Point > &b1,
+ const geometry::box < Point > &b2)
+ {
+ geometry::box < Point > enlarged_box = enlarge_box(b1, b2);
+ return geometry::area(enlarged_box);
     }
 
- return overlaps_x && overlaps_y;
- }
+
+ template < typename Point >
+ bool overlaps(const geometry::box < Point > &b1,
+ const geometry::box < Point > &b2)
+ {
+
+ bool overlaps_x, overlaps_y;
+ overlaps_x = overlaps_y = false;
+
+ if (geometry::get < 0 > (b1.min()) >= geometry::get < 0 > (b2.min())
+ && geometry::get < 0 > (b1.min()) <= geometry::get < 0 > (b2.max()))
+ {
+ overlaps_x = true;
+ }
+ if (geometry::get < 0 > (b1.max()) >= geometry::get < 0 > (b2.min())
+ && geometry::get < 0 > (b1.min()) <= geometry::get < 0 > (b2.max()))
+ {
+ overlaps_x = true;
+ }
+
+ if (geometry::get < 1 > (b1.min()) >= geometry::get < 1 > (b2.min())
+ && geometry::get < 1 > (b1.min()) <= geometry::get < 1 > (b2.max()))
+ {
+ overlaps_y = true;
+ }
+ if (geometry::get < 1 > (b1.max()) >= geometry::get < 1 > (b2.min())
+ && geometry::get < 1 > (b1.min()) <= geometry::get < 1 > (b2.max()))
+ {
+ overlaps_y = true;
+ }
+
+ return overlaps_x && overlaps_y;
+ }
 
 
-} // namespace spatial_index
-} // namespace boost
+ } // namespace spatial_index
+} // namespace boost
 
 #endif // BOOST_SPATIAL_INDEX_HELPERS_HPP

Modified: sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree.hpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree.hpp (original)
+++ sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree.hpp 2008-07-23 13:32:04 EDT (Wed, 23 Jul 2008)
@@ -1,5 +1,5 @@
 //
-// Spatial Index - QuadTree
+// Spatial Index - QuadTree
 //
 //
 // Copyright 2008 Federico J. Fernandez.
@@ -16,98 +16,108 @@
 
 // #include <boost/thread/xtime.hpp>
 
-namespace boost {
-namespace spatial_index {
-
-
-template<typename Point, typename Value>
-class quadtree
+namespace boost
 {
-private:
- quadtree_node<Point,Value> root;
- unsigned int element_count;
-
- // number of points in each node
- unsigned int node_size_;
-
-public:
- quadtree(const geometry::box<Point> &r)
- : root(r, 1), element_count(0), node_size_(1) {}
-
- quadtree(const geometry::box<Point> &r, const unsigned int M)
- : root(r, M), element_count(0), node_size_(M) {}
-
- quadtree(const geometry::box<Point> &r, const unsigned int m, const unsigned int M)
- : root(r, M), element_count(0), node_size_(M) {}
-
- /// remove the element with key 'k'
- void remove(const Point &k)
- {
- root.remove(k);
- element_count--;
- }
-
-
- void insert(const Point &k, const Value &v)
- {
- element_count++;
- root.insert(k, v);
- }
-
- void print(void)
- {
- std::cerr << "=================================" << std::endl;
- std::cerr << "Elements: " << elements() << std::endl;
- root.print();
- std::cerr << "=================================" << std::endl;
- }
-
-
- void bulk_insert(std::vector<Value> &values, std::vector<Point> &points)
- {
- // boost::xtime xt1, xt2;
- // boost::xtime_get(&xt1, boost::TIME_UTC);
-
- // unsigned int counter = 0;
-
- typename std::vector<Point>::iterator it_point;
- typename std::vector<Value>::iterator it_value;
- it_point = points.begin();
- it_value = values.begin();
- while(it_value != values.end() && it_point != points.end()) {
- insert(*it_point, *it_value);
-
- it_point++;
- it_value++;
-
- // counter++;
- // if(counter%10000 == 0) {
- // std::cerr << "counter: [" << counter << "]" << std::endl;
- // }
- }
- // boost::xtime_get(&xt2, boost::TIME_UTC);
- // std::cerr << "secs: " << xt2.sec - xt1.sec;
- // std::cerr << " nsecs: " << xt2.nsec - xt1.nsec << std::endl;
- }
-
- Value find(const Point &k)
+ namespace spatial_index
   {
- return root.find(k);
- }
 
- std::deque<Value> find(const geometry::box<Point> &r)
- {
- std::deque<Value> result;
- root.find(result, r);
- return result;
- }
 
- unsigned int elements(void) const { return element_count; }
-};
+ template < typename Point, typename Value > class quadtree
+ {
+ private:
+ quadtree_node < Point, Value > root;
+ unsigned int element_count;
+
+ // number of points in each node
+ unsigned int node_size_;
+
+ public:
+ quadtree(const geometry::box < Point > &r)
+ : root(r, 1), element_count(0), node_size_(1)
+ {
+ }
+
+ quadtree(const geometry::box < Point > &r, const unsigned int M)
+ : root(r, M), element_count(0), node_size_(M)
+ {
+ }
+
+ quadtree(const geometry::box < Point > &r, const unsigned int m,
+ const unsigned int M)
+ : root(r, M), element_count(0), node_size_(M)
+ {
+ }
+
+ /// remove the element with key 'k'
+ void remove(const Point & k)
+ {
+ root.remove(k);
+ element_count--;
+ }
+
+
+ void insert(const Point & k, const Value & v)
+ {
+ element_count++;
+ root.insert(k, v);
+ }
+
+ void print(void)
+ {
+ std::cerr << "=================================" << std::endl;
+ std::cerr << "Elements: " << elements() << std::endl;
+ root.print();
+ std::cerr << "=================================" << std::endl;
+ }
+
+
+ void bulk_insert(std::vector < Value > &values,
+ std::vector < Point > &points)
+ {
+ // boost::xtime xt1, xt2;
+ // boost::xtime_get(&xt1, boost::TIME_UTC);
+
+ // unsigned int counter = 0;
+
+ typename std::vector < Point >::iterator it_point;
+ typename std::vector < Value >::iterator it_value;
+ it_point = points.begin();
+ it_value = values.begin();
+ while (it_value != values.end() && it_point != points.end()) {
+ insert(*it_point, *it_value);
+
+ it_point++;
+ it_value++;
+
+ // counter++;
+ // if(counter%10000 == 0) {
+ // std::cerr << "counter: [" << counter << "]" << std::endl;
+ // }
+ }
+ // boost::xtime_get(&xt2, boost::TIME_UTC);
+ // std::cerr << "secs: " << xt2.sec - xt1.sec;
+ // std::cerr << " nsecs: " << xt2.nsec - xt1.nsec << std::endl;
+ }
+
+ Value find(const Point & k)
+ {
+ return root.find(k);
+ }
+
+ std::deque < Value > find(const geometry::box < Point > &r) {
+ std::deque < Value > result;
+ root.find(result, r);
+ return result;
+ }
+
+ unsigned int elements(void) const
+ {
+ return element_count;
+ }
+ };
 
 
-} // namespace spatial_index
-} // namespace boost
+ } // namespace spatial_index
+} // namespace boost
 
 #endif // BOOST_SPATIAL_INDEX_QUADTREE_HPP
-

Modified: sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree_node.hpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree_node.hpp (original)
+++ sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree_node.hpp 2008-07-23 13:32:04 EDT (Wed, 23 Jul 2008)
@@ -1,5 +1,5 @@
 //
-// Spatial Index - QuadTree Node
+// Spatial Index - QuadTree Node
 //
 //
 // Copyright 2008 Federico J. Fernandez.
@@ -19,310 +19,358 @@
 #include <iostream>
 #include <map>
 
-namespace boost {
-namespace spatial_index {
-
-template<typename Point, typename Value>
-class quadtree_node
+namespace boost
 {
-private:
- /// pointers to child nodes
- boost::shared_ptr<quadtree_node> nw_;
- boost::shared_ptr<quadtree_node> ne_;
- boost::shared_ptr<quadtree_node> sw_;
- boost::shared_ptr<quadtree_node> se_;
-
- /// this node's points
- std::map<Point, Value> m_;
-
- /// the bounding rectangle for the node
- geometry::box<Point> bounding_rectangle_;
-
- /// number of points in each node
- unsigned int node_size_;
-
- /// divide the node in four quadrants
- void divide_quadrants(geometry::box<Point> &ne_box, geometry::box<Point> &sw_box, geometry::box<Point> &se_box, geometry::box<Point> &nw_box) const
- {
-
- geometry::get<0>(ne_box.min()) = (geometry::get<0>(bounding_rectangle_.max()) - geometry::get<0>(bounding_rectangle_.min())) / 2.0
- + geometry::get<0>(bounding_rectangle_.min());
- geometry::get<1>(ne_box.min()) = (geometry::get<1>(bounding_rectangle_.max()) - geometry::get<1>(bounding_rectangle_.min())) / 2.0
- + geometry::get<1>(bounding_rectangle_.min());
- geometry::get<0>(ne_box.max()) = geometry::get<0>(bounding_rectangle_.max());
- geometry::get<1>(ne_box.max()) = geometry::get<1>(bounding_rectangle_.max());
-
- geometry::get<0>(sw_box.min()) = geometry::get<0>(bounding_rectangle_.min());
- geometry::get<1>(sw_box.min()) = geometry::get<1>(bounding_rectangle_.min());
- geometry::get<0>(sw_box.max()) = (geometry::get<0>(bounding_rectangle_.max()) - geometry::get<0>(bounding_rectangle_.min())) / 2.0
- + geometry::get<0>(bounding_rectangle_.min());
- geometry::get<1>(sw_box.max()) = (geometry::get<1>(bounding_rectangle_.max()) - geometry::get<1>(bounding_rectangle_.min())) / 2.0
- + geometry::get<1>(bounding_rectangle_.min());
-
- geometry::get<0>(se_box.min()) = (geometry::get<0>(bounding_rectangle_.max()) - geometry::get<0>(bounding_rectangle_.min())) / 2.0
- + geometry::get<0>(bounding_rectangle_.min());
- geometry::get<1>(se_box.min()) = geometry::get<1>(bounding_rectangle_.min());
- geometry::get<0>(se_box.max()) = geometry::get<0>(bounding_rectangle_.max());
- geometry::get<1>(se_box.max()) = (geometry::get<1>(bounding_rectangle_.max()) - geometry::get<1>(bounding_rectangle_.min())) / 2.0
- + geometry::get<1>(bounding_rectangle_.min());
-
- geometry::get<0>(nw_box.min()) = geometry::get<0>(bounding_rectangle_.min());
- geometry::get<1>(nw_box.min()) = (geometry::get<1>(bounding_rectangle_.max()) - geometry::get<1>(bounding_rectangle_.min())) / 2.0
- + geometry::get<1>(bounding_rectangle_.min());
- geometry::get<0>(nw_box.max()) = (geometry::get<0>(bounding_rectangle_.max()) - geometry::get<0>(bounding_rectangle_.min())) / 2.0
- + geometry::get<0>(bounding_rectangle_.min());
- geometry::get<1>(nw_box.max()) = geometry::get<1>(bounding_rectangle_.max());
- }
-
-
-public:
- quadtree_node(const geometry::box<Point> &r, const unsigned int node_size)
- : bounding_rectangle_(r), node_size_(node_size)
- {
- }
-
-
- bool empty_leaf(void) const
- {
- return (m_.size() == 0) &&
- (ne_ == boost::shared_ptr<quadtree_node>()) &&
- (se_ == boost::shared_ptr<quadtree_node>()) &&
- (nw_ == boost::shared_ptr<quadtree_node>()) &&
- (sw_ == boost::shared_ptr<quadtree_node>())
- ;
- }
-
- void insert(const Point &k, const Value &v)
- {
- if(m_.size() < node_size_) {
- m_[k] = v;
- } else {
- // IMP: maybe this could be done only one time at node creation
- geometry::box<Point> ne_box, sw_box, se_box, nw_box;
- divide_quadrants(ne_box, sw_box, se_box, nw_box);
-
- if(geometry::within(k, ne_box)) {
- if(this->ne_ == boost::shared_ptr<quadtree_node>()) {
- this->ne_ = boost::shared_ptr<quadtree_node>(new quadtree_node(ne_box, node_size_));
- }
- ne_->insert(k, v);
- return;
- }
- if(geometry::within(k, se_box)) {
- if(this->se_ == boost::shared_ptr<quadtree_node>()) {
- this->se_ = boost::shared_ptr<quadtree_node>(new quadtree_node(se_box, node_size_));
- }
- se_->insert(k, v);
- return;
- }
- if(geometry::within(k, nw_box)) {
- if(this->nw_ == boost::shared_ptr<quadtree_node>()) {
- this->nw_ = boost::shared_ptr<quadtree_node>(new quadtree_node(nw_box, node_size_));
- }
- nw_->insert(k, v);
- return;
- }
- if(geometry::within(k, sw_box)) {
- if(this->sw_ == boost::shared_ptr<quadtree_node>()) {
- this->sw_ = boost::shared_ptr<quadtree_node>(new quadtree_node(sw_box, node_size_));
- }
- sw_->insert(k, v);
- return;
- }
- }
- }
-
-
- void find(std::deque<Value> &result, const geometry::box<Point> &r)
- {
- if(m_.size() != 0) {
-
- if(geometry::get<0>(r.min()) > geometry::get<0>(bounding_rectangle_.max())
- || geometry::get<0>(r.max()) < geometry::get<0>(bounding_rectangle_.min())
- || geometry::get<1>(r.min()) > geometry::get<1>(bounding_rectangle_.max())
- || geometry::get<1>(r.max()) < geometry::get<1>(bounding_rectangle_.min())) {
- return;
- }
-
- for(typename std::map<Point,Value>::const_iterator it = m_.begin(); it != m_.end(); ++it) {
- if(geometry::get<0>(it->first) >= geometry::get<0>(r.min()) && geometry::get<0>(it->first) <= geometry::get<0>(r.max()) &&
- geometry::get<1>(it->first) >= geometry::get<1>(r.min()) && geometry::get<1>(it->first) <= geometry::get<1>(r.max())) {
- result.push_back(it->second);
- }
- }
-
- if(ne_ != boost::shared_ptr<quadtree_node>()) {
- ne_->find(result, r);
- }
- if(se_ != boost::shared_ptr<quadtree_node>()) {
- se_->find(result, r);
- }
- if(nw_ != boost::shared_ptr<quadtree_node>()) {
- nw_->find(result, r);
- }
- if(sw_ != boost::shared_ptr<quadtree_node>()) {
- sw_->find(result, r);
- }
- }
- }
-
-
- Value find(const Point &k)
- {
- typename std::map<Point, Value>::const_iterator it = m_.find(k);
- if(it != m_.end()) {
- return it->second;
- }
- return recursive_search(k);
- }
-
-
- Value recursive_search(const Point &k)
- {
- // IMP: maybe this could be done only one time at node creation
- // but it will consume more memory...
-
- geometry::box<Point> ne_box, sw_box, se_box, nw_box;
- divide_quadrants(ne_box, sw_box, se_box, nw_box);
-
- if(geometry::within(k, ne_box)) {
- if(ne_ != boost::shared_ptr<quadtree_node>()) {
- return ne_->find(k);
- } else {
- return Value();
- }
- }
- if(geometry::within(k, se_box)) {
- if(se_ != boost::shared_ptr<quadtree_node>()) {
- return se_->find(k);
- } else {
- return Value();
- }
- }
- if(geometry::within(k, nw_box)) {
- if(nw_ != boost::shared_ptr<quadtree_node>()) {
- return nw_->find(k);
- } else {
- return Value();
- }
- }
- if(geometry::within(k, sw_box)) {
- if(sw_ != boost::shared_ptr<quadtree_node>()) {
- return sw_->find(k);
- } else {
- return Value();
- }
- }
- // never reached
- return Value();
- }
-
-
- void remove(const Point &k)
- {
- typename std::map<Point, Value>::iterator it = m_.find(k);
- if(it != m_.end()) {
- m_.erase(it);
- return;
- }
- recursive_remove(k);
- }
-
-
- void recursive_remove(const Point &k)
+ namespace spatial_index
   {
- // IMP: maybe this could be done only one time at node creation
- // but it will consume more memory...
- geometry::box<Point> ne_box, sw_box, se_box, nw_box;
- divide_quadrants(ne_box, sw_box, se_box, nw_box);
 
-
- if(geometry::within(k, ne_box)) {
- if(ne_ != boost::shared_ptr<quadtree_node>()) {
- ne_->remove(k);
- if(ne_->empty_leaf()) {
- ne_ = boost::shared_ptr<quadtree_node>();
- }
- return;
- } else {
- throw std::logic_error("Not found");
- }
- }
- if(geometry::within(k, se_box)) {
- if(se_ != boost::shared_ptr<quadtree_node>()) {
- se_->remove(k);
- if(se_->empty_leaf()) {
- se_ = boost::shared_ptr<quadtree_node>();
- }
- return;
- } else {
- throw std::logic_error("Not found");
- }
- }
- if(geometry::within(k, nw_box)) {
- if(nw_ != boost::shared_ptr<quadtree_node>()) {
- nw_->remove(k);
- if(nw_->empty_leaf()) {
- nw_ = boost::shared_ptr<quadtree_node>();
- }
- return;
- } else {
- throw std::logic_error("Not found");
- }
- }
- if(geometry::within(k, sw_box)) {
- if(sw_ != boost::shared_ptr<quadtree_node>()) {
- sw_->remove(k);
- if(sw_->empty_leaf()) {
- sw_ = boost::shared_ptr<quadtree_node>();
- }
- return;
- } else {
- throw std::logic_error("Not found");
- }
- }
- }
-
-
- void print(void) const
- {
- std::cerr << "--------------------------------------" << std::endl;
- std::cerr << " [ ";
- for(typename std::map<Point,Value>::const_iterator it = m_.begin(); it != m_.end(); ++it) {
+ template < typename Point, typename Value > class quadtree_node
+ {
+ private:
+ /// pointers to child nodes
+ boost::shared_ptr < quadtree_node > nw_;
+ boost::shared_ptr < quadtree_node > ne_;
+ boost::shared_ptr < quadtree_node > sw_;
+ boost::shared_ptr < quadtree_node > se_;
+
+ /// this node's points
+ std::map < Point, Value > m_;
+
+ /// the bounding rectangle for the node
+ geometry::box < Point > bounding_rectangle_;
+
+ /// number of points in each node
+ unsigned int node_size_;
+
+ /// divide the node in four quadrants
+ void divide_quadrants(geometry::box < Point > &ne_box,
+ geometry::box < Point > &sw_box,
+ geometry::box < Point > &se_box,
+ geometry::box < Point > &nw_box) const
+ {
+
+ geometry::get < 0 > (ne_box.min()) =
+ (geometry::get < 0 > (bounding_rectangle_.max()) - geometry::get < 0 >
+ (bounding_rectangle_.min())) / 2.0 + geometry::get < 0 >
+ (bounding_rectangle_.min());
+ geometry::get < 1 > (ne_box.min()) =
+ (geometry::get < 1 > (bounding_rectangle_.max()) - geometry::get < 1 >
+ (bounding_rectangle_.min())) / 2.0 + geometry::get < 1 >
+ (bounding_rectangle_.min());
+ geometry::get < 0 > (ne_box.max()) =
+ geometry::get < 0 > (bounding_rectangle_.max());
+ geometry::get < 1 > (ne_box.max()) =
+ geometry::get < 1 > (bounding_rectangle_.max());
+
+ geometry::get < 0 > (sw_box.min()) =
+ geometry::get < 0 > (bounding_rectangle_.min());
+ geometry::get < 1 > (sw_box.min()) =
+ geometry::get < 1 > (bounding_rectangle_.min());
+ geometry::get < 0 > (sw_box.max()) =
+ (geometry::get < 0 > (bounding_rectangle_.max()) - geometry::get < 0 >
+ (bounding_rectangle_.min())) / 2.0 + geometry::get < 0 >
+ (bounding_rectangle_.min());
+ geometry::get < 1 > (sw_box.max()) =
+ (geometry::get < 1 > (bounding_rectangle_.max()) - geometry::get < 1 >
+ (bounding_rectangle_.min())) / 2.0 + geometry::get < 1 >
+ (bounding_rectangle_.min());
+
+ geometry::get < 0 > (se_box.min()) =
+ (geometry::get < 0 > (bounding_rectangle_.max()) - geometry::get < 0 >
+ (bounding_rectangle_.min())) / 2.0 + geometry::get < 0 >
+ (bounding_rectangle_.min());
+ geometry::get < 1 > (se_box.min()) =
+ geometry::get < 1 > (bounding_rectangle_.min());
+ geometry::get < 0 > (se_box.max()) =
+ geometry::get < 0 > (bounding_rectangle_.max());
+ geometry::get < 1 > (se_box.max()) =
+ (geometry::get < 1 > (bounding_rectangle_.max()) - geometry::get < 1 >
+ (bounding_rectangle_.min())) / 2.0 + geometry::get < 1 >
+ (bounding_rectangle_.min());
+
+ geometry::get < 0 > (nw_box.min()) =
+ geometry::get < 0 > (bounding_rectangle_.min());
+ geometry::get < 1 > (nw_box.min()) =
+ (geometry::get < 1 > (bounding_rectangle_.max()) - geometry::get < 1 >
+ (bounding_rectangle_.min())) / 2.0 + geometry::get < 1 >
+ (bounding_rectangle_.min());
+ geometry::get < 0 > (nw_box.max()) =
+ (geometry::get < 0 > (bounding_rectangle_.max()) - geometry::get < 0 >
+ (bounding_rectangle_.min())) / 2.0 + geometry::get < 0 >
+ (bounding_rectangle_.min());
+ geometry::get < 1 > (nw_box.max()) =
+ geometry::get < 1 > (bounding_rectangle_.max());
+ }
+
+
+ public:
+ quadtree_node(const geometry::box < Point > &r,
+ const unsigned int node_size)
+ : bounding_rectangle_(r), node_size_(node_size)
+ {
+ }
+
+
+ bool empty_leaf(void) const
+ {
+ return (m_.size() == 0) &&
+ (ne_ == boost::shared_ptr < quadtree_node > ()) &&
+ (se_ == boost::shared_ptr < quadtree_node > ()) &&
+ (nw_ == boost::shared_ptr < quadtree_node > ()) &&
+ (sw_ == boost::shared_ptr < quadtree_node > ());
+ }
+
+ void insert(const Point & k, const Value & v)
+ {
+ if (m_.size() < node_size_) {
+ m_[k] = v;
+ } else {
+ // IMP: maybe this could be done only one time at node creation
+ geometry::box < Point > ne_box, sw_box, se_box, nw_box;
+ divide_quadrants(ne_box, sw_box, se_box, nw_box);
+
+ if (geometry::within(k, ne_box)) {
+ if (this->ne_ == boost::shared_ptr < quadtree_node > ()) {
+ this->ne_ =
+ boost::shared_ptr < quadtree_node >
+ (new quadtree_node(ne_box, node_size_));
+ }
+ ne_->insert(k, v);
+ return;
+ }
+ if (geometry::within(k, se_box)) {
+ if (this->se_ == boost::shared_ptr < quadtree_node > ()) {
+ this->se_ =
+ boost::shared_ptr < quadtree_node >
+ (new quadtree_node(se_box, node_size_));
+ }
+ se_->insert(k, v);
+ return;
+ }
+ if (geometry::within(k, nw_box)) {
+ if (this->nw_ == boost::shared_ptr < quadtree_node > ()) {
+ this->nw_ =
+ boost::shared_ptr < quadtree_node >
+ (new quadtree_node(nw_box, node_size_));
+ }
+ nw_->insert(k, v);
+ return;
+ }
+ if (geometry::within(k, sw_box)) {
+ if (this->sw_ == boost::shared_ptr < quadtree_node > ()) {
+ this->sw_ =
+ boost::shared_ptr < quadtree_node >
+ (new quadtree_node(sw_box, node_size_));
+ }
+ sw_->insert(k, v);
+ return;
+ }
+ }
+ }
+
+
+ void find(std::deque < Value > &result, const geometry::box < Point > &r)
+ {
+ if (m_.size() != 0) {
+
+ if (geometry::get < 0 > (r.min()) > geometry::get < 0 >
+ (bounding_rectangle_.max())
+ || geometry::get < 0 > (r.max()) < geometry::get < 0 >
+ (bounding_rectangle_.min())
+ || geometry::get < 1 > (r.min()) > geometry::get < 1 >
+ (bounding_rectangle_.max())
+ || geometry::get < 1 > (r.max()) < geometry::get < 1 >
+ (bounding_rectangle_.min())) {
+ return;
+ }
+
+ for(typename std::map < Point, Value >::const_iterator it =
+ m_.begin(); it != m_.end(); ++it) {
+ if (geometry::get < 0 > (it->first) >= geometry::get < 0 > (r.min())
+ && geometry::get < 0 > (it->first) <= geometry::get < 0 >
+ (r.max())
+ && geometry::get < 1 > (it->first) >= geometry::get < 1 >
+ (r.min())
+ && geometry::get < 1 > (it->first) <= geometry::get < 1 >
+ (r.max())) {
+ result.push_back(it->second);
+ }
+ }
+
+ if (ne_ != boost::shared_ptr < quadtree_node > ()) {
+ ne_->find(result, r);
+ }
+ if (se_ != boost::shared_ptr < quadtree_node > ()) {
+ se_->find(result, r);
+ }
+ if (nw_ != boost::shared_ptr < quadtree_node > ()) {
+ nw_->find(result, r);
+ }
+ if (sw_ != boost::shared_ptr < quadtree_node > ()) {
+ sw_->find(result, r);
+ }
+ }
+ }
+
+
+ Value find(const Point & k)
+ {
+ typename std::map < Point, Value >::const_iterator it = m_.find(k);
+ if (it != m_.end()) {
+ return it->second;
+ }
+ return recursive_search(k);
+ }
+
+
+ Value recursive_search(const Point & k)
+ {
+ // IMP: maybe this could be done only one time at node creation
+ // but it will consume more memory...
+
+ geometry::box < Point > ne_box, sw_box, se_box, nw_box;
+ divide_quadrants(ne_box, sw_box, se_box, nw_box);
+
+ if (geometry::within(k, ne_box)) {
+ if (ne_ != boost::shared_ptr < quadtree_node > ()) {
+ return ne_->find(k);
+ } else {
+ return Value();
+ }
+ }
+ if (geometry::within(k, se_box)) {
+ if (se_ != boost::shared_ptr < quadtree_node > ()) {
+ return se_->find(k);
+ } else {
+ return Value();
+ }
+ }
+ if (geometry::within(k, nw_box)) {
+ if (nw_ != boost::shared_ptr < quadtree_node > ()) {
+ return nw_->find(k);
+ } else {
+ return Value();
+ }
+ }
+ if (geometry::within(k, sw_box)) {
+ if (sw_ != boost::shared_ptr < quadtree_node > ()) {
+ return sw_->find(k);
+ } else {
+ return Value();
+ }
+ }
+ // never reached
+ return Value();
+ }
+
+
+ void remove(const Point & k)
+ {
+ typename std::map < Point, Value >::iterator it = m_.find(k);
+ if (it != m_.end()) {
+ m_.erase(it);
+ return;
+ }
+ recursive_remove(k);
+ }
+
+
+ void recursive_remove(const Point & k)
+ {
+ // IMP: maybe this could be done only one time at node creation
+ // but it will consume more memory...
+ geometry::box < Point > ne_box, sw_box, se_box, nw_box;
+ divide_quadrants(ne_box, sw_box, se_box, nw_box);
+
+
+ if (geometry::within(k, ne_box)) {
+ if (ne_ != boost::shared_ptr < quadtree_node > ()) {
+ ne_->remove(k);
+ if (ne_->empty_leaf()) {
+ ne_ = boost::shared_ptr < quadtree_node > ();
+ }
+ return;
+ } else {
+ throw std::logic_error("Not found");
+ }
+ }
+ if (geometry::within(k, se_box)) {
+ if (se_ != boost::shared_ptr < quadtree_node > ()) {
+ se_->remove(k);
+ if (se_->empty_leaf()) {
+ se_ = boost::shared_ptr < quadtree_node > ();
+ }
+ return;
+ } else {
+ throw std::logic_error("Not found");
+ }
+ }
+ if (geometry::within(k, nw_box)) {
+ if (nw_ != boost::shared_ptr < quadtree_node > ()) {
+ nw_->remove(k);
+ if (nw_->empty_leaf()) {
+ nw_ = boost::shared_ptr < quadtree_node > ();
+ }
+ return;
+ } else {
+ throw std::logic_error("Not found");
+ }
+ }
+ if (geometry::within(k, sw_box)) {
+ if (sw_ != boost::shared_ptr < quadtree_node > ()) {
+ sw_->remove(k);
+ if (sw_->empty_leaf()) {
+ sw_ = boost::shared_ptr < quadtree_node > ();
+ }
+ return;
+ } else {
+ throw std::logic_error("Not found");
+ }
+ }
+ }
+
+
+ void print(void) const
+ {
+ std::cerr << "--------------------------------------" << std::endl;
+ std::cerr << " [ ";
+ for(typename std::map < Point, Value >::const_iterator it = m_.begin();
+ it != m_.end(); ++it)
+ {
 // std::cerr << it->second << " ";
- }
- std::cerr << " ] " << std::endl;;
+ }
+ std::cerr << " ] " << std::endl;;
 
- if(sw_.get() != 0) {
- sw_->print();
- } else {
- std::cerr << "SW not defined" << std::endl;
- }
-
- if(nw_.get() != 0) {
- nw_->print();
- } else {
- std::cerr << "NW not defined" << std::endl;
- }
-
- if(se_.get() != 0) {
- se_->print();
- } else {
- std::cerr << "SE not defined" << std::endl;
- }
-
- if(ne_.get() != 0) {
- ne_->print();
- } else {
- std::cerr << "NE not defined" << std::endl;
- }
- std::cerr << "--------------------------------------" << std::endl;
- }
+ if (sw_.get() != 0) {
+ sw_->print();
+ } else {
+ std::cerr << "SW not defined" << std::endl;
+ }
+
+ if (nw_.get() != 0) {
+ nw_->print();
+ } else {
+ std::cerr << "NW not defined" << std::endl;
+ }
+
+ if (se_.get() != 0) {
+ se_->print();
+ } else {
+ std::cerr << "SE not defined" << std::endl;
+ }
+
+ if (ne_.get() != 0) {
+ ne_->print();
+ } else {
+ std::cerr << "NE not defined" << std::endl;
+ }
+ std::cerr << "--------------------------------------" << std::endl;
+ }
 
-};
+ };
 
 
-} // namespace spatial_index
-} // namespace boost
+ } // namespace spatial_index
+} // namespace boost
 
 #endif // BOOST_SPATIAL_INDEX_QUADTREE_NODE_HPP

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-07-23 13:32:04 EDT (Wed, 23 Jul 2008)
@@ -1,5 +1,5 @@
 //
-// Spatial Index - rTree
+// Spatial Index - rTree
 //
 //
 // Copyright 2008 Federico J. Fernandez.
@@ -19,573 +19,624 @@
 #include "rtree_node.hpp"
 #include "rtree_leaf.hpp"
 
-namespace boost {
-namespace spatial_index {
-
- template<typename Point, typename Value>
- class rtree
+namespace boost
+{
+ namespace spatial_index
   {
- public:
- rtree(const unsigned int &M, const unsigned int &m)
- : element_count_(0), m_(m), M_(M),
- root_(new rtree_node<Point, Value>(boost::shared_ptr< rtree_node<Point,Value> >(), 1))
- {
- }
-
- rtree(const geometry::box<Point> &b, const unsigned int &M, const unsigned int &m)
- : element_count_(0), m_(m), M_(M),
- root_(new rtree_node<Point, Value>(boost::shared_ptr< rtree_node<Point,Value> >(), 1))
- {
- }
-
-
- /// remove the element with key 'k'
- void remove(const Point &k)
- {
- /// it's the same than removing a box of only one point
- this->remove(geometry::box<Point>(k, k));
- }
-
-
- /// remove elements inside the box 'k'
- void remove(const geometry::box<Point> &k)
- {
- try {
- boost::shared_ptr<rtree_node<Point, Value> > l(choose_exact_leaf(k));
- typename rtree_leaf<Point,Value>::leaves_map q_leaves;
-
- l->remove(k);
-
- if(l->elements() < m_ && elements() > m_) {
- q_leaves = l->get_leaves();
-
- // we remove the leaf_node in the parent node because now it's empty
- l->get_parent()->remove(l->get_parent()->get_box(l));
- }
-
- typename rtree_node<Point,Value>::node_map q_nodes;
- condense_tree(l, q_nodes);
-
- std::vector<std::pair<geometry::box<Point>, Value> > s;
- for(typename rtree_node<Point,Value>::node_map::const_iterator it = q_nodes.begin(); it != q_nodes.end(); ++it) {
- typename rtree_leaf<Point,Value>::leaves_map leaves = it->second->get_leaves();
-
- // reinserting leaves from nodes
- for(typename rtree_leaf<Point,Value>::leaves_map::const_iterator itl = leaves.begin(); itl != leaves.end(); ++itl) {
- s.push_back(*itl);
- }
- }
-
- for(typename std::vector<std::pair<geometry::box<Point>, Value> >::const_iterator it = s.begin(); it != s.end(); ++it) {
- element_count_--;
- insert(it->first, it->second);
- }
-
- // if the root has only one child and the child is not a leaf, make it the root
- if(root_->elements() == 1) {
- if(!root_->first_element()->is_leaf()) {
- root_ = root_->first_element();
- }
- }
-
- // reinserting leaves
- for(typename rtree_leaf<Point,Value>::leaves_map::const_iterator it = q_leaves.begin(); it != q_leaves.end(); ++it) {
- element_count_--;
- insert(it->first, it->second);
- }
-
- element_count_--;
-
- } catch(std::logic_error &e) {
- // not found
- std::cerr << e.what() << std::endl;
- return;
- }
- }
-
-
- unsigned int elements(void) const { return element_count_; }
-
-
- void print(void)
- {
- std::cerr << "===================================" << std::endl;
- std::cerr << " Min/Max: " << m_ << " / " << M_ << std::endl;
- std::cerr << "Leaves: " << root_->get_leaves().size() << std::endl;
- root_->print();
- std::cerr << "===================================" << std::endl;
- }
-
- void insert(const Point &k, const Value &v)
- {
- // it's the same than inserting a box of only one point
- this->insert(geometry::box<Point>(k,k), v);
- }
-
-
- void insert(const geometry::box<Point> &e, const Value &v)
- {
- element_count_++;
-
- boost::shared_ptr<rtree_node<Point, Value> > l(choose_corresponding_leaf(e));
-
- // check if the selected leaf is full to do the split if necessary
- if(l->elements() >= M_) {
- l->insert(e, v);
-
- // split!
- boost::shared_ptr< rtree_node<Point, Value> > n1(new rtree_leaf<Point,Value>(l->get_parent()));
- boost::shared_ptr< rtree_node<Point, Value> > n2(new rtree_leaf<Point,Value>(l->get_parent()));
-
- split_node(l, n1, n2);
- adjust_tree(l, n1, n2);
- } else {
- l->insert(e, v);
- adjust_tree(l);
- }
- }
-
-
- void bulk_insert(std::vector<Value> &values, std::vector<Point> &points)
- {
- typename std::vector<Point>::iterator it_point;
- typename std::vector<Value>::iterator it_value;
-
- // unsigned int count = 0;
-
- it_point = points.begin();
- it_value = values.begin();
- while(it_value != values.end() && it_point != points.end()) {
- geometry::box<geometry::point_xy<double> > box(*it_point, *it_point);
- insert(box, *it_value);
-
- it_point++;
- it_value++;
- // count++;
-
- // if(count % 1000 == 0) {
- // std::cerr << "Count: " << count << std::endl;
- // print();
- // }
- }
- }
-
- Value find(const Point &k)
- {
- std::deque<Value> result;
- geometry::box<geometry::point_xy<double> > query_box(k, k);
-
- root_->find(query_box, result, true);
- if(result.size() >= 1) {
- return result[0];
- }
- return Value();
- }
 
-
- std::deque<Value> find(const geometry::box<Point> &r)
- {
- std::deque<Value> result;
- root_->find(r, result, false);
- return result;
- }
-
-
-
- private:
- /// number of elements
- unsigned int element_count_;
-
- /// minimum number of elements per node
- unsigned int m_;
-
- /// maximum number of elements per node
- unsigned int M_;
-
- /// tree root
- boost::shared_ptr< rtree_node<Point,Value> > root_;
-
-
- private:
-
- void condense_tree(const boost::shared_ptr<rtree_node<Point,Value> > &l,
- typename rtree_node<Point,Value>::node_map &q_nodes)
+ template < typename Point, typename Value > class rtree
     {
- if(l.get() == root_.get()) {
- // if it's the root we are done
- return;
- }
-
- boost::shared_ptr<rtree_node<Point,Value> > parent = l->get_parent();
- parent->adjust_box(l);
-
- if(parent->elements() < m_) {
- if(parent.get() == root_.get()) {
- // if the parent is underfull and it's the root we just exit
- return;
- }
-
- // get the nodes that we should reinsert
- typename rtree_node<Point,Value>::node_map this_nodes = parent->get_nodes();
- for(typename rtree_node<Point,Value>::node_map::const_iterator it = this_nodes.begin(); it != this_nodes.end(); ++it) {
- q_nodes.push_back(*it);
- }
-
- // we remove the node in the parent node because now it should be re inserted
- parent->get_parent()->remove(parent->get_parent()->get_box(parent));
- }
-
- condense_tree(parent, q_nodes);
- }
-
-
- void adjust_tree(boost::shared_ptr<rtree_node<Point, Value> > &n)
- {
- if(n.get() == root_.get()) {
- // 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)
- {
- // check if we are in the root and do the split
- if(l.get() == root_.get()) {
- 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));
- new_root->add_node(n1->compute_box(), n1);
- new_root->add_node(n2->compute_box(), n2);
-
- n1->set_parent(new_root);
- n2->set_parent(new_root);
-
- n1->update_parent(n1);
- n2->update_parent(n2);
-
- root_ = new_root;
- return;
- }
- boost::shared_ptr<rtree_node<Point,Value> > parent = l->get_parent();
-
- parent->replace_node(l, n1);
- parent->add_node(n2->compute_box(), n2);
-
- // if parent is full, split and readjust
- if(parent->elements() > M_) {
-
- boost::shared_ptr< rtree_node<Point, Value> > p1(new
- rtree_node<Point,Value>(parent->get_parent(),
- parent->get_level()));
- boost::shared_ptr< rtree_node<Point, Value> > p2(new
- rtree_node<Point,Value>(parent->get_parent(),
- parent->get_level()));
-
- split_node(parent, p1, p2);
- adjust_tree(parent, p1, p2);
- } else {
- 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
- {
- unsigned int seed1, seed2;
- std::vector< geometry::box<Point> > boxes = n->get_boxes();
-
- n1->set_parent(n->get_parent());
- n2->set_parent(n->get_parent());
-
- linear_pick_seeds(n, seed1, seed2);
-
- if(n->is_leaf()) {
- n1->add_value(boxes[seed1], n->get_value(seed1));
- n2->add_value(boxes[seed2], n->get_value(seed2));
- } else {
- n1->add_node(boxes[seed1], n->get_node(seed1));
- n2->add_node(boxes[seed2], n->get_node(seed2));
- }
-
- unsigned int index = 0;
-
- if(n->is_leaf()) {
- typename rtree_leaf<Point,Value>::leaves_map nodes = n->get_leaves();
- unsigned int remaining = nodes.size()-2;
- for(typename rtree_leaf<Point,Value>::leaves_map::const_iterator it = nodes.begin(); it != nodes.end(); ++it, index++) {
-
- if(index != seed1 && index != seed2) {
- if(n1->elements() + remaining == m_) {
- n1->add_value(it->first, it->second);
- continue;
- }
- if(n2->elements() + remaining == m_) {
- n2->add_value(it->first, it->second);
- continue;
- }
-
- remaining--;
-
- /// 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_value(it->first, it->second);
- }
- if(eb1_area - b1_area < eb2_area - b2_area) {
- n1->add_value(it->first, it->second);
- }
- if(eb1_area - b1_area == eb2_area - b2_area) {
- if(b1_area < b2_area) {
- n1->add_value(it->first, it->second);
- }
- if(b1_area > b2_area) {
- n2->add_value(it->first, it->second);
- }
- if(b1_area == b2_area) {
- if(n1->elements() > n2->elements()) {
- n2->add_value(it->first, it->second);
- } else {
- n1->add_value(it->first, it->second);
- }
- }
- }
- }
- }
- } else {
- typename rtree_node<Point,Value>::node_map nodes = n->get_nodes();
- unsigned int remaining = nodes.size()-2;
- for(typename rtree_node<Point,Value>::node_map::const_iterator it = nodes.begin(); it != nodes.end(); ++it, index++) {
-
- if(index != seed1 && index != seed2) {
-
- if(n1->elements() + remaining == m_) {
- n1->add_node(it->first, it->second);
- continue;
- }
- if(n2->elements() + remaining == m_) {
- n2->add_node(it->first, it->second);
- continue;
- }
-
- remaining--;
-
- /// 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);
- }
- }
- }
-
- }
- }
- }
- }
-
-
- void linear_pick_seeds(const boost::shared_ptr< rtree_node<Point,Value> > &n,
- unsigned int &seed1,
- unsigned int &seed2) const
- {
- // get boxes from the node
- std::vector< geometry::box<Point> > boxes = n->get_boxes();
- if(boxes.size() == 0) {
- throw std::logic_error("Empty Node trying to Pick Seeds");
- }
-
- // only two dim for now
- // unsigned int dimensions = geometry::point_traits<Point>::coordinate_count;
-
- // find the first two elements
- double separation_x, separation_y;
- unsigned int first_x, second_x;
- unsigned int first_y, second_y;
- find_normalized_separations<0u>(boxes, separation_x, first_x, second_x);
- find_normalized_separations<1u>(boxes, separation_y, first_y, second_y);
-
- if(separation_x > separation_y) {
- seed1 = first_x;
- seed2 = second_x;
- } else {
- seed1 = first_y;
- seed2 = second_y;
- }
- }
-
-
- template<unsigned int Dimension>
- void find_normalized_separations(const std::vector< geometry::box<Point> > &boxes,
- double &separation,
- unsigned int &first, unsigned int &second) const
- {
- if(boxes.size() < 2) {
- throw std::logic_error("At least two boxes needed to split");
- }
-
- // find the lowest high
- typename std::vector< geometry::box<Point> >::const_iterator it = boxes.begin();
- double lowest_high = geometry::get<Dimension>(it->max());
- unsigned int lowest_high_index = 0;
- unsigned int index;
- ++it;
- index = 1;
- for(; it != boxes.end(); ++it) {
- if(geometry::get<Dimension>(it->max()) < lowest_high) {
- lowest_high = geometry::get<Dimension>(it->max());
- lowest_high_index = index;
- }
- index++;
- }
-
- // find the highest low
- double highest_low;
- unsigned int highest_low_index;
- if(lowest_high_index == 0) {
- highest_low = geometry::get<Dimension>(boxes[1].min());
- highest_low_index = 1;
- } else {
- highest_low = geometry::get<Dimension>(boxes[0].min());
- highest_low_index = 0;
- }
- index = 0;
- for(typename std::vector< geometry::box<Point> >::const_iterator it = boxes.begin(); it != boxes.end(); ++it, index++) {
- if(geometry::get<Dimension>(it->min()) >= highest_low && index != lowest_high_index) {
- highest_low = geometry::get<Dimension>(it->min());
- highest_low_index = index;
- }
- }
-
- // find the lowest low
- it = boxes.begin();
- double lowest_low = geometry::get<Dimension>(it->min());
- ++it;
- for(; it != boxes.end(); ++it) {
- if(geometry::get<Dimension>(it->min()) < lowest_low) {
- lowest_low = geometry::get<Dimension>(it->min());
- }
- }
-
- // find the highest high
- it = boxes.begin();
- double highest_high = geometry::get<Dimension>(it->max());
- ++it;
- for(; it != boxes.end(); ++it) {
- if(geometry::get<Dimension>(it->max()) > highest_high) {
- highest_high = geometry::get<Dimension>(it->max());
- }
- }
-
- double width = highest_high - lowest_low;
-
- separation = (highest_low - lowest_high) / width;
- first = highest_low_index;
- second = lowest_high_index;
- }
-
-
- boost::shared_ptr<rtree_node<Point, Value> > choose_corresponding_leaf(const geometry::box<Point> e)
- {
- boost::shared_ptr< rtree_node<Point, Value> > N = root_;
-
- // if the tree is empty add an initial leaf
- if(root_->elements() == 0) {
- boost::shared_ptr< rtree_leaf<Point, Value> > new_leaf(new rtree_leaf<Point, Value>(root_));
- root_->add_leaf_node(geometry::box<Point>(), new_leaf);
-
- return new_leaf;
- }
-
- while(!N->is_leaf()) {
- /// traverse N's map to see which node we should select
- N = N->choose_node(e);
- }
- return N;
- }
-
-
- boost::shared_ptr<rtree_node<Point, Value> > choose_exact_leaf(const geometry::box<Point> &e) const
- {
- // find possible leaves
- typename std::vector<boost::shared_ptr<rtree_node<Point,Value> > > nodes;
- root_->find_leaves(e, nodes);
-
- // refine the result
- for(typename std::vector<boost::shared_ptr<rtree_node<Point,Value> > >::const_iterator it = nodes.begin();
- it != nodes.end(); ++it) {
-
- typename std::vector< std::pair< geometry::box<Point>, Value > > leaves = (*it)->get_leaves();
- for(typename std::vector< std::pair< geometry::box<Point>, Value > >::const_iterator itl = leaves.begin();
- itl != leaves.end(); ++itl) {
-
- if(itl->first.max() == e.max() && itl->first.min() == e.min()) {
- return *it;
- }
-
- }
-
+ public:
+ rtree(const unsigned int &M, const unsigned int &m)
+ : element_count_(0), m_(m), M_(M),
+ root_(new rtree_node < Point,
+ Value > (boost::shared_ptr < rtree_node < Point, Value > >(), 1))
+ {
+ }
+
+ rtree(const geometry::box < Point > &b, const unsigned int &M,
+ const unsigned int &m)
+ : element_count_(0), m_(m), M_(M), root_(
+ new rtree_node < Point, Value > (boost::shared_ptr <
+ rtree_node < Point,
+ Value > >(), 1))
+ {
+ }
+
+
+ /// remove the element with key 'k'
+ void remove(const Point & k)
+ {
+ /// it's the same than removing a box of only one point
+ this->remove(geometry::box < Point > (k, k));
+ }
+
+
+ /// remove elements inside the box 'k'
+ void remove(const geometry::box < Point > &k)
+ {
+ try {
+ boost::shared_ptr < rtree_node < Point,
+ Value > >l(choose_exact_leaf(k));
+ typename rtree_leaf < Point, Value >::leaves_map q_leaves;
+
+ l->remove(k);
+
+ if (l->elements() < m_ && elements() > m_) {
+ q_leaves = l->get_leaves();
+
+ // we remove the leaf_node in the parent node because now it's empty
+ l->get_parent()->remove(l->get_parent()->get_box(l));
+ }
+
+ typename rtree_node < Point, Value >::node_map q_nodes;
+ condense_tree(l, q_nodes);
+
+ std::vector < std::pair < geometry::box < Point >, Value > >s;
+ for(typename rtree_node < Point,
+ Value >::node_map::const_iterator it = q_nodes.begin();
+ it != q_nodes.end(); ++it) {
+ typename rtree_leaf < Point, Value >::leaves_map leaves =
+ it->second->get_leaves();
+
+ // reinserting leaves from nodes
+ for(typename rtree_leaf < Point,
+ Value >::leaves_map::const_iterator itl = leaves.begin();
+ itl != leaves.end(); ++itl) {
+ s.push_back(*itl);
+ }
+ }
+
+ for(typename std::vector < std::pair < geometry::box < Point >,
+ Value > >::const_iterator it = s.begin(); it != s.end(); ++it) {
+ element_count_--;
+ insert(it->first, it->second);
+ }
+
+ // if the root has only one child and the child is not a leaf, make it the root
+ if (root_->elements() == 1) {
+ if (!root_->first_element()->is_leaf()) {
+ root_ = root_->first_element();
+ }
+ }
+ // reinserting leaves
+ for(typename rtree_leaf < Point,
+ Value >::leaves_map::const_iterator it = q_leaves.begin();
+ it != q_leaves.end(); ++it) {
+ element_count_--;
+ insert(it->first, it->second);
+ }
+
+ element_count_--;
+
+ }
+ catch(std::logic_error & e) {
+ // not found
+ std::cerr << e.what() << std::endl;
+ return;
+ }
+ }
+
+
+ unsigned int elements(void) const
+ {
+ return element_count_;
+ }
+
+
+ void print(void)
+ {
+ std::cerr << "===================================" << std::endl;
+ std::cerr << " Min/Max: " << m_ << " / " << M_ << std::endl;
+ std::cerr << "Leaves: " << root_->get_leaves().size() << std::endl;
+ root_->print();
+ std::cerr << "===================================" << std::endl;
+ }
+
+ void insert(const Point & k, const Value & v)
+ {
+ // it's the same than inserting a box of only one point
+ this->insert(geometry::box < Point > (k, k), v);
+ }
+
+
+ void insert(const geometry::box < Point > &e, const Value & v)
+ {
+ element_count_++;
+
+ boost::shared_ptr < rtree_node < Point,
+ Value > >l(choose_corresponding_leaf(e));
+
+ // check if the selected leaf is full to do the split if necessary
+ if (l->elements() >= M_) {
+ l->insert(e, v);
+
+ // split!
+ boost::shared_ptr < rtree_node < Point,
+ Value > >n1(new rtree_leaf < Point, Value > (l->get_parent()));
+ boost::shared_ptr < rtree_node < Point,
+ Value > >n2(new rtree_leaf < Point, Value > (l->get_parent()));
+
+ split_node(l, n1, n2);
+ adjust_tree(l, n1, n2);
+ } else {
+ l->insert(e, v);
+ adjust_tree(l);
+ }
+ }
+
+
+ void bulk_insert(std::vector < Value > &values,
+ std::vector < Point > &points)
+ {
+ typename std::vector < Point >::iterator it_point;
+ typename std::vector < Value >::iterator it_value;
+
+ // unsigned int count = 0;
+
+ it_point = points.begin();
+ it_value = values.begin();
+ while (it_value != values.end() && it_point != points.end()) {
+ geometry::box < geometry::point_xy < double > > box(*it_point,
+ *it_point);
+ insert(box, *it_value);
+
+ it_point++;
+ it_value++;
+ // count++;
+
+ // if(count % 1000 == 0) {
+ // std::cerr << "Count: " << count << std::endl;
+ // print();
+ // }
+ }
+ }
+
+ Value find(const Point & k)
+ {
+ std::deque < Value > result;
+ geometry::box < geometry::point_xy < double > > query_box(k, k);
+
+ root_->find(query_box, result, true);
+ if (result.size() >= 1) {
+ return result[0];
+ }
+ return Value();
+ }
+
+
+ std::deque < Value > find(const geometry::box < Point > &r) {
+ std::deque < Value > result;
+ root_->find(r, result, false);
+ return result;
+ }
+
+
+
+ private:
+ /// number of elements
+ unsigned int element_count_;
+
+ /// minimum number of elements per node
+ unsigned int m_;
+
+ /// maximum number of elements per node
+ unsigned int M_;
+
+ /// tree root
+ boost::shared_ptr < rtree_node < Point, Value > >root_;
+
+
+ private:
+
+ void condense_tree(const boost::shared_ptr < rtree_node < Point,
+ Value > >&l, typename rtree_node < Point,
+ Value >::node_map & q_nodes)
+ {
+ if (l.get() == root_.get()) {
+ // if it's the root we are done
+ return;
+ }
+
+ boost::shared_ptr < rtree_node < Point, Value > >parent =
+ l->get_parent();
+ parent->adjust_box(l);
+
+ if (parent->elements() < m_) {
+ if (parent.get() == root_.get()) {
+ // if the parent is underfull and it's the root we just exit
+ return;
+ }
+ // get the nodes that we should reinsert
+ typename rtree_node < Point, Value >::node_map this_nodes =
+ parent->get_nodes();
+ for(typename rtree_node < Point,
+ Value >::node_map::const_iterator it = this_nodes.begin();
+ it != this_nodes.end(); ++it) {
+ q_nodes.push_back(*it);
+ }
+
+ // we remove the node in the parent node because now it should be
+ // re inserted
+ parent->get_parent()->remove(parent->get_parent()->get_box(parent));
+ }
+
+ condense_tree(parent, q_nodes);
+ }
+
+
+ void adjust_tree(boost::shared_ptr < rtree_node < Point, Value > >&n)
+ {
+ if (n.get() == root_.get()) {
+ // 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)
+ {
+ // check if we are in the root and do the split
+ if (l.get() == root_.get()) {
+ 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));
+ new_root->add_node(n1->compute_box(), n1);
+ new_root->add_node(n2->compute_box(), n2);
+
+ n1->set_parent(new_root);
+ n2->set_parent(new_root);
+
+ n1->update_parent(n1);
+ n2->update_parent(n2);
+
+ root_ = new_root;
+ return;
+ }
+ boost::shared_ptr < rtree_node < Point, Value > >parent =
+ l->get_parent();
+
+ parent->replace_node(l, n1);
+ parent->add_node(n2->compute_box(), n2);
+
+ // if parent is full, split and readjust
+ if (parent->elements() > M_) {
+
+ boost::shared_ptr < rtree_node < Point, Value > >p1(new
+ rtree_node <Point, Value >
+ (parent->get_parent(), parent->get_level()));
+ boost::shared_ptr < rtree_node < Point,
+ Value > >p2(new rtree_node < Point,
+ Value > (parent->get_parent(), parent->get_level()));
+
+ split_node(parent, p1, p2);
+ adjust_tree(parent, p1, p2);
+ } else {
+ 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
+ {
+ unsigned int seed1, seed2;
+ std::vector < geometry::box < Point > >boxes = n->get_boxes();
+
+ n1->set_parent(n->get_parent());
+ n2->set_parent(n->get_parent());
+
+ linear_pick_seeds(n, seed1, seed2);
+
+ if (n->is_leaf())
+ {
+ n1->add_value(boxes[seed1], n->get_value(seed1));
+ n2->add_value(boxes[seed2], n->get_value(seed2));
+ } else
+ {
+ n1->add_node(boxes[seed1], n->get_node(seed1));
+ n2->add_node(boxes[seed2], n->get_node(seed2));
+ }
+
+ unsigned int index = 0;
+
+ if (n->is_leaf()) {
+ typename rtree_leaf < Point, Value >::leaves_map nodes =
+ n->get_leaves();
+ unsigned int remaining = nodes.size() - 2;
+ for(typename rtree_leaf < Point,
+ Value >::leaves_map::const_iterator it = nodes.begin();
+ it != nodes.end(); ++it, index++) {
+
+ if (index != seed1 && index != seed2) {
+ if (n1->elements() + remaining == m_) {
+ n1->add_value(it->first, it->second);
+ continue;
+ }
+ if (n2->elements() + remaining == m_) {
+ n2->add_value(it->first, it->second);
+ continue;
+ }
+
+ remaining--;
+
+ /// 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_value(it->first, it->second);
+ }
+ if (eb1_area - b1_area < eb2_area - b2_area) {
+ n1->add_value(it->first, it->second);
+ }
+ if (eb1_area - b1_area == eb2_area - b2_area) {
+ if (b1_area < b2_area) {
+ n1->add_value(it->first, it->second);
+ }
+ if (b1_area > b2_area) {
+ n2->add_value(it->first, it->second);
+ }
+ if (b1_area == b2_area) {
+ if (n1->elements() > n2->elements()) {
+ n2->add_value(it->first, it->second);
+ } else {
+ n1->add_value(it->first, it->second);
+ }
+ }
+ }
+ }
+ }
+ } else {
+ typename rtree_node < Point, Value >::node_map nodes = n->get_nodes();
+ unsigned int remaining = nodes.size() - 2;
+ for(typename rtree_node < Point,
+ Value >::node_map::const_iterator it = nodes.begin();
+ it != nodes.end(); ++it, index++) {
+
+ if (index != seed1 && index != seed2) {
+
+ if (n1->elements() + remaining == m_) {
+ n1->add_node(it->first, it->second);
+ continue;
+ }
+ if (n2->elements() + remaining == m_) {
+ n2->add_node(it->first, it->second);
+ continue;
+ }
+
+ remaining--;
+
+ /// 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);
+ }
+ }
+ }
+
+ }
+ }
+ }
+ }
+
+
+ void linear_pick_seeds(const boost::shared_ptr < rtree_node < Point,
+ Value > >&n, unsigned int &seed1,
+ unsigned int &seed2) const
+ {
+ // get boxes from the node
+ std::vector < geometry::box < Point > >boxes = n->get_boxes();
+ if (boxes.size() == 0) {
+ throw std::logic_error("Empty Node trying to Pick Seeds");
+ }
+ // only two dim for now
+ // unsigned int dimensions = geometry::point_traits<Point>::coordinate_count;
+
+ // find the first two elements
+ double separation_x, separation_y;
+ unsigned int first_x, second_x;
+ unsigned int first_y, second_y;
+ find_normalized_separations < 0u > (boxes, separation_x, first_x,
+ second_x);
+ find_normalized_separations < 1u > (boxes, separation_y, first_y,
+ second_y);
+
+ if (separation_x > separation_y) {
+ seed1 = first_x;
+ seed2 = second_x;
+ } else {
+ seed1 = first_y;
+ seed2 = second_y;
+ }
+ }
+
+
+ template < unsigned int Dimension >
+ void find_normalized_separations(const std::vector < geometry::box <
+ Point > >&boxes, double &separation,
+ unsigned int &first,
+ unsigned int &second) const
+ {
+ if (boxes.size() < 2)
+ {
+ throw std::logic_error("At least two boxes needed to split");
+ }
+ // find the lowest high
+ typename std::vector < geometry::box < Point > >::const_iterator it =
+ boxes.begin();
+ double lowest_high = geometry::get < Dimension > (it->max());
+ unsigned int lowest_high_index = 0;
+ unsigned int index;
+ ++it;
+ index = 1;
+ for(; it != boxes.end(); ++it) {
+ if (geometry::get < Dimension > (it->max()) < lowest_high) {
+ lowest_high = geometry::get < Dimension > (it->max());
+ lowest_high_index = index;
+ }
+ index++;
+ }
+
+ // find the highest low
+ double highest_low;
+ unsigned int highest_low_index;
+ if (lowest_high_index == 0) {
+ highest_low = geometry::get < Dimension > (boxes[1].min());
+ highest_low_index = 1;
+ } else {
+ highest_low = geometry::get < Dimension > (boxes[0].min());
+ highest_low_index = 0;
+ }
+ index = 0;
+ for(typename std::vector < geometry::box < Point >
+ >::const_iterator it = boxes.begin(); it != boxes.end();
+ ++it, index++) {
+ if (geometry::get < Dimension > (it->min()) >= highest_low
+ && index != lowest_high_index) {
+ highest_low = geometry::get < Dimension > (it->min());
+ highest_low_index = index;
+ }
+ }
+
+ // find the lowest low
+ it = boxes.begin();
+ double lowest_low = geometry::get < Dimension > (it->min());
+ ++it;
+ for(; it != boxes.end(); ++it) {
+ if (geometry::get < Dimension > (it->min()) < lowest_low) {
+ lowest_low = geometry::get < Dimension > (it->min());
+ }
+ }
+
+ // find the highest high
+ it = boxes.begin();
+ double highest_high = geometry::get < Dimension > (it->max());
+ ++it;
+ for(; it != boxes.end(); ++it) {
+ if (geometry::get < Dimension > (it->max()) > highest_high) {
+ highest_high = geometry::get < Dimension > (it->max());
+ }
+ }
+
+ double width = highest_high - lowest_low;
+
+ separation = (highest_low - lowest_high) / width;
+ first = highest_low_index;
+ second = lowest_high_index;
+ }
+
+
+ boost::shared_ptr < rtree_node < Point,
+ Value > >choose_corresponding_leaf(const geometry::box < Point > e)
+ {
+ boost::shared_ptr < rtree_node < Point, Value > >N = root_;
+
+ // if the tree is empty add an initial leaf
+ if (root_->elements() == 0) {
+ boost::shared_ptr < rtree_leaf < Point,
+ Value > >new_leaf(new rtree_leaf < Point, Value > (root_));
+ root_->add_leaf_node(geometry::box < Point > (), new_leaf);
+
+ return new_leaf;
+ }
+
+ while (!N->is_leaf()) {
+ /// traverse N's map to see which node we should select
+ N = N->choose_node(e);
+ }
+ return N;
+ }
+
+
+ boost::shared_ptr < rtree_node < Point,
+ Value > >choose_exact_leaf(const geometry::box < Point > &e) const
+ {
+ // find possible leaves
+ typename std::vector < boost::shared_ptr < rtree_node < Point,
+ Value > > > nodes;
+ root_->find_leaves(e, nodes);
+
+ // refine the result
+ for(typename std::vector < boost::shared_ptr < rtree_node < Point,
+ Value > > >::const_iterator it = nodes.begin(); it != nodes.end();
+ ++it)
+ {
+
+ typename std::vector < std::pair < geometry::box < Point >,
+ Value > >leaves = (*it)->get_leaves();
+ for(typename std::vector < std::pair < geometry::box < Point >,
+ Value > >::const_iterator itl = leaves.begin();
+ itl != leaves.end(); ++itl)
+ {
+
+ if (itl->first.max() == e.max() && itl->first.min() == e.min()) {
+ return *it;
+ }
+
+ }
+
+ }
+ throw std::logic_error("Leaf not found");
       }
- throw std::logic_error("Leaf not found");
- }
 
- };
+ };
 
 
-} // namespace spatial_index
-} // namespace boost
+ } // namespace spatial_index
+} // namespace boost
 
 #endif // BOOST_SPATIAL_INDEX_RTREE_HPP

Modified: sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_leaf.hpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_leaf.hpp (original)
+++ sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_leaf.hpp 2008-07-23 13:32:04 EDT (Wed, 23 Jul 2008)
@@ -1,5 +1,5 @@
 //
-// Spatial Index - rTree Leaf
+// Spatial Index - rTree Leaf
 //
 //
 // Copyright 2008 Federico J. Fernandez.
@@ -14,133 +14,164 @@
 
 #include <geometry/area.hpp>
 
-namespace boost {
-namespace spatial_index {
-
- template<typename Point, typename Value>
- class rtree_leaf : public rtree_node<Point, Value>
+namespace boost
+{
+ namespace spatial_index
   {
- public:
- typedef std::vector< std::pair< geometry::box<Point>, Value > > leaves_map;
-
- public:
- rtree_leaf(void) {}
- rtree_leaf(const boost::shared_ptr< rtree_node<Point,Value> > &parent)
- : rtree_node<Point,Value>(parent, 0) {}
 
- /// query method
- virtual void find(const geometry::box<Point> &e, std::deque<Value> &r, const bool exact_match)
+ template < typename Point, typename Value >
+ class rtree_leaf:public rtree_node < Point, Value >
     {
- for(typename leaves_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
- if(exact_match) {
- if(it->first.max() == e.max() && it->first.min() == e.min()) {
- r.push_back(it->second);
- }
- } else {
- if(overlaps(it->first, e)) {
- r.push_back(it->second);
- }
- }
+ public:
+ typedef std::vector < std::pair < geometry::box < Point >,
+ Value > >leaves_map;
+
+ public:
+ rtree_leaf(void)
+ {
+ }
+
+ rtree_leaf(const boost::shared_ptr < rtree_node < Point, Value > >&parent)
+ : rtree_node < Point, Value > (parent, 0)
+ {
       }
- }
 
- /// compute bounding box for this leaf
- virtual geometry::box<Point> compute_box(void) const
- {
- if(nodes_.empty()) {
- return geometry::box<Point>();
+ /// query method
+ virtual void find(const geometry::box < Point > &e,
+ std::deque < Value > &r, const bool exact_match)
+ {
+ for(typename leaves_map::const_iterator it = nodes_.begin();
+ it != nodes_.end(); ++it) {
+ if (exact_match) {
+ if (it->first.max() == e.max() && it->first.min() == e.min()) {
+ r.push_back(it->second);
+ }
+ } else {
+ if (overlaps(it->first, e)) {
+ r.push_back(it->second);
+ }
+ }
+ }
       }
-
- typename leaves_map::const_iterator it = nodes_.begin();
- geometry::box<Point> r = it->first;
- it++;
- for(; it != nodes_.end(); ++it) {
- r = enlarge_box(r, it->first);
+
+ /// compute bounding box for this leaf
+ virtual geometry::box < Point > compute_box(void) const
+ {
+ if (nodes_.empty())
+ {
+ return geometry::box < Point > ();
+ }
+
+ typename leaves_map::const_iterator it = nodes_.begin();
+ geometry::box < Point > r = it->first;
+ it++;
+ for(; it != nodes_.end(); ++it) {
+ r = enlarge_box(r, it->first);
+ }
+ return r;
       }
- return r;
- }
 
- /// yes, we are a leaf
- virtual bool is_leaf(void) const { return true; }
+ /// yes, we are a leaf
+ virtual bool is_leaf(void) const
+ {
+ return true;
+ }
 
- /// element count
- virtual unsigned int elements(void) const
- {
- return nodes_.size();
- }
+ /// element count
+ virtual unsigned int elements(void) const
+ {
+ return nodes_.size();
+ }
 
- virtual void insert(const geometry::box<Point> &e, const Value &v)
- {
- nodes_.push_back(std::make_pair(e, v));
- }
+ virtual void insert(const geometry::box < Point > &e, const Value & v)
+ {
+ nodes_.push_back(std::make_pair(e, v));
+ }
 
- virtual std::vector< std::pair< geometry::box<Point>, Value > > get_leaves(void) const
- {
- return nodes_;
- }
+ virtual std::vector < std::pair < geometry::box < Point >,
+ Value > >get_leaves(void) const
+ {
+ return nodes_;
+ }
 
- 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_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 add_value(const geometry::box < Point > &b, const Value & v)
+ {
+ nodes_.push_back(std::make_pair(b, v));
+ }
 
- virtual Value get_value(const unsigned int i) const { return nodes_[i].second; }
+ virtual Value get_value(const unsigned int i) const
+ {
+ return nodes_[i].second;
+ }
 
- /// box projector for leaf
- virtual geometry::box<Point> get_box(const unsigned int i) const { return nodes_[i].first; }
+ /// box projector for leaf
+ virtual geometry::box < Point > get_box(const unsigned int i) const
+ {
+ return nodes_[i].first;
+ }
 
 
- /// remove value with key 'k' in this leaf
- virtual void remove(const geometry::box<Point> &k)
- {
+ /// remove value with key 'k' in this leaf
+ virtual void remove(const geometry::box < Point > &k)
+ {
 
- for(typename leaves_map::iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
- if(it->first.min() == k.min() && it->first.max() == k.max()) {
- nodes_.erase(it);
- return;
- }
+ for(typename leaves_map::iterator it = nodes_.begin();
+ it != nodes_.end(); ++it) {
+ if (it->first.min() == k.min() && it->first.max() == k.max()) {
+ nodes_.erase(it);
+ return;
+ }
+ }
+ throw std::logic_error("Node not found.");
       }
- throw std::logic_error("Node not found.");
- }
 
 
- virtual std::vector< geometry::box<Point> > get_boxes(void) const
- {
- std::vector< geometry::box<Point> > r;
- for(typename leaves_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
- r.push_back(it->first);
+ virtual std::vector < geometry::box < Point > >get_boxes(void) const
+ {
+ std::vector < geometry::box < Point > >r;
+ for(typename leaves_map::const_iterator it = nodes_.begin();
+ it != nodes_.end(); ++it) {
+ r.push_back(it->first);
+ }
+ return r;
       }
- return r;
- }
 
- virtual void print(void) const
- {
- std::cerr << "\t" << " --> Leaf --------" << std::endl;
- std::cerr << "\t" << " Size: " << nodes_.size() << std::endl;
- for(typename leaves_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
+ virtual void print(void) const
+ {
+ std::cerr << "\t" << " --> Leaf --------" << std::endl;
+ std::cerr << "\t" << " Size: " << nodes_.size() << std::endl;
+ for(typename leaves_map::const_iterator it = nodes_.begin();
+ it != nodes_.end(); ++it)
+ {
 
- std::cerr << "\t" << " | ";
- std::cerr << "( " << geometry::get<0>(it->first.min()) << " , " << geometry::get<1>(it->first.min()) << " ) x " ;
- std::cerr << "( " << geometry::get<0>(it->first.max()) << " , " << geometry::get<1>(it->first.max()) << " )" ;
- std::cerr << " -> ";
- std::cerr << it->second;
- std::cerr << " | " << std::endl;;
+ std::cerr << "\t" << " | ";
+ std::cerr << "( " << geometry::get < 0 >
+ (it->first.min()) << " , " << geometry::get < 1 >
+ (it->first.min()) << " ) x ";
+ std::cerr << "( " << geometry::get < 0 >
+ (it->first.max()) << " , " << geometry::get < 1 >
+ (it->first.max()) << " )";
+ std::cerr << " -> ";
+ std::cerr << it->second;
+ std::cerr << " | " << std::endl;;
+ }
+ std::cerr << "\t" << " --< Leaf --------" << std::endl;
       }
- std::cerr << "\t" << " --< Leaf --------" << std::endl;
- }
 
- private:
- leaves_map nodes_;
- };
+ private:
+ leaves_map nodes_;
+ };
 
 
 
-} // namespace spatial_index
-} // namespace boost
+ } // namespace spatial_index
+} // namespace boost
 
 #endif // BOOST_SPATIAL_INDEX_RTREE_LEAF_HPP

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-07-23 13:32:04 EDT (Wed, 23 Jul 2008)
@@ -1,5 +1,5 @@
 //
-// Spatial Index - rTree Node
+// Spatial Index - rTree Node
 //
 //
 // Copyright 2008 Federico J. Fernandez.
@@ -14,318 +14,384 @@
 
 #include <geometry/area.hpp>
 
-namespace boost {
-namespace spatial_index {
-
- template<typename Point, typename Value>
- class rtree_leaf;
-
- template<typename Point, typename Value>
- class rtree_node
+namespace boost
+{
+ namespace spatial_index
   {
- 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) {}
-
- /// standard constructor
- rtree_node(const boost::shared_ptr<rtree_node<Point, Value> > &parent, const unsigned int &level)
- : parent_(parent), level_(level) {}
-
- /// level projector
- virtual unsigned int get_level(void) const { return level_; }
-
- /// element count
- virtual unsigned int elements(void) const
- {
- return nodes_.size();
- }
-
- /// first element, to replace root in case of condensing
- boost::shared_ptr<rtree_node<Point, Value> > first_element(void) const
- {
- if(nodes_.size() == 0) {
- throw std::logic_error("first_element in empty node");
- }
- return nodes_.begin()->second;
- }
-
- /// true if it is a leaf node
- virtual bool is_leaf(void) const { return false; }
-
- /// get a node
- boost::shared_ptr< rtree_node<Point, Value> > get_node(const unsigned int i) { return nodes_[i].second; }
-
- /// query method
- virtual void find(const geometry::box<Point> &e, std::deque<Value> &r, const bool exact_match)
- {
- for(typename node_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
- if(overlaps(it->first, e)) {
- it->second->find(e, r, exact_match);
- }
- }
- }
-
- void find_leaves(const geometry::box<Point> &e,
- typename std::vector<boost::shared_ptr<rtree_node<Point,Value> > > &result) const
- {
- for(typename node_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
- if(overlaps(it->first, e)) {
- if(it->second->is_leaf()) {
- result.push_back(it->second);
- } else {
- it->second->find_leaves(e, result);
- }
- }
- }
- }
-
- /// compute bounding box for this leaf
- virtual geometry::box<Point> compute_box(void) const
- {
- if(nodes_.empty()) {
- return geometry::box<Point>();
- }
-
- typename node_map::const_iterator it = nodes_.begin();
- geometry::box<Point> r = it->first;
- it++;
- for(; it != nodes_.end(); ++it) {
- r = enlarge_box(r, it->first);
- }
- return r;
- }
 
- /// insert a value (not allowed for a node)
- virtual void insert(const geometry::box<Point> &e, const Value &v)
- {
- throw std::logic_error("Insert in node!");
- }
-
- /// get the envelopes of a node
- virtual std::vector< geometry::box<Point> > get_boxes(void) const
- {
- std::vector< geometry::box<Point> > r;
- for(typename node_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
- r.push_back(it->first);
- }
- 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()) {
- nodes_[index] = std::make_pair(n->compute_box(), n);
- return;
- }
- }
- }
-
- virtual void remove(const geometry::box<Point> &k)
- {
- for(typename node_map::iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
- if(it->first.min() == k.min() && it->first.max() == k.max()) {
- nodes_.erase(it);
- return;
- }
- }
- }
-
- /// 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()) {
- nodes_[index] = std::make_pair(new_l->compute_box(), new_l);
- new_l->update_parent(new_l);
- return;
- }
- }
- throw std::logic_error("Node not found.");
- }
-
- /// add a node
- virtual void add_node(const geometry::box<Point> &b,
- const boost::shared_ptr<rtree_node<Point, Value> > &n)
- {
- nodes_.push_back(std::make_pair(b, n));
- n->update_parent(n);
- }
-
- /// add a value (not allowed in nodes)
- 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));
- }
+ template < typename Point, typename Value > class rtree_leaf;
 
- /// insertion algorithm choose node
- boost::shared_ptr<rtree_node<Point, Value> > choose_node(const geometry::box<Point> e)
+ template < typename Point, typename Value > class rtree_node
     {
- if(nodes_.size() == 0) {
- throw std::logic_error("Empty node trying to choose the least enlargement node.");
- }
- bool first = true;
- double min_area;
- double min_diff_area;
- boost::shared_ptr<rtree_node<Point,Value> > chosen_node;
-
- // check for the least enlargement
- 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;
- }
- }
- }
-
- }
- }
- return chosen_node;
- }
-
- /// empty the node
- virtual void empty_nodes(void) {
- nodes_.clear();
- }
-
- /// projector for parent
- boost::shared_ptr<rtree_node<Point,Value> > get_parent(void) const {
- return parent_;
- }
-
- /// update the parent of all the childs
- void update_parent(const boost::shared_ptr<rtree_node<Point,Value> > &p)
- {
- for(typename node_map::iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
- it->second->set_parent(p);
- }
- }
-
- /// set parent
- void set_parent(const boost::shared_ptr<rtree_node<Point,Value> > &p)
- {
- parent_ = p;
- }
-
- /// 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."); }
-
- /// box projector for node
- virtual geometry::box<Point> get_box(const unsigned int i) const { return nodes_[i].first; }
-
- /// box projector for node
- virtual geometry::box<Point> get_box(const boost::shared_ptr<rtree_node<Point, Value> > &l) const
- {
- for(typename node_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
- if(it->second.get() == l.get()) {
- return it->first;
- }
- }
- throw std::logic_error("Node not found");
- }
-
- /// value projector for the nodes
- node_map get_nodes(void) const { return nodes_; }
-
-
- /// get leaves for a node
- virtual std::vector< std::pair< geometry::box<Point>, Value > > get_leaves(void) const
- {
- std::vector< std::pair< geometry::box<Point>, Value > > l;
-
- for(typename node_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
- typename std::vector< std::pair< geometry::box<Point>, Value > > this_leaves = it->second->get_leaves();
-
- for(typename std::vector<std::pair<geometry::box<Point>, Value> >::iterator it_leaf = this_leaves.begin();
- it_leaf != this_leaves.end(); ++it_leaf) {
-
- l.push_back(*it_leaf);
-
- }
-
- }
-
- return l;
- }
-
- /// print node
- virtual void print(void) const
- {
- std::cerr << " --> Node --------" << std::endl;
- std::cerr << " Address: " << this << std::endl;
- std::cerr << " Level: " << level_ << std::endl;
- std::cerr << " Size: " << nodes_.size() << std::endl;
- std::cerr << " | ";
- for(typename node_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
-
- if(it->second->get_parent().get() != this) {
- std::cerr << "ERROR - " << this << " is not " <<it->second->get_parent().get() << " ";
- }
-
- std::cerr << "( " << geometry::get<0>(it->first.min()) << " , " << geometry::get<1>(it->first.min()) << " ) x " ;
- std::cerr << "( " << geometry::get<0>(it->first.max()) << " , " << geometry::get<1>(it->first.max()) << " )" ;
- std::cerr << " | ";
- }
- std::cerr << std::endl;
- std::cerr << " --< Node --------" << std::endl;
-
- // print child nodes
- std::cerr << " Children: " << std::endl;
- for(typename node_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
- it->second->print();
- }
- }
-
- /// destructor (virtual because we have virtual functions)
- virtual ~rtree_node(void) {}
-
- private:
-
- // parent node
- boost::shared_ptr< rtree_node<Point, Value> > parent_;
-
- // level of this node
- unsigned int level_;
+ 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)
+ {
+ }
+
+ /// standard constructor
+ rtree_node(const boost::shared_ptr < rtree_node < Point, Value > >&parent,
+ const unsigned int &level)
+ : parent_(parent), level_(level)
+ {
+ }
+
+ /// level projector
+ virtual unsigned int get_level(void) const
+ {
+ return level_;
+ }
+
+ /// element count
+ virtual unsigned int elements(void) const
+ {
+ return nodes_.size();
+ }
+
+ /// first element, to replace root in case of condensing
+ boost::shared_ptr < rtree_node < Point, Value > >first_element(void) const
+ {
+ if (nodes_.size() == 0) {
+ throw std::logic_error("first_element in empty node");
+ }
+ return nodes_.begin()->second;
+ }
+
+ /// true if it is a leaf node
+ virtual bool is_leaf(void) const
+ {
+ return false;
+ }
+
+ /// get a node
+ boost::shared_ptr < rtree_node < Point,
+ Value > >get_node(const unsigned int i)
+ {
+ return nodes_[i].second;
+ }
+
+ /// query method
+ virtual void find(const geometry::box < Point > &e,
+ std::deque < Value > &r, const bool exact_match)
+ {
+ for(typename node_map::const_iterator it = nodes_.begin();
+ it != nodes_.end(); ++it) {
+ if (overlaps(it->first, e)) {
+ it->second->find(e, r, exact_match);
+ }
+ }
+ }
+
+ void find_leaves(const geometry::box < Point > &e,
+ typename std::vector < boost::shared_ptr < rtree_node <
+ Point, Value > > > &result) const
+ {
+ for(typename node_map::const_iterator it = nodes_.begin();
+ it != nodes_.end(); ++it)
+ {
+ if (overlaps(it->first, e)) {
+ if (it->second->is_leaf()) {
+ result.push_back(it->second);
+ } else {
+ it->second->find_leaves(e, result);
+ }
+ }
+ }
+ }
+
+ /// compute bounding box for this leaf
+ virtual geometry::box < Point > compute_box(void) const
+ {
+ if (nodes_.empty()) {
+ return geometry::box < Point > ();
+ }
+
+ typename node_map::const_iterator it = nodes_.begin();
+ geometry::box < Point > r = it->first;
+ it++;
+ for(; it != nodes_.end(); ++it) {
+ r = enlarge_box(r, it->first);
+ }
+ return r;
+ }
+
+ /// insert a value (not allowed for a node)
+ virtual void insert(const geometry::box < Point > &e, const Value & v)
+ {
+ throw std::logic_error("Insert in node!");
+ }
+
+ /// get the envelopes of a node
+ virtual std::vector < geometry::box < Point > >get_boxes(void) const
+ {
+ std::vector < geometry::box < Point > >r;
+ for(typename node_map::const_iterator it = nodes_.begin();
+ it != nodes_.end(); ++it) {
+ r.push_back(it->first);
+ }
+ 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()) {
+ nodes_[index] = std::make_pair(n->compute_box(), n);
+ return;
+ }
+ }
+ }
+
+ virtual void remove(const geometry::box < Point > &k)
+ {
+ for(typename node_map::iterator it = nodes_.begin();
+ it != nodes_.end(); ++it) {
+ if (it->first.min() == k.min() && it->first.max() == k.max()) {
+ nodes_.erase(it);
+ return;
+ }
+ }
+ }
+
+ /// 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()) {
+ nodes_[index] = std::make_pair(new_l->compute_box(), new_l);
+ new_l->update_parent(new_l);
+ return;
+ }
+ }
+ throw std::logic_error("Node not found.");
+ }
+
+ /// add a node
+ virtual void add_node(const geometry::box < Point > &b,
+ const boost::shared_ptr < rtree_node < Point,
+ Value > >&n)
+ {
+ nodes_.push_back(std::make_pair(b, n));
+ n->update_parent(n);
+ }
+
+ /// add a value (not allowed in nodes)
+ 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));
+ }
+
+ /// insertion algorithm choose node
+ boost::shared_ptr < rtree_node < Point, Value > >
+ choose_node(const geometry::box < Point > e)
+ {
+ if (nodes_.size() == 0) {
+ throw std::
+ logic_error
+ ("Empty node trying to choose the least enlargement node.");
+ }
+ bool first = true;
+ double min_area;
+ double min_diff_area;
+ boost::shared_ptr < rtree_node < Point, Value > >chosen_node;
+
+ // check for the least enlargement
+ 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;
+ }
+ }
+ }
+
+ }
+ }
+ return chosen_node;
+ }
+
+ /// empty the node
+ virtual void empty_nodes(void)
+ {
+ nodes_.clear();
+ }
+
+ /// projector for parent
+ boost::shared_ptr < rtree_node < Point, Value > >get_parent(void) const
+ {
+ return parent_;
+ }
+
+ /// update the parent of all the childs
+ void update_parent(const boost::shared_ptr < rtree_node < Point,
+ Value > >&p)
+ {
+ for(typename node_map::iterator it = nodes_.begin();
+ it != nodes_.end(); ++it) {
+ it->second->set_parent(p);
+ }
+ }
+
+ /// set parent
+ void set_parent(const boost::shared_ptr < rtree_node < Point, Value > >&p)
+ {
+ parent_ = p;
+ }
+
+ /// 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.");
+ }
+
+ /// box projector for node
+ virtual geometry::box < Point > get_box(const unsigned int i) const
+ {
+ return nodes_[i].first;
+ }
+
+ /// box projector for node
+ virtual geometry::box < Point > get_box(const boost::shared_ptr <
+ rtree_node < Point,
+ Value > >&l) const
+ {
+ for(typename node_map::const_iterator it = nodes_.begin();
+ it != nodes_.end(); ++it)
+ {
+ if (it->second.get() == l.get()) {
+ return it->first;
+ }
+ }
+ throw std::logic_error("Node not found");
+ }
+
+ /// value projector for the nodes
+ node_map get_nodes(void) const
+ {
+ return nodes_;
+ }
+
+
+ /// get leaves for a node
+ virtual std::vector < std::pair < geometry::box < Point >,
+ Value > >get_leaves(void) const
+ {
+ std::vector < std::pair < geometry::box < Point >, Value > >l;
+
+ for(typename node_map::const_iterator it = nodes_.begin();
+ it != nodes_.end(); ++it)
+ {
+ typename std::vector < std::pair < geometry::box < Point >,
+ Value > >this_leaves = it->second->get_leaves();
+
+ for(typename std::vector < std::pair < geometry::box < Point >,
+ Value > >::iterator it_leaf = this_leaves.begin();
+ it_leaf != this_leaves.end(); ++it_leaf)
+ {
+
+ l.push_back(*it_leaf);
+
+ }
+
+ }
+
+ return l;
+ }
+
+ /// print node
+ virtual void print(void) const
+ {
+ std::cerr << " --> Node --------" << std::endl;
+ std::cerr << " Address: " << this << std::endl;
+ std::cerr << " Level: " << level_ << std::endl;
+ std::cerr << " Size: " << nodes_.size() << std::endl;
+ std::cerr << " | ";
+ for(typename node_map::const_iterator it = nodes_.begin();
+ it != nodes_.end(); ++it)
+ {
+
+ if (it->second->get_parent().get() != this) {
+ std::cerr << "ERROR - " << this << " is not " << it->second->
+ get_parent().get() << " ";
+ }
+
+ std::cerr << "( " << geometry::get < 0 >
+ (it->first.min()) << " , " << geometry::get < 1 >
+ (it->first.min()) << " ) x ";
+ std::cerr << "( " << geometry::get < 0 >
+ (it->first.max()) << " , " << geometry::get < 1 >
+ (it->first.max()) << " )";
+ std::cerr << " | ";
+ }
+ std::cerr << std::endl;
+ std::cerr << " --< Node --------" << std::endl;
+
+ // print child nodes
+ std::cerr << " Children: " << std::endl;
+ for(typename node_map::const_iterator it = nodes_.begin();
+ it != nodes_.end(); ++it) {
+ it->second->print();
+ }
+ }
+
+ /// destructor (virtual because we have virtual functions)
+ virtual ~ rtree_node(void)
+ {
+ }
+
+ private:
+
+ // parent node
+ boost::shared_ptr < rtree_node < Point, Value > >parent_;
+
+ // level of this node
+ unsigned int level_;
 
- /// child nodes
- node_map nodes_;
+ /// child nodes
+ node_map nodes_;
 
- };
+ };
 
-} // namespace spatial_index
-} // namespace boost
+ } // namespace spatial_index
+} // namespace boost
 
 #endif // BOOST_SPATIAL_INDEX_RTREE_NODE_HPP

Modified: sandbox/SOC/2008/spacial_indexing/boost/spatial_index/spatial_index.hpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/boost/spatial_index/spatial_index.hpp (original)
+++ sandbox/SOC/2008/spacial_indexing/boost/spatial_index/spatial_index.hpp 2008-07-23 13:32:04 EDT (Wed, 23 Jul 2008)
@@ -13,105 +13,157 @@
 #include <geometry/geometry.hpp>
 #include <geometry/box.hpp>
 
-namespace boost {
-namespace spatial_index {
-
- /// spatial index interface
- template<typename Point, typename Value, typename Index>
- class spatial_index
- {
- private:
- /// non constructible
- spatial_index() {}
- };
-
-
- /// forward declaration for quadtree
- template<typename Point, typename Value>
- class quadtree;
-
- /// forward declaration for rtree
- template<typename Point, typename Value>
- class rtree;
-
-
- /// specialization for quadtree
- template<typename Point, typename Value>
- class spatial_index<Point, Value, quadtree<Point, Value> >
+namespace boost
+{
+ namespace spatial_index
   {
- public:
- /// quadtree constructor
- spatial_index(const geometry::box<Point> &b, const unsigned int M) : i_(b, M) {}
-
- /// insert data 'v' with key 'k'
- void insert(const Point &k, const Value &v) { i_.insert(k, v); }
-
- /// remove data with key 'k'
- void remove(const Point &k) { i_.remove(k); }
-
- /// bulk insert data from values
- void bulk_insert(std::vector<Value> &values, std::vector<Point> &points) { i_.bulk_insert(values, points); }
-
- /// find element with key 'k'
- Value find(const Point &k) { return i_.find(k); }
-
- /// find element in the defined rectangle
- /// TODO: change container
- std::deque<Value> find(const geometry::box<Point> &r) { return i_.find(r); }
-
- /// element count in the index
- unsigned int elements(void) const { return i_.elements(); }
-
- /// debug print
- void print(void) { i_.print(); }
-
- private:
- quadtree<Point, Value> i_;
- };
-
- /// specialization for rtree
- template<typename Point, typename Value>
- class spatial_index<Point, Value, rtree<Point, Value> >
- {
- public:
-
- /// rtree constructor
- spatial_index(const unsigned int m, const unsigned int M) : i_(m, M) {}
-
- /// insert data 'v' with key 'k'
- void insert(const Point &k, const Value &v) { i_.insert(k, v); }
-
- /// insert data with envelope 'e' with key 'k'
- void insert(const geometry::box<Point> &e, const Value &v) { i_.insert(e, v); }
-
- /// remove data with key 'k'
- void remove(const Point &k) { i_.remove(k); }
-
- /// remove data with key 'k'
- void remove(const geometry::box<Point> &k) { i_.remove(k); }
-
- /// bulk insert data from values
- void bulk_insert(std::vector<Value> &values, std::vector<Point> &points) { i_.bulk_insert(values, points); }
-
- /// find element with key 'k'
- Value find(const Point &k) { return i_.find(k); }
-
- /// find element in the defined rectangle
- /// TODO: change container
- std::deque<Value> find(const geometry::box<Point> &r) { return i_.find(r); }
-
- /// element count in the index
- unsigned int elements(void) const { return i_.elements(); }
 
- /// debug print
- void print(void) { i_.print(); }
-
- private:
- rtree<Point, Value> i_;
- };
+ /// spatial index interface
+ template < typename Point, typename Value, typename Index >
+ class spatial_index
+ {
+ private:
+ /// non constructible
+ spatial_index() {
+ }
+ };
+
+
+ /// forward declaration for quadtree
+ template < typename Point, typename Value > class quadtree;
+
+ /// forward declaration for rtree
+ template < typename Point, typename Value > class rtree;
+
+
+ /// specialization for quadtree
+ template < typename Point, typename Value >
+ class spatial_index < Point, Value, quadtree < Point, Value > > {
+ public:
+ /// quadtree constructor
+ spatial_index(const geometry::box < Point > &b,
+ const unsigned int M):i_(b, M)
+ {
+ }
+
+ /// insert data 'v' with key 'k'
+ void insert(const Point & k, const Value & v)
+ {
+ i_.insert(k, v);
+ }
+
+ /// remove data with key 'k'
+ void remove(const Point & k)
+ {
+ i_.remove(k);
+ }
+
+ /// bulk insert data from values
+ void bulk_insert(std::vector < Value > &values,
+ std::vector < Point > &points)
+ {
+ i_.bulk_insert(values, points);
+ }
+
+ /// find element with key 'k'
+ Value find(const Point & k)
+ {
+ return i_.find(k);
+ }
+
+ /// find element in the defined rectangle
+ /// TODO: change container
+ std::deque < Value > find(const geometry::box < Point > &r) {
+ return i_.find(r);
+ }
+
+ /// element count in the index
+ unsigned int elements(void) const
+ {
+ return i_.elements();
+ }
+
+ /// debug print
+ void print(void)
+ {
+ i_.print();
+ }
+
+ private:
+ quadtree < Point, Value > i_;
+ };
+
+ /// specialization for rtree
+ template < typename Point, typename Value >
+ class spatial_index < Point, Value, rtree < Point, Value > > {
+ public:
+
+ /// rtree constructor
+ spatial_index(const unsigned int m, const unsigned int M):i_(m, M)
+ {
+ }
+
+ /// insert data 'v' with key 'k'
+ void insert(const Point & k, const Value & v)
+ {
+ i_.insert(k, v);
+ }
+
+ /// insert data with envelope 'e' with key 'k'
+ void insert(const geometry::box < Point > &e, const Value & v)
+ {
+ i_.insert(e, v);
+ }
+
+ /// remove data with key 'k'
+ void remove(const Point & k)
+ {
+ i_.remove(k);
+ }
+
+ /// remove data with key 'k'
+ void remove(const geometry::box < Point > &k)
+ {
+ i_.remove(k);
+ }
+
+ /// bulk insert data from values
+ void bulk_insert(std::vector < Value > &values,
+ std::vector < Point > &points)
+ {
+ i_.bulk_insert(values, points);
+ }
+
+ /// find element with key 'k'
+ Value find(const Point & k)
+ {
+ return i_.find(k);
+ }
+
+ /// find element in the defined rectangle
+ /// TODO: change container
+ std::deque < Value > find(const geometry::box < Point > &r) {
+ return i_.find(r);
+ }
+
+ /// element count in the index
+ unsigned int elements(void) const
+ {
+ return i_.elements();
+ }
+
+ /// debug print
+ void print(void)
+ {
+ i_.print();
+ }
+
+ private:
+ rtree < Point, Value > i_;
+ };
 
 
-} // namespace spatial_index
-} // namespace boost
+ } // namespace spatial_index
+} // namespace boost
 
 #endif // BOOST_SPATIAL_INDEX_SPATIAL_INDEX_HPP

Date view Thread view Subject view Author view

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