|
|
Boost-Commit : |
From: mariano.consoni_at_[hidden]
Date: 2008-06-13 10:14:07
Author: mconsoni
Date: 2008-06-13 10:14:06 EDT (Fri, 13 Jun 2008)
New Revision: 46373
URL: http://svn.boost.org/trac/boost/changeset/46373
Log:
- node split for leaves.
Text files modified:
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp | 61 ++++++++++++++++++++++++++++-
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_leaf.hpp | 38 ++++++++++++++++-
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp | 81 ++++++++++++++++++++++++++++-----------
3 files changed, 149 insertions(+), 31 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-13 10:14:06 EDT (Fri, 13 Jun 2008)
@@ -118,9 +118,64 @@
linear_pick_seeds(n, seed1, seed2);
if(n->is_leaf()) {
- n->get_value(seed1);
-// n1->add_value(boxes[seed1], n->get_value(seed1));
- // n2->add_node(boxes[seed2], n->get_node(seed2));
+ n1->add_value(boxes[seed1], n->get_value(seed1));
+ n2->add_value(boxes[seed2], n->get_value(seed2));
+
+ n1->print();
+ n2->print();
+
+ unsigned int index = 0;
+ typename rtree_leaf<Point,Value>::leaves_map nodes = n->get_leaves();
+ for(typename rtree_leaf<Point,Value>::leaves_map::const_iterator it = nodes.begin(); it != nodes.end(); ++it, index++) {
+ if(index != seed1 && index != seed2) {
+ // TODO: check if the remaining elements should be in one group because of the minimum
+
+ /// current boxes of each group
+ geometry::box<Point> b1, b2;
+
+ /// enlarged boxes of each group
+ geometry::box<Point> eb1, eb2;
+ b1 = n1->compute_box();
+ b2 = n2->compute_box();
+
+ /// areas
+ double b1_area, b2_area;
+ double eb1_area, eb2_area;
+ b1_area = geometry::area(b1);
+ b2_area = geometry::area(b2);
+
+ eb1_area = compute_union_area(b1, it->first);
+ eb2_area = compute_union_area(b2, it->first);
+
+ if(eb1_area - b1_area > eb2_area - b2_area) {
+ n2->add_value(it->first, it->second);
+ }
+ if(eb1_area - b1_area < eb2_area - b2_area) {
+ n1->add_value(it->first, it->second);
+ }
+ if(eb1_area - b1_area == eb2_area - b2_area) {
+ if(b1_area < b2_area) {
+ n1->add_value(it->first, it->second);
+ }
+ if(b1_area > b2_area) {
+ n2->add_value(it->first, it->second);
+ }
+ if(b1_area == b2_area) {
+ if(n1->elements() > n2->elements()) {
+ n2->add_value(it->first, it->second);
+ } else {
+ n1->add_value(it->first, it->second);
+ }
+ }
+ }
+
+ n1->print();
+ n2->print();
+
+ }
+ }
+ } else {
+ // TODO
}
}
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-06-13 10:14:06 EDT (Fri, 13 Jun 2008)
@@ -1,11 +1,12 @@
+//
+// Spatial Index - rTree Leaf
+//
+//
// 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)
//
-//
-// Spatial Index - rTree Leaf
-//
#ifndef BOOST_SPATIAL_INDEX_RTREE_LEAF_HPP
@@ -20,21 +21,51 @@
class rtree_leaf : public rtree_node<Point, Value>
{
public:
+ typedef std::vector< std::pair< geometry::box<Point>, Value > > leaves_map;
+
+ public:
rtree_leaf(void) : L_(8), level_(0) {}
rtree_leaf(const boost::shared_ptr< rtree_node<Point,Value> > &parent, const unsigned int &L)
: rtree_node<Point,Value>(parent, 0, 0, 0), L_(L), level_(0) {}
+ /// compute bounding box for this leaf
+ virtual geometry::box<Point> compute_box(void) const
+ {
+ if(nodes_.empty()) {
+ throw std::logic_error("Compute box in an empty node.");
+ }
+
+ typename leaves_map::const_iterator it = nodes_.begin();
+ geometry::box<Point> r = it->first;
+ it++;
+ for(; it != nodes_.end(); ++it) {
+ r = enlarge_box(r, it->first);
+ }
+ return r;
+ }
+
/// yes, we are a leaf
virtual bool is_leaf(void) const { return true; }
virtual bool is_full(void) const { return nodes_.size() >= L_; }
+ /// element count
+ virtual unsigned int elements(void) const
+ {
+ return nodes_.size();
+ }
+
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
+ {
+ return nodes_;
+ }
+
virtual void add_node(const geometry::box<Point> &b, const boost::shared_ptr<rtree_node<Point, Value> > &n)
{
throw std::logic_error("Can't add node to leaf node.");
@@ -91,7 +122,6 @@
// level of this node
unsigned int level_;
- typedef std::vector< std::pair< geometry::box<Point>, Value > > leaves_map;
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-06-13 10:14:06 EDT (Fri, 13 Jun 2008)
@@ -1,11 +1,12 @@
+//
+// Spatial Index - rTree 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)
//
-//
-// Spatial Index - rTree Node
-//
#ifndef BOOST_SPATIAL_INDEX_RTREE_NODE_HPP
@@ -33,6 +34,12 @@
/// true if the node is full
virtual bool is_full(void) const { return nodes_.size() >= M_; }
+ /// element count
+ virtual unsigned int elements(void) const
+ {
+ return nodes_.size();
+ }
+
/// true if it is a leaf node
virtual bool is_leaf(void) const { return false; }
@@ -45,6 +52,28 @@
/// get a node
boost::shared_ptr< rtree_node<Point, Value> > get_node(const unsigned int i) { return nodes_[i].second; }
+ /// get leaves
+ virtual std::vector< std::pair< geometry::box<Point>, Value > > get_leaves(void) const
+ {
+ throw std::logic_error("No leaves in a non-leaf node.");
+ }
+
+ /// compute bounding box for this leaf
+ virtual geometry::box<Point> compute_box(void) const
+ {
+ if(nodes_.empty()) {
+ throw std::logic_error("Compute box in an empty node.");
+ }
+
+ typename node_map::const_iterator it = nodes_.begin();
+ geometry::box<Point> r = it->first;
+ it++;
+ for(; it != nodes_.end(); ++it) {
+ r = enlarge_box(r, it->first);
+ }
+ return r;
+ }
+
/// insert a value (not allowed for a node)
virtual void insert(const geometry::box<Point> &e, const Value &v)
{
@@ -194,30 +223,34 @@
private:
- /// given two boxes, create the minimal box that contains them
- geometry::box<Point> enlarge_box(const geometry::box<Point> &b1, const geometry::box<Point> &b2) const
- {
- Point min(
- geometry::get<0>(b1.min()) < geometry::get<0>(b2.min()) ? geometry::get<0>(b1.min()) : geometry::get<0>(b2.min()),
- geometry::get<1>(b1.min()) < geometry::get<1>(b2.min()) ? geometry::get<1>(b1.min()) : geometry::get<1>(b2.min())
- );
-
- Point max(
- geometry::get<0>(b1.max()) > geometry::get<0>(b2.max()) ? geometry::get<0>(b1.max()) : geometry::get<0>(b2.max()),
- geometry::get<1>(b1.max()) > geometry::get<1>(b2.max()) ? geometry::get<1>(b1.max()) : geometry::get<1>(b2.max())
- );
+ };
- return geometry::box<Point>(min, max);
- }
+ /// given two boxes, create the minimal box that contains them
+ template<typename Point>
+ geometry::box<Point> enlarge_box(const geometry::box<Point> &b1, const geometry::box<Point> &b2)
+ {
+ Point min(
+ geometry::get<0>(b1.min()) < geometry::get<0>(b2.min()) ? geometry::get<0>(b1.min()) : geometry::get<0>(b2.min()),
+ geometry::get<1>(b1.min()) < geometry::get<1>(b2.min()) ? geometry::get<1>(b1.min()) : geometry::get<1>(b2.min())
+ );
+
+ Point max(
+ geometry::get<0>(b1.max()) > geometry::get<0>(b2.max()) ? geometry::get<0>(b1.max()) : geometry::get<0>(b2.max()),
+ geometry::get<1>(b1.max()) > geometry::get<1>(b2.max()) ? geometry::get<1>(b1.max()) : geometry::get<1>(b2.max())
+ );
+
+ return geometry::box<Point>(min, max);
+ }
+
+ /// compute the area of the union of b1 and b2
+ template<typename Point>
+ double compute_union_area(const geometry::box<Point> &b1, const geometry::box<Point> &b2)
+ {
+ geometry::box<Point> enlarged_box = enlarge_box(b1, b2);
+ return geometry::area(enlarged_box);
+ }
- /// compute the area of the union of b1 and b2
- double compute_union_area(const geometry::box<Point> &b1, const geometry::box<Point> &b2) const
- {
- geometry::box<Point> enlarged_box = enlarge_box(b1, b2);
- return geometry::area(enlarged_box);
- }
- };
} // namespace spatial_index
} // namespace boost
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