[Boost-commit] svn:boost r46416 - in sandbox/SOC/2008/spacial_indexing: boost/spatial_index libs/spatial_index/test

From: mariano.consoni_at_[hidden]
Date: 2008-06-16 05:36:48

Author: mconsoni
Date: 2008-06-16 05:36:47 EDT (Mon, 16 Jun 2008)
New Revision: 46416
URL: http://svn.boost.org/trac/boost/changeset/46416

Log:

- envelope query implemented.

Added:
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/helpers.hpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp                 |     7 +++++--                                 
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_leaf.hpp            |    10 ++++++++++                              
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp            |    11 +++++++++++                             
   sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp |    30 +++++++++---------------------          
   4 files changed, 35 insertions(+), 23 deletions(-)

Added: sandbox/SOC/2008/spacial_indexing/boost/spatial_index/helpers.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/spacial_indexing/boost/spatial_index/helpers.hpp	2008-06-16 05:36:47 EDT (Mon, 16 Jun 2008)
@@ -0,0 +1,42 @@
+// Copyright 2008 Federico J. Fernandez.
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+
+#ifndef BOOST_SPATIAL_INDEX_HELPERS_HPP
+#define BOOST_SPATIAL_INDEX_HELPERS_HPP
+
+namespace boost {
+namespace spatial_index {
+
+
+  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
+
+#endif // BOOST_SPATIAL_INDEX_HELPERS_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-06-16 05:36:47 EDT (Mon, 16 Jun 2008)
@@ -9,6 +9,8 @@
 
 #include <geometry/area.hpp>
 
+#include "helpers.hpp"
+
 #include "rtree_node.hpp"
 #include "rtree_leaf.hpp"
 
@@ -88,8 +90,9 @@
 
     virtual std::deque<Value> find(const geometry::box<Point> &r)
     {
-	std::deque<Value> result;
-	return result;
+      std::deque<Value> result;
+      root_->find(r, result);
+      return result;
     }
 
     virtual unsigned int elements(void) { return element_count; }

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-06-16 05:36:47 EDT (Mon, 16 Jun 2008)
@@ -28,6 +28,16 @@
     rtree_leaf(const boost::shared_ptr< rtree_node<Point,Value> > &parent, const unsigned int &L) 
       : rtree_node<Point,Value>(parent, 0, 0, 0), L_(L), level_(0) {}
 
+    /// query method
+    virtual void  find(const geometry::box<Point> &e, std::deque<Value> &r)
+    {
+      for(typename leaves_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
+	if(overlaps(it->first, e)) {
+	  r.push_back(it->second);
+	}
+      }
+    }
+
     /// compute bounding box for this leaf
     virtual geometry::box<Point> compute_box(void) const
     {

Modified: sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp	(original)
+++ sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp	2008-06-16 05:36:47 EDT (Mon, 16 Jun 2008)
@@ -59,6 +59,17 @@
     /// 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)
+    {
+      for(typename node_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
+	if(overlaps(it->first, e)) {
+	  it->second->find(e, r);
+	}
+      }
+    }
+
+
     /// get leaves
     virtual std::vector< std::pair< geometry::box<Point>, Value > > get_leaves(void) const
     {

Modified: sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp	(original)
+++ sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp	2008-06-16 05:36:47 EDT (Mon, 16 Jun 2008)
@@ -91,18 +91,15 @@
          q->insert(e15, 15);
          q->print();
 
-//  	std::cerr << " --> insert" << std::endl;
-//  	q->insert(geometry::point_xy<double>(1.0,1.0), it++);
-//  	std::cerr << " --> insert" << std::endl;
-//  	q->insert(geometry::point_xy<double>(2.0,1.0), it++);
-//  	std::cerr << " --> insert" << std::endl;
-//  	q->insert(geometry::point_xy<double>(5.0,5.0), it++);
-//  	std::cerr << " --> insert" << std::endl;
-//  	q->insert(geometry::point_xy<double>(1.0,6.0), it++);
-//  	std::cerr << " --> insert" << std::endl;
-//  	q->insert(geometry::point_xy<double>(9.0,9.0), it++);
-//  	std::cerr << " --> insert" << std::endl;
-//  	q->insert(geometry::point_xy<double>(9.0,8.0), it++);
+	std::cerr << " --> find rectangle" << std::endl;
+	geometry::box<geometry::point_xy<double> > query_box(geometry::point_xy<double>(0.0, 0.0), geometry::point_xy<double>(2.0, 2.0));
+	std::deque< unsigned int > d = q->find(query_box);
+// 	BOOST_CHECK_EQUAL(d.size(), 3u);
+	unsigned int i = 0;
+	for(std::deque<unsigned int>::const_iterator dit = d.begin(); dit != d.end(); ++dit) {
+		std::cerr << "Value: " << *dit << std::endl;
+// 		BOOST_CHECK_EQUAL(*(*dit), res[i++]);
+	}
 
 
 // 	std::vector<std::string>::iterator it1;
@@ -126,15 +123,6 @@
 // 	std::cerr << "Elements: " << q->elements() << std::endl;
 // 	BOOST_CHECK_EQUAL(q->elements(), 6u);
 
-// 	std::cerr << " --> find rectangle" << std::endl;
-// 	geometry::box<geometry::point_xy<double> > query_box(geometry::point_xy<double>(0.0, 0.0), geometry::point_xy<double>(5.0, 5.0));
-// 	std::deque< std::vector<std::string>::iterator > d = q->find(query_box);
-// 	BOOST_CHECK_EQUAL(d.size(), 3u);
-// 	unsigned int i = 0;
-// 	for(std::deque< std::vector<std::string>::iterator >::const_iterator dit = d.begin(); dit != d.end(); ++dit) {
-// 		std::cerr << "Value: " << *(*dit) << std::endl;
-// 		BOOST_CHECK_EQUAL(*(*dit), res[i++]);
-// 	}
 
 
         return 0;