From: mariano.consoni_at_[hidden]
Date: 2008-06-16 08:09:11
Author: mconsoni
Date: 2008-06-16 08:09:10 EDT (Mon, 16 Jun 2008)
New Revision: 46417
URL: http://svn.boost.org/trac/boost/changeset/46417
Log:
- Regression working again.
Text files modified:
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree.hpp | 90 ++++++++++++++++++--------------
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree_node.hpp | 2
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp | 28 ++++++++-
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/spatial_index.hpp | 4
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test.cpp | 17 +++--
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/random_test.cpp | 44 +++++++-------
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp | 111 +++++++++++++++++++++------------------
7 files changed, 169 insertions(+), 127 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-16 08:09:10 EDT (Mon, 16 Jun 2008)
@@ -26,46 +26,58 @@
unsigned int node_size_;
public:
- quadtree(const geometry::box<Point> &r)
- : root(r, 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 Point &k, const Value &v)
- {
- element_count++;
- root.insert(k, 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<Point>::iterator it_point;
- it_point = v.begin();
- Value it_data = v_begin;
- while(it_data != v_end && it_point != v.end()) {
- insert(*it_point, it_data);
-
- it_data++;
- it_point++;
-
- //counter++;
- //if(counter%10000 == 0) {
- //std::cerr << "counter: [" << counter << "]" << std::endl;
- //}
- }
-
-// boost::xtime_get(&xt2, boost::TIME_UTC);
-// std::cerr << "secs: " << xt2.sec - xt1.sec;
-// std::cerr << " nsecs: " << xt2.nsec - xt1.nsec << std::endl;
- }
-
- virtual Value find(const Point &k)
- {
- return root.find(k);
- }
+ virtual void insert(const Point &k, const Value &v)
+ {
+ element_count++;
+ root.insert(k, v);
+ }
+
+ virtual void print(void) const
+ {
+ std::cerr << "Not implemented." << std::endl;
+ }
+
+ /// insert data with envelope 'e' with key 'k'
+ virtual void insert(const geometry::box<Point> &e, const Value &v)
+ {
+ std::cerr << "Box insertion not implemented." << std::endl;
+ }
+
+
+ virtual void bulk_insert(std::vector<Value> &values, std::vector<Point> &points)
+ {
+ // boost::xtime xt1, xt2;
+ // boost::xtime_get(&xt1, boost::TIME_UTC);
+
+ // unsigned int counter = 0;
+
+ typename std::vector<Point>::iterator it_point;
+ typename std::vector<Value>::iterator it_value;
+ it_point = points.begin();
+ it_value = values.begin();
+ while(it_value != values.end() && it_point != points.end()) {
+ insert(*it_point, *it_value);
+
+ it_point++;
+ it_value++;
+
+ // counter++;
+ // if(counter%10000 == 0) {
+ // std::cerr << "counter: [" << counter << "]" << std::endl;
+ // }
+ }
+ // boost::xtime_get(&xt2, boost::TIME_UTC);
+ // std::cerr << "secs: " << xt2.sec - xt1.sec;
+ // std::cerr << " nsecs: " << xt2.nsec - xt1.nsec << std::endl;
+ }
+
+ virtual Value find(const Point &k)
+ {
+ return root.find(k);
+ }
virtual std::deque<Value> find(const geometry::box<Point> &r)
{
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-16 08:09:10 EDT (Mon, 16 Jun 2008)
@@ -82,7 +82,7 @@
void insert(const Point &k, const Value &v)
{
if(m_.size() < node_size_) {
- std::cerr << "Empty quadtree_node --> inserting (" << *v << ")" << std::endl;
+// std::cerr << "Empty quadtree_node --> inserting (" << v << ")" << std::endl;
m_[k] = v;
} else {
// std::cerr << "Quadtree_Node division: ";
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 08:09:10 EDT (Mon, 16 Jun 2008)
@@ -79,12 +79,30 @@
element_count++;
}
- virtual void bulk_insert(Value &v_begin, Value &v_end, std::vector<Point> &v)
+ virtual void bulk_insert(std::vector<Value> &values, std::vector<Point> &points)
{
+ typename std::vector<Point>::iterator it_point;
+ typename std::vector<Value>::iterator it_value;
+ it_point = points.begin();
+ it_value = values.begin();
+ while(it_value != values.end() && it_point != points.end()) {
+ geometry::box<geometry::point_xy<double> > box(*it_point, *it_point);
+ insert(box, *it_value);
+
+ it_point++;
+ it_value++;
+ }
}
virtual Value find(const Point &k)
{
+ std::deque<Value> result;
+ geometry::box<geometry::point_xy<double> > query_box(k, k);
+
+ root_->find(query_box, result);
+ if(result.size() >= 1) {
+ return result[0];
+ }
return Value();
}
@@ -171,10 +189,10 @@
unsigned int remaining = nodes.size() - index; // 2 because of the seeds
- std::cerr << "Remaining: " << remaining;
- std::cerr << " n1: " << n1->elements();
- std::cerr << " n2: " << n2->elements();
- std::cerr << std::endl;
+// std::cerr << "Remaining: " << remaining;
+// std::cerr << " n1: " << n1->elements();
+// std::cerr << " n2: " << n2->elements();
+// std::cerr << std::endl;
if(n1->elements() + remaining == m_) {
n1->add_value(it->first, it->second);
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-16 08:09:10 EDT (Mon, 16 Jun 2008)
@@ -38,8 +38,8 @@
/// insert data with envelope 'e' with key 'k'
virtual void insert(const geometry::box<Point> &e, const Value &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;
+ /// bulk insert data from values
+ virtual void bulk_insert(std::vector<Value> &values, std::vector<Point> &points) = 0;
/// find element with key 'k'
virtual Value find(const Point &k) = 0;
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-16 08:09:10 EDT (Mon, 16 Jun 2008)
@@ -103,17 +103,17 @@
ids.push_back(i);
}
- boost::shared_ptr< boost::spatial_index::spatial_index< geometry::point_xy<double> , std::vector<unsigned int>::iterator > >
- q(new boost::spatial_index::quadtree< geometry::point_xy<double>, std::vector<unsigned int>::iterator >(plane));
+ boost::shared_ptr< boost::spatial_index::spatial_index< geometry::point_xy<double> , unsigned int > >
+ q(new boost::spatial_index::quadtree< geometry::point_xy<double>, unsigned int >(plane));
// load data
std::cerr << " --> bulk insert" << std::endl;
std::vector<unsigned int>::iterator b, e;
- b = ids.begin();
- e = ids.end();
+// b = ids.begin();
+// e = ids.end();
start = time(NULL);
- q->bulk_insert(b,e, points);
+ q->bulk_insert(ids, points);
std::cerr << "Insertion time: " << time(NULL) - start << " seconds." << std::endl;
// -- wait to check memory
@@ -133,19 +133,20 @@
start = time(NULL);
- std::deque< std::vector<unsigned int>::iterator > d = q->find(query_box);
+ std::deque<unsigned int> d = q->find(query_box);
std::cerr << " --> find rectangle" << std::endl;
BOOST_CHECK_EQUAL(rect_count, d.size());
std::cerr << "Retrieve (rectangle with " << d.size() << " elements) time: " << time(NULL) - start << " seconds." << std::endl;
start = time(NULL);
for(unsigned int j=0; j < find_count; j++) {
- std::vector<unsigned int>::iterator it = q->find(search_positions[j]);
+ unsigned int i = q->find(search_positions[j]);
+// std::vector<unsigned int>::iterator it = q->find(search_positions[j]);
//std::cout << search_data[j]
// << " - found in (" << search_positions[j].first << "," << search_positions[j].second << ") --> "
// << *it << std::endl;
- BOOST_CHECK_EQUAL(*it, search_data[j]);
+ BOOST_CHECK_EQUAL(i, search_data[j]);
}
std::cerr << "Retrieve time: " << time(NULL) - start << " seconds." << std::endl;
Modified: sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/random_test.cpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/random_test.cpp (original)
+++ sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/random_test.cpp 2008-06-16 08:09:10 EDT (Mon, 16 Jun 2008)
@@ -51,26 +51,26 @@
// number of points to find on the search phase
const unsigned int find_count = 50;
- boost::shared_ptr< boost::spatial_index::spatial_index< geometry::point_xy<double> , std::vector<unsigned int>::iterator > >
- q(new boost::spatial_index::quadtree< geometry::point_xy<double>, std::vector<unsigned int>::iterator >(plane));
+ boost::shared_ptr< boost::spatial_index::spatial_index< geometry::point_xy<double> , unsigned int > >
+ q(new boost::spatial_index::quadtree<geometry::point_xy<double>, unsigned int>(plane));
- // generate random data
- for(unsigned int i = 0; i < points_count; i++) {
- double x = drandom((int) MAX_X);
- double y = drandom((int) MAX_Y);
-
- ids.push_back(i);
- points.push_back(geometry::point_xy<double>(x, y));
-
- // std::cerr << "insert " << i << " -> (" << x << ", " << y << ")" << std::endl;
- }
-
- // insert data
- std::cerr << " --> bulk insert" << std::endl;
- std::vector<unsigned int>::iterator b, e;
- b = ids.begin();
- e = ids.end();
- q->bulk_insert(b,e, points);
+ // generate random data
+ for(unsigned int i = 0; i < points_count; i++) {
+ double x = drandom((int) MAX_X);
+ double y = drandom((int) MAX_Y);
+
+ ids.push_back(i);
+ points.push_back(geometry::point_xy<double>(x, y));
+
+ // std::cerr << "insert " << i << " -> (" << x << ", " << y << ")" << std::endl;
+ }
+
+ // insert data
+ std::cerr << " --> bulk insert" << std::endl;
+ // std::vector<unsigned int>::iterator b, e;
+ // b = ids.begin();
+ // e = ids.end();
+ q->bulk_insert(ids, points);
// search
std::vector<geometry::point_xy<double> > search_positions;
@@ -85,13 +85,13 @@
// search data and compare
for(unsigned int j=0; j < find_count; j++) {
- std::vector<unsigned int>::iterator it = q->find(search_positions[j]);
+ unsigned int i = q->find(search_positions[j]);
std::cout << search_data[j]
<< " - found in (" << geometry::get<0>(search_positions[j]) << "," << geometry::get<1>(search_positions[j])
- << ") --> " << *it << std::endl;
+ << ") --> " << i << std::endl;
// check if the retrieved data is equal to the stored data
- BOOST_CHECK_EQUAL(*it, search_data[j]);
+ BOOST_CHECK_EQUAL(i, search_data[j]);
}
return 0;
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 08:09:10 EDT (Mon, 16 Jun 2008)
@@ -16,36 +16,46 @@
int test_main(int, char* [])
{
- std::vector<std::string> data;
- std::vector< geometry::point_xy<double> > points;
+ geometry::box<geometry::point_xy<double> > b(geometry::point_xy<double>(0.0, 0.0), geometry::point_xy<double>(20.0, 20.0));
- data.push_back("test0");
- data.push_back("test1");
- data.push_back("test2");
- data.push_back("test3");
- data.push_back("test4");
- data.push_back("test5");
-
- points.push_back(geometry::point_xy<double>(1.0,1.0));
- points.push_back(geometry::point_xy<double>(2.0,1.0));
- points.push_back(geometry::point_xy<double>(5.0,5.0));
- points.push_back(geometry::point_xy<double>(1.0,6.0));
- points.push_back(geometry::point_xy<double>(9.0,9.0));
- points.push_back(geometry::point_xy<double>(9.0,8.0));
+ {
+ boost::shared_ptr< boost::spatial_index::spatial_index< geometry::point_xy<double> , unsigned int > >
+ q(new boost::spatial_index::rtree< geometry::point_xy<double> , unsigned int >(b, 4, 2, 4));
+
+ std::cerr << std::endl;
+ std::cerr << " --> bulk insert" << std::endl;
+ std::cerr << std::endl;
+
+ std::vector<unsigned int> data;
+ std::vector< geometry::point_xy<double> > points;
+
+ points.push_back(geometry::point_xy<double>(2.0,2.0));
+ points.push_back(geometry::point_xy<double>(1.0,3.0));
+ points.push_back(geometry::point_xy<double>(1.5,5.0));
+ points.push_back(geometry::point_xy<double>(5.5,5.0));
+ points.push_back(geometry::point_xy<double>(2.0,5.0));
+
+ data.push_back(1);
+ data.push_back(2);
+ data.push_back(3);
+ data.push_back(4);
+ data.push_back(5);
- geometry::box<geometry::point_xy<double> > b(geometry::point_xy<double>(0.0, 0.0), geometry::point_xy<double>(20.0, 20.0));
+ q->bulk_insert(data, points);
+
+ q->print();
+ }
+
+ std::cerr << std::endl;
+ std::cerr << " --> end bulk insert" << std::endl;
+ std::cerr << std::endl;
+
+
+ /// insertion tests
boost::shared_ptr< boost::spatial_index::spatial_index< geometry::point_xy<double> , unsigned int > >
q(new boost::spatial_index::rtree< geometry::point_xy<double> , unsigned int >(b, 4, 2, 4));
-// std::cerr << " --> bulk insert" << std::endl;
-// std::vector<std::string>::iterator b, e;
-// b = data.begin();
-// e = data.end();
-// q->bulk_insert(b,e, points);
-
-// std::vector<std::string>::iterator it = data.begin();
-
geometry::box<geometry::point_xy<double> > e1(geometry::point_xy<double>(2.0, 2.0), geometry::point_xy<double>(4.0, 4.0));
geometry::box<geometry::point_xy<double> > e2(geometry::point_xy<double>(0.0, 1.0), geometry::point_xy<double>(2.0, 2.0));
geometry::box<geometry::point_xy<double> > e3(geometry::point_xy<double>(5.0, 4.0), geometry::point_xy<double>(6.0, 6.0));
@@ -63,7 +73,7 @@
geometry::box<geometry::point_xy<double> > e12(geometry::point_xy<double>(10.0, 10.0), geometry::point_xy<double>(12.0, 13.0));
geometry::box<geometry::point_xy<double> > e13(geometry::point_xy<double>(10.0, 12.0), geometry::point_xy<double>(13.0, 13.0));
- geometry::box<geometry::point_xy<double> > e14(geometry::point_xy<double>(10.0, 13.0), geometry::point_xy<double>(12.0, 13.5));
+ geometry::box<geometry::point_xy<double> > e14(geometry::point_xy<double>(10.0, 13.0), geometry::point_xy<double>(10.0, 13.0));
geometry::box<geometry::point_xy<double> > e15(geometry::point_xy<double>(10.0, 13.0), geometry::point_xy<double>(12.0, 14.0));
@@ -91,39 +101,40 @@
q->insert(e15, 15);
q->print();
- std::cerr << " --> find rectangle" << std::endl;
+ /// find everything overlaping with an envelope
+ std::cerr << " --> find in envelope" << std::endl;
+
+ /// expected result
+ std::deque<unsigned int> result;
+ result.push_back(2);
+ result.push_back(1);
+ result.push_back(9);
+ result.push_back(10);
+ result.push_back(11);
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);
+ BOOST_CHECK_EQUAL(d.size(), 5u);
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++]);
+ BOOST_CHECK_EQUAL(*dit, result[i++]);
}
+ /// find individual points (not found)
+ {
+ std::cerr << " --> find" << std::endl;
+ unsigned int v = q->find(geometry::point_xy<double>(0.0,0.0));
+ BOOST_CHECK_EQUAL(v, 0u);
+ std::cout << "Value: " << v << std::endl;
+ }
-// std::vector<std::string>::iterator it1;
-
-// std::cerr << " --> find" << std::endl;
-// it1 = q->find(geometry::point_xy<double>(9.0,9.0));
-// BOOST_CHECK_EQUAL(*it1, "test4");
-// std::cout << " " << *it1 << std::endl;
-
-// std::cerr << " --> find" << std::endl;
-// it1 = q->find(geometry::point_xy<double>(5.0,5.0));
-// BOOST_CHECK_EQUAL(*it1, "test2");
-// std::cout << " " << *it1 << std::endl;
-
-// // expected result
-// std::vector<std::string> res;
-// res.push_back("test0");
-// res.push_back("test1");
-// res.push_back("test2");
-
-// std::cerr << "Elements: " << q->elements() << std::endl;
-// BOOST_CHECK_EQUAL(q->elements(), 6u);
-
-
+ /// find individual points (found)
+ {
+ std::cerr << " --> find" << std::endl;
+ unsigned int v = q->find(geometry::point_xy<double>(10.0,13.0));
+ BOOST_CHECK_EQUAL(v, 14u);
+ std::cout << "Value: " << v << std::endl;
+ }
return 0;
};