summaryrefslogtreecommitdiff
path: root/boost/geometry/algorithms/detail/partition.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/geometry/algorithms/detail/partition.hpp')
-rw-r--r--boost/geometry/algorithms/detail/partition.hpp349
1 files changed, 273 insertions, 76 deletions
diff --git a/boost/geometry/algorithms/detail/partition.hpp b/boost/geometry/algorithms/detail/partition.hpp
index a44d5637bc..25a34ba2ec 100644
--- a/boost/geometry/algorithms/detail/partition.hpp
+++ b/boost/geometry/algorithms/detail/partition.hpp
@@ -10,7 +10,6 @@
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP
#include <vector>
-#include <boost/assert.hpp>
#include <boost/range/algorithm/copy.hpp>
#include <boost/geometry/algorithms/assign.hpp>
#include <boost/geometry/core/coordinate_type.hpp>
@@ -24,7 +23,7 @@ namespace detail { namespace partition
typedef std::vector<std::size_t> index_vector_type;
template <int Dimension, typename Box>
-void divide_box(Box const& box, Box& lower_box, Box& upper_box)
+inline void divide_box(Box const& box, Box& lower_box, Box& upper_box)
{
typedef typename coordinate_type<Box>::type ctype;
@@ -79,20 +78,39 @@ inline void divide_into_subsets(Box const& lower_box,
}
else
{
- // Is nowhere! Should not occur!
- BOOST_ASSERT(false);
+ // Is nowhere. That is (since 1.58) possible, it might be
+ // skipped by the OverlapsPolicy to enhance performance
}
}
}
+template <typename ExpandPolicy, typename Box, typename InputCollection>
+inline void expand_with_elements(Box& total,
+ InputCollection const& collection,
+ index_vector_type const& input)
+{
+ typedef boost::range_iterator<index_vector_type const>::type it_type;
+ for(it_type it = boost::begin(input); it != boost::end(input); ++it)
+ {
+ ExpandPolicy::apply(total, collection[*it]);
+ }
+}
+
+
// Match collection with itself
template <typename InputCollection, typename Policy>
inline void handle_one(InputCollection const& collection,
index_vector_type const& input,
Policy& policy)
{
+ if (boost::size(input) == 0)
+ {
+ return;
+ }
+
typedef boost::range_iterator<index_vector_type const>::type
index_iterator_type;
+
// Quadratic behaviour at lowest level (lowest quad, or all exceeding)
for(index_iterator_type it1 = boost::begin(input);
it1 != boost::end(input);
@@ -118,6 +136,11 @@ inline void handle_two(
InputCollection2 const& collection2, index_vector_type const& input2,
Policy& policy)
{
+ if (boost::size(input1) == 0 || boost::size(input2) == 0)
+ {
+ return;
+ }
+
typedef boost::range_iterator
<
index_vector_type const
@@ -136,43 +159,116 @@ inline void handle_two(
}
}
+inline bool recurse_ok(index_vector_type const& input,
+ std::size_t min_elements, std::size_t level)
+{
+ return boost::size(input) >= min_elements
+ && level < 100;
+}
+
+inline bool recurse_ok(index_vector_type const& input1,
+ index_vector_type const& input2,
+ std::size_t min_elements, std::size_t level)
+{
+ return boost::size(input1) >= min_elements
+ && recurse_ok(input2, min_elements, level);
+}
+
+inline bool recurse_ok(index_vector_type const& input1,
+ index_vector_type const& input2,
+ index_vector_type const& input3,
+ std::size_t min_elements, std::size_t level)
+{
+ return boost::size(input1) >= min_elements
+ && recurse_ok(input2, input3, min_elements, level);
+}
+
+template
+<
+ int Dimension,
+ typename Box,
+ typename OverlapsPolicy1,
+ typename OverlapsPolicy2,
+ typename ExpandPolicy1,
+ typename ExpandPolicy2,
+ typename VisitBoxPolicy
+>
+class partition_two_collections;
+
+
template
<
int Dimension,
typename Box,
typename OverlapsPolicy,
+ typename ExpandPolicy,
typename VisitBoxPolicy
>
class partition_one_collection
{
typedef std::vector<std::size_t> index_vector_type;
- typedef typename coordinate_type<Box>::type ctype;
- typedef partition_one_collection
+
+ template <typename InputCollection>
+ static inline Box get_new_box(InputCollection const& collection,
+ index_vector_type const& input)
+ {
+ Box box;
+ geometry::assign_inverse(box);
+ expand_with_elements<ExpandPolicy>(box, collection, input);
+ return box;
+ }
+
+ template <typename InputCollection, typename Policy>
+ static inline void next_level(Box const& box,
+ InputCollection const& collection,
+ index_vector_type const& input,
+ std::size_t level, std::size_t min_elements,
+ Policy& policy, VisitBoxPolicy& box_policy)
+ {
+ if (recurse_ok(input, min_elements, level))
+ {
+ partition_one_collection
<
1 - Dimension,
Box,
OverlapsPolicy,
+ ExpandPolicy,
VisitBoxPolicy
- > sub_divide;
+ >::apply(box, collection, input,
+ level + 1, min_elements, policy, box_policy);
+ }
+ else
+ {
+ handle_one(collection, input, policy);
+ }
+ }
+ // Function to switch to two collections if there are geometries exceeding
+ // the separation line
template <typename InputCollection, typename Policy>
- static inline void next_level(Box const& box,
+ static inline void next_level2(Box const& box,
InputCollection const& collection,
- index_vector_type const& input,
- int level, std::size_t min_elements,
+ index_vector_type const& input1,
+ index_vector_type const& input2,
+ std::size_t level, std::size_t min_elements,
Policy& policy, VisitBoxPolicy& box_policy)
{
- if (boost::size(input) > 0)
+
+ if (recurse_ok(input1, input2, min_elements, level))
{
- if (std::size_t(boost::size(input)) > min_elements && level < 100)
- {
- sub_divide::apply(box, collection, input, level + 1,
- min_elements, policy, box_policy);
- }
- else
- {
- handle_one(collection, input, policy);
- }
+ partition_two_collections
+ <
+ 1 - Dimension,
+ Box,
+ OverlapsPolicy, OverlapsPolicy,
+ ExpandPolicy, ExpandPolicy,
+ VisitBoxPolicy
+ >::apply(box, collection, input1, collection, input2,
+ level + 1, min_elements, policy, box_policy);
+ }
+ else
+ {
+ handle_two(collection, input1, collection, input2, policy);
}
}
@@ -181,7 +277,7 @@ public :
static inline void apply(Box const& box,
InputCollection const& collection,
index_vector_type const& input,
- int level,
+ std::size_t level,
std::size_t min_elements,
Policy& policy, VisitBoxPolicy& box_policy)
{
@@ -196,11 +292,20 @@ public :
if (boost::size(exceeding) > 0)
{
- // All what is not fitting a partition should be combined
- // with each other, and with all which is fitting.
- handle_one(collection, exceeding, policy);
- handle_two(collection, exceeding, collection, lower, policy);
- handle_two(collection, exceeding, collection, upper, policy);
+ // Get the box of exceeding-only
+ Box exceeding_box = get_new_box(collection, exceeding);
+
+ // Recursively do exceeding elements only, in next dimension they
+ // will probably be less exceeding within the new box
+ next_level(exceeding_box, collection, exceeding, level,
+ min_elements, policy, box_policy);
+
+ // Switch to two collections, combine exceeding with lower resp upper
+ // but not lower/lower, upper/upper
+ next_level2(exceeding_box, collection, exceeding, lower, level,
+ min_elements, policy, box_policy);
+ next_level2(exceeding_box, collection, exceeding, upper, level,
+ min_elements, policy, box_policy);
}
// Recursively call operation both parts
@@ -217,20 +322,13 @@ template
typename Box,
typename OverlapsPolicy1,
typename OverlapsPolicy2,
+ typename ExpandPolicy1,
+ typename ExpandPolicy2,
typename VisitBoxPolicy
>
class partition_two_collections
{
typedef std::vector<std::size_t> index_vector_type;
- typedef typename coordinate_type<Box>::type ctype;
- typedef partition_two_collections
- <
- 1 - Dimension,
- Box,
- OverlapsPolicy1,
- OverlapsPolicy2,
- VisitBoxPolicy
- > sub_divide;
template
<
@@ -243,25 +341,50 @@ class partition_two_collections
index_vector_type const& input1,
InputCollection2 const& collection2,
index_vector_type const& input2,
- int level, std::size_t min_elements,
+ std::size_t level, std::size_t min_elements,
Policy& policy, VisitBoxPolicy& box_policy)
{
- if (boost::size(input1) > 0 && boost::size(input2) > 0)
- {
- if (std::size_t(boost::size(input1)) > min_elements
- && std::size_t(boost::size(input2)) > min_elements
- && level < 100)
- {
- sub_divide::apply(box, collection1, input1, collection2,
- input2, level + 1, min_elements,
- policy, box_policy);
- }
- else
- {
- box_policy.apply(box, level + 1);
- handle_two(collection1, input1, collection2, input2, policy);
- }
- }
+ partition_two_collections
+ <
+ 1 - Dimension,
+ Box,
+ OverlapsPolicy1,
+ OverlapsPolicy2,
+ ExpandPolicy1,
+ ExpandPolicy2,
+ VisitBoxPolicy
+ >::apply(box, collection1, input1, collection2, input2,
+ level + 1, min_elements,
+ policy, box_policy);
+ }
+
+ template
+ <
+ typename ExpandPolicy,
+ typename InputCollection
+ >
+ static inline Box get_new_box(InputCollection const& collection,
+ index_vector_type const& input)
+ {
+ Box box;
+ geometry::assign_inverse(box);
+ expand_with_elements<ExpandPolicy>(box, collection, input);
+ return box;
+ }
+
+ template
+ <
+ typename InputCollection1,
+ typename InputCollection2
+ >
+ static inline Box get_new_box(InputCollection1 const& collection1,
+ index_vector_type const& input1,
+ InputCollection2 const& collection2,
+ index_vector_type const& input2)
+ {
+ Box box = get_new_box<ExpandPolicy1>(collection1, input1);
+ expand_with_elements<ExpandPolicy2>(box, collection2, input2);
+ return box;
}
public :
@@ -274,7 +397,7 @@ public :
static inline void apply(Box const& box,
InputCollection1 const& collection1, index_vector_type const& input1,
InputCollection2 const& collection2, index_vector_type const& input2,
- int level,
+ std::size_t level,
std::size_t min_elements,
Policy& policy, VisitBoxPolicy& box_policy)
{
@@ -293,36 +416,100 @@ public :
if (boost::size(exceeding1) > 0)
{
// All exceeding from 1 with 2:
- handle_two(collection1, exceeding1, collection2, exceeding2,
- policy);
+
+ if (recurse_ok(exceeding1, exceeding2, min_elements, level))
+ {
+ Box exceeding_box = get_new_box(collection1, exceeding1,
+ collection2, exceeding2);
+ next_level(exceeding_box, collection1, exceeding1,
+ collection2, exceeding2, level,
+ min_elements, policy, box_policy);
+ }
+ else
+ {
+ handle_two(collection1, exceeding1, collection2, exceeding2,
+ policy);
+ }
// All exceeding from 1 with lower and upper of 2:
- handle_two(collection1, exceeding1, collection2, lower2, policy);
- handle_two(collection1, exceeding1, collection2, upper2, policy);
+
+ // (Check sizes of all three collections to avoid recurse into
+ // the same combinations again and again)
+ if (recurse_ok(lower2, upper2, exceeding1, min_elements, level))
+ {
+ Box exceeding_box
+ = get_new_box<ExpandPolicy1>(collection1, exceeding1);
+ next_level(exceeding_box, collection1, exceeding1,
+ collection2, lower2, level, min_elements, policy, box_policy);
+ next_level(exceeding_box, collection1, exceeding1,
+ collection2, upper2, level, min_elements, policy, box_policy);
+ }
+ else
+ {
+ handle_two(collection1, exceeding1, collection2, lower2, policy);
+ handle_two(collection1, exceeding1, collection2, upper2, policy);
+ }
}
+
if (boost::size(exceeding2) > 0)
{
// All exceeding from 2 with lower and upper of 1:
- handle_two(collection1, lower1, collection2, exceeding2, policy);
- handle_two(collection1, upper1, collection2, exceeding2, policy);
+ if (recurse_ok(lower1, upper1, exceeding2, min_elements, level))
+ {
+ Box exceeding_box
+ = get_new_box<ExpandPolicy2>(collection2, exceeding2);
+ next_level(exceeding_box, collection1, lower1,
+ collection2, exceeding2, level, min_elements, policy, box_policy);
+ next_level(exceeding_box, collection1, upper1,
+ collection2, exceeding2, level, min_elements, policy, box_policy);
+ }
+ else
+ {
+ handle_two(collection1, lower1, collection2, exceeding2, policy);
+ handle_two(collection1, upper1, collection2, exceeding2, policy);
+ }
}
- next_level(lower_box, collection1, lower1, collection2, lower2, level,
- min_elements, policy, box_policy);
- next_level(upper_box, collection1, upper1, collection2, upper2, level,
- min_elements, policy, box_policy);
+ if (recurse_ok(lower1, lower2, min_elements, level))
+ {
+ next_level(lower_box, collection1, lower1, collection2, lower2, level,
+ min_elements, policy, box_policy);
+ }
+ else
+ {
+ handle_two(collection1, lower1, collection2, lower2, policy);
+ }
+ if (recurse_ok(upper1, upper2, min_elements, level))
+ {
+ next_level(upper_box, collection1, upper1, collection2, upper2, level,
+ min_elements, policy, box_policy);
+ }
+ else
+ {
+ handle_two(collection1, upper1, collection2, upper2, policy);
+ }
}
};
-}} // namespace detail::partition
-
struct visit_no_policy
{
template <typename Box>
- static inline void apply(Box const&, int )
+ static inline void apply(Box const&, std::size_t )
{}
};
+struct include_all_policy
+{
+ template <typename Item>
+ static inline bool apply(Item const&)
+ {
+ return true;
+ }
+};
+
+
+}} // namespace detail::partition
+
template
<
typename Box,
@@ -330,13 +517,15 @@ template
typename OverlapsPolicy1,
typename ExpandPolicy2 = ExpandPolicy1,
typename OverlapsPolicy2 = OverlapsPolicy1,
- typename VisitBoxPolicy = visit_no_policy
+ typename IncludePolicy1 = detail::partition::include_all_policy,
+ typename IncludePolicy2 = detail::partition::include_all_policy,
+ typename VisitBoxPolicy = detail::partition::visit_no_policy
>
class partition
{
typedef std::vector<std::size_t> index_vector_type;
- template <typename ExpandPolicy, typename InputCollection>
+ template <typename ExpandPolicy, typename IncludePolicy, typename InputCollection>
static inline void expand_to_collection(InputCollection const& collection,
Box& total, index_vector_type& index_vector)
{
@@ -346,8 +535,11 @@ class partition
it != boost::end(collection);
++it, ++index)
{
- ExpandPolicy::apply(total, *it);
- index_vector.push_back(index);
+ if (IncludePolicy::apply(*it))
+ {
+ ExpandPolicy::apply(total, *it);
+ index_vector.push_back(index);
+ }
}
}
@@ -356,7 +548,7 @@ public :
static inline void apply(InputCollection const& collection,
VisitPolicy& visitor,
std::size_t min_elements = 16,
- VisitBoxPolicy box_visitor = visit_no_policy()
+ VisitBoxPolicy box_visitor = detail::partition::visit_no_policy()
)
{
if (std::size_t(boost::size(collection)) > min_elements)
@@ -364,12 +556,14 @@ public :
index_vector_type index_vector;
Box total;
assign_inverse(total);
- expand_to_collection<ExpandPolicy1>(collection, total, index_vector);
+ expand_to_collection<ExpandPolicy1, IncludePolicy1>(collection,
+ total, index_vector);
detail::partition::partition_one_collection
<
0, Box,
OverlapsPolicy1,
+ ExpandPolicy1,
VisitBoxPolicy
>::apply(total, collection, index_vector, 0, min_elements,
visitor, box_visitor);
@@ -403,7 +597,7 @@ public :
InputCollection2 const& collection2,
VisitPolicy& visitor,
std::size_t min_elements = 16,
- VisitBoxPolicy box_visitor = visit_no_policy()
+ VisitBoxPolicy box_visitor = detail::partition::visit_no_policy()
)
{
if (std::size_t(boost::size(collection1)) > min_elements
@@ -412,12 +606,15 @@ public :
index_vector_type index_vector1, index_vector2;
Box total;
assign_inverse(total);
- expand_to_collection<ExpandPolicy1>(collection1, total, index_vector1);
- expand_to_collection<ExpandPolicy2>(collection2, total, index_vector2);
+ expand_to_collection<ExpandPolicy1, IncludePolicy1>(collection1,
+ total, index_vector1);
+ expand_to_collection<ExpandPolicy2, IncludePolicy2>(collection2,
+ total, index_vector2);
detail::partition::partition_two_collections
<
- 0, Box, OverlapsPolicy1, OverlapsPolicy2, VisitBoxPolicy
+ 0, Box, OverlapsPolicy1, OverlapsPolicy2,
+ ExpandPolicy1, ExpandPolicy2, VisitBoxPolicy
>::apply(total,
collection1, index_vector1,
collection2, index_vector2,