Subject: [Boost-commit] svn:boost r71880 - in sandbox-branches/geometry/index_080_new: boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/quadratic boost/geometry/extensions/index/rtree/rstar tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-05-11 17:15:01
Author: awulkiew
Date: 2011-05-11 17:15:00 EDT (Wed, 11 May 2011)
New Revision: 71880
URL: http://svn.boost.org/trac/boost/changeset/71880
Log:
rstar partially implemented
Added:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp (contents, props changed)
Text files modified:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp | 2
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp | 98 ++++-----------------------------------
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/rstar.hpp | 3
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp | 3 -
sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp | 7 +-
5 files changed, 17 insertions(+), 96 deletions(-)
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp 2011-05-11 17:15:00 EDT (Wed, 11 May 2011)
@@ -12,8 +12,6 @@
#include <algorithm>
-#include <boost/tuple/tuple.hpp>
-
#include <boost/geometry/extensions/index/algorithms/area.hpp>
#include <boost/geometry/extensions/index/algorithms/union_area.hpp>
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-05-11 17:15:00 EDT (Wed, 11 May 2011)
@@ -34,7 +34,7 @@
typedef typename rtree::internal_node<Value, Box, rstar_tag>::type internal_node;
typedef typename rtree::leaf<Value, Box, rstar_tag>::type leaf;
- typedef typename internal_node::children_type children_type;
+ typedef typename rtree::elements_type<internal_node>::type children_type;
typedef typename index::default_area_result<Box>::type area_type;
typedef typename index::default_overlap_result<Box>::type overlap_type;
@@ -43,25 +43,26 @@
template <typename Indexable>
static inline size_t apply(internal_node & n, Indexable const& indexable)
{
- assert(!n.children.empty());
+ children_type & children = rtree::elements_get(n);
+ assert(!children.empty());
bool has_leaves = boost::apply_visitor(
visitors::is_leaf<Value, Box, rstar_tag>(),
- *n.children.front().second);
+ *children.front().second);
if ( has_leaves )
return branch_impl(n, indexable);
- //return impl<branch_areas>(n, indexable);
else
return internal_node_impl(n, indexable);
- //return impl<internal_node_areas>(n, indexable);
}
private:
template <typename Indexable>
static inline size_t branch_impl(internal_node & n, Indexable const& indexable)
{
- size_t children_count = n.children.size();
+ children_type & children = rtree::elements_get(n);
+ size_t children_count = 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));
@@ -70,7 +71,7 @@
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];
+ child_type const& ch_i = children[i];
Box ch_ext;
// calculate expanded box fo node ch_i
@@ -82,7 +83,7 @@
for (size_t j = i + 1 ; j < children_count ; ++j )
{
- child_type const& ch_j = n.children[j];
+ child_type const& ch_j = children[j];
// add overlap of both boxes
overlap_type ovl = index::overlap(ch_i.first, ch_j.first);
@@ -128,7 +129,8 @@
template <typename Indexable>
static inline size_t internal_node_impl(internal_node & n, Indexable const& indexable)
{
- size_t children_count = n.children.size();
+ children_type & children = rtree::elements_get(n);
+ size_t children_count = children.size();
// choose index with smallest area change or smallest area
size_t choosen_index = 0;
@@ -139,7 +141,7 @@
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];
+ child_type const& ch_i = children[i];
Box ch_exp;
geometry::convert(ch_i.first, ch_exp);
@@ -159,82 +161,6 @@
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
Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp 2011-05-11 17:15:00 EDT (Wed, 11 May 2011)
@@ -0,0 +1,212 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree quadratic split algorithm implementation
+//
+// Copyright 2011 Adam Wulkiewicz.
+// Use, modification and distribution is subject to 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_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_REDISTRIBUTE_ELEMENTS_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_REDISTRIBUTE_ELEMENTS_HPP
+
+#include <algorithm>
+
+#include <boost/geometry/extensions/index/algorithms/area.hpp>
+#include <boost/geometry/extensions/index/algorithms/union_area.hpp>
+
+#include <boost/geometry/extensions/index/rtree/node.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/insert.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/is_leaf.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail { namespace rtree { namespace visitors {
+
+namespace detail {
+
+template <typename Value, typename Translator, typename Box>
+struct redistribute_elements<Value, Translator, Box, rstar_tag>
+{
+ typedef typename rtree::node<Value, Box, rstar_tag>::type node;
+ typedef typename rtree::internal_node<Value, Box, rstar_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, Box, rstar_tag>::type leaf;
+
+ typedef typename index::default_area_result<Box>::type area_type;
+
+ template <typename Node>
+ static inline void apply(Node & n,
+ Node & second_node,
+ Box & box1,
+ Box & box2,
+ size_t min_elems,
+ size_t max_elems,
+ Translator const& tr)
+ {
+ typedef typename rtree::elements_type<Node>::type elements_type;
+ typedef typename elements_type::value_type element_type;
+ typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
+ typedef typename index::traits::coordinate_type<indexable_type>::type coordinate_type;
+
+ // copy original elements
+ elements_type elements_copy = rtree::elements_get(n);
+
+ // calculate initial seeds
+ size_t seed1 = 0;
+ size_t seed2 = 0;
+ quadratic::pick_seeds<elements_type, Translator, Box>::apply(elements_copy, tr, seed1, seed2);
+
+ // prepare nodes' elements containers
+ elements_type & elements1 = rtree::elements_get(n);
+ elements_type & elements2 = rtree::elements_get(second_node);
+ elements1.clear();
+ assert(elements2.empty());
+
+ // add seeds
+ elements1.push_back(elements_copy[seed1]);
+ elements2.push_back(elements_copy[seed2]);
+
+ // calculate boxes
+ geometry::convert(rtree::element_indexable(elements_copy[seed1], tr), box1);
+ geometry::convert(rtree::element_indexable(elements_copy[seed2], tr), box2);
+
+ // remove seeds
+ if (seed1 < seed2)
+ {
+ elements_copy.erase(elements_copy.begin() + seed2);
+ elements_copy.erase(elements_copy.begin() + seed1);
+ }
+ else
+ {
+ elements_copy.erase(elements_copy.begin() + seed1);
+ elements_copy.erase(elements_copy.begin() + seed2);
+ }
+
+ // initialize areas
+ area_type area1 = index::area(box1);
+ area_type area2 = index::area(box2);
+
+ size_t remaining = elements_copy.size();
+
+ // redistribute the rest of the elements
+ while ( !elements_copy.empty() )
+ {
+ typename elements_type::reverse_iterator el_it = elements_copy.rbegin();
+ bool insert_into_group1 = false;
+
+ size_t elements1_count = elements1.size();
+ size_t elements2_count = elements2.size();
+
+ // if there is small number of elements left and the number of elements in node is lesser than min_elems
+ // just insert them to this node
+ if ( elements1_count + remaining <= min_elems )
+ {
+ insert_into_group1 = true;
+ }
+ else if ( elements2_count + remaining <= min_elems )
+ {
+ insert_into_group1 = false;
+ }
+ // insert the best element
+ else
+ {
+ // find element with minimum groups areas increses differences
+ area_type area_increase1 = 0;
+ area_type area_increase2 = 0;
+ el_it = pick_next(elements_copy.rbegin(), elements_copy.rend(),
+ box1, box2, area1, area2, tr,
+ area_increase1, area_increase2);
+
+ if ( area_increase1 < area_increase2 ||
+ ( area_increase1 == area_increase2 && area1 < area2 ) ||
+ ( area1 == area2 && elements1_count <= elements2_count ) )
+ {
+ insert_into_group1 = true;
+ }
+ else
+ {
+ insert_into_group1 = false;
+ }
+ }
+
+ // move element to the choosen group
+ element_type const& elem = *el_it;
+ indexable_type const& indexable = rtree::element_indexable(elem, tr);
+
+ if ( insert_into_group1 )
+ {
+ elements1.push_back(elem);
+ geometry::expand(box1, indexable);
+ area1 = index::area(box1);
+ }
+ else
+ {
+ elements2.push_back(elem);
+ geometry::expand(box2, indexable);
+ area2 = index::area(box2);
+ }
+
+ assert(!elements_copy.empty());
+ elements_copy.erase(--el_it.base());
+
+ assert(0 < remaining);
+ --remaining;
+ }
+ }
+
+ // sprawdzic szukanie najmniejszego powiekszenia wezla dla grupy1 i grupy2
+
+ template <typename It>
+ static inline It pick_next(It first, It last,
+ Box const& box1, Box const& box2,
+ area_type const& area1, area_type const& area2,
+ Translator const& tr,
+ area_type & out_area_increase1, area_type & out_area_increase2)
+ {
+ typedef typename boost::iterator_value<It>::type element_type;
+ typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
+
+ area_type greatest_area_incrase_diff = 0;
+ It out_it = first;
+ out_area_increase1 = 0;
+ out_area_increase2 = 0;
+
+ // find element with greatest difference between increased group's boxes areas
+ for ( It el_it = first ; el_it != last ; ++el_it )
+ {
+ indexable_type const& indexable = rtree::element_indexable(*el_it, tr);
+
+ // calculate enlarged boxes and areas
+ Box enlarged_box1(box1);
+ Box enlarged_box2(box2);
+ geometry::expand(enlarged_box1, indexable);
+ geometry::expand(enlarged_box2, indexable);
+ area_type enlarged_area1 = index::area(enlarged_box1);
+ area_type enlarged_area2 = index::area(enlarged_box2);
+
+ area_type area_incrase1 = (enlarged_area1 - area1);
+ area_type area_incrase2 = (enlarged_area2 - area2);
+
+ area_type area_incrase_diff = area_incrase1 < area_incrase2 ?
+ area_incrase2 - area_incrase1 : area_incrase1 - area_incrase2;
+
+ if ( greatest_area_incrase_diff < area_incrase_diff )
+ {
+ greatest_area_incrase_diff = area_incrase_diff;
+ out_it = el_it;
+ out_area_increase1 = area_incrase1;
+ out_area_increase2 = area_incrase2;
+ }
+ }
+
+ return out_it;
+ }
+};
+
+} // namespace detail
+
+}}} // namespace detail::rtree::visitors
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_REDISTRIBUTE_ELEMENTS_HPP
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/rstar.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/rstar.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/rstar.hpp 2011-05-11 17:15:00 EDT (Wed, 11 May 2011)
@@ -17,7 +17,6 @@
}}} // namespace boost::geometry::index
#include <boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp>
-
-#include <boost/geometry/extensions/index/rtree/rstar/insert.hpp>
+#include <boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp>
#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_RSTAR_HPP
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp 2011-05-11 17:15:00 EDT (Wed, 11 May 2011)
@@ -21,10 +21,7 @@
#include <boost/geometry/extensions/index/rtree/visitors/remove.hpp>
#include <boost/geometry/extensions/index/rtree/linear/linear.hpp>
-
#include <boost/geometry/extensions/index/rtree/quadratic/quadratic.hpp>
-
-// TODO: awulkiew - correct implementation
//#include <boost/geometry/extensions/index/rtree/rstar/rstar.hpp>
namespace boost { namespace geometry { namespace index {
Modified: sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp (original)
+++ sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp 2011-05-11 17:15:00 EDT (Wed, 11 May 2011)
@@ -6,7 +6,7 @@
#include <boost/timer.hpp>
#include <boost/foreach.hpp>
-#include <boost/geometry/extensions/index/rtree/visitors/save.hpp>
+//#include <boost/geometry/extensions/index/rtree/visitors/save.hpp>
int main()
{
@@ -19,6 +19,7 @@
typedef bg::model::box<P> B;
typedef bgi::rtree<std::pair<B, size_t>, bgi::default_parameter, bgi::linear_tag> RT;
//typedef bgi::rtree<std::pair<B, size_t>, bgi::default_parameter, bgi::quadratic_tag> RT;
+ //typedef bgi::rtree<std::pair<B, size_t>, bgi::default_parameter, bgi::rstar_tag> RT;
std::ifstream file_cfg("config.txt");
size_t max_elems = 4;
@@ -60,7 +61,7 @@
std::cout << "time: " << tim.elapsed() << "s\n";
}
- if ( save_ch == 's' )
+ /*if ( save_ch == 's' )
{
std::cout << "saving...\n";
std::ofstream file("save_new.txt", std::ofstream::trunc);
@@ -73,7 +74,7 @@
> saving_v(file, t.get_translator());
t.apply_visitor(saving_v);
std::cout << "saved...\n";
- }
+ }*/
{
std::cout << "searching time test...\n";