Subject: [Boost-commit] svn:boost r71763 - in sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree: linear quadratic
From: adam.wulkiewicz_at_[hidden]
Date: 2011-05-06 09:36:37
Author: awulkiew
Date: 2011-05-06 09:36:37 EDT (Fri, 06 May 2011)
New Revision: 71763
URL: http://svn.boost.org/trac/boost/changeset/71763
Log:
quadratic split error corrected
Text files modified:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp | 30 ++++++++++++------------------
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp | 34 +++++++++++++++++++---------------
2 files changed, 31 insertions(+), 33 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-06 09:36:37 EDT (Fri, 06 May 2011)
@@ -231,17 +231,20 @@
{
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 )
{
- insert_into_group1 = true;
+ elements1.push_back(elem);
+ geometry::expand(box1, indexable);
+ area1 = index::area(box1);
}
else if ( elements2.size() + remaining <= min_elems )
{
- insert_into_group1 = false;
+ elements2.push_back(elem);
+ geometry::expand(box2, indexable);
+ area2 = index::area(box2);
}
// choose better node and insert element
else
@@ -262,26 +265,17 @@
( area_increase1 == area_increase2 && area1 < area2 ) ||
( area1 == area2 && elements1.size() <= elements2.size() ) )
{
- insert_into_group1 = true;
+ elements1.push_back(elem);
+ box1 = enlarged_box1;
+ area1 = enlarged_area1;
}
else
{
- insert_into_group1 = false;
+ elements2.push_back(elem);
+ box2 = enlarged_box2;
+ area2 = enlarged_area2;
}
}
-
- 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;
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-06 09:36:37 EDT (Fri, 06 May 2011)
@@ -47,10 +47,11 @@
assert(2 <= elements_count);
+ area_type greatest_free_area = 0;
seed1 = 0;
seed2 = 1;
- area_type greatest_free_area = 0;
- for ( size_t i = 0 ; i < elements_count ; ++i )
+
+ for ( size_t i = 0 ; i < elements_count - 1 ; ++i )
{
for ( size_t j = i + 1 ; j < elements_count ; ++j )
{
@@ -164,9 +165,9 @@
// 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);
+ 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 ) ||
@@ -198,7 +199,7 @@
}
assert(!elements_copy.empty());
- elements_copy.erase(elements_copy.begin() + elements_copy.size() - 1);
+ elements_copy.erase(--el_it.base());
assert(0 < remaining);
--remaining;
@@ -208,21 +209,24 @@
assert(min_elems <= elements2.size() && elements2.size() <= max_elems);
}
+ // sprawdzic szukanie najmniejszego powiekszenia wezla dla grupy1 i grupy2
+
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)
+ 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;
- out_it = first;
+ 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);
@@ -248,9 +252,9 @@
out_area_increase1 = area_incrase1;
out_area_increase2 = area_incrase2;
}
-
- break;
}
+
+ return out_it;
}
};