|
|
Boost-Commit : |
From: mariano.consoni_at_[hidden]
Date: 2008-07-08 15:13:59
Author: mconsoni
Date: 2008-07-08 15:13:58 EDT (Tue, 08 Jul 2008)
New Revision: 47247
URL: http://svn.boost.org/trac/boost/changeset/47247
Log:
- More cleanups.
Text files modified:
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree.hpp | 13 +++----
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree_node.hpp | 66 ++++-----------------------------------
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp | 25 +++++++++-----
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_leaf.hpp | 3 -
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp | 66 ++++++++++-----------------------------
5 files changed, 47 insertions(+), 126 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-08 15:13:58 EDT (Tue, 08 Jul 2008)
@@ -1,7 +1,12 @@
+//
+// Spatial Index - 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)
+//
#ifndef BOOST_SPATIAL_INDEX_QUADTREE_HPP
@@ -33,7 +38,6 @@
virtual void remove(const Point &k)
{
root.remove(k);
- // root.clean();
element_count--;
}
@@ -61,7 +65,7 @@
/// 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;
+ throw std::logic_error("Box insertion not implemented.");
}
@@ -104,11 +108,6 @@
return result;
}
- void clean(void)
- {
- root.clean();
- }
-
virtual unsigned int elements(void) const { return element_count; }
virtual ~quadtree() {}
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-07-08 15:13:58 EDT (Tue, 08 Jul 2008)
@@ -1,7 +1,12 @@
+//
+// Spatial Index - QuadTree Node
+//
+//
// 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_QUADTREE_NODE_HPP
@@ -74,47 +79,9 @@
quadtree_node(const geometry::box<Point> &r, const unsigned int node_size)
: bounding_rectangle_(r), node_size_(node_size)
{
- // std::cerr << "Creating quadtree_node with " <<
- // "min_x: " << min_x << " min_y: " << min_y << " max_x: " << max_x << " max_y " << max_y << std::endl;
}
- void clean(void)
- {
- if(nw_ != boost::shared_ptr<quadtree_node>()) {
- if(nw_->empty_leaf()) {
- nw_ = boost::shared_ptr<quadtree_node>();
- } else {
- nw_->clean();
- }
- }
-
- if(sw_ != boost::shared_ptr<quadtree_node>()) {
- if(sw_->empty_leaf()) {
- sw_ = boost::shared_ptr<quadtree_node>();
- } else {
- sw_->clean();
- }
- }
-
- if(se_ != boost::shared_ptr<quadtree_node>()) {
- if(se_->empty_leaf()) {
- se_ = boost::shared_ptr<quadtree_node>();
- } else {
- se_->clean();
- }
- }
-
- if(ne_ != boost::shared_ptr<quadtree_node>()) {
- if(ne_->empty_leaf()) {
- ne_ = boost::shared_ptr<quadtree_node>();
- } else {
- ne_->clean();
- }
- }
-
- }
-
bool empty_leaf(void) const
{
return (m_.size() == 0) &&
@@ -128,15 +95,8 @@
void insert(const Point &k, const Value &v)
{
if(m_.size() < node_size_) {
-// std::cerr << "Empty quadtree_node --> inserting (" << v << ")" << std::endl;
m_[k] = v;
} else {
- // std::cerr << "Quadtree_Node division: ";
- // // quadtree_node division
- // std::cerr << " (" << k.first << ", " << k.second << ")" ;
- // std::cerr << " in (" << min_x_ << ", " << min_y_ << ")";
- // std::cerr << " x (" << max_x_ << ", " << max_y_ << ")" << std::endl;
-
// IMP: maybe this could be done only one time at node creation
geometry::box<Point> ne_box, sw_box, se_box, nw_box;
divide_quadrants(ne_box, sw_box, se_box, nw_box);
@@ -176,21 +136,15 @@
void find(std::deque<Value> &result, const geometry::box<Point> &r)
{
if(m_.size() != 0) {
- // std::cerr << "Node: X1:" << min_x_ << " X2:" << max_x_ << " Y1:" << min_y_ << " Y2: " << max_y_ << std::endl;
- // std::cerr << "Query: X1:" << x1 << " X2:" << x2 << " Y1:" << y1 << " Y2: " << y2 << std::endl;
if(geometry::get<0>(r.min()) > geometry::get<0>(bounding_rectangle_.max())
|| geometry::get<0>(r.max()) < geometry::get<0>(bounding_rectangle_.min())
|| geometry::get<1>(r.min()) > geometry::get<1>(bounding_rectangle_.max())
|| geometry::get<1>(r.max()) < geometry::get<1>(bounding_rectangle_.min())) {
- // std::cerr << "Not Inside" << std::endl;
return;
}
- // std::cerr << "Inside" << std::endl;
-
for(typename std::map<Point,Value>::const_iterator it = m_.begin(); it != m_.end(); ++it) {
-// std::cerr << "Checking: (" << geometry::get<0>(it->first) << "," << geometry::get<1>(it->first) << ")" << std::endl;
if(geometry::get<0>(it->first) >= geometry::get<0>(r.min()) && geometry::get<0>(it->first) <= geometry::get<0>(r.max()) &&
geometry::get<1>(it->first) >= geometry::get<1>(r.min()) && geometry::get<1>(it->first) <= geometry::get<1>(r.max())) {
result.push_back(it->second);
@@ -209,8 +163,6 @@
if(sw_ != boost::shared_ptr<quadtree_node>()) {
sw_->find(result, r);
}
-
- // std::cerr << std::endl;
}
}
@@ -265,6 +217,7 @@
return Value();
}
+
void remove(const Point &k)
{
typename std::map<Point, Value>::iterator it = m_.find(k);
@@ -275,14 +228,9 @@
recursive_remove(k);
}
+
void recursive_remove(const Point &k)
{
-// std::cerr << "Recursive_remove" << std::endl;
-
-// std::cerr << "Checking: (" << geometry::get<0>(k) << "," << geometry::get<1>(k) << ")" << std::endl;
-// std::cerr << "in : (" << geometry::get<0>(bounding_rectangle_.min()) << "," << geometry::get<1>(bounding_rectangle_.min()) << ") x ";
-// std::cerr << "(" << geometry::get<0>(bounding_rectangle_.max()) << "," << geometry::get<1>(bounding_rectangle_.max()) << ")" << std::endl;
-
// IMP: maybe this could be done only one time at node creation
// but it will consume more memory...
geometry::box<Point> ne_box, sw_box, se_box, nw_box;
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-08 15:13:58 EDT (Tue, 08 Jul 2008)
@@ -1,7 +1,12 @@
+//
+// Spatial Index - rTree
+//
+//
// 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
@@ -36,7 +41,7 @@
}
- /// remove the element with key 'k'
+ /// remove elements inside the box 'k'
virtual void remove(const geometry::box<Point> &k)
{
try {
@@ -184,7 +189,7 @@
private:
- /// cached number of elements
+ /// number of elements
unsigned int element_count_;
/// minimum number of elements per node
@@ -291,8 +296,6 @@
boost::shared_ptr<rtree_node<Point, Value> > &n1,
boost::shared_ptr<rtree_node<Point, Value> > &n2) const
{
- // TODO: unify
-
unsigned int seed1, seed2;
std::vector< geometry::box<Point> > boxes = n->get_boxes();
@@ -304,11 +307,18 @@
if(n->is_leaf()) {
n1->add_value(boxes[seed1], n->get_value(seed1));
n2->add_value(boxes[seed2], n->get_value(seed2));
+ } else {
+ n1->add_node(boxes[seed1], n->get_node(seed1));
+ n2->add_node(boxes[seed2], n->get_node(seed2));
+ }
+
+ unsigned int index = 0;
- unsigned int index = 0;
+ if(n->is_leaf()) {
typename rtree_leaf<Point,Value>::leaves_map nodes = n->get_leaves();
unsigned int remaining = nodes.size()-2;
for(typename rtree_leaf<Point,Value>::leaves_map::const_iterator it = nodes.begin(); it != nodes.end(); ++it, index++) {
+
if(index != seed1 && index != seed2) {
if(n1->elements() + remaining == m_) {
n1->add_value(it->first, it->second);
@@ -362,13 +372,10 @@
}
}
} else {
- n1->add_node(boxes[seed1], n->get_node(seed1));
- n2->add_node(boxes[seed2], n->get_node(seed2));
-
- unsigned int index = 0;
typename rtree_node<Point,Value>::node_map nodes = n->get_nodes();
unsigned int remaining = nodes.size()-2;
for(typename rtree_node<Point,Value>::node_map::const_iterator it = nodes.begin(); it != nodes.end(); ++it, index++) {
+
if(index != seed1 && index != seed2) {
if(n1->elements() + remaining == m_) {
Modified: sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_leaf.hpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_leaf.hpp (original)
+++ sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_leaf.hpp 2008-07-08 15:13:58 EDT (Tue, 08 Jul 2008)
@@ -72,7 +72,6 @@
virtual void insert(const geometry::box<Point> &e, const Value &v)
{
nodes_.push_back(std::make_pair(e, v));
-// std::cerr << "Node size: " << nodes_.size() << std::endl;
}
virtual std::vector< std::pair< geometry::box<Point>, Value > > get_leaves(void) const
@@ -102,7 +101,6 @@
for(typename leaves_map::iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
if(it->first.min() == k.min() && it->first.max() == k.max()) {
-// std::cerr << "Erasing node." << std::endl;
nodes_.erase(it);
return;
}
@@ -137,7 +135,6 @@
}
private:
-
leaves_map nodes_;
};
Modified: sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp (original)
+++ sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp 2008-07-08 15:13:58 EDT (Tue, 08 Jul 2008)
@@ -25,13 +25,14 @@
{
public:
/// type for the node map
- typedef std::vector< std::pair<geometry::box<Point>, boost::shared_ptr<rtree_node<Point, Value> > > > node_map;
+ typedef std::vector< std::pair<geometry::box<Point>,
+ boost::shared_ptr<rtree_node<Point, Value> > > > node_map;
public:
/// default constructor (needed for the containers)
rtree_node(void) {}
- /// normal constructor
+ /// standard constructor
rtree_node(const boost::shared_ptr<rtree_node<Point, Value> > &parent, const unsigned int &level)
: parent_(parent), level_(level) {}
@@ -69,19 +70,10 @@
}
}
- void find_leaves(const geometry::box<Point> &e, typename std::vector<boost::shared_ptr<rtree_node<Point,Value> > > &result) const
+ void find_leaves(const geometry::box<Point> &e,
+ typename std::vector<boost::shared_ptr<rtree_node<Point,Value> > > &result) const
{
-// std::cerr << "find_leaves\n";
-
for(typename node_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
-
- // std::cerr << "e: ( " << geometry::get<0>(e.min()) << " , " << geometry::get<1>(e.min()) << " ) x " ;
- // std::cerr << "( " << geometry::get<0>(e.max()) << " , " << geometry::get<1>(e.max()) << " )" ;
-
-
- // std::cerr << "it: ( " << geometry::get<0>(it->first.min()) << " , " << geometry::get<1>(it->first.min()) << " ) x " ;
- // std::cerr << "( " << geometry::get<0>(it->first.max()) << " , " << geometry::get<1>(it->first.max()) << " )" ;
-
if(overlaps(it->first, e)) {
if(it->second->is_leaf()) {
result.push_back(it->second);
@@ -92,7 +84,6 @@
}
}
-
/// compute bounding box for this leaf
virtual geometry::box<Point> compute_box(void) const
{
@@ -112,7 +103,7 @@
/// insert a value (not allowed for a node)
virtual void insert(const geometry::box<Point> &e, const Value &v)
{
- std::cerr << "Insert in node!" << std::endl;
+ throw std::logic_error("Insert in node!");
}
/// get the envelopes of a node
@@ -131,26 +122,16 @@
unsigned int index = 0;
for(typename node_map::iterator it = nodes_.begin(); it != nodes_.end(); ++it, index++) {
if(it->second.get() == n.get()) {
-// std::cerr << "---------------------------------------->" << std::endl;
-// std::cerr << "Node found!" << std::endl;
-// std::cerr << "Box: " << geometry::get<0>(n->compute_box().min()) << " , " <<geometry::get<1>(n->compute_box().min()) << std::endl;
-// std::cerr << "Box: " << geometry::get<0>(n->compute_box().max()) << " , " <<geometry::get<1>(n->compute_box().max()) << std::endl;
- if(it->second->get_parent().get() != n->get_parent().get()) {
- std::cerr << "ERR" << std::endl;
- }
nodes_[index] = std::make_pair(n->compute_box(), n);
-// std::cerr << "---------------------------------------->" << std::endl;
return;
}
}
-// std::cerr << "adjust_node: node not found." << std::endl;
}
virtual void remove(const geometry::box<Point> &k)
{
for(typename node_map::iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
if(it->first.min() == k.min() && it->first.max() == k.max()) {
-// std::cerr << "Erasing node." << std::endl;
nodes_.erase(it);
return;
}
@@ -158,22 +139,23 @@
}
/// replace the node in the nodes_ vector and recompute the box
- void replace_node(const boost::shared_ptr<rtree_node<Point, Value> > &l, boost::shared_ptr<rtree_node<Point, Value> > &new_l)
+ void replace_node(const boost::shared_ptr<rtree_node<Point, Value> > &l,
+ boost::shared_ptr<rtree_node<Point, Value> > &new_l)
{
unsigned int index = 0;
for(typename node_map::iterator it = nodes_.begin(); it != nodes_.end(); ++it, index++) {
if(it->second.get() == l.get()) {
-// std::cerr << "Node found!" << std::endl;
nodes_[index] = std::make_pair(new_l->compute_box(), new_l);
new_l->update_parent(new_l);
return;
}
}
- std::cerr << "replace_node: node not found." << std::endl;
+ throw std::logic_error("Node not found.");
}
/// add a node
- virtual void add_node(const geometry::box<Point> &b, const boost::shared_ptr<rtree_node<Point, Value> > &n)
+ virtual void add_node(const geometry::box<Point> &b,
+ const boost::shared_ptr<rtree_node<Point, Value> > &n)
{
nodes_.push_back(std::make_pair(b, n));
n->update_parent(n);
@@ -202,6 +184,7 @@
double min_diff_area;
boost::shared_ptr<rtree_node<Point,Value> > chosen_node;
+ // check for the least enlargement
for(typename node_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
double diff_area = compute_union_area(e, it->first) - geometry::area(it->first);
@@ -230,7 +213,6 @@
}
}
-// std::cerr << "We have a node." << std::endl;
return chosen_node;
}
@@ -244,7 +226,7 @@
return parent_;
}
- // update the parent of all the childs
+ /// update the parent of all the childs
void update_parent(const boost::shared_ptr<rtree_node<Point,Value> > &p)
{
for(typename node_map::iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
@@ -252,7 +234,7 @@
}
}
- // setter for parent
+ /// set parent
void set_parent(const boost::shared_ptr<rtree_node<Point,Value> > &p)
{
parent_ = p;
@@ -275,7 +257,6 @@
throw std::logic_error("Node not found");
}
-
/// value projector for the nodes
node_map get_nodes(void) const { return nodes_; }
@@ -288,8 +269,11 @@
for(typename node_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
typename std::vector< std::pair< geometry::box<Point>, Value > > this_leaves = it->second->get_leaves();
- for(typename std::vector<std::pair<geometry::box<Point>, Value> >::iterator it_leaf = this_leaves.begin(); it_leaf != this_leaves.end(); ++it_leaf) {
+ for(typename std::vector<std::pair<geometry::box<Point>, Value> >::iterator it_leaf = this_leaves.begin();
+ it_leaf != this_leaves.end(); ++it_leaf) {
+
l.push_back(*it_leaf);
+
}
}
@@ -325,22 +309,11 @@
}
}
-// boost::shared_ptr<rtree_node<Point, Value> > get_node(const geometry::box<Point> &e) const
-// {
-// for(typename node_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
-// if(it->first.max() == e.max() && it->first.min() == e.min()) {
-// return it->second;
-// }
-// }
-
-// }
-
/// destructor (virtual because we have virtual functions)
virtual ~rtree_node(void) {}
private:
-
// parent node
boost::shared_ptr< rtree_node<Point, Value> > parent_;
@@ -352,10 +325,7 @@
};
-
-
} // namespace spatial_index
} // namespace boost
#endif // BOOST_SPATIAL_INDEX_RTREE_NODE_HPP
-
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