Boost logo

Boost-Commit :

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;


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