From: mariano.consoni_at_[hidden]
Date: 2008-07-24 11:14:45
Author: mconsoni
Date: 2008-07-24 11:14:38 EDT (Thu, 24 Jul 2008)
New Revision: 47760
URL: http://svn.boost.org/trac/boost/changeset/47760
Log:
- Limited to 80 columns.
Text files modified:
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/custom_point_test.cpp | 206 +++++++++++++++++++++------------------
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test.cpp | 115 ++++++++++++---------
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test_rtree.cpp | 40 +++++--
3 files changed, 201 insertions(+), 160 deletions(-)
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-24 11:14:38 EDT (Thu, 24 Jul 2008)
@@ -1,7 +1,13 @@
+//
+// Boost.SpatialIndex - example showing the use of a user-defined point class
+//
// 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)
+//
+// See http://www.boost.org/ for latest version.
+//
#include <boost/spatial_index.hpp>
@@ -21,7 +27,7 @@
// we define our own point
-struct my_2d_point: boost::tuple<float, float>
+struct my_2d_point: boost::tuple < float, float >
{
typedef float coordinate_type;
enum { coordinate_count = 2 };
@@ -30,27 +36,31 @@
{
get<0>() = 0.0;
get<1>() = 0.0;
-
}
+
my_2d_point(float x, float y)
{
get<0>() = x;
get<1>() = y;
}
- bool operator<(const my_2d_point &o) const { return get<0>() < o.get<0>(); }
+ bool operator<(const my_2d_point & o) const
+ {
+ return get<0> () <o. get <0> ();
+ }
- // Because the geometry::point concept shares the "get" methods with boost::tuple,
- // no more methods are needed.
+ // Because the geometry::point concept shares the "get" methods with
+ // boost::tuple, no more methods are needed.
};
-namespace geometry {
-
- template <>
- struct strategy_traits<my_2d_point, my_2d_point>
+namespace geometry
+{
+ template <>
+ struct strategy_traits < my_2d_point, my_2d_point >
{
- typedef strategy::distance::pythagoras<my_2d_point, my_2d_point> point_distance;
+ typedef strategy::distance::pythagoras < my_2d_point, my_2d_point >
+ point_distance;
typedef strategy::not_implemented point_segment_distance;
typedef strategy::not_implemented area;
typedef strategy::not_implemented within;
@@ -58,102 +68,106 @@
typedef strategy::not_implemented envelope;
};
- template <>
- struct wkt_traits<my_2d_point>
+ template <> struct wkt_traits < my_2d_point >
{
- typedef impl::wkt::stream_point<my_2d_point> stream_type;
+ typedef impl::wkt::stream_point < my_2d_point > stream_type;
};
-
-} // namespace geometry
+} // namespace geometry
-
-template <typename CH, typename TR>
-inline std::basic_ostream<CH,TR>& operator<<(std::basic_ostream<CH,TR> &os, const my_2d_point &p)
+template < typename CH, typename TR >
+inline std::basic_ostream < CH,TR > &
+operator<<(std::basic_ostream < CH, TR > &os, const my_2d_point & p)
{
- os << geometry::as_wkt<my_2d_point>(p);
- return os;
+ os << geometry::as_wkt < my_2d_point > (p);
+ return os;
}
-int test_main(int, char* [])
+int test_main(int, char *[])
{
- std::vector<std::string> data;
- std::vector< my_2d_point > points;
+ std::vector < std::string > data;
+ std::vector < my_2d_point > points;
- 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(my_2d_point(1.0,1.0));
- points.push_back(my_2d_point(2.0,1.0));
- points.push_back(my_2d_point(5.0,5.0));
- points.push_back(my_2d_point(1.0,6.0));
- points.push_back(my_2d_point(9.0,9.0));
- points.push_back(my_2d_point(9.0,8.0));
-
- geometry::box<my_2d_point > b(my_2d_point(0.0, 0.0), my_2d_point(20.0, 20.0));
-
- 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, 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);
-
- std::vector<std::string>::iterator it = data.begin();
-
- std::cerr << " --> insert" << std::endl;
- 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++);
- std::cerr << " --> insert" << std::endl;
- 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++);
- std::cerr << " --> insert" << std::endl;
- 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++);
-
-
- std::vector<std::string>::iterator it1;
-
- std::cerr << " --> find" << std::endl;
- 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));
- 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);
-
- 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);
- 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++]);
- }
+ 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(my_2d_point(1.0, 1.0));
+ points.push_back(my_2d_point(2.0, 1.0));
+ points.push_back(my_2d_point(5.0, 5.0));
+ points.push_back(my_2d_point(1.0, 6.0));
+ points.push_back(my_2d_point(9.0, 9.0));
+ points.push_back(my_2d_point(9.0, 8.0));
+
+ geometry::box < my_2d_point > b(my_2d_point(0.0, 0.0),
+ my_2d_point(20.0, 20.0));
+
+ 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, 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);
+
+ std::vector < std::string >::iterator it = data.begin();
+
+ std::cerr << " --> insert" << std::endl;
+ 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++);
+ std::cerr << " --> insert" << std::endl;
+ 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++);
+ std::cerr << " --> insert" << std::endl;
+ 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++);
+
+
+ std::vector < std::string >::iterator it1;
+
+ std::cerr << " --> find" << std::endl;
+ 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));
+ 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);
+
+ 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);
+ 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;
+ return 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-07-24 11:14:38 EDT (Thu, 24 Jul 2008)
@@ -1,7 +1,13 @@
+//
+// Boost.SpatialIndex - performance example for quadtree
+//
// 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)
+//
+// See http://www.boost.org/ for latest version.
+//
#include <boost/spatial_index.hpp>
@@ -18,13 +24,13 @@
// query rectangle
double rect_count;
-geometry::box<geometry::point_xy<double> > query_box;
+geometry::box < geometry::point_xy < double > > query_box;
-std::vector< geometry::point_xy<double> > read_data(void)
+std::vector < geometry::point_xy < double > > read_data(void)
{
- std::set< geometry::point_xy<double> > v;
- std::vector< geometry::point_xy<double> > r;
+ std::set < geometry::point_xy < double > > v;
+ std::vector < geometry::point_xy < double > > r;
std::ifstream data;
data.open("gis-data.txt");
@@ -41,20 +47,20 @@
double x, y;
data >> x;
data >> y;
- if(geometry::within(geometry::point_xy<double>(x,y), query_box)) {
+ if(geometry::within(geometry::point_xy < double >(x, y), query_box)) {
rect_count++;
}
- v.insert(geometry::point_xy<double>(x,y));
+ v.insert(geometry::point_xy < double >(x, y));
while(!data.eof()) {
data >> x;
data >> y;
- if(geometry::within(geometry::point_xy<double>(x,y), query_box)) {
+ if(geometry::within(geometry::point_xy < double >(x, y), query_box)) {
// std::cerr << "Rect: (" << x << "," << y << ")" << std::endl;
rect_count++;
}
- v.insert(geometry::point_xy<double>(x,y));
+ v.insert(geometry::point_xy < double >(x, y));
}
copy(v.begin(), v.end(), std::back_inserter(r));
return r;
@@ -63,29 +69,29 @@
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;
}
-int test_main(int, char* [])
+int test_main(int, char *[])
{
- std::vector<unsigned int> ids;
- std::vector< geometry::point_xy<double> > points = read_data();
+ std::vector < unsigned int > ids;
+ std::vector < geometry::point_xy < double > > points = read_data();
// -- wait to check memory
-// std::cerr << "check memory --> After Reading Data." << std::endl;
-// sleep(5);
+ // std::cerr << "check memory --> After Reading Data." << std::endl;
+ // sleep(5);
// -- wait to check memory
// start time
@@ -94,29 +100,33 @@
// std::cerr << "Size: " << points.size() << std::endl;
// plane
- geometry::box<geometry::point_xy<double> > plane(geometry::point_xy<double>(-130.0, 0.0), geometry::point_xy<double>(-60.0, 80.0));
+ geometry::box < geometry::point_xy < double > > plane(
+ geometry::point_xy < double >(-130.0, 0.0),
+ geometry::point_xy < double >(-60.0, 80.0));
// number of points to find on the search phase
const unsigned int find_count = 100000;
- for(unsigned int i = 0; i < points.size(); i++) {
+ for (unsigned int i = 0; i < points.size(); i++) {
ids.push_back(i);
}
- typedef geometry::point_xy<double> point_type;
+ 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, 1);
+ boost::spatial_index::spatial_index < point_type, value_type,
+ boost::spatial_index::quadtree < point_type, value_type > >q(plane, 1);
// load data
std::cerr << " --> bulk insert" << std::endl;
- std::vector<unsigned int>::iterator b, e;
+ 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 << "Insertion time: " << time(NULL) -
+ start << " seconds." << std::endl;
// -- wait to check memory
// std::cerr << "check memory --> After Building Index." << std::endl;
@@ -124,9 +134,9 @@
// -- 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++) {
+ 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]);
@@ -135,48 +145,54 @@
start = time(NULL);
- std::deque<unsigned int> 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;
+ 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++) {
+ 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 << ") --> "
+ // << " - 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 << "Retrieve time: " << time(NULL) -
+ start << " seconds." << std::endl;
+
-
std::cerr << " --> removal tests" << std::endl;
- for(unsigned int j=0; j < find_count/1000; j++) {
+ 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 << "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;
+ 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 << "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;
+ // 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;
@@ -184,6 +200,3 @@
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-24 11:14:38 EDT (Thu, 24 Jul 2008)
@@ -1,8 +1,13 @@
+//
+// Boost.SpatialIndex - performance example for quadtree
+//
// 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)
-
+//
+// See http://www.boost.org/ for latest version.
+//
#include <boost/spatial_index.hpp>
@@ -102,7 +107,8 @@
typedef geometry::point_xy<double> point_type;
typedef unsigned int value_type;
- boost::spatial_index::spatial_index<point_type, value_type, boost::spatial_index::rtree<point_type, value_type> > q(16, 8);
+ boost::spatial_index::spatial_index<point_type, value_type,
+ boost::spatial_index::rtree<point_type, value_type> > q(16, 8);
// load data
std::cerr << " --> bulk insert" << std::endl;
@@ -112,7 +118,8 @@
start = time(NULL);
q.bulk_insert(ids, points);
- std::cerr << "Insertion time: " << time(NULL) - start << " seconds." << std::endl;
+ std::cerr << "Insertion time: " << time(NULL) - start << " seconds."
+ << std::endl;
// std::cerr << "Elements: " << q.elements() << std::endl;
@@ -138,27 +145,32 @@
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;
+ // 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 << ") --> "
+ // << " - 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 << "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]));
+ 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;
@@ -170,13 +182,15 @@
// 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 << "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.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;