From: mariano.consoni_at_[hidden]
Date: 2008-06-09 15:43:42
Author: mconsoni
Date: 2008-06-09 15:43:41 EDT (Mon, 09 Jun 2008)
New Revision: 46281
URL: http://svn.boost.org/trac/boost/changeset/46281
Log:
- Initial structure for the rTree.
- Initial test to test-driven development for the rTree.
Added:
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp (contents, props changed)
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp (contents, props changed)
Text files modified:
sandbox/SOC/2008/spacial_indexing/boost/spatial_index.hpp | 1 +
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/Jamfile | 1 +
2 files changed, 2 insertions(+), 0 deletions(-)
Modified: sandbox/SOC/2008/spacial_indexing/boost/spatial_index.hpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/boost/spatial_index.hpp (original)
+++ sandbox/SOC/2008/spacial_indexing/boost/spatial_index.hpp 2008-06-09 15:43:41 EDT (Mon, 09 Jun 2008)
@@ -10,6 +10,7 @@
#include <boost/spatial_index/spatial_index.hpp>
#include <boost/spatial_index/quadtree.hpp>
+#include <boost/spatial_index/rtree.hpp>
#endif // BOOST_SPATIAL_INDEX_HPP
Added: sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp 2008-06-09 15:43:41 EDT (Mon, 09 Jun 2008)
@@ -0,0 +1,70 @@
+// 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)
+
+
+#ifndef BOOST_SPATIAL_INDEX_RTREE_HPP
+#define BOOST_SPATIAL_INDEX_RTREE_HPP
+
+// #include "quadtree_node.hpp"
+
+// #include <boost/thread/xtime.hpp>
+
+namespace boost {
+namespace spatial_index {
+
+ template<typename Point, typename Value>
+ class rtree_node
+ {
+ };
+
+
+ template<typename Point, typename Value>
+ class rtree : public spatial_index<Point, Value>
+ {
+ private:
+ rtree_node<Point,Value> root;
+ unsigned int element_count;
+
+ // minimum number of points in each node
+ unsigned int m_;
+ // maximum number of points in each node
+ unsigned int M_;
+
+ public:
+ rtree(const unsigned int &m, const unsigned int &M) : element_count(0), m_(m), M_(M) {}
+
+ virtual void insert(const Point &k, const Value &v)
+ {
+ element_count++;
+ }
+
+ virtual void bulk_insert(Value &v_begin, Value &v_end, std::vector<Point> &v)
+ {
+ }
+
+ virtual Value find(const Point &k)
+ {
+ return Value();
+ }
+
+
+ virtual std::deque<Value> find(const geometry::box<Point> &r)
+ {
+ std::deque<Value> result;
+ return result;
+ }
+
+ virtual unsigned int elements(void) { return element_count; }
+
+
+ virtual ~rtree() {}
+ };
+
+
+} // namespace spatial_index
+} // namespace boost
+
+#endif // BOOST_SPATIAL_INDEX_RTREE_HPP
+
Modified: sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/Jamfile
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/Jamfile (original)
+++ sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/Jamfile 2008-06-09 15:43:41 EDT (Mon, 09 Jun 2008)
@@ -13,6 +13,7 @@
;
run simple_test.cpp ;
+run simple_test_rtree.cpp ;
run custom_point_test.cpp ;
run random_test.cpp ;
run performance_test.cpp ;
Added: sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp 2008-06-09 15:43:41 EDT (Mon, 09 Jun 2008)
@@ -0,0 +1,96 @@
+// 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)
+
+
+#include <boost/spatial_index.hpp>
+
+#include <boost/test/included/test_exec_monitor.hpp>
+#include <boost/shared_ptr.hpp>
+
+#include <geometry/geometry.hpp>
+
+#include <vector>
+#include <string>
+
+int test_main(int, char* [])
+{
+ std::vector<std::string> data;
+ std::vector< geometry::point_xy<double> > 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(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));
+
+ 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::rtree< geometry::point_xy<double> , std::vector<std::string>::iterator >(4, 8));
+
+// 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(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++);
+ std::cerr << " --> insert" << std::endl;
+ 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++);
+ std::cerr << " --> insert" << std::endl;
+ 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++);
+
+
+// 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);
+
+// 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);
+// 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;
+};