From: mariano.consoni_at_[hidden]
Date: 2008-06-23 07:08:46
Author: mconsoni
Date: 2008-06-23 07:08:44 EDT (Mon, 23 Jun 2008)
New Revision: 46623
URL: http://svn.boost.org/trac/boost/changeset/46623
Log:
- Remove algorithm for quadtree and tests.
Text files modified:
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree.hpp | 29 ++++----
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree_node.hpp | 126 ++++++++++++++++++++++++++++-----------
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp | 6 +
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/spatial_index.hpp | 3
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test.cpp | 18 +++++
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test_rtree.cpp | 2
6 files changed, 134 insertions(+), 50 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-23 07:08:44 EDT (Mon, 23 Jun 2008)
@@ -19,11 +19,11 @@
class quadtree : public spatial_index<Point, Value>
{
private:
- quadtree_node<Point,Value> root;
- unsigned int element_count;
+ quadtree_node<Point,Value> root;
+ unsigned int element_count;
- // number of points in each node
- unsigned int node_size_;
+ // number of points in each node
+ unsigned int node_size_;
public:
quadtree(const geometry::box<Point> &r)
@@ -33,14 +33,15 @@
/// TODO: implement
virtual void remove(const Point &k)
{
- std::cerr << "Not implemented yet." << std::endl;
+ root.remove(k);
+ element_count--;
}
/// remove data with key 'k'
/// TODO: implement
virtual void remove(const geometry::box<Point> &k)
{
- std::cerr << "Not implemented yet." << std::endl;
+ std::cerr << "Boxes not implemented in quadtrees." << std::endl;
}
@@ -94,17 +95,17 @@
return root.find(k);
}
- virtual std::deque<Value> find(const geometry::box<Point> &r)
- {
- std::deque<Value> result;
- root.find(result, r);
- return result;
- }
+ virtual std::deque<Value> find(const geometry::box<Point> &r)
+ {
+ std::deque<Value> result;
+ root.find(result, r);
+ return result;
+ }
- virtual unsigned int elements(void) { return element_count; }
+ virtual unsigned int elements(void) { return element_count; }
- virtual ~quadtree() {}
+ 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-06-23 07:08:44 EDT (Mon, 23 Jun 2008)
@@ -78,6 +78,15 @@
// "min_x: " << min_x << " min_y: " << min_y << " max_x: " << max_x << " max_y " << max_y << std::endl;
}
+ 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 insert(const Point &k, const Value &v)
{
@@ -140,10 +149,11 @@
// 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;
+// 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);
@@ -170,56 +180,102 @@
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;
}
+ return recursive_search(k);
+ }
- // 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);
+ Value recursive_search(const Point &k)
+ {
+ // IMP: maybe this could be done only one time at node creation
+ // but it will consume more memory...
- // TODO: replace with algorithm
- if(geometry::within(k, ne_box)) {
- if(ne_ != boost::shared_ptr<quadtree_node>()) {
- return ne_->find(k);
- } else {
- return Value();
- }
+ 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, 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, 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();
- }
+ }
+ 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 recursive_remove(const Point &k)
+ {
+// std::cerr << "Recursive_remove" << std::endl;
+
+// std::cerr << "Checking: (" << geometry::get<0>(k) << "," << geometry::get<1>(k) << ")" << std::endl;
+// std::cerr << "in : (" << geometry::get<0>(bounding_rectangle_.min()) << "," << geometry::get<1>(bounding_rectangle_.min()) << ") x ";
+// std::cerr << "(" << geometry::get<0>(bounding_rectangle_.max()) << "," << geometry::get<1>(bounding_rectangle_.max()) << ")" << std::endl;
+
+ // 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);
+ return;
+ } else {
+ throw std::logic_error("Not found");
+ }
+ }
+ if(geometry::within(k, se_box)) {
+ if(se_ != boost::shared_ptr<quadtree_node>()) {
+ se_->remove(k);
+ return;
+ } else {
+ throw std::logic_error("Not found");
+ }
+ }
+ if(geometry::within(k, nw_box)) {
+ if(nw_ != boost::shared_ptr<quadtree_node>()) {
+ nw_->remove(k);
+ return;
+ } else {
+ throw std::logic_error("Not found");
+ }
+ }
+ if(geometry::within(k, sw_box)) {
+ if(sw_ != boost::shared_ptr<quadtree_node>()) {
+ sw_->remove(k);
+ return;
+ } else {
+ throw std::logic_error("Not found");
+ }
+ }
+ }
+
+
};
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-23 07:08:44 EDT (Mon, 23 Jun 2008)
@@ -39,6 +39,12 @@
}
/// remove the element with key 'k'
+ virtual void remove(const Point &k)
+ {
+ this->remove(geometry::box<Point>(k, k));
+ }
+
+ /// remove the element with key 'k'
virtual void remove(const geometry::box<Point> &k)
{
try {
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-23 07:08:44 EDT (Mon, 23 Jun 2008)
@@ -30,6 +30,9 @@
virtual void insert(const geometry::box<Point> &e, const Value &v) = 0;
/// remove data with key 'k'
+ virtual void remove(const Point &k) = 0;
+
+ /// remove data with key 'k'
virtual void remove(const geometry::box<Point> &k) = 0;
/// bulk insert data from values
Modified: sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test.cpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test.cpp (original)
+++ sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test.cpp 2008-06-23 07:08:44 EDT (Mon, 23 Jun 2008)
@@ -150,6 +150,24 @@
}
std::cerr << "Retrieve time: " << time(NULL) - start << " seconds." << std::endl;
+
+ std::cerr << " --> removal tests" << std::endl;
+ for(unsigned int j=0; j < find_count/1000; j++) {
+ std::cerr << "Removal: " << j << std::endl;
+ q->remove(search_positions[j]);
+// std::cerr << "Elements: " << q->elements() << std::endl;
+ }
+ std::cerr << std::endl;
+
+ std::cerr << " --> requery test" << std::endl;
+ start = time(NULL);
+ for(unsigned int j=0; j < find_count/1000; j++) {
+ unsigned int i = q->find(search_positions[j]);
+// std::cerr << "Prev. Value: " << search_data[j] << std::endl;
+ BOOST_CHECK_EQUAL(i, 0u);
+ }
+ std::cerr << "Removal time: " << time(NULL) - start << " seconds." << std::endl;
+
return 0;
}
Modified: sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test_rtree.cpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test_rtree.cpp (original)
+++ sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test_rtree.cpp 2008-06-23 07:08:44 EDT (Mon, 23 Jun 2008)
@@ -165,7 +165,7 @@
// std::cerr << "Prev. Value: " << search_data[j] << std::endl;
BOOST_CHECK_EQUAL(i, 0u);
}
- std::cerr << "Retrieve time: " << time(NULL) - start << " seconds." << std::endl;
+ std::cerr << "Removal time: " << time(NULL) - start << " seconds." << std::endl;
return 0;
}