Subject: [Boost-commit] svn:boost r70746 - in sandbox-branches/geometry/index_080_new: boost/geometry/extensions/index/rtree/rstar tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-03-30 06:16:04
Author: awulkiew
Date: 2011-03-30 06:16:03 EDT (Wed, 30 Mar 2011)
New Revision: 70746
URL: http://svn.boost.org/trac/boost/changeset/70746
Log:
choose_next_node algorithm changed
Text files modified:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp | 228 +++++++++++++++++++++++++++++----------
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert.hpp | 26 ++-
sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp | 3
3 files changed, 186 insertions(+), 71 deletions(-)
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp 2011-03-30 06:16:03 EDT (Wed, 30 Mar 2011)
@@ -12,6 +12,8 @@
#include <algorithm>
+#include <boost/geometry/algorithms/expand.hpp>
+
#include <boost/geometry/extensions/index/algorithms/area.hpp>
#include <boost/geometry/extensions/index/algorithms/overlap.hpp>
#include <boost/geometry/extensions/index/algorithms/union_area.hpp>
@@ -32,6 +34,9 @@
typedef typename internal_node::children_type children_type;
+ typedef typename index::area_result<Box>::type area_type;
+ typedef typename index::overlap_result<Box>::type overlap_type;
+
public:
template <typename Indexable>
static inline size_t apply(internal_node & n, Indexable const& indexable)
@@ -42,89 +47,192 @@
visitors::is_leaf<Value, Box, rstar_tag>(),
*n.children.front().second);
- if ( !has_leaves )
- return impl<internal_node_areas>(n, indexable);
+ if ( has_leaves )
+ return branch_impl(n, indexable);
+ //return impl<branch_areas>(n, indexable);
else
- return impl<branch_areas>(n, indexable);
+ return internal_node_impl(n, indexable);
+ //return impl<internal_node_areas>(n, indexable);
}
private:
- template <typename Areas, typename Indexable>
- static inline size_t impl(internal_node & n, Indexable const& indexable)
+ template <typename Indexable>
+ static inline size_t branch_impl(internal_node & n, Indexable const& indexable)
{
- typedef typename children_type::iterator children_iterator;
-
- //assert(!n.children.empty());
+ size_t children_count = n.children.size();
+ // overlaps values of all nodes' boxes,
+ // overlaps and areas of extended boxes are stored at indexes i + children_count
+ std::vector<overlap_type> overlaps(children_count * 2, overlap_type(0));
+ std::vector<overlap_type> areas(children_count * 2);
+ // caculate overlaps and areas of all nodes' boxes
+ for (size_t i = 0 ; i < children_count ; ++i )
+ {
+ typedef typename children_type::value_type child_type;
+ child_type const& ch_i = n.children[i];
- children_iterator temp_it = n.children.begin();
- children_iterator child_it = temp_it;
- Areas min_areas(n.children, child_it, indexable);
+ Box ch_ext;
+ // calculate expanded box fo node ch_i
+ geometry::convert(ch_i.first, ch_ext);
+ geometry::expand(ch_ext, indexable);
- for (children_iterator it = ++temp_it;
- it != n.children.end(); ++it)
- {
- Areas areas(n.children, it, indexable);
+ areas[i] = index::area(ch_i.first);
+ areas[i + children_count] = index::area(ch_ext);
- if ( areas < min_areas )
+ for (size_t j = i + 1 ; j < children_count ; ++j )
{
- child_it = it;
- min_areas = areas;
+ child_type const& ch_j = n.children[j];
+
+ // add overlap of both boxes
+ overlap_type ovl = index::overlap(ch_i.first, ch_j.first);
+ overlaps[i] += ovl;
+ overlaps[j] += ovl;
+
+ // add overlap of expanded box i and box j
+ overlaps[i + children_count] = index::overlap(ch_ext, ch_j.first);
+
+ // add overlap of expanded box j and box i
+ geometry::convert(ch_j.first, ch_ext);
+ geometry::expand(ch_ext, indexable);
+ overlaps[j + children_count] = index::overlap(ch_ext, ch_i.first);
}
}
- // TODO: awulkiew - switch to indexes in the whole class?
- return child_it - n.children.begin();
- }
+ // choose index with smallest overlap change value, or area change or smallest area
+ size_t choosen_index = 0;
+ overlap_type smallest_overlap_change = std::numeric_limits<overlap_type>::max();
+ area_type smallest_area_change = std::numeric_limits<area_type>::max();
+ area_type smallest_area = std::numeric_limits<area_type>::max();
- struct branch_areas
- {
- typedef typename index::area_result<Box>::type area_type;
-
- template <typename Indexable>
- inline branch_areas(children_type const& ch, typename children_type::iterator const& k_it, Indexable const& indexable)
+ for ( size_t i = 0 ; i < children_count ; ++i )
{
- overlap_area = 0;
- for (typename children_type::const_iterator it = ch.begin(); it != ch.end(); ++it)
- if ( it != k_it )
- overlap_area += index::overlap(k_it->first, it->first);
-
- area = index::area(k_it->first);
-
- diff_area = index::union_area(k_it->first, indexable) - area;
- }
-
- inline bool operator<(branch_areas &a) const
- {
- return overlap_area < a.overlap_area ||
- ( overlap_area == a.overlap_area && diff_area < a.diff_area ) ||
- ( diff_area == a.diff_area && area < a.area );
+ overlap_type overlap_change = overlaps[i + children_count] - overlaps[i];
+ area_type area_change = areas[i + children_count] - areas[i];
+ area_type area = areas[i + children_count];
+
+ if ( overlap_change < smallest_overlap_change ||
+ ( overlap_change == smallest_overlap_change && area_change < smallest_area_change ) ||
+ ( area_change == smallest_area_change && smallest_area < area ) )
+ {
+ smallest_overlap_change = overlap_change;
+ smallest_area_change = area_change;
+ smallest_area = area;
+ choosen_index = i;
+ }
}
- area_type overlap_area;
- area_type diff_area;
- area_type area;
- };
+ return choosen_index;
+ }
- struct internal_node_areas
+ template <typename Indexable>
+ static inline size_t internal_node_impl(internal_node & n, Indexable const& indexable)
{
- typedef typename area_result<Box>::type area_type;
+ size_t children_count = n.children.size();
- template <typename Indexable>
- inline internal_node_areas(children_type const&, typename children_type::iterator const& k_it, Indexable const& indexable)
- {
- area = index::area(k_it->first);
- diff_area = index::union_area(k_it->first, indexable) - area;
- }
+ // choose index with smallest overlap change value, or area change or smallest area
+ size_t choosen_index = 0;
+ area_type smallest_area_change = std::numeric_limits<area_type>::max();
+ area_type smallest_area = std::numeric_limits<area_type>::max();
- inline bool operator<(internal_node_areas &a) const
+ // caculate areas and areas of all nodes' boxes
+ for ( size_t i = 0 ; i < children_count ; ++i )
{
- return diff_area < a.diff_area ||
- ( diff_area == a.diff_area && area < a.area );
+ typedef typename children_type::value_type child_type;
+ child_type const& ch_i = n.children[i];
+
+ Box ch_exp;
+ geometry::convert(ch_i.first, ch_exp);
+ geometry::expand(ch_exp, indexable);
+
+ area_type area = index::area(ch_exp);
+ area_type area_change = area - index::area(ch_i.first);
+
+ if ( area_change < smallest_area_change ||
+ ( area_change == smallest_area_change && smallest_area < area ) )
+ {
+ smallest_area_change = area_change;
+ smallest_area = area;
+ choosen_index = i;
+ }
}
- area_type diff_area;
- area_type area;
- };
+ return choosen_index;
+ }
+
+ //template <typename Areas, typename Indexable>
+ //static inline size_t impl(internal_node & n, Indexable const& indexable)
+ //{
+ // typedef typename children_type::iterator children_iterator;
+
+ // //assert(!n.children.empty());
+
+ // children_iterator temp_it = n.children.begin();
+ // children_iterator child_it = temp_it;
+ // Areas min_areas(n.children, child_it, indexable);
+
+ // for (children_iterator it = ++temp_it;
+ // it != n.children.end(); ++it)
+ // {
+ // Areas areas(n.children, it, indexable);
+
+ // if ( areas < min_areas )
+ // {
+ // child_it = it;
+ // min_areas = areas;
+ // }
+ // }
+
+ // return child_it - n.children.begin();
+ //}
+
+ //struct branch_areas
+ //{
+ // typedef typename index::area_result<Box>::type area_type;
+
+ // template <typename Indexable>
+ // inline branch_areas(children_type const& ch, typename children_type::iterator const& k_it, Indexable const& indexable)
+ // {
+ // overlap_area = 0;
+ // for (typename children_type::const_iterator it = ch.begin(); it != ch.end(); ++it)
+ // if ( it != k_it )
+ // overlap_area += index::overlap(k_it->first, it->first);
+
+ // area = index::area(k_it->first);
+
+ // diff_area = index::union_area(k_it->first, indexable) - area;
+ // }
+
+ // inline bool operator<(branch_areas &a) const
+ // {
+ // return overlap_area < a.overlap_area ||
+ // ( overlap_area == a.overlap_area && diff_area < a.diff_area ) ||
+ // ( diff_area == a.diff_area && area < a.area );
+ // }
+
+ // area_type overlap_area;
+ // area_type diff_area;
+ // area_type area;
+ //};
+
+ //struct internal_node_areas
+ //{
+ // typedef typename area_result<Box>::type area_type;
+
+ // template <typename Indexable>
+ // inline internal_node_areas(children_type const&, typename children_type::iterator const& k_it, Indexable const& indexable)
+ // {
+ // area = index::area(k_it->first);
+ // diff_area = index::union_area(k_it->first, indexable) - area;
+ // }
+
+ // inline bool operator<(internal_node_areas &a) const
+ // {
+ // return diff_area < a.diff_area ||
+ // ( diff_area == a.diff_area && area < a.area );
+ // }
+
+ // area_type diff_area;
+ // area_type area;
+ //};
};
}}} // namespace detail::rtree:rstar
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert.hpp 2011-03-30 06:16:03 EDT (Wed, 30 Mar 2011)
@@ -41,7 +41,7 @@
inline explicit insert(node* & root, Value const& v, size_t min_elements, size_t max_elements, Translator const& t)
: m_value(v), m_tr(t), m_min_elems_per_node(min_elements), m_max_elems_per_node(max_elements)
, m_root_node(root)
- , m_parent(0), m_current_child_index(0)
+ , m_parent(0), m_current_child_index(0), m_current_level(0)
{}
inline void operator()(internal_node & n)
@@ -50,13 +50,14 @@
internal_node * parent_bckup = m_parent;
m_parent = &n;
size_t current_child_index_bckup = m_current_child_index;
+ size_t current_level_bckup = m_current_level;
// choose next node, where value insert traversing should go
m_current_child_index =
rstar::choose_next_node<Value, Box>::
apply(n, m_tr(m_value));
- // TODO: awulkiew - if reinsert is implemented this must be changed
+ // expand the node to contain value
geometry::expand(n.children[m_current_child_index].first, m_tr(m_value));
// next traversing step
@@ -65,12 +66,10 @@
// restore previous traverse inputs
m_parent = parent_bckup;
m_current_child_index = current_child_index_bckup;
+ m_current_level = current_level_bckup;
if ( m_max_elems_per_node < n.children.size() )
- {
- rstar::split<Value, Translator, Box>::
- apply(n, m_parent, m_current_child_index, m_root_node, m_min_elems_per_node, m_max_elems_per_node, m_tr);
- }
+ overflow_treatment(n);
}
inline void operator()(leaf & n)
@@ -78,13 +77,19 @@
n.values.push_back(m_value);
if ( m_max_elems_per_node < n.values.size() )
- {
- rstar::split<Value, Translator, Box>::
- apply(n, m_parent, m_current_child_index, m_root_node, m_min_elems_per_node, m_max_elems_per_node, m_tr);
- }
+ overflow_treatment(n);
}
private:
+ template <typename Node>
+ inline void overflow_treatment(Node & n)
+ {
+ // TODO: awulkiew - reinsert
+
+ rstar::split<Value, Translator, Box>::
+ apply(n, m_parent, m_current_child_index, m_root_node, m_min_elems_per_node, m_max_elems_per_node, m_tr);
+ }
+
Value const& m_value;
Translator const& m_tr;
size_t m_min_elems_per_node;
@@ -95,6 +100,7 @@
// traversing input parameters
internal_node *m_parent;
size_t m_current_child_index;
+ size_t m_current_level;
};
}}} // namespace detail::rtree::visitors
Modified: sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp (original)
+++ sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp 2011-03-30 06:16:03 EDT (Wed, 30 Mar 2011)
@@ -9,7 +9,8 @@
typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
typedef boost::geometry::model::box<P> B;
-boost::geometry::index::rtree<B> t(2, 1);
+//boost::geometry::index::rtree<B> t(2, 1);
+boost::geometry::index::rtree<B> t(4, 2);
void render_scene(void)
{