From: mariano.consoni_at_[hidden]
Date: 2008-07-16 13:51:50
Author: mconsoni
Date: 2008-07-16 13:51:49 EDT (Wed, 16 Jul 2008)
New Revision: 47478
URL: http://svn.boost.org/trac/boost/changeset/47478
Log:
- Moved from virtual interface to template spatial_index class.
Text files modified:
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree.hpp | 28 +-
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp | 26 +-
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/spatial_index.hpp | 26 +-
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/custom_point_test.cpp | 29 +-
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test.cpp | 154 +++++++++---------
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test_rtree.cpp | 190 +++++++++++-----------
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/random_test.cpp | 28 +-
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/random_test_rtree.cpp | 29 +-
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test.cpp | 30 +-
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp | 337 ++++++++++++++++++++-------------------
10 files changed, 452 insertions(+), 425 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-07-16 13:51:49 EDT (Wed, 16 Jul 2008)
@@ -21,7 +21,7 @@
template<typename Point, typename Value>
-class quadtree : public spatial_index<Point, Value>
+class quadtree
{
private:
quadtree_node<Point,Value> root;
@@ -34,27 +34,33 @@
quadtree(const geometry::box<Point> &r)
: root(r, 1), element_count(0), node_size_(1) {}
+ quadtree(const geometry::box<Point> &r, const unsigned int M)
+ : root(r, M), element_count(0), node_size_(M) {}
+
+ quadtree(const geometry::box<Point> &r, const unsigned int m, const unsigned int M)
+ : root(r, M), element_count(0), node_size_(M) {}
+
/// remove the element with key 'k'
- virtual void remove(const Point &k)
+ void remove(const Point &k)
{
root.remove(k);
element_count--;
}
/// remove data with key 'k'
- virtual void remove(const geometry::box<Point> &k)
+ void remove(const geometry::box<Point> &k)
{
std::cerr << "Boxes not implemented in quadtrees." << std::endl;
}
- virtual void insert(const Point &k, const Value &v)
+ void insert(const Point &k, const Value &v)
{
element_count++;
root.insert(k, v);
}
- virtual void print(void)
+ void print(void)
{
std::cerr << "=================================" << std::endl;
std::cerr << "Elements: " << elements() << std::endl;
@@ -63,13 +69,13 @@
}
/// insert data with envelope 'e' with key 'k'
- virtual void insert(const geometry::box<Point> &e, const Value &v)
+ void insert(const geometry::box<Point> &e, const Value &v)
{
throw std::logic_error("Box insertion not implemented.");
}
- virtual void bulk_insert(std::vector<Value> &values, std::vector<Point> &points)
+ void bulk_insert(std::vector<Value> &values, std::vector<Point> &points)
{
// boost::xtime xt1, xt2;
// boost::xtime_get(&xt1, boost::TIME_UTC);
@@ -96,21 +102,19 @@
// std::cerr << " nsecs: " << xt2.nsec - xt1.nsec << std::endl;
}
- virtual Value find(const Point &k)
+ Value find(const Point &k)
{
return root.find(k);
}
- virtual std::deque<Value> find(const geometry::box<Point> &r)
+ std::deque<Value> find(const geometry::box<Point> &r)
{
std::deque<Value> result;
root.find(result, r);
return result;
}
- virtual unsigned int elements(void) const { return element_count; }
-
- virtual ~quadtree() {}
+ unsigned int elements(void) const { return element_count; }
};
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-07-16 13:51:49 EDT (Wed, 16 Jul 2008)
@@ -23,7 +23,7 @@
namespace spatial_index {
template<typename Point, typename Value>
- class rtree : public spatial_index<Point, Value>
+ class rtree
{
public:
rtree(const unsigned int &M, const unsigned int &m)
@@ -32,9 +32,15 @@
{
}
+ rtree(const geometry::box<Point> &b, const unsigned int &M, const unsigned int &m)
+ : element_count_(0), m_(m), M_(M),
+ root_(new rtree_node<Point, Value>(boost::shared_ptr< rtree_node<Point,Value> >(), 1))
+ {
+ }
+
/// remove the element with key 'k'
- virtual void remove(const Point &k)
+ void remove(const Point &k)
{
/// it's the same than removing a box of only one point
this->remove(geometry::box<Point>(k, k));
@@ -42,7 +48,7 @@
/// remove elements inside the box 'k'
- virtual void remove(const geometry::box<Point> &k)
+ void remove(const geometry::box<Point> &k)
{
try {
boost::shared_ptr<rtree_node<Point, Value> > l(choose_exact_leaf(k));
@@ -98,10 +104,10 @@
}
- virtual unsigned int elements(void) const { return element_count_; }
+ unsigned int elements(void) const { return element_count_; }
- virtual void print(void)
+ void print(void)
{
std::cerr << "===================================" << std::endl;
std::cerr << " Min/Max: " << m_ << " / " << M_ << std::endl;
@@ -110,7 +116,7 @@
std::cerr << "===================================" << std::endl;
}
- virtual void insert(const Point &k, const Value &v)
+ void insert(const Point &k, const Value &v)
{
// it's the same than inserting a box of only one point
this->insert(geometry::box<Point>(k,k), v);
@@ -140,7 +146,7 @@
}
- virtual void bulk_insert(std::vector<Value> &values, std::vector<Point> &points)
+ 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;
@@ -164,7 +170,7 @@
}
}
- virtual Value find(const Point &k)
+ Value find(const Point &k)
{
std::deque<Value> result;
geometry::box<geometry::point_xy<double> > query_box(k, k);
@@ -177,7 +183,7 @@
}
- virtual std::deque<Value> find(const geometry::box<Point> &r)
+ std::deque<Value> find(const geometry::box<Point> &r)
{
std::deque<Value> result;
root_->find(r, result, false);
@@ -185,8 +191,6 @@
}
- virtual ~rtree() {}
-
private:
/// number of elements
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-07-16 13:51:49 EDT (Wed, 16 Jul 2008)
@@ -17,42 +17,44 @@
namespace spatial_index {
/// spatial index interface
-template<typename Point, typename Value>
+template<typename Point, typename Value, typename Index>
class spatial_index
{
public:
+ spatial_index(const geometry::box<Point> &b, const unsigned int m, const unsigned int M) : i_(b, m, M) {}
+
/// insert data 'v' with key 'k'
- virtual void insert(const Point &k, const Value &v) = 0;
+ void insert(const Point &k, const Value &v) { i_.insert(k, v); }
/// insert data with envelope 'e' with key 'k'
- virtual void insert(const geometry::box<Point> &e, const Value &v) = 0;
+ void insert(const geometry::box<Point> &e, const Value &v) { i_.insert(e, v); }
/// remove data with key 'k'
- virtual void remove(const Point &k) = 0;
+ void remove(const Point &k) { i_.remove(k); }
/// remove data with key 'k'
- virtual void remove(const geometry::box<Point> &k) = 0;
+ void remove(const geometry::box<Point> &k) { i_.remove(k); }
/// bulk insert data from values
- virtual void bulk_insert(std::vector<Value> &values, std::vector<Point> &points) = 0;
+ void bulk_insert(std::vector<Value> &values, std::vector<Point> &points) { i_.bulk_insert(values, points); }
/// find element with key 'k'
- virtual Value find(const Point &k) = 0;
+ Value find(const Point &k) { return i_.find(k); }
/// find element in the defined rectangle
/// TODO: change container
- virtual std::deque<Value> find(const geometry::box<Point> &r) = 0;
+ std::deque<Value> find(const geometry::box<Point> &r) { return i_.find(r); }
/// element count in the index
- virtual unsigned int elements(void) const = 0;
+ unsigned int elements(void) const { return i_.elements(); }
/// debug print
- virtual void print(void) = 0;
+ void print(void) { i_.print(); }
- /// destructor
- virtual ~spatial_index(void) {}
+private:
+ Index i_;
};
} // namespace spatial_index
Modified: sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/custom_point_test.cpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/custom_point_test.cpp (original)
+++ sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/custom_point_test.cpp 2008-07-16 13:51:49 EDT (Wed, 16 Jul 2008)
@@ -98,40 +98,41 @@
geometry::box<my_2d_point > b(my_2d_point(0.0, 0.0), my_2d_point(20.0, 20.0));
- boost::shared_ptr< boost::spatial_index::spatial_index< my_2d_point , std::vector<std::string>::iterator > >
- q(new boost::spatial_index::quadtree< my_2d_point , std::vector<std::string>::iterator >(b));
+ typedef std::vector<std::string>::iterator value_type;
+
+ boost::spatial_index::spatial_index<my_2d_point, value_type, boost::spatial_index::quadtree<my_2d_point, value_type> > q(b, 0, 1);
// 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);
+// q.bulk_insert(b,e, points);
std::vector<std::string>::iterator it = data.begin();
std::cerr << " --> insert" << std::endl;
- q->insert(my_2d_point(1.0,1.0), it++);
+ q.insert(my_2d_point(1.0,1.0), it++);
std::cerr << " --> insert" << std::endl;
- q->insert(my_2d_point(2.0,1.0), it++);
+ q.insert(my_2d_point(2.0,1.0), it++);
std::cerr << " --> insert" << std::endl;
- q->insert(my_2d_point(5.0,5.0), it++);
+ q.insert(my_2d_point(5.0,5.0), it++);
std::cerr << " --> insert" << std::endl;
- q->insert(my_2d_point(1.0,6.0), it++);
+ q.insert(my_2d_point(1.0,6.0), it++);
std::cerr << " --> insert" << std::endl;
- q->insert(my_2d_point(9.0,9.0), it++);
+ q.insert(my_2d_point(9.0,9.0), it++);
std::cerr << " --> insert" << std::endl;
- q->insert(my_2d_point(9.0,8.0), it++);
+ q.insert(my_2d_point(9.0,8.0), it++);
std::vector<std::string>::iterator it1;
std::cerr << " --> find" << std::endl;
- it1 = q->find(my_2d_point(9.0,9.0));
+ it1 = q.find(my_2d_point(9.0,9.0));
BOOST_CHECK_EQUAL(*it1, "test4");
std::cout << " " << *it1 << std::endl;
std::cerr << " --> find" << std::endl;
- it1 = q->find(my_2d_point(5.0,5.0));
+ it1 = q.find(my_2d_point(5.0,5.0));
BOOST_CHECK_EQUAL(*it1, "test2");
std::cout << " " << *it1 << std::endl;
@@ -141,12 +142,12 @@
res.push_back("test1");
res.push_back("test2");
- std::cerr << "Elements: " << q->elements() << std::endl;
- BOOST_CHECK_EQUAL(q->elements(), 6u);
+ std::cerr << "Elements: " << q.elements() << std::endl;
+ BOOST_CHECK_EQUAL(q.elements(), 6u);
std::cerr << " --> find rectangle" << std::endl;
geometry::box<my_2d_point > query_box(my_2d_point(0.0, 0.0), my_2d_point(5.0, 5.0));
- std::deque< std::vector<std::string>::iterator > d = q->find(query_box);
+ 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) {
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-07-16 13:51:49 EDT (Wed, 16 Jul 2008)
@@ -103,84 +103,86 @@
ids.push_back(i);
}
- 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));
+ typedef geometry::point_xy<double> point_type;
+ typedef unsigned int value_type;
- // load data
- std::cerr << " --> bulk insert" << std::endl;
- std::vector<unsigned int>::iterator b, e;
-// b = ids.begin();
-// e = ids.end();
-
- start = time(NULL);
- q->bulk_insert(ids, points);
- std::cerr << "Insertion time: " << time(NULL) - start << " seconds." << std::endl;
-
- // -- wait to check memory
-// std::cerr << "check memory --> After Building Index." << std::endl;
-// sleep(5);
- // -- wait to check memory
-
- // search
- std::vector< geometry::point_xy<double> > search_positions;
- std::vector<unsigned int> search_data;
- for(unsigned int j=0; j < find_count; j++) {
- unsigned int pos = (int) drandom(points.size());
-
- search_positions.push_back(points[pos]);
- search_data.push_back(pos);
- }
-
-
- start = time(NULL);
- 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++) {
- 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(i, search_data[j]);
- }
- 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;
-
-// std::cerr << " --> complete removal tests" << std::endl;
-// unsigned int total = q->elements();
-// for(unsigned int j=0; j < total; j++) {
-// unsigned int e = q->elements();
-// q->remove(points[total-j-1]);
-// BOOST_CHECK_EQUAL(e, q->elements()+1);
-// // std::cerr << "Elements: " << e << std::endl;
-// }
-// q->print();
-// std::cerr << "Elements: " << q->elements() << std::endl;
- // std::cerr << std::endl;
+ boost::spatial_index::spatial_index<point_type, value_type, boost::spatial_index::quadtree<point_type, value_type> > q(plane, 0, 1);
- return 0;
+ // load data
+ std::cerr << " --> bulk insert" << std::endl;
+ std::vector<unsigned int>::iterator b, e;
+ // b = ids.begin();
+ // e = ids.end();
+
+ start = time(NULL);
+ q.bulk_insert(ids, points);
+ std::cerr << "Insertion time: " << time(NULL) - start << " seconds." << std::endl;
+
+ // -- wait to check memory
+ // std::cerr << "check memory --> After Building Index." << std::endl;
+ // sleep(5);
+ // -- wait to check memory
+
+ // search
+ std::vector< geometry::point_xy<double> > search_positions;
+ std::vector<unsigned int> search_data;
+ for(unsigned int j=0; j < find_count; j++) {
+ unsigned int pos = (int) drandom(points.size());
+
+ search_positions.push_back(points[pos]);
+ search_data.push_back(pos);
+ }
+
+
+ start = time(NULL);
+ 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++) {
+ 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(i, search_data[j]);
+ }
+ 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;
+
+ // std::cerr << " --> complete removal tests" << std::endl;
+ // unsigned int total = q.elements();
+ // for(unsigned int j=0; j < total; j++) {
+ // unsigned int e = q.elements();
+ // q.remove(points[total-j-1]);
+ // BOOST_CHECK_EQUAL(e, q.elements()+1);
+ // // std::cerr << "Elements: " << e << std::endl;
+ // }
+ // q.print();
+ // std::cerr << "Elements: " << q.elements() << std::endl;
+ // std::cerr << 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-07-16 13:51:49 EDT (Wed, 16 Jul 2008)
@@ -62,18 +62,18 @@
double drandom(unsigned int upper_bound)
{
- double r; /* random value in range [0,1) */
- long int M; /* user supplied upper boundary */
+ double r; /* random value in range [0,1) */
+ long int M; /* user supplied upper boundary */
- struct timeval tv;
- struct timezone tz;
- gettimeofday(&tv, &tz);
- srand(tv.tv_usec);
-
- M = upper_bound; /* Choose M. Upper bound */
- r = ( (double)rand() / ((double)(RAND_MAX)+(double)(1)) );
-
- return r * M;
+ struct timeval tv;
+ struct timezone tz;
+ gettimeofday(&tv, &tz);
+ srand(tv.tv_usec);
+
+ M = upper_bound; /* Choose M. Upper bound */
+ r = ( (double)rand() / ((double)(RAND_MAX)+(double)(1)) );
+
+ return r * M;
}
@@ -99,88 +99,92 @@
ids.push_back(i);
}
- 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 >(16, 8));
+ typedef geometry::point_xy<double> point_type;
+ typedef unsigned int value_type;
+
+ geometry::box<point_type> plane;
+
+ boost::spatial_index::spatial_index<point_type, value_type, boost::spatial_index::rtree<point_type, value_type> > q(plane, 16, 8);
+
+ // load data
+ std::cerr << " --> bulk insert" << std::endl;
+ std::vector<unsigned int>::iterator b, e;
+ // b = ids.begin();
+ // e = ids.end();
+
+ start = time(NULL);
+ q.bulk_insert(ids, points);
+ std::cerr << "Insertion time: " << time(NULL) - start << " seconds." << std::endl;
+
+ // std::cerr << "Elements: " << q.elements() << std::endl;
+
+ // q.print();
+
+ // -- wait to check memory
+ // std::cerr << "check memory --> After Building Index." << std::endl;
+ // sleep(5);
+ // -- wait to check memory
+
+ // search
+ std::vector< geometry::point_xy<double> > search_positions;
+ std::vector<unsigned int> search_data;
+ for(unsigned int j=0; j < find_count; j++) {
+ unsigned int pos = (int) drandom(points.size());
+
+ search_positions.push_back(points[pos]);
+ search_data.push_back(pos);
+ }
+
+
+ start = time(NULL);
+ std::deque<unsigned int> d = q.find(query_box);
+ std::cerr << " --> find rectangle" << std::endl;
+ BOOST_CHECK_EQUAL(rect_count, d.size());
+ // for(std::deque<unsigned int>::const_iterator it = d.begin(); it != d.end(); ++it) {
+ // std::cerr << "r: " << *it << std::endl;
+ // }
+ 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++) {
+ 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(i, search_data[j]);
+ }
+ 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++) {
+ q.remove(geometry::box<geometry::point_xy<double> >(search_positions[j], 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;
- // load data
- std::cerr << " --> bulk insert" << std::endl;
- std::vector<unsigned int>::iterator b, e;
- // b = ids.begin();
- // e = ids.end();
-
- start = time(NULL);
- q->bulk_insert(ids, points);
- std::cerr << "Insertion time: " << time(NULL) - start << " seconds." << std::endl;
-
-// std::cerr << "Elements: " << q->elements() << std::endl;
-
-// q->print();
-
- // -- wait to check memory
- // std::cerr << "check memory --> After Building Index." << std::endl;
- // sleep(5);
- // -- wait to check memory
-
- // search
- std::vector< geometry::point_xy<double> > search_positions;
- std::vector<unsigned int> search_data;
- for(unsigned int j=0; j < find_count; j++) {
- unsigned int pos = (int) drandom(points.size());
-
- search_positions.push_back(points[pos]);
- search_data.push_back(pos);
- }
-
-
- start = time(NULL);
- std::deque<unsigned int> d = q->find(query_box);
- std::cerr << " --> find rectangle" << std::endl;
- BOOST_CHECK_EQUAL(rect_count, d.size());
-// for(std::deque<unsigned int>::const_iterator it = d.begin(); it != d.end(); ++it) {
-// std::cerr << "r: " << *it << std::endl;
-// }
- 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++) {
- 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(i, search_data[j]);
- }
- 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++) {
- q->remove(geometry::box<geometry::point_xy<double> >(search_positions[j], 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;
-
-// std::cerr << " --> complete removal tests" << std::endl;
-// unsigned int total = q->elements();
-// for(unsigned int j=0; j < total; j++) {
-// // unsigned int e = q->elements();
-// q->remove(geometry::box<geometry::point_xy<double> >(points[j], points[j]));
-// // q->print();
-// // BOOST_CHECK_EQUAL(e, q->elements()+1);
-// // std::cerr << "Elements: " << e << std::endl;
-// }
-// std::cerr << std::endl;
-// q->print();
+ // std::cerr << " --> complete removal tests" << std::endl;
+ // unsigned int total = q.elements();
+ // for(unsigned int j=0; j < total; j++) {
+ // // unsigned int e = q.elements();
+ // q.remove(geometry::box<geometry::point_xy<double> >(points[j], points[j]));
+ // // q.print();
+ // // BOOST_CHECK_EQUAL(e, q.elements()+1);
+ // // std::cerr << "Elements: " << e << std::endl;
+ // }
+ // std::cerr << std::endl;
+ // q.print();
- return 0;
+ return 0;
}
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-07-16 13:51:49 EDT (Wed, 16 Jul 2008)
@@ -21,18 +21,18 @@
double drandom(unsigned int upper_bound)
{
- double r; /* random value in range [0,1) */
- long int M; /* user supplied upper boundary */
+ double r; /* random value in range [0,1) */
+ long int M; /* user supplied upper boundary */
- struct timeval tv;
- struct timezone tz;
- gettimeofday(&tv, &tz);
- srand(tv.tv_usec);
+ struct timeval tv;
+ struct timezone tz;
+ gettimeofday(&tv, &tz);
+ srand(tv.tv_usec);
- M = upper_bound; /* Choose M. Upper bound */
- r = ( (double)rand() / ((double)(RAND_MAX)+(double)(1)) );
+ M = upper_bound; /* Choose M. Upper bound */
+ r = ( (double)rand() / ((double)(RAND_MAX)+(double)(1)) );
- return r * M;
+ return r * M;
}
@@ -51,8 +51,10 @@
// 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> , unsigned int > >
- q(new boost::spatial_index::quadtree<geometry::point_xy<double>, unsigned int>(plane));
+ typedef geometry::point_xy<double> point_type;
+ typedef unsigned int value_type;
+
+ boost::spatial_index::spatial_index<point_type, value_type, boost::spatial_index::quadtree<point_type, value_type> > q(plane, 0, 1);
// generate random data
for(unsigned int i = 0; i < points_count; i++) {
@@ -70,7 +72,7 @@
// std::vector<unsigned int>::iterator b, e;
// b = ids.begin();
// e = ids.end();
- q->bulk_insert(ids, points);
+ q.bulk_insert(ids, points);
// search
std::vector<geometry::point_xy<double> > search_positions;
@@ -85,7 +87,7 @@
// search data and compare
for(unsigned int j=0; j < find_count; j++) {
- unsigned int i = 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])
<< ") --> " << i << std::endl;
Modified: sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/random_test_rtree.cpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/random_test_rtree.cpp (original)
+++ sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/random_test_rtree.cpp 2008-07-16 13:51:49 EDT (Wed, 16 Jul 2008)
@@ -21,18 +21,18 @@
double drandom(unsigned int upper_bound)
{
- double r; /* random value in range [0,1) */
- long int M; /* user supplied upper boundary */
+ double r; /* random value in range [0,1) */
+ long int M; /* user supplied upper boundary */
- struct timeval tv;
- struct timezone tz;
- gettimeofday(&tv, &tz);
- srand(tv.tv_usec);
+ struct timeval tv;
+ struct timezone tz;
+ gettimeofday(&tv, &tz);
+ srand(tv.tv_usec);
- M = upper_bound; /* Choose M. Upper bound */
- r = ( (double)rand() / ((double)(RAND_MAX)+(double)(1)) );
+ M = upper_bound; /* Choose M. Upper bound */
+ r = ( (double)rand() / ((double)(RAND_MAX)+(double)(1)) );
- return r * M;
+ return r * M;
}
@@ -48,8 +48,11 @@
// 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> , unsigned int > >
- q(new boost::spatial_index::rtree<geometry::point_xy<double>, unsigned int>(8, 4));
+ typedef geometry::point_xy<double> point_type;
+ typedef unsigned int value_type;
+
+ geometry::box<point_type> plane;
+ boost::spatial_index::spatial_index<point_type, value_type, boost::spatial_index::rtree<point_type, value_type> > q(plane, 8, 4);
// generate random data
for(unsigned int i = 0; i < points_count; i++) {
@@ -67,7 +70,7 @@
// std::vector<unsigned int>::iterator b, e;
// b = ids.begin();
// e = ids.end();
- q->bulk_insert(ids, points);
+ q.bulk_insert(ids, points);
// search
std::vector<geometry::point_xy<double> > search_positions;
@@ -82,7 +85,7 @@
// search data and compare
for(unsigned int j=0; j < find_count; j++) {
- unsigned int i = 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])
<< ") --> " << i << std::endl;
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-07-16 13:51:49 EDT (Wed, 16 Jul 2008)
@@ -35,40 +35,42 @@
geometry::box<geometry::point_xy<double> > b(geometry::point_xy<double>(0.0, 0.0), geometry::point_xy<double>(20.0, 20.0));
- boost::shared_ptr< boost::spatial_index::spatial_index< geometry::point_xy<double> , std::vector<std::string>::iterator > >
- q(new boost::spatial_index::quadtree< geometry::point_xy<double> , std::vector<std::string>::iterator >(b));
+ typedef geometry::point_xy<double> point_type;
+ typedef std::vector<std::string>::iterator value_type;
+
+ boost::spatial_index::spatial_index<point_type, value_type, boost::spatial_index::quadtree<point_type, value_type> > q(b, 0, 1);
// 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);
+// q.bulk_insert(b,e, points);
std::vector<std::string>::iterator it = data.begin();
std::cerr << " --> insert" << std::endl;
- q->insert(geometry::point_xy<double>(1.0,1.0), it++);
+ 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++);
+ 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++);
+ 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++);
+ 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++);
+ 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++);
+ q.insert(geometry::point_xy<double>(9.0,8.0), it++);
std::vector<std::string>::iterator it1;
std::cerr << " --> find" << std::endl;
- it1 = q->find(geometry::point_xy<double>(9.0,9.0));
+ 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));
+ it1 = q.find(geometry::point_xy<double>(5.0,5.0));
BOOST_CHECK_EQUAL(*it1, "test2");
std::cout << " " << *it1 << std::endl;
@@ -78,12 +80,12 @@
res.push_back("test1");
res.push_back("test2");
- std::cerr << "Elements: " << q->elements() << std::endl;
- BOOST_CHECK_EQUAL(q->elements(), 6u);
+ 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);
+ 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) {
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-07-16 13:51:49 EDT (Wed, 16 Jul 2008)
@@ -17,182 +17,185 @@
int test_main(int, char* [])
{
- {
- 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 >(4, 2));
+ typedef geometry::point_xy<double> point_type;
+ typedef unsigned int value_type;
- std::cerr << std::endl;
- std::cerr << " --> bulk insert" << std::endl;
- std::cerr << std::endl;
+ geometry::box<point_type> b;
- std::vector<unsigned int> data;
- std::vector< geometry::point_xy<double> > points;
+ {
+ boost::spatial_index::spatial_index<point_type, value_type, boost::spatial_index::rtree<point_type, value_type> > q(b, 4, 2);
- 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));
+ std::cerr << std::endl;
+ std::cerr << " --> bulk insert" << std::endl;
+ std::cerr << std::endl;
- data.push_back(1);
- data.push_back(2);
- data.push_back(3);
- data.push_back(4);
- data.push_back(5);
+ std::vector<unsigned int> data;
+ std::vector< geometry::point_xy<double> > points;
- q->bulk_insert(data, 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));
-// q->print();
- }
+ data.push_back(1);
+ data.push_back(2);
+ data.push_back(3);
+ data.push_back(4);
+ data.push_back(5);
- std::cerr << std::endl;
- std::cerr << " --> end bulk insert" << std::endl;
- std::cerr << std::endl;
+ 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 >(4, 2));
- 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));
- geometry::box<geometry::point_xy<double> > e4(geometry::point_xy<double>(5.0, 5.0), geometry::point_xy<double>(8.0, 8.0));
- geometry::box<geometry::point_xy<double> > e5(geometry::point_xy<double>(7.0, 4.0), geometry::point_xy<double>(12.0, 7.0));
-
-
- geometry::box<geometry::point_xy<double> > e6(geometry::point_xy<double>(5.0, 5.0), geometry::point_xy<double>(9.0, 10.0));
- geometry::box<geometry::point_xy<double> > e7(geometry::point_xy<double>(7.0, 7.0), geometry::point_xy<double>(12.0, 12.0));
-
- geometry::box<geometry::point_xy<double> > e8(geometry::point_xy<double>(1.0, 5.0), geometry::point_xy<double>(2.0, 10.0));
- geometry::box<geometry::point_xy<double> > e9(geometry::point_xy<double>(1.0, 1.0), geometry::point_xy<double>(3.0, 3.0));
- geometry::box<geometry::point_xy<double> > e10(geometry::point_xy<double>(1.5, 1.0), geometry::point_xy<double>(2.5, 3.0));
- geometry::box<geometry::point_xy<double> > e11(geometry::point_xy<double>(1.0, 0.0), geometry::point_xy<double>(2.0, 3.0));
-
- 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>(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));
-
- geometry::box<geometry::point_xy<double> > e16(geometry::point_xy<double>(7.0, 7.0), geometry::point_xy<double>(8.8,8.8));
- geometry::box<geometry::point_xy<double> > e17(geometry::point_xy<double>(8.0, 9.0), geometry::point_xy<double>(9.0,10.0));
- geometry::box<geometry::point_xy<double> > e18(geometry::point_xy<double>(10.0, 10.0), geometry::point_xy<double>(11.0,11.0));
- geometry::box<geometry::point_xy<double> > e19(geometry::point_xy<double>(10.0, 11.0), geometry::point_xy<double>(12.0,12.5));
- geometry::box<geometry::point_xy<double> > e20(geometry::point_xy<double>(11.0, 10.0), geometry::point_xy<double>(14.0,14.0));
- geometry::box<geometry::point_xy<double> > e21(geometry::point_xy<double>(12.0, 12.0), geometry::point_xy<double>(14.0,14.0));
- geometry::box<geometry::point_xy<double> > e22(geometry::point_xy<double>(12.0, 12.0), geometry::point_xy<double>(12.5,12.5));
- geometry::box<geometry::point_xy<double> > e23(geometry::point_xy<double>(13.0, 11.0), geometry::point_xy<double>(13.5,11.5));
- geometry::box<geometry::point_xy<double> > e24(geometry::point_xy<double>(13.0, 12.0), geometry::point_xy<double>(13.5,12.5));
- geometry::box<geometry::point_xy<double> > e25(geometry::point_xy<double>(13.0, 13.0), geometry::point_xy<double>(13.5,13.5));
-
- geometry::box<geometry::point_xy<double> > e26(geometry::point_xy<double>(11.0, 13.0), geometry::point_xy<double>(13.5,15.5));
- geometry::box<geometry::point_xy<double> > e27(geometry::point_xy<double>(11.0, 13.0), geometry::point_xy<double>(13.5,13.5));
-
-
- geometry::box<geometry::point_xy<double> > e28(geometry::point_xy<double>(9.0, 13.0), geometry::point_xy<double>(10.0,14.0));
- geometry::box<geometry::point_xy<double> > e29(geometry::point_xy<double>(9.0, 10.0), geometry::point_xy<double>(15.0,15.0));
-
- geometry::box<geometry::point_xy<double> > e30(geometry::point_xy<double>(9.0, 13.0), geometry::point_xy<double>(9.5,14.0));
- geometry::box<geometry::point_xy<double> > e31(geometry::point_xy<double>(10.0, 10.0), geometry::point_xy<double>(14.0,15.0));
-
-
-
- std::cerr << " --> insert env" << std::endl;
- q->insert(e1, 1);
- q->insert(e2, 2);
- q->insert(e3, 3);
- q->insert(e4, 4);
- q->insert(e5, 5);
-// q->print();
-
- q->insert(e6, 6);
- q->insert(e7, 7);
-// q->print();
-
- q->insert(e8, 8);
- q->insert(e9, 9);
- q->insert(e10, 10);
- q->insert(e11, 11);
-
- q->insert(e12, 12);
- q->insert(e13, 13);
- q->insert(e14, 14);
- q->insert(e15, 15);
-
-// q->print();
-
- q->insert(e16, 16);
- q->insert(e17, 17);
- q->insert(e18, 18);
- q->insert(e19, 19);
- q->insert(e20, 20);
- q->insert(e21, 21);
-
-
- q->insert(e22, 22);
- q->insert(e23, 23);
-
- q->insert(e24, 24);
- q->insert(e25, 25);
-
- q->insert(e26, 26);
- q->insert(e27, 27);
-
- q->insert(e28, 28);
- q->insert(e29, 29);
-
- q->insert(e30, 30);
- q->insert(e31, 31);
-
- /// 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(), 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, 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;
- }
-
- /// 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;
- }
-
- // remove test
- std::cerr << " --> remove" << std::endl;
- q->remove(geometry::box<geometry::point_xy<double> >(geometry::point_xy<double>(10.0,10.0), geometry::point_xy<double>(12.0,13.0)));
-
- std::cerr << " --> remove" << std::endl;
- q->remove(geometry::box<geometry::point_xy<double> >(geometry::point_xy<double>(7.0,4.0), geometry::point_xy<double>(12.0,7.0)));
-
- std::cerr << " --> remove" << std::endl;
- q->remove(geometry::box<geometry::point_xy<double> >(geometry::point_xy<double>(10.0,12.0), geometry::point_xy<double>(13.0,13.0)));
-
- std::cerr << " --> remove" << std::endl;
- q->remove(geometry::box<geometry::point_xy<double> >(geometry::point_xy<double>(10.0,10.0), geometry::point_xy<double>(11.0,11.0)));
- q->print();
+ /// insertion tests
+ boost::spatial_index::spatial_index<point_type, value_type, boost::spatial_index::rtree<point_type, value_type> > q(b, 4, 2);
+
- return 0;
+ 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));
+ geometry::box<geometry::point_xy<double> > e4(geometry::point_xy<double>(5.0, 5.0), geometry::point_xy<double>(8.0, 8.0));
+ geometry::box<geometry::point_xy<double> > e5(geometry::point_xy<double>(7.0, 4.0), geometry::point_xy<double>(12.0, 7.0));
+
+
+ geometry::box<geometry::point_xy<double> > e6(geometry::point_xy<double>(5.0, 5.0), geometry::point_xy<double>(9.0, 10.0));
+ geometry::box<geometry::point_xy<double> > e7(geometry::point_xy<double>(7.0, 7.0), geometry::point_xy<double>(12.0, 12.0));
+
+ geometry::box<geometry::point_xy<double> > e8(geometry::point_xy<double>(1.0, 5.0), geometry::point_xy<double>(2.0, 10.0));
+ geometry::box<geometry::point_xy<double> > e9(geometry::point_xy<double>(1.0, 1.0), geometry::point_xy<double>(3.0, 3.0));
+ geometry::box<geometry::point_xy<double> > e10(geometry::point_xy<double>(1.5, 1.0), geometry::point_xy<double>(2.5, 3.0));
+ geometry::box<geometry::point_xy<double> > e11(geometry::point_xy<double>(1.0, 0.0), geometry::point_xy<double>(2.0, 3.0));
+
+ 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>(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));
+
+ geometry::box<geometry::point_xy<double> > e16(geometry::point_xy<double>(7.0, 7.0), geometry::point_xy<double>(8.8,8.8));
+ geometry::box<geometry::point_xy<double> > e17(geometry::point_xy<double>(8.0, 9.0), geometry::point_xy<double>(9.0,10.0));
+ geometry::box<geometry::point_xy<double> > e18(geometry::point_xy<double>(10.0, 10.0), geometry::point_xy<double>(11.0,11.0));
+ geometry::box<geometry::point_xy<double> > e19(geometry::point_xy<double>(10.0, 11.0), geometry::point_xy<double>(12.0,12.5));
+ geometry::box<geometry::point_xy<double> > e20(geometry::point_xy<double>(11.0, 10.0), geometry::point_xy<double>(14.0,14.0));
+ geometry::box<geometry::point_xy<double> > e21(geometry::point_xy<double>(12.0, 12.0), geometry::point_xy<double>(14.0,14.0));
+ geometry::box<geometry::point_xy<double> > e22(geometry::point_xy<double>(12.0, 12.0), geometry::point_xy<double>(12.5,12.5));
+ geometry::box<geometry::point_xy<double> > e23(geometry::point_xy<double>(13.0, 11.0), geometry::point_xy<double>(13.5,11.5));
+ geometry::box<geometry::point_xy<double> > e24(geometry::point_xy<double>(13.0, 12.0), geometry::point_xy<double>(13.5,12.5));
+ geometry::box<geometry::point_xy<double> > e25(geometry::point_xy<double>(13.0, 13.0), geometry::point_xy<double>(13.5,13.5));
+
+ geometry::box<geometry::point_xy<double> > e26(geometry::point_xy<double>(11.0, 13.0), geometry::point_xy<double>(13.5,15.5));
+ geometry::box<geometry::point_xy<double> > e27(geometry::point_xy<double>(11.0, 13.0), geometry::point_xy<double>(13.5,13.5));
+
+
+ geometry::box<geometry::point_xy<double> > e28(geometry::point_xy<double>(9.0, 13.0), geometry::point_xy<double>(10.0,14.0));
+ geometry::box<geometry::point_xy<double> > e29(geometry::point_xy<double>(9.0, 10.0), geometry::point_xy<double>(15.0,15.0));
+
+ geometry::box<geometry::point_xy<double> > e30(geometry::point_xy<double>(9.0, 13.0), geometry::point_xy<double>(9.5,14.0));
+ geometry::box<geometry::point_xy<double> > e31(geometry::point_xy<double>(10.0, 10.0), geometry::point_xy<double>(14.0,15.0));
+
+
+
+ std::cerr << " --> insert env" << std::endl;
+ q.insert(e1, 1);
+ q.insert(e2, 2);
+ q.insert(e3, 3);
+ q.insert(e4, 4);
+ q.insert(e5, 5);
+ // q.print();
+
+ q.insert(e6, 6);
+ q.insert(e7, 7);
+ // q.print();
+
+ q.insert(e8, 8);
+ q.insert(e9, 9);
+ q.insert(e10, 10);
+ q.insert(e11, 11);
+
+ q.insert(e12, 12);
+ q.insert(e13, 13);
+ q.insert(e14, 14);
+ q.insert(e15, 15);
+
+ // q.print();
+
+ q.insert(e16, 16);
+ q.insert(e17, 17);
+ q.insert(e18, 18);
+ q.insert(e19, 19);
+ q.insert(e20, 20);
+ q.insert(e21, 21);
+
+
+ q.insert(e22, 22);
+ q.insert(e23, 23);
+
+ q.insert(e24, 24);
+ q.insert(e25, 25);
+
+ q.insert(e26, 26);
+ q.insert(e27, 27);
+
+ q.insert(e28, 28);
+ q.insert(e29, 29);
+
+ q.insert(e30, 30);
+ q.insert(e31, 31);
+
+ /// 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(), 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, 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;
+ }
+
+ /// 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;
+ }
+
+ // remove test
+ std::cerr << " --> remove" << std::endl;
+ q.remove(geometry::box<geometry::point_xy<double> >(geometry::point_xy<double>(10.0,10.0), geometry::point_xy<double>(12.0,13.0)));
+
+ std::cerr << " --> remove" << std::endl;
+ q.remove(geometry::box<geometry::point_xy<double> >(geometry::point_xy<double>(7.0,4.0), geometry::point_xy<double>(12.0,7.0)));
+
+ std::cerr << " --> remove" << std::endl;
+ q.remove(geometry::box<geometry::point_xy<double> >(geometry::point_xy<double>(10.0,12.0), geometry::point_xy<double>(13.0,13.0)));
+
+ std::cerr << " --> remove" << std::endl;
+ q.remove(geometry::box<geometry::point_xy<double> >(geometry::point_xy<double>(10.0,10.0), geometry::point_xy<double>(11.0,11.0)));
+ q.print();
+
+ return 0;
}