|
|
Boost-Commit : |
From: mariano.consoni_at_[hidden]
Date: 2008-06-10 09:10:59
Author: mconsoni
Date: 2008-06-10 09:10:58 EDT (Tue, 10 Jun 2008)
New Revision: 46292
URL: http://svn.boost.org/trac/boost/changeset/46292
Log:
- RTree Insert.
Text files modified:
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp | 164 ++++++++++++++++++++++++++++++++-------
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/spatial_index.hpp | 29 +++---
sandbox/SOC/2008/spacial_indexing/geometry/box.hpp | 5 +
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp | 33 ++++---
4 files changed, 174 insertions(+), 57 deletions(-)
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-10 09:10:58 EDT (Tue, 10 Jun 2008)
@@ -15,52 +15,156 @@
namespace spatial_index {
template<typename Point, typename Value>
+ class rtree_leaf;
+
+ template<typename Point, typename Value>
class rtree_node
{
- };
+ public:
+ rtree_node(void) : m_(4), M_(8) {}
+ rtree_node(const unsigned int &level, const unsigned int &m, const unsigned int &M)
+ : level_(level), m_(m), M_(M) {}
+ /// true if it is a leaf node
+ virtual bool is_leaf(void) { return false; }
- template<typename Point, typename Value>
- class rtree : public spatial_index<Point, Value>
+ void add_leaf_node(const geometry::box<Point> &b, const boost::shared_ptr<rtree_leaf<Point, Value> > &l)
{
- 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++;
+ if(nodes_.size() < M_) {
+ nodes_[b] = l;
+ } else {
+ // split
}
- virtual void bulk_insert(Value &v_begin, Value &v_end, std::vector<Point> &v)
- {
- }
+ }
- virtual Value find(const Point &k)
- {
- return Value();
- }
+ virtual ~rtree_node(void) {}
+
+
+
+
+ // level of this node
+ unsigned int level_;
+
+ // minimum number of elements per node
+ unsigned int m_;
+ // maximum number of elements per node
+ unsigned int M_;
+
+ std::map<geometry::box<Point>, boost::shared_ptr<rtree_node> > nodes_;
+
+ };
+
+
+ template<typename Point, typename Value>
+ class rtree_leaf : public rtree_node<Point, Value>
+ {
+ public:
+ rtree_leaf(void) : L_(8), level_(0) {}
+ rtree_leaf(const unsigned int &L) : L_(L), level_(0) {}
+
+ /// yes, we are a leaf
+ virtual bool is_leaf(void) { return true; }
+
+ private:
+ // maximum number of elements per leaf
+ unsigned int L_;
- virtual std::deque<Value> find(const geometry::box<Point> &r)
- {
+ // level of this node
+ unsigned int level_;
+
+
+ std::map<geometry::box<Point>, Value > nodes_;
+ };
+
+
+ template<typename Point, typename Value>
+ class rtree : public spatial_index<Point, Value>
+ {
+ private:
+ unsigned int element_count;
+
+ // maximum number of elements per leaf
+ unsigned int L_;
+ // minimum number of elements per node
+ unsigned int m_;
+ // maximum number of elements per node
+ unsigned int M_;
+
+ boost::shared_ptr< rtree_node<Point,Value> > root_;
+
+ public:
+ rtree(const geometry::box<Point> &initial_box, const unsigned int &L, const unsigned int &m, const unsigned int &M)
+ : element_count(0), L_(L), m_(m), M_(M),
+ root_(new rtree_node<Point, Value>(1, m, M))
+ {
+ boost::shared_ptr< rtree_leaf<Point, Value> > new_leaf(new rtree_leaf<Point, Value>(L));
+ root_->add_leaf_node(initial_box, new_leaf);
+ }
+
+ virtual void insert(const Point &k, const Value &v)
+ {
+ element_count++;
+ }
+
+ // TODO: do private
+
+
+ void insert(const geometry::box<Point> &e, const Value &v)
+ {
+ boost::shared_ptr<rtree_node<Point, Value> > l = choose_leaf(e);
+
+ 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() {}
- virtual unsigned int elements(void) { return element_count; }
+ private:
- virtual ~rtree() {}
- };
+ boost::shared_ptr<rtree_node<Point, Value> > choose_leaf(const geometry::box<Point> e)
+ {
+ boost::shared_ptr< rtree_node<Point, Value> > N = root_;
+
+ std::cerr << "Choosing." << std::endl;
+
+// while() {
+ if(N->is_leaf()) {
+ return N;
+ } else {
+ /// traverse N's map to see which node we should select
+ std::cerr << "Not a leaf." << std::endl;
+
+
+ }
+// }
+ // FIXME
+ return root_;
+
+ }
+
+
+ };
} // namespace spatial_index
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-10 09:10:58 EDT (Tue, 10 Jun 2008)
@@ -32,24 +32,27 @@
public:
- /// insert data 'v' with key 'k'
- virtual void insert(const Point &k, const Value &v) = 0;
+ /// insert data 'v' with key 'k'
+ virtual void insert(const Point &k, const Value &v) = 0;
+
+ /// 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 (v_begin, v_end)
+ virtual void bulk_insert(Value &v_begin, Value &v_end, std::vector<Point> &v) = 0;
- /// find element with key 'k'
- virtual Value find(const Point &k) = 0;
+ /// find element with key 'k'
+ virtual Value find(const Point &k) = 0;
- /// find element in the defined rectangle
- /// TODO: change container
- virtual std::deque<Value> find(const geometry::box<Point> &r) = 0;
+ /// find element in the defined rectangle
+ /// TODO: change container
+ virtual std::deque<Value> find(const geometry::box<Point> &r) = 0;
- /// element count in the index
- virtual unsigned int elements(void) = 0;
+ /// element count in the index
+ virtual unsigned int elements(void) = 0;
- /// destructor
- virtual ~spatial_index(void) {}
+ /// destructor
+ virtual ~spatial_index(void) {}
};
} // namespace spatial_index
Modified: sandbox/SOC/2008/spacial_indexing/geometry/box.hpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/geometry/box.hpp (original)
+++ sandbox/SOC/2008/spacial_indexing/geometry/box.hpp 2008-06-10 09:10:58 EDT (Tue, 10 Jun 2008)
@@ -76,6 +76,11 @@
inline P& min() { return m_min; }
inline P& max() { return m_max; }
+ bool operator<(const box<P> &p) const {
+ return get<0>(min()) < get<0>(p.min());
+ }
+
+
private :
P m_min, m_max;
typedef typename point_traits<P>::coordinate_type T;
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-10 09:10:58 EDT (Tue, 10 Jun 2008)
@@ -34,9 +34,9 @@
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));
+ q(new boost::spatial_index::rtree< geometry::point_xy<double> , std::vector<std::string>::iterator >(b, 8, 4, 8));
// std::cerr << " --> bulk insert" << std::endl;
// std::vector<std::string>::iterator b, e;
@@ -46,18 +46,23 @@
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++);
+
+ geometry::box<geometry::point_xy<double> > e(geometry::point_xy<double>(2.0, 2.0), geometry::point_xy<double>(4.0, 4.0));
+ std::cerr << " --> insert env" << std::endl;
+ q->insert(e, it++);
+
+// 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;
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk