|
|
Boost-Commit : |
From: mariano.consoni_at_[hidden]
Date: 2008-05-22 23:08:19
Author: mconsoni
Date: 2008-05-22 23:08:19 EDT (Thu, 22 May 2008)
New Revision: 45669
URL: http://svn.boost.org/trac/boost/changeset/45669
Log:
- Rectangle query implemented.
Text files modified:
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree.hpp | 8 +++
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree_node.hpp | 89 ++++++++++++++++++++++++++++++++++++++++
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/spatial_index.hpp | 6 ++
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test.cpp | 6 ++
4 files changed, 109 insertions(+), 0 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-05-22 23:08:19 EDT (Thu, 22 May 2008)
@@ -64,6 +64,14 @@
return root.find(k);
}
+ virtual std::deque<Value> find(const double x1, const double x2, const double y1, const double y2)
+ {
+ std::deque<Value> r;
+ root.find(r, x1, x2, y1, y2);
+ return r;
+ }
+
+
virtual unsigned int elements(void) { return element_count; }
virtual ~quadtree() {}
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-05-22 23:08:19 EDT (Thu, 22 May 2008)
@@ -100,6 +100,95 @@
}
}
+
+ void find(std::deque<Value> &r, const double x1, const double x2, const double y1, const double y2)
+ {
+ if(v_ != Value()) {
+
+ if(k_.first >= x1 && k_.first <= x2 && k_.second >= y1 && k_.second <= y2) {
+ r.push_back(v_);
+ }
+
+ if(
+ (x1 >= min_x_ && x1 < min_x_+(max_x_-min_x_)/2.0) &&
+ (y1 >= min_y_ && y1 < min_y_+(max_y_-min_y_)/2.0) ||
+
+ (x1 >= min_x_ && x1 < min_x_+(max_x_-min_x_)/2.0) &&
+ (y2 >= min_y_ && y2 < min_y_+(max_y_-min_y_)/2.0) ||
+
+ (x2 >= min_x_ && x2 < min_x_+(max_x_-min_x_)/2.0) &&
+ (y1 >= min_y_ && y1 < min_y_+(max_y_-min_y_)/2.0) ||
+
+ (x2 >= min_x_ && x2 < min_x_+(max_x_-min_x_)/2.0) &&
+ (y2 >= min_y_ && y2 < min_y_+(max_y_-min_y_)/2.0)
+
+ ) {
+ if(ne_ != boost::shared_ptr<quadtree_node>()) {
+ ne_->find(r, x1, x2, y1, y2);
+ }
+ }
+ if(
+ (x1 >= min_x_ && x1 < min_x_+(max_x_-min_x_)/2.0) &&
+ (y1 >= min_y_+(max_y_-min_y_)/2.0 && y1 < max_y_) ||
+
+ (x1 >= min_x_ && x1 < min_x_+(max_x_-min_x_)/2.0) &&
+ (y2 >= min_y_+(max_y_-min_y_)/2.0 && y2 < max_y_) ||
+
+ (x2 >= min_x_ && x2 < min_x_+(max_x_-min_x_)/2.0) &&
+ (y1 >= min_y_+(max_y_-min_y_)/2.0 && y1 < max_y_) ||
+
+ (x2 >= min_x_ && x2 < min_x_+(max_x_-min_x_)/2.0) &&
+ (y2 >= min_y_+(max_y_-min_y_)/2.0 && y2 < max_y_)
+
+ ) {
+ if(se_ != boost::shared_ptr<quadtree_node>()) {
+ se_->find(r, x1, x2, y1, y2);
+ }
+
+ }
+
+ if(
+ (x1 >= min_x_+(max_x_-min_x_)/2.0 && x1 < max_x_) &&
+ (y1 >= min_y_ && y1 < min_y_+(max_y_-min_y_)/2.0) ||
+
+ (x1 >= min_x_+(max_x_-min_x_)/2.0 && x1 < max_x_) &&
+ (y2 >= min_y_ && y2 < min_y_+(max_y_-min_y_)/2.0) ||
+
+
+ (x2 >= min_x_+(max_x_-min_x_)/2.0 && x2 < max_x_) &&
+ (y1 >= min_y_ && y1 < min_y_+(max_y_-min_y_)/2.0) ||
+
+ (x2 >= min_x_+(max_x_-min_x_)/2.0 && x2 < max_x_) &&
+ (y2 >= min_y_ && y2 < min_y_+(max_y_-min_y_)/2.0)
+
+ ) {
+ if(nw_ != boost::shared_ptr<quadtree_node>()) {
+ nw_->find(r, x1, x2, y1, y2);
+ }
+
+ }
+ if(
+ (x1 >= min_x_+(max_x_-min_x_)/2.0 && x1 < max_x_) &&
+ (y1 >= min_y_+(max_y_-min_y_)/2.0 && y1 < max_y_) ||
+
+ (x1 >= min_x_+(max_x_-min_x_)/2.0 && x1 < max_x_) &&
+ (y2 >= min_y_+(max_y_-min_y_)/2.0 && y2 < max_y_) ||
+
+ (x2 >= min_x_+(max_x_-min_x_)/2.0 && x2 < max_x_) &&
+ (y1 >= min_y_+(max_y_-min_y_)/2.0 && y1 < max_y_) ||
+
+ (x2 >= min_x_+(max_x_-min_x_)/2.0 && x2 < max_x_) &&
+ (y2 >= min_y_+(max_y_-min_y_)/2.0 && y2 < max_y_)
+
+ ) {
+ if(sw_ != boost::shared_ptr<quadtree_node>()) {
+ sw_->find(r, x1, x2, y1, y2);
+ }
+
+ }
+ }
+ }
+
Value find(const Key &k)
{
if(v_ == 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-05-22 23:08:19 EDT (Thu, 22 May 2008)
@@ -8,6 +8,7 @@
#define BOOST_SPATIAL_INDEX_SPATIAL_INDEX_HPP
#include <vector>
+#include <deque>
namespace boost {
namespace spatial_index {
@@ -37,6 +38,11 @@
/// find element with key 'k'
virtual Value find(const Key &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;
+
/// element count in the index
virtual unsigned int elements(void) = 0;
Modified: sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test.cpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test.cpp (original)
+++ sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test.cpp 2008-05-22 23:08:19 EDT (Thu, 22 May 2008)
@@ -71,6 +71,12 @@
BOOST_CHECK_EQUAL(*it1, "test2");
std::cout << " " << *it1 << std::endl;
+ std::cerr << " --> find rectangle" << std::endl;
+ std::deque< std::vector<std::string>::iterator > d = q->find(0.0, 5.0, 0.0, 5.0);
+ for(std::deque< std::vector<std::string>::iterator >::const_iterator dit = d.begin(); dit != d.end(); ++dit) {
+ std::cerr << "Value: " << *(*dit) << std::endl;
+ }
+
std::cerr << "Elements: " << q->elements() << std::endl;
BOOST_CHECK_EQUAL(q->elements(), 6u);
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