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

From: mariano.consoni_at_[hidden]
Date: 2008-06-04 15:29:20

Author: mconsoni
Date: 2008-06-04 15:29:19 EDT (Wed, 04 Jun 2008)
New Revision: 46137
URL: http://svn.boost.org/trac/boost/changeset/46137

Log:
- Initial Geometry Library integration.
 -> we add the current code
 -> the quadtree code was modificated to adapt to the new point and box classes.
 -> simple_test was adapted to the new style (the other tests are pending)

Text files modified: 
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree.hpp      |    26 +-                                      
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree_node.hpp |   361 +++++++++++++++++++++------------------ 
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/spatial_index.hpp |    16                                         
   3 files changed, 214 insertions(+), 189 deletions(-)

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-06-04 15:29:19 EDT (Wed, 04 Jun 2008)
@@ -15,34 +15,34 @@
 namespace spatial_index {
 
 
-template<typename Key, typename Value>
-class quadtree : public spatial_index<Key, Value>
+template<typename Point, typename Value>
+class quadtree : public spatial_index<Point, Value>
 {
 private:
-	quadtree_node<Key,Value> root;
+	quadtree_node<Point,Value> root;
         unsigned int element_count;
 
         // number of points in each node
         unsigned int node_size_;
 
 public:
-	quadtree(double min_x, double min_y, double max_x, double max_y) 
-		: root(min_x, min_y, max_x, max_y, 1), element_count(0), node_size_(1)  {}
+ 	quadtree(const geometry::box<Point> &r)
+		: root(r, 1), element_count(0), node_size_(1)  {}
           
-	virtual void insert(const Key &k, const Value &v)
+	virtual void insert(const Point &k, const Value &v)
         {
                 element_count++;
                 root.insert(k, v);
         }
 
-	virtual void bulk_insert(Value &v_begin, Value &v_end, std::vector<Key> &v)
+	virtual void bulk_insert(Value &v_begin, Value &v_end, std::vector<Point> &v)
         {
 // 		boost::xtime xt1, xt2;
 // 		boost::xtime_get(&xt1, boost::TIME_UTC);
 
                 //unsigned int counter = 0;
 
-		typename std::vector<Key>::iterator it_point;
+		typename std::vector<Point>::iterator it_point;
                 it_point = v.begin();
                 Value it_data = v_begin;
                 while(it_data != v_end && it_point != v.end()) {
@@ -62,16 +62,16 @@
 // 		std::cerr << " nsecs: " << xt2.nsec - xt1.nsec << std::endl;
         }
 
-	virtual Value find(const Key &k)
+	virtual Value find(const Point &k)
         {
                 return root.find(k);
         }
 
-	virtual std::deque<Value> find(const double x1, const double x2, const double y1, const double y2)
+ 	virtual std::deque<Value> find(const geometry::box<Point> &r)
         {
-		std::deque<Value> r;
-		root.find(r, x1, x2, y1, y2);
-		return r;
+		std::deque<Value> result;
+		root.find(result, r);
+		return result;
         }
 
 

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-06-04 15:29:19 EDT (Wed, 04 Jun 2008)
@@ -9,194 +9,217 @@
 
 #include <boost/shared_ptr.hpp>
 
+#include <geometry/within.hpp>
+
 #include <iostream>
 #include <map>
 
 namespace boost {
 namespace spatial_index {
 
-template<typename Key, typename Value>
+template<typename Point, typename Value>
 class quadtree_node
 {
 private:
-	boost::shared_ptr<quadtree_node> nw_;
-	boost::shared_ptr<quadtree_node> ne_;
-	boost::shared_ptr<quadtree_node> sw_;
-	boost::shared_ptr<quadtree_node> se_;
+  /// 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_;
 
-	std::map<Key, Value> m_;
-	
-	double min_x_;
-	double min_y_;
+  /// this node's points
+  std::map<Point, Value> m_;
 
-	double max_x_;
-	double max_y_;
+  /// the bounding rectangle for the node
+  geometry::box<Point> bounding_rectangle_;
         
-	// number of points in each node
-	unsigned int node_size_;
+  /// number of points in each node
+  unsigned int node_size_;
 
-public:
-	quadtree_node(double min_x, double min_y, double max_x, double max_y, unsigned int node_size) 
-		: min_x_(min_x), min_y_(min_y), max_x_(max_x), max_y_(max_y), node_size_(node_size)
-	{
-// 		std::cerr << "Creating quadtree_node with " << 
-// 			"min_x: " << min_x << " min_y: " << min_y << " max_x: " << max_x << " max_y " << max_y << std::endl;
-	}
+  /// 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());
+  }
 
 
-	void insert(const Key &k, const Value &v)
-	{
-		if(m_.size() < node_size_) {
-// 			std::cerr << "Empty quadtree_node --> inserting" << std::endl;
-			m_[k] = v;
-		} else {
-//  			std::cerr << "Quadtree_Node division: ";
-// 			// quadtree_node division
-//  			std::cerr << " (" << k.first << ", " << k.second << ")" ;
-//  			std::cerr << " in (" << min_x_ << ", " << min_y_ << ")"; 
-//  			std::cerr << " x (" << max_x_ << ", " << max_y_ << ")" << std::endl; 
-			
-			if((k.first >= min_x_ && k.first < min_x_+(max_x_-min_x_)/2.0) && 
-			   (k.second >= min_y_ && k.second < min_y_+(max_y_-min_y_)/2.0)) {
-				if(this->ne_ == boost::shared_ptr<quadtree_node>()) {
-					this->ne_ = boost::shared_ptr<quadtree_node>(new quadtree_node(min_x_, min_y_, min_x_+(max_x_-min_x_)/2.0, 
-												       min_y_+(max_y_-min_y_)/2.0, node_size_));
-				}
-				ne_->insert(k, v);
-			}
- 			if((k.first >= min_x_ && k.first < min_x_+(max_x_-min_x_)/2.0) && 
- 			   (k.second >= min_y_+(max_y_-min_y_)/2.0 && k.second < max_y_)) {
-				if(this->se_ == boost::shared_ptr<quadtree_node>()) {
-					this->se_ = boost::shared_ptr<quadtree_node>(new quadtree_node(min_x_, 
-												       min_y_+(max_y_-min_y_)/2.0,
-												       min_x_+(max_x_-min_x_)/2.0, 
-												       max_y_, node_size_));
-				}
-				se_->insert(k, v);
-			}
-		      
- 			if((k.first >= min_x_+(max_x_-min_x_)/2.0 && k.first < max_x_) &&
- 			   (k.second >= min_y_ && k.second < min_y_+(max_y_-min_y_)/2.0)) {
-			
-				if(this->nw_ == boost::shared_ptr<quadtree_node>()) {
-					this->nw_ = boost::shared_ptr<quadtree_node>(new quadtree_node(min_x_+(max_x_-min_x_)/2.0, min_y_, max_x_, 
-												       min_y_+(max_y_-min_y_)/2.0, node_size_));
-				}
-				nw_->insert(k, v);
-			}
-		      
-
- 			if((k.first >= min_x_+(max_x_-min_x_)/2.0 && k.first < max_x_) &&
- 			   (k.second >= min_y_+(max_y_-min_y_)/2.0 && k.second < max_y_)) {
-				
-				if(this->sw_ == boost::shared_ptr<quadtree_node>()) {
-					this->sw_ = boost::shared_ptr<quadtree_node>(new quadtree_node(min_x_+(max_x_-min_x_)/2.0, 
-												     min_y_+(max_y_-min_y_)/2.0,
-												       max_x_, max_y_, node_size_));
-				}
-				sw_->insert(k, v);
-			}
-			
-		}
+public:
+  quadtree_node(const geometry::box<Point> &r, const unsigned int node_size) 
+    : bounding_rectangle_(r), node_size_(node_size)
+  {
+    // std::cerr << "Creating quadtree_node with " << 
+    // "min_x: " << min_x << " min_y: " << min_y << " max_x: " << max_x << " max_y " << max_y << std::endl;
+  }
+
+
+  void insert(const Point &k, const Value &v)
+  {
+    if(m_.size() < node_size_) {
+      std::cerr << "Empty quadtree_node --> inserting (" << *v << ")" << std::endl;
+      m_[k] = v;
+    } else {
+      // std::cerr << "Quadtree_Node division: ";
+      // // quadtree_node division
+      // std::cerr << " (" << k.first << ", " << k.second << ")" ;
+      // std::cerr << " in (" << min_x_ << ", " << min_y_ << ")"; 
+      // std::cerr << " x (" << max_x_ << ", " << max_y_ << ")" << std::endl; 
+
+      // 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> &r, const double x1, const double x2, const double y1, const double y2)
-	{
-		if(m_.size() != 0) {
-// 			std::cerr << "Node: X1:" << min_x_ << " X2:" << max_x_ << " Y1:" << min_y_ << " Y2: " << max_y_ << std::endl;
-// 			std::cerr << "Query: X1:" << x1 << " X2:" << x2 << " Y1:" << y1 << " Y2: " << y2 << std::endl;
-
-			if(x1 > max_x_ || x2 < min_x_ || y1 > max_y_ || y2 < min_y_) {
-// 				std::cerr << "Not Inside" << std::endl;
-				return;
-			}
-
-// 			std::cerr << "Inside" << std::endl;
-
-			for(typename std::map<Key,Value>::const_iterator it = m_.begin(); it != m_.end(); ++it) {
-// 				std::cerr << "Checking: (" << it->first.first << "," << it->first.second << ")" << std::endl;
-				if(it->first.first >= x1 && it->first.first <= x2 && it->first.second >= y1 && it->first.second <= y2) {
-					r.push_back(it->second);
-				}
-			}
-
-			if(ne_ != boost::shared_ptr<quadtree_node>()) {
-				ne_->find(r, x1, x2, y1, y2);
-			}
-			if(se_ != boost::shared_ptr<quadtree_node>()) {
-				se_->find(r, x1, x2, y1, y2);
-			}
-			if(nw_ != boost::shared_ptr<quadtree_node>()) {
-				nw_->find(r, x1, x2, y1, y2);
-			}
-			if(sw_ != boost::shared_ptr<quadtree_node>()) {
-				sw_->find(r, x1, x2, y1, y2);
-			}
-			
-// 			std::cerr << std::endl;
-		}
-	}
-
-
-	Value find(const Key &k)
-	{
-		if(m_.size() == 0) {
-			return Value();
-		} else {
-// 			std::cerr << "compare: " << k_.first << " with " << k.first;
-// 			std::cerr << " " << k_.second << " with " << k.second << std::endl;
-			typename std::map<Key, Value>::const_iterator it = m_.find(k);
-			if(it != m_.end()) {
-// 				std::cerr << "ok" << std::endl;
-				return it->second;
-			}
-
-			if((k.first >= min_x_ && k.first < min_x_+(max_x_-min_x_)/2.0) && 
-			   (k.second >= min_y_ && k.second < min_y_+(max_y_-min_y_)/2.0)) {
-				if(ne_ != boost::shared_ptr<quadtree_node>()) {
-					return ne_->find(k);
-				} else {
-					return Value();
-// 					return v_;
-				}
-			}
- 			if((k.first >= min_x_ && k.first < min_x_+(max_x_-min_x_)/2.0) && 
- 			   (k.second >= min_y_+(max_y_-min_y_)/2.0 && k.second < max_y_)) {
-				if(se_ != boost::shared_ptr<quadtree_node>()) {
-					return se_->find(k);
-				} else {
-					return Value();
-// 					return v_;
-				}
-			      
-			}
-
- 			if((k.first >= min_x_+(max_x_-min_x_)/2.0 && k.first < max_x_) &&
- 			   (k.second >= min_y_ && k.second < min_y_+(max_y_-min_y_)/2.0)) {
-				if(nw_ != boost::shared_ptr<quadtree_node>()) {
-					return nw_->find(k);
-				} else {
-					return Value();
-// 					return v_;
-				}
-			      
-			}
- 			if((k.first >= min_x_+(max_x_-min_x_)/2.0 && k.first < max_x_) &&
- 			   (k.second >= min_y_+(max_y_-min_y_)/2.0 && k.second < max_y_)) {
-				if(sw_ != boost::shared_ptr<quadtree_node>()) {
-					return sw_->find(k);
-				} else {
-					return Value();
-// 					return v_;
-				}
-			      
-			}
-		}
-		// never reached
-		return Value();
+  void find(std::deque<Value> &result, const geometry::box<Point> &r)
+  {
+    if(m_.size() != 0) {
+      // std::cerr << "Node: X1:" << min_x_ << " X2:" << max_x_ << " Y1:" << min_y_ << " Y2: " << max_y_ << std::endl;
+      // std::cerr << "Query: X1:" << x1 << " X2:" << x2 << " Y1:" << y1 << " Y2: " << y2 << std::endl;
+
+      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())) {
+	// std::cerr << "Not Inside" << std::endl;
+	return;
+      }
+      // std::cerr << "Inside" << std::endl;
+
+      for(typename std::map<Point,Value>::const_iterator it = m_.begin(); it != m_.end(); ++it) {
+	std::cerr << "Checking: (" << geometry::get<0>(it->first) << "," << geometry::get<1>(it->first) << ")" << std::endl;
+	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);
+      }
+
+      // std::cerr << std::endl;
+    }
+  }
+
+
+  Value find(const Point &k)
+  {
+    if(m_.size() == 0) {
+      return Value();
+    } else {
+      // std::cerr << "compare: " << k_.first << " with " << k.first;
+      // std::cerr << " " << k_.second << " with " << k.second << std::endl;
+      typename std::map<Point, Value>::const_iterator it = m_.find(k);
+      if(it != m_.end()) {
+	// std::cerr << "ok" << std::endl;
+	return it->second;
+      }
+
+
+      // 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);
+
+      // TODO: replace with algorithm
+      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();
+  }
+
 };
 
 

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-06-04 15:29:19 EDT (Wed, 04 Jun 2008)
@@ -10,6 +10,9 @@
 #include <vector>
 #include <deque>
 
+#include <boost/geometry/geometry.hpp>
+#include <boost/geometry/box.hpp>
+
 namespace boost {
 namespace spatial_index {
 
@@ -23,25 +26,24 @@
     Since spatial_index does nothing, it is not very useful.
 */
 
-template<typename Key, typename Value>
+template<typename Point, typename Value>
 class spatial_index
 {
 
 public:
 
         /// insert data 'v' with key 'k'
-	virtual void insert(const Key &k, const Value &v) = 0;
+	virtual void insert(const Point &k, const Value &v) = 0;
         
-	/// bulk insert data in (v_begin, v_end)
-	virtual void bulk_insert(Value &v_begin, Value &v_end, std::vector<Key> &v) = 0;
+	/// bulk insert data from (v_begin, v_end)
+	virtual void bulk_insert(Value &v_begin, Value &v_end, std::vector<Point> &v) = 0;
 
         /// find element with key 'k'
-	virtual Value find(const Key &k) = 0;
+	virtual Value find(const Point &k) = 0;
 
         /// find element in the defined rectangle
         /// TODO: change container
-	/// TODO: use rectangle from the Geometry Library
-	virtual std::deque<Value> find(const double x1, const double x2, const double y1, const double y2) = 0;
+ 	virtual std::deque<Value> find(const geometry::box<Point> &r) = 0;
 
         /// element count in the index
         virtual unsigned int elements(void) = 0;