Subject: [Boost-commit] svn:boost r69839 - in trunk/boost/geometry/algorithms/detail: . overlay
From: barend.gehrels_at_[hidden]
Date: 2011-03-11 06:36:46
Author: barendgehrels
Date: 2011-03-11 06:36:43 EST (Fri, 11 Mar 2011)
New Revision: 69839
URL: http://svn.boost.org/trac/boost/changeset/69839
Log:
Worked on divide_and_conquer, now called partition, extra internal vectors with exceeding were not necessary, and therefore the mapping with processed-info neither
Added:
trunk/boost/geometry/algorithms/detail/partition.hpp
- copied, changed from r69828, /trunk/boost/geometry/algorithms/detail/divide_and_conquer.hpp
Removed:
trunk/boost/geometry/algorithms/detail/divide_and_conquer.hpp
Text files modified:
trunk/boost/geometry/algorithms/detail/overlay/assign_parents.hpp | 126 ++++++++++-----------
trunk/boost/geometry/algorithms/detail/partition.hpp | 229 ++++++++++++++-------------------------
2 files changed, 143 insertions(+), 212 deletions(-)
Deleted: trunk/boost/geometry/algorithms/detail/divide_and_conquer.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/divide_and_conquer.hpp 2011-03-11 06:36:43 EST (Fri, 11 Mar 2011)
+++ (empty file)
@@ -1,263 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Copyright Barend Gehrels 2010, Geodan, Amsterdam, the Netherlands.
-// 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_ALGORITHMS_DETAIL_DIVIDE_AND_CONQUER_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DIVIDE_AND_CONQUER_HPP
-
-#include <vector>
-#include <boost/range/algorithm/copy.hpp>
-#include <boost/geometry/core/coordinate_type.hpp>
-
-namespace boost { namespace geometry
-{
-
-
-namespace detail
-{
-
-// Helper structure
-struct dac_index
-{
- int index; // in original vector
- bool is_quad_exceeding;
-
- dac_index(int i = 0)
- : index(i)
- , is_quad_exceeding(false)
- {}
-};
-
-
-class avoid_duplicates_helper
-{
- std::set<std::pair<int,int> > processed;
-
-public :
- template <typename Item>
- inline bool apply(Item const& item1, Item const& item2)
- {
- bool done = false;
- if (item1.is_quad_exceeding && item2.is_quad_exceeding)
- {
- std::pair<int,int> p;
- if (item1.index < item2.index)
- {
- p.first = item1.index;
- p.second = item2.index;
- }
- else
- {
- p.first = item2.index;
- p.second = item1.index;
- }
-
- BOOST_AUTO(sit, processed.find(p));
- if (sit == boost::end(processed))
- {
- processed.insert(p);
- }
- else
- {
- done = true;
- }
- }
- return !done;
- }
-};
-
-template <typename Visitor>
-class dac_static_visitor_avoiding_duplicates
-{
- typedef std::vector<dac_index> dac_vector_type;
- typedef boost::range_iterator<dac_vector_type const>::type dac_iterator_type;
-
- avoid_duplicates_helper avoid_duplicates;
- Visitor& m_visitor;
-
-public :
- dac_static_visitor_avoiding_duplicates(Visitor& visitor)
- : m_visitor(visitor)
- {}
-
- template <typename InputCollection>
- inline void apply(InputCollection const& collection,
- dac_vector_type const& indexes)
- {
- // Quadratic loop over the lowest quad
- for(dac_iterator_type it1 = boost::begin(indexes); it1 != boost::end(indexes); ++it1)
- {
- for(dac_iterator_type it2 = boost::begin(indexes); it2 != boost::end(indexes); ++it2)
- {
- // This policy always calls in order of original colection
- if (it1->index < it2->index)
- {
- // This policy avoids handlig duplicates
- if (avoid_duplicates.apply(*it1, *it2))
- {
- m_visitor.apply(collection[it1->index], collection[it2->index],
- it1->is_quad_exceeding, it2->is_quad_exceeding);
- }
- }
- }
- }
- }
-};
-
-
-template
-<
- int Dimension,
- typename Box,
- typename OverlapsPolicy
->
-struct divide_and_conquer
-{
- typedef typename coordinate_type<Box>::type ctype;
-
- template <typename InputCollection, typename Policy>
- static inline void next_level(Box const& box,
- InputCollection const& collection,
- std::vector<dac_index> const& fitting_in_quad,
- std::vector<dac_index> exceeding_quad, // effectively const
- int level, int min_elements,
- Policy& policy)
- {
- typedef divide_and_conquer
- <
- 1 - Dimension,
- Box,
- OverlapsPolicy
- > sub_divide;
-
- if (level < 50
- && boost::size(fitting_in_quad) > min_elements
- && boost::size(fitting_in_quad) > boost::size(exceeding_quad)
- )
- {
- sub_divide::apply(box, collection, fitting_in_quad, exceeding_quad, level + 1, min_elements, policy);
- }
- else
- {
- boost::copy(fitting_in_quad, std::back_inserter(exceeding_quad));
- policy.apply(collection, exceeding_quad);
- }
- }
-
- template <typename InputCollection, typename Policy>
- static inline void apply(Box const& box,
- InputCollection const& collection,
- std::vector<dac_index> const& fitting_in_quad,
- std::vector<dac_index>& exceeding_quad, // by value is intentional
- int level,
- int min_elements,
- Policy& policy,
- int size = -1)
- {
-
- typedef typename boost::range_value<InputCollection>::type item_type;
-
- if (size == -1)
- {
- size = boost::size(collection);
- }
-
- // Divide input box into two parts, e.g. left/right
- ctype two = 2;
- ctype mid = (geometry::get<min_corner, Dimension>(box)
- + geometry::get<max_corner, Dimension>(box)) / two;
-
- Box lower = box, upper = box;
- geometry::set<max_corner, Dimension>(lower, mid);
- geometry::set<min_corner, Dimension>(upper, mid);
-
- // Divide collection into three subsets: lower, upper and oversized (not-fitting)
- // (lower == left or bottom, upper == right or top)
- std::vector<dac_index> lower_index, upper_index;
- bool has_exceeding = false;
- for(std::vector<dac_index>::const_iterator it = boost::begin(fitting_in_quad); it != boost::end(fitting_in_quad); ++it)
- {
- bool const overlaps_lower = OverlapsPolicy::apply(lower, collection[it->index]);
- bool const overlaps_upper = OverlapsPolicy::apply(upper, collection[it->index]);
-
- if (overlaps_lower && overlaps_upper)
- {
- dac_index oversized = *it;
- oversized.is_quad_exceeding = true;
- has_exceeding = true;
- exceeding_quad.push_back(oversized);
- }
- else if (overlaps_lower)
- {
- lower_index.push_back(*it);
- }
- else if (overlaps_upper)
- {
- upper_index.push_back(*it);
- }
- else
- {
- // Is nowhere! Should not occur!
- BOOST_ASSERT(true);
- }
- }
-
- // Recursively call operation both halves
- if (boost::size(lower_index) > 0 || has_exceeding)
- {
- next_level(lower, collection, lower_index, exceeding_quad, level, min_elements, policy);
- }
- if (boost::size(upper_index) > 0)
- {
- next_level(upper, collection, upper_index, exceeding_quad, level, min_elements, policy);
- }
- }
-};
-}
-
-
-template
-<
- typename Box,
- typename ExpandPolicy,
- typename OverlapsPolicy
->
-struct divide_and_conquer
-{
-
- template <typename InputCollection, typename Visitor>
- static inline void apply(InputCollection const& collection, Visitor& visitor, int min_elements = 16)
- {
- std::vector<detail::dac_index> index_vector, empty;
-
-
- // Determine total box
- Box total;
- assign_inverse(total);
- int index = 0;
- for(typename boost::range_iterator<InputCollection const>::type it
- = boost::begin(collection);
- it != boost::end(collection);
- ++it, ++index)
- {
- ExpandPolicy::apply(total, *it);
- index_vector.push_back(detail::dac_index(index));
- }
-
- // First call to recursive function
- detail::dac_static_visitor_avoiding_duplicates<Visitor> policy(visitor);
- detail::divide_and_conquer
- <
- 0, Box, OverlapsPolicy
- >::apply(total, collection, index_vector, empty, 0, min_elements, policy);
- }
-};
-
-
-}} // namespace boost::geometry
-
-
-#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RING_IDENTIFIER_HPP
Modified: trunk/boost/geometry/algorithms/detail/overlay/assign_parents.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/assign_parents.hpp (original)
+++ trunk/boost/geometry/algorithms/detail/overlay/assign_parents.hpp 2011-03-11 06:36:43 EST (Fri, 11 Mar 2011)
@@ -10,7 +10,7 @@
#include <boost/geometry/algorithms/area.hpp>
#include <boost/geometry/algorithms/envelope.hpp>
-#include <boost/geometry/algorithms/detail/divide_and_conquer.hpp>
+#include <boost/geometry/algorithms/detail/partition.hpp>
#include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
#include <boost/geometry/algorithms/detail/overlay/within_util.hpp>
@@ -31,7 +31,7 @@
typename Geometry1, typename Geometry2,
typename RingCollection
>
-static inline bool within_selected_input(Item const& item2, ring_identifier const& ring_id,
+static inline bool within_selected_input(Item const& item2, ring_identifier const& ring_id,
Geometry1 const& geometry1, Geometry2 const& geometry2,
RingCollection const& collection)
{
@@ -68,10 +68,13 @@
area_type abs_area;
model::box<Point> envelope;
+ inline ring_info_helper()
+ : real_area(0), abs_area(0)
+ {}
+
inline ring_info_helper(ring_identifier i, area_type a)
: id(i), real_area(a), abs_area(abs(a))
{}
-
};
@@ -105,7 +108,7 @@
bool m_check_for_orientation;
- inline assign_visitor(Geometry1 const& g1, Geometry2 const& g2, Collection const& c,
+ inline assign_visitor(Geometry1 const& g1, Geometry2 const& g2, Collection const& c,
RingMap& map, bool check)
: m_geometry1(g1)
, m_geometry2(g2)
@@ -115,12 +118,12 @@
{}
template <typename Item>
- inline void apply(Item const& outer, Item const& inner, bool , bool , bool first = true)
+ inline void apply(Item const& outer, Item const& inner, bool first = true)
{
if (first && outer.real_area < 0)
{
- // Call reversed function
- apply(inner, outer, false, false, false);
+ // Reverse arguments
+ apply(inner, outer, false);
return;
}
@@ -135,7 +138,7 @@
)
{
// Only assign parent if that parent is smaller (or if it is the first)
- if (inner_in_map.parent.source_index == -1
+ if (inner_in_map.parent.source_index == -1
|| outer.abs_area < inner_in_map.parent_area)
{
inner_in_map.parent = outer.id;
@@ -171,8 +174,6 @@
typedef typename RingMap::iterator map_iterator_type;
-
- // A map is not sortable, so copy ring_id/area and added envelope to vector
{
typedef ring_info_helper<point_type> helper;
typedef std::vector<helper> vector_type;
@@ -182,34 +183,38 @@
boost::timer timer;
#endif
- vector_type vector;
- vector.reserve(ring_map.size());
- int count_total = ring_map.size();
- int count_positive = 0;
+ std::size_t count_total = ring_map.size();
+ std::size_t count_positive = 0;
+ int index_positive = -1;
+ std::size_t index = 0;
- for (map_iterator_type it = boost::begin(ring_map); it != boost::end(ring_map); ++it)
+ // Copy to vector (with new approach this might be obsolete as well, using the map directly)
+ vector_type vector(count_total);
+
+ for (map_iterator_type it = boost::begin(ring_map); it != boost::end(ring_map); ++it, ++index)
{
- vector.push_back(helper(it->first, it->second.get_area()));
- helper& back = vector.back();
+ vector[index] = helper(it->first, it->second.get_area());
+ helper& item = vector[index];
switch(it->first.source_index)
{
case 0 :
geometry::envelope(get_ring<tag1>::apply(it->first, geometry1),
- back.envelope);
+ item.envelope);
break;
case 1 :
geometry::envelope(get_ring<tag2>::apply(it->first, geometry2),
- back.envelope);
+ item.envelope);
break;
case 2 :
geometry::envelope(get_ring<void>::apply(it->first, collection),
- back.envelope);
+ item.envelope);
break;
}
- if (back.real_area > 0)
+ if (item.real_area > 0)
{
count_positive++;
+ index_positive = index;
}
}
@@ -217,62 +222,49 @@
std::cout << " ap: created helper vector: " << timer.elapsed() << std::endl;
#endif
- if (count_positive == count_total && ! check_for_orientation)
+ if (! check_for_orientation)
{
- // Only positive rings, no assignment of parents or reversal necessary, ready here.
- return;
- }
+ if (count_positive == count_total)
+ {
+ // Optimization for only positive rings
+ // -> no assignment of parents or reversal necessary, ready here.
+ return;
+ }
- // If there are only a few positive rings, the loop below is not quadratic and can be handled.
- // If there are many positive rings + many negative ones, we divide and conquer.
- if (count_positive < 5)
- {
- // Assign parents
- // Semi-quadratic loop over rings to compare them to each other (envelope first)
- // Walks from largest abs(area) to smallest -> most direct parent comes last.
- int np = 0, nn = 0;
- for (vector_iterator_type out_it = boost::begin(vector);
- out_it != boost::end(vector); ++out_it)
+ if (count_positive == 1)
{
- if (out_it->real_area > 0)
+ // Optimization for one outer ring
+ // -> assign this as parent to all others (all interior rings)
+ // In unions, this is probably the most occuring case and gives
+ // a dramatic improvement (factor 5 for star_comb testcase)
+ ring_identifier id_of_positive = vector[index_positive].id;
+ ring_info_type& outer = ring_map[id_of_positive];
+ std::size_t index = 0;
+ for (vector_iterator_type it = boost::begin(vector);
+ it != boost::end(vector); ++it, ++index)
{
- np++;
- vector_iterator_type inn_it = out_it;
- for (vector_iterator_type inn_it = boost::begin(vector);
- inn_it != boost::end(vector); ++inn_it)
+ if (index != index_positive)
{
- // TODO: this is effectively now the same as above (in visitor), harmonize
- if ( (inn_it->real_area < 0 || check_for_orientation))
- {
- ring_info_type& inner = ring_map[inn_it->id];
- if (geometry::within(inner.point, out_it->envelope)
- && within_selected_input(inner, out_it->id, geometry1, geometry2, collection))
- {
- if (inner.parent.source_index == -1 || out_it->abs_area < inner.parent_area)
- {
- inner.parent = out_it->id;
- inner.parent_area = out_it->abs_area;
- }
- }
- }
+ ring_info_type& inner = ring_map[it->id];
+ inner.parent = id_of_positive;
+ outer.children.push_back(it->id);
}
}
- else
- {
- nn++;
- }
+ return;
}
}
- else
- {
- assign_visitor<Geometry1, Geometry2, RingCollection, RingMap>
- visitor(geometry1, geometry2, collection, ring_map, check_for_orientation);
- geometry::divide_and_conquer
- <
- box_type, ring_info_helper_get_box, ring_info_helper_ovelaps_box
- >::apply(vector, visitor, 32);
- }
+ assign_visitor
+ <
+ Geometry1, Geometry2,
+ RingCollection, RingMap
+ > visitor(geometry1, geometry2, collection, ring_map, check_for_orientation);
+
+ geometry::partition
+ <
+ box_type, ring_info_helper_get_box, ring_info_helper_ovelaps_box
+ >::apply(vector, visitor);
+
#ifdef BOOST_GEOMETRY_TIME_OVERLAY
std::cout << " ap: quadradic loop: " << timer.elapsed() << std::endl;
std::cout << " ap: POS " << np << " NEG: " << nn << std::endl;
Copied: trunk/boost/geometry/algorithms/detail/partition.hpp (from r69828, /trunk/boost/geometry/algorithms/detail/divide_and_conquer.hpp)
==============================================================================
--- /trunk/boost/geometry/algorithms/detail/divide_and_conquer.hpp (original)
+++ trunk/boost/geometry/algorithms/detail/partition.hpp 2011-03-11 06:36:43 EST (Fri, 11 Mar 2011)
@@ -5,8 +5,8 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DIVIDE_AND_CONQUER_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DIVIDE_AND_CONQUER_HPP
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP
#include <vector>
#include <boost/range/algorithm/copy.hpp>
@@ -19,184 +19,119 @@
namespace detail
{
-// Helper structure
-struct dac_index
+template
+<
+ int Dimension,
+ typename Box,
+ typename OverlapsPolicy
+>
+class partition
{
- int index; // in original vector
- bool is_quad_exceeding;
-
- dac_index(int i = 0)
- : index(i)
- , is_quad_exceeding(false)
- {}
-};
-
+ typedef typename coordinate_type<Box>::type ctype;
+ typedef std::vector<std::size_t> index_vector_type;
+ typedef boost::range_iterator<index_vector_type const>::type index_iterator_type;
+ typedef partition
+ <
+ 1 - Dimension,
+ Box,
+ OverlapsPolicy
+ > sub_divide;
-class avoid_duplicates_helper
-{
- std::set<std::pair<int,int> > processed;
-public :
- template <typename Item>
- inline bool apply(Item const& item1, Item const& item2)
+ template <typename InputCollection, typename Policy>
+ static inline void handle(InputCollection const& collection,
+ index_vector_type const& input,
+ Policy& policy)
{
- bool done = false;
- if (item1.is_quad_exceeding && item2.is_quad_exceeding)
+ // Quadratic behaviour at lowest level (lowest quad, or all exceeding)
+ for(index_iterator_type it1 = boost::begin(input); it1 != boost::end(input); ++it1)
{
- std::pair<int,int> p;
- if (item1.index < item2.index)
- {
- p.first = item1.index;
- p.second = item2.index;
- }
- else
- {
- p.first = item2.index;
- p.second = item1.index;
- }
-
- BOOST_AUTO(sit, processed.find(p));
- if (sit == boost::end(processed))
- {
- processed.insert(p);
- }
- else
+ for(index_iterator_type it2 = boost::begin(input); it2 != boost::end(input); ++it2)
{
- done = true;
+ policy.apply(collection[*it1], collection[*it2]);
}
}
- return !done;
}
-};
-
-template <typename Visitor>
-class dac_static_visitor_avoiding_duplicates
-{
- typedef std::vector<dac_index> dac_vector_type;
- typedef boost::range_iterator<dac_vector_type const>::type dac_iterator_type;
-
- avoid_duplicates_helper avoid_duplicates;
- Visitor& m_visitor;
-public :
- dac_static_visitor_avoiding_duplicates(Visitor& visitor)
- : m_visitor(visitor)
- {}
-
- template <typename InputCollection>
- inline void apply(InputCollection const& collection,
- dac_vector_type const& indexes)
+ template <typename InputCollection, typename Policy>
+ static inline void handle_exceeding(InputCollection const& collection,
+ index_vector_type const& exceeding,
+ index_vector_type const& input,
+ Policy& policy)
{
- // Quadratic loop over the lowest quad
- for(dac_iterator_type it1 = boost::begin(indexes); it1 != boost::end(indexes); ++it1)
+ if (boost::size(input) > 0)
{
- for(dac_iterator_type it2 = boost::begin(indexes); it2 != boost::end(indexes); ++it2)
+ for(index_iterator_type it1 = boost::begin(exceeding); it1 != boost::end(exceeding); ++it1)
{
- // This policy always calls in order of original colection
- if (it1->index < it2->index)
+ for(index_iterator_type it2 = boost::begin(input); it2 != boost::end(input); ++it2)
{
- // This policy avoids handlig duplicates
- if (avoid_duplicates.apply(*it1, *it2))
- {
- m_visitor.apply(collection[it1->index], collection[it2->index],
- it1->is_quad_exceeding, it2->is_quad_exceeding);
- }
+ policy.apply(collection[*it1], collection[*it2]);
}
}
}
}
-};
-
-
-template
-<
- int Dimension,
- typename Box,
- typename OverlapsPolicy
->
-struct divide_and_conquer
-{
- typedef typename coordinate_type<Box>::type ctype;
template <typename InputCollection, typename Policy>
- static inline void next_level(Box const& box,
+ static inline void next_level(Box const& box,
InputCollection const& collection,
- std::vector<dac_index> const& fitting_in_quad,
- std::vector<dac_index> exceeding_quad, // effectively const
+ index_vector_type const& input,
int level, int min_elements,
Policy& policy)
{
- typedef divide_and_conquer
- <
- 1 - Dimension,
- Box,
- OverlapsPolicy
- > sub_divide;
-
- if (level < 50
- && boost::size(fitting_in_quad) > min_elements
- && boost::size(fitting_in_quad) > boost::size(exceeding_quad)
- )
- {
- sub_divide::apply(box, collection, fitting_in_quad, exceeding_quad, level + 1, min_elements, policy);
- }
- else
+ if (boost::size(input) > 0)
{
- boost::copy(fitting_in_quad, std::back_inserter(exceeding_quad));
- policy.apply(collection, exceeding_quad);
+ if (boost::size(input) > min_elements && level < 100)
+ {
+ sub_divide::apply(box, collection, input, level + 1, min_elements, policy);
+ }
+ else
+ {
+ handle(collection, input, policy);
+ }
}
}
+public :
template <typename InputCollection, typename Policy>
static inline void apply(Box const& box,
InputCollection const& collection,
- std::vector<dac_index> const& fitting_in_quad,
- std::vector<dac_index>& exceeding_quad, // by value is intentional
+ index_vector_type const& input,
int level,
int min_elements,
- Policy& policy,
- int size = -1)
+ Policy& policy)
{
-
typedef typename boost::range_value<InputCollection>::type item_type;
- if (size == -1)
- {
- size = boost::size(collection);
- }
-
// Divide input box into two parts, e.g. left/right
ctype two = 2;
ctype mid = (geometry::get<min_corner, Dimension>(box)
+ geometry::get<max_corner, Dimension>(box)) / two;
- Box lower = box, upper = box;
- geometry::set<max_corner, Dimension>(lower, mid);
- geometry::set<min_corner, Dimension>(upper, mid);
+ Box lower_box = box, upper_box = box;
+ geometry::set<max_corner, Dimension>(lower_box, mid);
+ geometry::set<min_corner, Dimension>(upper_box, mid);
// Divide collection into three subsets: lower, upper and oversized (not-fitting)
// (lower == left or bottom, upper == right or top)
- std::vector<dac_index> lower_index, upper_index;
- bool has_exceeding = false;
- for(std::vector<dac_index>::const_iterator it = boost::begin(fitting_in_quad); it != boost::end(fitting_in_quad); ++it)
+ index_vector_type lower, upper, exceeding;
+ for(index_iterator_type it = boost::begin(input);
+ it != boost::end(input);
+ ++it)
{
- bool const overlaps_lower = OverlapsPolicy::apply(lower, collection[it->index]);
- bool const overlaps_upper = OverlapsPolicy::apply(upper, collection[it->index]);
+ bool const lower_overlapping = OverlapsPolicy::apply(lower_box, collection[*it]);
+ bool const upper_overlapping = OverlapsPolicy::apply(upper_box, collection[*it]);
- if (overlaps_lower && overlaps_upper)
+ if (lower_overlapping && upper_overlapping)
{
- dac_index oversized = *it;
- oversized.is_quad_exceeding = true;
- has_exceeding = true;
- exceeding_quad.push_back(oversized);
+ exceeding.push_back(*it);
}
- else if (overlaps_lower)
+ else if (lower_overlapping)
{
- lower_index.push_back(*it);
+ lower.push_back(*it);
}
- else if (overlaps_upper)
+ else if (upper_overlapping)
{
- upper_index.push_back(*it);
+ upper.push_back(*it);
}
else
{
@@ -205,17 +140,21 @@
}
}
- // Recursively call operation both halves
- if (boost::size(lower_index) > 0 || has_exceeding)
+ if (boost::size(exceeding) > 0)
{
- next_level(lower, collection, lower_index, exceeding_quad, level, min_elements, policy);
- }
- if (boost::size(upper_index) > 0)
- {
- next_level(upper, collection, upper_index, exceeding_quad, level, min_elements, policy);
+ // All what is not fitting a partition should be combined
+ // with each other, and with all which is fitting.
+ handle(collection, exceeding, policy);
+ handle_exceeding(collection, exceeding, lower, policy);
+ handle_exceeding(collection, exceeding, upper, policy);
}
+
+ // Recursively call operation both halves
+ next_level(lower_box, collection, lower, level, min_elements, policy);
+ next_level(upper_box, collection, upper, level, min_elements, policy);
}
};
+
}
@@ -225,34 +164,34 @@
typename ExpandPolicy,
typename OverlapsPolicy
>
-struct divide_and_conquer
+class partition
{
+ typedef std::vector<std::size_t> index_vector_type;
+public :
template <typename InputCollection, typename Visitor>
static inline void apply(InputCollection const& collection, Visitor& visitor, int min_elements = 16)
{
- std::vector<detail::dac_index> index_vector, empty;
-
+ index_vector_type index_vector;
// Determine total box
Box total;
assign_inverse(total);
- int index = 0;
+ std::size_t index = 0;
for(typename boost::range_iterator<InputCollection const>::type it
= boost::begin(collection);
it != boost::end(collection);
++it, ++index)
{
ExpandPolicy::apply(total, *it);
- index_vector.push_back(detail::dac_index(index));
+ index_vector.push_back(index);
}
- // First call to recursive function
- detail::dac_static_visitor_avoiding_duplicates<Visitor> policy(visitor);
- detail::divide_and_conquer
+ // Start recursion
+ detail::partition
<
0, Box, OverlapsPolicy
- >::apply(total, collection, index_vector, empty, 0, min_elements, policy);
+ >::apply(total, collection, index_vector, 0, min_elements, visitor);
}
};