Subject: [Boost-commit] svn:boost r71755 - in sandbox-branches/geometry/index_080_new: boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/linear boost/geometry/extensions/index/rtree/quadratic boost/geometry/extensions/index/rtree/visitors tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-05-05 20:51:50
Author: awulkiew
Date: 2011-05-05 20:51:49 EDT (Thu, 05 May 2011)
New Revision: 71755
URL: http://svn.boost.org/trac/boost/changeset/71755
Log:
quadratic split algorithm added, error in linear split corrected
Text files modified:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp | 87 ++++++-----------
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp | 184 +++++++++++++++++++++++++++++++++++++++
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp | 3
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/insert.hpp | 2
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/remove.hpp | 3
sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp | 2
sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp | 3
7 files changed, 221 insertions(+), 63 deletions(-)
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp 2011-05-05 20:51:49 EDT (Thu, 05 May 2011)
@@ -193,8 +193,6 @@
typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
typedef typename index::traits::coordinate_type<indexable_type>::type coordinate_type;
typedef typename index::default_area_result<Box>::type area_type;
-
- static const size_t dimension = index::traits::dimension<indexable_type>::value;
// copy original elements
elements_type elements_copy = rtree::elements_get(n);
@@ -233,27 +231,21 @@
{
element_type const& elem = elements_copy[i];
indexable_type const& indexable = rtree::element_indexable(elem, tr);
+ bool insert_into_group1 = false;
// 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.size() + remaining == min_elems )
+ if ( elements1.size() + remaining <= min_elems )
{
- elements1.push_back(elem);
- geometry::expand(box1, indexable);
- area1 = index::area(box1);
+ insert_into_group1 = true;
}
- else if ( elements2.size() + remaining == min_elems )
+ else if ( elements2.size() + remaining <= min_elems )
{
- elements2.push_back(elem);
- geometry::expand(box2, indexable);
- area2 = index::area(box2);
+ insert_into_group1 = false;
}
// choose better node and insert element
else
{
- assert(0 < remaining);
- remaining--;
-
// calculate enlarged boxes and areas
Box enlarged_box1(box1);
Box enlarged_box2(box2);
@@ -262,57 +254,42 @@
area_type enlarged_area1 = index::area(enlarged_box1);
area_type enlarged_area2 = index::area(enlarged_box2);
- area_type areas_diff1 = enlarged_area1 - area1;
- area_type areas_diff2 = enlarged_area2 - area2;
+ area_type area_increase1 = enlarged_area1 - area1;
+ area_type area_increase2 = enlarged_area2 - area2;
- // choose group which box area have to be enlarged least
- if ( areas_diff1 < areas_diff2 )
- {
- elements1.push_back(elem);
- box1 = enlarged_box1;
- area1 = enlarged_area1;
- }
- else if ( areas_diff2 < areas_diff1 )
+ // choose group which box area have to be enlarged least or has smaller area or has fewer elements
+ if ( area_increase1 < area_increase2 ||
+ ( area_increase1 == area_increase2 && area1 < area2 ) ||
+ ( area1 == area2 && elements1.size() <= elements2.size() ) )
{
- elements2.push_back(elem);
- box2 = enlarged_box2;
- area2 = enlarged_area2;
+ insert_into_group1 = true;
}
else
{
- // choose group which box has smaller area
- if ( area1 < area2 )
- {
- elements1.push_back(elem);
- box1 = enlarged_box1;
- area1 = enlarged_area1;
- }
- else if ( area2 < area1 )
- {
- elements2.push_back(elem);
- box2 = enlarged_box2;
- area2 = enlarged_area2;
- }
- else
- {
- // choose group with fewer elements
- if ( elements1.size() <= elements2.size() )
- {
- elements1.push_back(elem);
- box1 = enlarged_box1;
- area1 = enlarged_area1;
- }
- else
- {
- elements2.push_back(elem);
- box2 = enlarged_box2;
- area2 = enlarged_area2;
- }
- }
+ insert_into_group1 = false;
}
}
+
+ 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(0 < remaining);
+ --remaining;
}
}
+
+ assert(min_elems <= elements1.size() && elements1.size() <= max_elems);
+ assert(min_elems <= elements2.size() && elements2.size() <= max_elems);
}
};
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-05 20:51:49 EDT (Thu, 05 May 2011)
@@ -54,11 +54,11 @@
{
for ( size_t j = i + 1 ; j < elements_count ; ++j )
{
- indexable_type & ind1 = rtree::element_indexable(elements[i], tr);
- indexable_type & ind2 = rtree::element_indexable(elements[j], tr);
+ indexable_type const& ind1 = rtree::element_indexable(elements[i], tr);
+ indexable_type const& ind2 = rtree::element_indexable(elements[j], tr);
box_type enlarged_box;
- geometry::convert(ind1);
+ geometry::convert(ind1, enlarged_box);
geometry::expand(enlarged_box, ind2);
area_type free_area = index::area(enlarged_box) - index::area(ind1) - index::area(ind2);
@@ -76,7 +76,183 @@
} // namespace quadratic
-// TODO: awulkiew - redistribute
+template <typename Value, typename Translator, typename Box>
+struct redistribute_elements<Value, Translator, Box, quadratic_tag>
+{
+ typedef typename rtree::node<Value, Box, quadratic_tag>::type node;
+ typedef typename rtree::internal_node<Value, Box, quadratic_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, Box, quadratic_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() )
+ {
+ 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;
+ pick_next(elements_copy.rbegin(), elements_copy.rend(),
+ box1, box2, area1, area2, tr,
+ el_it, 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(elements_copy.begin() + elements_copy.size() - 1);
+
+ assert(0 < remaining);
+ --remaining;
+ }
+
+ assert(min_elems <= elements1.size() && elements1.size() <= max_elems);
+ assert(min_elems <= elements2.size() && elements2.size() <= max_elems);
+ }
+
+ template <typename It>
+ static inline void pick_next(It first, It last,
+ Box const& box1, Box const& box2,
+ area_type const& area1, area_type const& area2,
+ Translator const& tr,
+ It out_it, 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;
+ out_it = first;
+ out_area_increase1 = 0;
+ out_area_increase2 = 0;
+
+ 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;
+ }
+
+ break;
+ }
+ }
+};
} // namespace detail
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-05 20:51:49 EDT (Thu, 05 May 2011)
@@ -22,8 +22,9 @@
#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/quadratic/quadratic.hpp>
//#include <boost/geometry/extensions/index/rtree/rstar/rstar.hpp>
namespace boost { namespace geometry { namespace index {
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/insert.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/insert.hpp 2011-05-05 20:51:49 EDT (Thu, 05 May 2011)
@@ -211,7 +211,7 @@
traverse_apply_visitor(visitor, n, choosen_node_index);
}
- // TODO: awulkiew - change name to handle_overflow or overflow_treatment?
+ // TODO: awulkiew - change post_traverse name to handle_overflow or overflow_treatment?
template <typename Node>
inline void post_traverse(Node &n)
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/remove.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/remove.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/remove.hpp 2011-05-05 20:51:49 EDT (Thu, 05 May 2011)
@@ -48,9 +48,12 @@
typedef typename rtree::elements_type<internal_node>::type children_type;
children_type & children = rtree::elements_get(n);
+ // traverse children which boxes intersects value's box
size_t child_node_index = 0;
for ( ; child_node_index < children.size() ; ++child_node_index )
{
+ // TODO: awulkiew - change intersects to within
+
if ( geometry::intersects(children[child_node_index].first, m_tr(m_value)) )
{
// next traversing step
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-05-05 20:51:49 EDT (Thu, 05 May 2011)
@@ -9,7 +9,7 @@
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(4, 2);
+boost::geometry::index::rtree<B, boost::geometry::index::default_parameter, boost::geometry::index::quadratic_tag> t(4, 2);
std::vector<B> vect;
void render_scene(void)
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-05 20:51:49 EDT (Thu, 05 May 2011)
@@ -17,7 +17,8 @@
typedef bg::model::point<float, 2, bg::cs::cartesian> P;
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::linear_tag> RT;
+ typedef bgi::rtree<std::pair<B, size_t>, bgi::default_parameter, bgi::quadratic_tag> RT;
std::ifstream file_cfg("config.txt");
size_t max_elems = 4;