diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/partition.hpp')
-rw-r--r-- | boost/geometry/algorithms/detail/partition.hpp | 349 |
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, |