Chris@16: // Boost.Geometry (aka GGL, Generic Geometry Library)
Chris@16: 
Chris@101: // Copyright (c) 2011-2014 Barend Gehrels, Amsterdam, the Netherlands.
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software License,
Chris@16: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP
Chris@16: #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP
Chris@16: 
Chris@16: #include <vector>
Chris@16: #include <boost/range/algorithm/copy.hpp>
Chris@16: #include <boost/geometry/algorithms/assign.hpp>
Chris@16: #include <boost/geometry/core/coordinate_type.hpp>
Chris@16: 
Chris@16: namespace boost { namespace geometry
Chris@16: {
Chris@16: 
Chris@16: namespace detail { namespace partition
Chris@16: {
Chris@16: 
Chris@16: typedef std::vector<std::size_t> index_vector_type;
Chris@16: 
Chris@16: template <int Dimension, typename Box>
Chris@16: inline void divide_box(Box const& box, Box& lower_box, Box& upper_box)
Chris@16: {
Chris@16:     typedef typename coordinate_type<Box>::type ctype;
Chris@16: 
Chris@16:     // Divide input box into two parts, e.g. left/right
Chris@16:     ctype two = 2;
Chris@16:     ctype mid = (geometry::get<min_corner, Dimension>(box)
Chris@16:             + geometry::get<max_corner, Dimension>(box)) / two;
Chris@16: 
Chris@16:     lower_box = box;
Chris@16:     upper_box = box;
Chris@16:     geometry::set<max_corner, Dimension>(lower_box, mid);
Chris@16:     geometry::set<min_corner, Dimension>(upper_box, mid);
Chris@16: }
Chris@16: 
Chris@16: // Divide collection into three subsets: lower, upper and oversized
Chris@101: // (not-fitting)
Chris@16: // (lower == left or bottom, upper == right or top)
Chris@16: template <typename OverlapsPolicy, typename InputCollection, typename Box>
Chris@101: inline void divide_into_subsets(Box const& lower_box,
Chris@16:         Box const& upper_box,
Chris@16:         InputCollection const& collection,
Chris@16:         index_vector_type const& input,
Chris@16:         index_vector_type& lower,
Chris@16:         index_vector_type& upper,
Chris@16:         index_vector_type& exceeding)
Chris@16: {
Chris@16:     typedef boost::range_iterator
Chris@16:         <
Chris@16:             index_vector_type const
Chris@16:         >::type index_iterator_type;
Chris@16: 
Chris@16:     for(index_iterator_type it = boost::begin(input);
Chris@16:         it != boost::end(input);
Chris@16:         ++it)
Chris@16:     {
Chris@16:         bool const lower_overlapping = OverlapsPolicy::apply(lower_box,
Chris@16:                     collection[*it]);
Chris@16:         bool const upper_overlapping = OverlapsPolicy::apply(upper_box,
Chris@16:                     collection[*it]);
Chris@16: 
Chris@16:         if (lower_overlapping && upper_overlapping)
Chris@16:         {
Chris@16:             exceeding.push_back(*it);
Chris@16:         }
Chris@16:         else if (lower_overlapping)
Chris@16:         {
Chris@16:             lower.push_back(*it);
Chris@16:         }
Chris@16:         else if (upper_overlapping)
Chris@16:         {
Chris@16:             upper.push_back(*it);
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@101:             // Is nowhere. That is (since 1.58) possible, it might be
Chris@101:             // skipped by the OverlapsPolicy to enhance performance
Chris@16:         }
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@101: template <typename ExpandPolicy, typename Box, typename InputCollection>
Chris@101: inline void expand_with_elements(Box& total,
Chris@101:                 InputCollection const& collection,
Chris@101:                 index_vector_type const& input)
Chris@101: {
Chris@101:     typedef boost::range_iterator<index_vector_type const>::type it_type;
Chris@101:     for(it_type it = boost::begin(input); it != boost::end(input); ++it)
Chris@101:     {
Chris@101:         ExpandPolicy::apply(total, collection[*it]);
Chris@101:     }
Chris@101: }
Chris@101: 
Chris@101: 
Chris@16: // Match collection with itself
Chris@16: template <typename InputCollection, typename Policy>
Chris@101: inline void handle_one(InputCollection const& collection,
Chris@16:         index_vector_type const& input,
Chris@16:         Policy& policy)
Chris@16: {
Chris@101:     if (boost::size(input) == 0)
Chris@101:     {
Chris@101:         return;
Chris@101:     }
Chris@101: 
Chris@16:     typedef boost::range_iterator<index_vector_type const>::type
Chris@16:                 index_iterator_type;
Chris@101: 
Chris@16:     // Quadratic behaviour at lowest level (lowest quad, or all exceeding)
Chris@16:     for(index_iterator_type it1 = boost::begin(input);
Chris@16:         it1 != boost::end(input);
Chris@16:         ++it1)
Chris@16:     {
Chris@16:         index_iterator_type it2 = it1;
Chris@16:         for(++it2; it2 != boost::end(input); ++it2)
Chris@16:         {
Chris@16:             policy.apply(collection[*it1], collection[*it2]);
Chris@16:         }
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: // Match collection 1 with collection 2
Chris@101: template
Chris@101: <
Chris@101:     typename InputCollection1,
Chris@101:     typename InputCollection2,
Chris@101:     typename Policy
Chris@101: >
Chris@101: inline void handle_two(
Chris@101:         InputCollection1 const& collection1, index_vector_type const& input1,
Chris@101:         InputCollection2 const& collection2, index_vector_type const& input2,
Chris@16:         Policy& policy)
Chris@16: {
Chris@101:     if (boost::size(input1) == 0 || boost::size(input2) == 0)
Chris@101:     {
Chris@101:         return;
Chris@101:     }
Chris@101: 
Chris@16:     typedef boost::range_iterator
Chris@16:         <
Chris@16:             index_vector_type const
Chris@16:         >::type index_iterator_type;
Chris@16: 
Chris@16:     for(index_iterator_type it1 = boost::begin(input1);
Chris@16:         it1 != boost::end(input1);
Chris@16:         ++it1)
Chris@16:     {
Chris@16:         for(index_iterator_type it2 = boost::begin(input2);
Chris@16:             it2 != boost::end(input2);
Chris@16:             ++it2)
Chris@16:         {
Chris@16:             policy.apply(collection1[*it1], collection2[*it2]);
Chris@16:         }
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@101: inline bool recurse_ok(index_vector_type const& input,
Chris@101:                 std::size_t min_elements, std::size_t level)
Chris@101: {
Chris@101:     return boost::size(input) >= min_elements
Chris@101:         && level < 100;
Chris@101: }
Chris@101: 
Chris@101: inline bool recurse_ok(index_vector_type const& input1,
Chris@101:                 index_vector_type const& input2,
Chris@101:                 std::size_t min_elements, std::size_t level)
Chris@101: {
Chris@101:     return boost::size(input1) >= min_elements
Chris@101:         && recurse_ok(input2, min_elements, level);
Chris@101: }
Chris@101: 
Chris@101: inline bool recurse_ok(index_vector_type const& input1,
Chris@101:                 index_vector_type const& input2,
Chris@101:                 index_vector_type const& input3,
Chris@101:                 std::size_t min_elements, std::size_t level)
Chris@101: {
Chris@101:     return boost::size(input1) >= min_elements
Chris@101:         && recurse_ok(input2, input3, min_elements, level);
Chris@101: }
Chris@101: 
Chris@101: template
Chris@101: <
Chris@101:     int Dimension,
Chris@101:     typename Box,
Chris@101:     typename OverlapsPolicy1,
Chris@101:     typename OverlapsPolicy2,
Chris@101:     typename ExpandPolicy1,
Chris@101:     typename ExpandPolicy2,
Chris@101:     typename VisitBoxPolicy
Chris@101: >
Chris@101: class partition_two_collections;
Chris@101: 
Chris@101: 
Chris@16: template
Chris@16: <
Chris@16:     int Dimension,
Chris@16:     typename Box,
Chris@16:     typename OverlapsPolicy,
Chris@101:     typename ExpandPolicy,
Chris@16:     typename VisitBoxPolicy
Chris@16: >
Chris@16: class partition_one_collection
Chris@16: {
Chris@16:     typedef std::vector<std::size_t> index_vector_type;
Chris@101: 
Chris@101:     template <typename InputCollection>
Chris@101:     static inline Box get_new_box(InputCollection const& collection,
Chris@101:                     index_vector_type const& input)
Chris@101:     {
Chris@101:         Box box;
Chris@101:         geometry::assign_inverse(box);
Chris@101:         expand_with_elements<ExpandPolicy>(box, collection, input);
Chris@101:         return box;
Chris@101:     }
Chris@16: 
Chris@16:     template <typename InputCollection, typename Policy>
Chris@16:     static inline void next_level(Box const& box,
Chris@16:             InputCollection const& collection,
Chris@16:             index_vector_type const& input,
Chris@101:             std::size_t level, std::size_t min_elements,
Chris@16:             Policy& policy, VisitBoxPolicy& box_policy)
Chris@16:     {
Chris@101:         if (recurse_ok(input, min_elements, level))
Chris@16:         {
Chris@101:             partition_one_collection
Chris@101:             <
Chris@101:                 1 - Dimension,
Chris@101:                 Box,
Chris@101:                 OverlapsPolicy,
Chris@101:                 ExpandPolicy,
Chris@101:                 VisitBoxPolicy
Chris@101:             >::apply(box, collection, input,
Chris@101:                 level + 1, min_elements, policy, box_policy);
Chris@101:         }
Chris@101:         else
Chris@101:         {
Chris@101:             handle_one(collection, input, policy);
Chris@101:         }
Chris@101:     }
Chris@101: 
Chris@101:     // Function to switch to two collections if there are geometries exceeding
Chris@101:     // the separation line
Chris@101:     template <typename InputCollection, typename Policy>
Chris@101:     static inline void next_level2(Box const& box,
Chris@101:             InputCollection const& collection,
Chris@101:             index_vector_type const& input1,
Chris@101:             index_vector_type const& input2,
Chris@101:             std::size_t level, std::size_t min_elements,
Chris@101:             Policy& policy, VisitBoxPolicy& box_policy)
Chris@101:     {
Chris@101: 
Chris@101:         if (recurse_ok(input1, input2, min_elements, level))
Chris@101:         {
Chris@101:             partition_two_collections
Chris@101:             <
Chris@101:                 1 - Dimension,
Chris@101:                 Box,
Chris@101:                 OverlapsPolicy, OverlapsPolicy,
Chris@101:                 ExpandPolicy, ExpandPolicy,
Chris@101:                 VisitBoxPolicy
Chris@101:             >::apply(box, collection, input1, collection, input2,
Chris@101:                 level + 1, min_elements, policy, box_policy);
Chris@101:         }
Chris@101:         else
Chris@101:         {
Chris@101:             handle_two(collection, input1, collection, input2, policy);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16: public :
Chris@16:     template <typename InputCollection, typename Policy>
Chris@16:     static inline void apply(Box const& box,
Chris@16:             InputCollection const& collection,
Chris@16:             index_vector_type const& input,
Chris@101:             std::size_t level,
Chris@16:             std::size_t min_elements,
Chris@16:             Policy& policy, VisitBoxPolicy& box_policy)
Chris@16:     {
Chris@16:         box_policy.apply(box, level);
Chris@16: 
Chris@16:         Box lower_box, upper_box;
Chris@16:         divide_box<Dimension>(box, lower_box, upper_box);
Chris@16: 
Chris@16:         index_vector_type lower, upper, exceeding;
Chris@16:         divide_into_subsets<OverlapsPolicy>(lower_box, upper_box, collection,
Chris@16:                     input, lower, upper, exceeding);
Chris@16: 
Chris@16:         if (boost::size(exceeding) > 0)
Chris@16:         {
Chris@101:             // Get the box of exceeding-only
Chris@101:             Box exceeding_box = get_new_box(collection, exceeding);
Chris@101: 
Chris@101:             // Recursively do exceeding elements only, in next dimension they
Chris@101:             // will probably be less exceeding within the new box
Chris@101:             next_level(exceeding_box, collection, exceeding, level,
Chris@101:                 min_elements, policy, box_policy);
Chris@101: 
Chris@101:             // Switch to two collections, combine exceeding with lower resp upper
Chris@101:             // but not lower/lower, upper/upper
Chris@101:             next_level2(exceeding_box, collection, exceeding, lower, level,
Chris@101:                 min_elements, policy, box_policy);
Chris@101:             next_level2(exceeding_box, collection, exceeding, upper, level,
Chris@101:                 min_elements, policy, box_policy);
Chris@16:         }
Chris@16: 
Chris@16:         // Recursively call operation both parts
Chris@16:         next_level(lower_box, collection, lower, level, min_elements,
Chris@16:                         policy, box_policy);
Chris@16:         next_level(upper_box, collection, upper, level, min_elements,
Chris@16:                         policy, box_policy);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template
Chris@16: <
Chris@16:     int Dimension,
Chris@16:     typename Box,
Chris@101:     typename OverlapsPolicy1,
Chris@101:     typename OverlapsPolicy2,
Chris@101:     typename ExpandPolicy1,
Chris@101:     typename ExpandPolicy2,
Chris@16:     typename VisitBoxPolicy
Chris@16: >
Chris@16: class partition_two_collections
Chris@16: {
Chris@16:     typedef std::vector<std::size_t> index_vector_type;
Chris@16: 
Chris@101:     template
Chris@101:     <
Chris@101:         typename InputCollection1,
Chris@101:         typename InputCollection2,
Chris@101:         typename Policy
Chris@101:     >
Chris@16:     static inline void next_level(Box const& box,
Chris@101:             InputCollection1 const& collection1,
Chris@16:             index_vector_type const& input1,
Chris@101:             InputCollection2 const& collection2,
Chris@16:             index_vector_type const& input2,
Chris@101:             std::size_t level, std::size_t min_elements,
Chris@16:             Policy& policy, VisitBoxPolicy& box_policy)
Chris@16:     {
Chris@101:         partition_two_collections
Chris@101:         <
Chris@101:             1 - Dimension,
Chris@101:             Box,
Chris@101:             OverlapsPolicy1,
Chris@101:             OverlapsPolicy2,
Chris@101:             ExpandPolicy1,
Chris@101:             ExpandPolicy2,
Chris@101:             VisitBoxPolicy
Chris@101:         >::apply(box, collection1, input1, collection2, input2,
Chris@101:                 level + 1, min_elements,
Chris@101:                 policy, box_policy);
Chris@101:     }
Chris@101: 
Chris@101:     template
Chris@101:     <
Chris@101:         typename ExpandPolicy,
Chris@101:         typename InputCollection
Chris@101:     >
Chris@101:     static inline Box get_new_box(InputCollection const& collection,
Chris@101:                     index_vector_type const& input)
Chris@101:     {
Chris@101:         Box box;
Chris@101:         geometry::assign_inverse(box);
Chris@101:         expand_with_elements<ExpandPolicy>(box, collection, input);
Chris@101:         return box;
Chris@101:     }
Chris@101: 
Chris@101:     template
Chris@101:     <
Chris@101:         typename InputCollection1,
Chris@101:         typename InputCollection2
Chris@101:     >
Chris@101:     static inline Box get_new_box(InputCollection1 const& collection1,
Chris@101:                     index_vector_type const& input1,
Chris@101:                     InputCollection2 const& collection2,
Chris@101:                     index_vector_type const& input2)
Chris@101:     {
Chris@101:         Box box = get_new_box<ExpandPolicy1>(collection1, input1);
Chris@101:         expand_with_elements<ExpandPolicy2>(box, collection2, input2);
Chris@101:         return box;
Chris@16:     }
Chris@16: 
Chris@16: public :
Chris@101:     template
Chris@101:     <
Chris@101:         typename InputCollection1,
Chris@101:         typename InputCollection2,
Chris@101:         typename Policy
Chris@101:     >
Chris@16:     static inline void apply(Box const& box,
Chris@101:             InputCollection1 const& collection1, index_vector_type const& input1,
Chris@101:             InputCollection2 const& collection2, index_vector_type const& input2,
Chris@101:             std::size_t level,
Chris@16:             std::size_t min_elements,
Chris@16:             Policy& policy, VisitBoxPolicy& box_policy)
Chris@16:     {
Chris@16:         box_policy.apply(box, level);
Chris@16: 
Chris@16:         Box lower_box, upper_box;
Chris@16:         divide_box<Dimension>(box, lower_box, upper_box);
Chris@16: 
Chris@16:         index_vector_type lower1, upper1, exceeding1;
Chris@16:         index_vector_type lower2, upper2, exceeding2;
Chris@101:         divide_into_subsets<OverlapsPolicy1>(lower_box, upper_box, collection1,
Chris@16:                     input1, lower1, upper1, exceeding1);
Chris@101:         divide_into_subsets<OverlapsPolicy2>(lower_box, upper_box, collection2,
Chris@16:                     input2, lower2, upper2, exceeding2);
Chris@16: 
Chris@16:         if (boost::size(exceeding1) > 0)
Chris@16:         {
Chris@16:             // All exceeding from 1 with 2:
Chris@101: 
Chris@101:             if (recurse_ok(exceeding1, exceeding2, min_elements, level))
Chris@101:             {
Chris@101:                 Box exceeding_box = get_new_box(collection1, exceeding1,
Chris@101:                             collection2, exceeding2);
Chris@101:                 next_level(exceeding_box, collection1, exceeding1,
Chris@101:                                 collection2, exceeding2, level,
Chris@101:                                 min_elements, policy, box_policy);
Chris@101:             }
Chris@101:             else
Chris@101:             {
Chris@101:                 handle_two(collection1, exceeding1, collection2, exceeding2,
Chris@101:                             policy);
Chris@101:             }
Chris@16: 
Chris@16:             // All exceeding from 1 with lower and upper of 2:
Chris@101: 
Chris@101:             // (Check sizes of all three collections to avoid recurse into
Chris@101:             // the same combinations again and again)
Chris@101:             if (recurse_ok(lower2, upper2, exceeding1, min_elements, level))
Chris@101:             {
Chris@101:                 Box exceeding_box
Chris@101:                     = get_new_box<ExpandPolicy1>(collection1, exceeding1);
Chris@101:                 next_level(exceeding_box, collection1, exceeding1,
Chris@101:                     collection2, lower2, level, min_elements, policy, box_policy);
Chris@101:                 next_level(exceeding_box, collection1, exceeding1,
Chris@101:                     collection2, upper2, level, min_elements, policy, box_policy);
Chris@101:             }
Chris@101:             else
Chris@101:             {
Chris@101:                 handle_two(collection1, exceeding1, collection2, lower2, policy);
Chris@101:                 handle_two(collection1, exceeding1, collection2, upper2, policy);
Chris@101:             }
Chris@16:         }
Chris@101: 
Chris@16:         if (boost::size(exceeding2) > 0)
Chris@16:         {
Chris@16:             // All exceeding from 2 with lower and upper of 1:
Chris@101:             if (recurse_ok(lower1, upper1, exceeding2, min_elements, level))
Chris@101:             {
Chris@101:                 Box exceeding_box
Chris@101:                     = get_new_box<ExpandPolicy2>(collection2, exceeding2);
Chris@101:                 next_level(exceeding_box, collection1, lower1,
Chris@101:                     collection2, exceeding2, level, min_elements, policy, box_policy);
Chris@101:                 next_level(exceeding_box, collection1, upper1,
Chris@101:                     collection2, exceeding2, level, min_elements, policy, box_policy);
Chris@101:             }
Chris@101:             else
Chris@101:             {
Chris@101:                 handle_two(collection1, lower1, collection2, exceeding2, policy);
Chris@101:                 handle_two(collection1, upper1, collection2, exceeding2, policy);
Chris@101:             }
Chris@16:         }
Chris@16: 
Chris@101:         if (recurse_ok(lower1, lower2, min_elements, level))
Chris@101:         {
Chris@101:             next_level(lower_box, collection1, lower1, collection2, lower2, level,
Chris@101:                             min_elements, policy, box_policy);
Chris@101:         }
Chris@101:         else
Chris@101:         {
Chris@101:             handle_two(collection1, lower1, collection2, lower2, policy);
Chris@101:         }
Chris@101:         if (recurse_ok(upper1, upper2, min_elements, level))
Chris@101:         {
Chris@101:             next_level(upper_box, collection1, upper1, collection2, upper2, level,
Chris@101:                             min_elements, policy, box_policy);
Chris@101:         }
Chris@101:         else
Chris@101:         {
Chris@101:             handle_two(collection1, upper1, collection2, upper2, policy);
Chris@101:         }
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: struct visit_no_policy
Chris@16: {
Chris@16:     template <typename Box>
Chris@101:     static inline void apply(Box const&, std::size_t )
Chris@16:     {}
Chris@16: };
Chris@16: 
Chris@101: struct include_all_policy
Chris@101: {
Chris@101:     template <typename Item>
Chris@101:     static inline bool apply(Item const&)
Chris@101:     {
Chris@101:         return true;
Chris@101:     }
Chris@101: };
Chris@101: 
Chris@101: 
Chris@101: }} // namespace detail::partition
Chris@101: 
Chris@16: template
Chris@16: <
Chris@16:     typename Box,
Chris@101:     typename ExpandPolicy1,
Chris@101:     typename OverlapsPolicy1,
Chris@101:     typename ExpandPolicy2 = ExpandPolicy1,
Chris@101:     typename OverlapsPolicy2 = OverlapsPolicy1,
Chris@101:     typename IncludePolicy1 = detail::partition::include_all_policy,
Chris@101:     typename IncludePolicy2 = detail::partition::include_all_policy,
Chris@101:     typename VisitBoxPolicy = detail::partition::visit_no_policy
Chris@16: >
Chris@16: class partition
Chris@16: {
Chris@16:     typedef std::vector<std::size_t> index_vector_type;
Chris@16: 
Chris@101:     template <typename ExpandPolicy, typename IncludePolicy, typename InputCollection>
Chris@16:     static inline void expand_to_collection(InputCollection const& collection,
Chris@16:                 Box& total, index_vector_type& index_vector)
Chris@16:     {
Chris@16:         std::size_t index = 0;
Chris@16:         for(typename boost::range_iterator<InputCollection const>::type it
Chris@16:             = boost::begin(collection);
Chris@16:             it != boost::end(collection);
Chris@16:             ++it, ++index)
Chris@16:         {
Chris@101:             if (IncludePolicy::apply(*it))
Chris@101:             {
Chris@101:                 ExpandPolicy::apply(total, *it);
Chris@101:                 index_vector.push_back(index);
Chris@101:             }
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16: public :
Chris@16:     template <typename InputCollection, typename VisitPolicy>
Chris@16:     static inline void apply(InputCollection const& collection,
Chris@16:             VisitPolicy& visitor,
Chris@16:             std::size_t min_elements = 16,
Chris@101:             VisitBoxPolicy box_visitor = detail::partition::visit_no_policy()
Chris@16:             )
Chris@16:     {
Chris@16:         if (std::size_t(boost::size(collection)) > min_elements)
Chris@16:         {
Chris@16:             index_vector_type index_vector;
Chris@16:             Box total;
Chris@16:             assign_inverse(total);
Chris@101:             expand_to_collection<ExpandPolicy1, IncludePolicy1>(collection,
Chris@101:                     total, index_vector);
Chris@16: 
Chris@16:             detail::partition::partition_one_collection
Chris@16:                 <
Chris@16:                     0, Box,
Chris@101:                     OverlapsPolicy1,
Chris@101:                     ExpandPolicy1,
Chris@16:                     VisitBoxPolicy
Chris@16:                 >::apply(total, collection, index_vector, 0, min_elements,
Chris@16:                                 visitor, box_visitor);
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@16:             typedef typename boost::range_iterator
Chris@16:                 <
Chris@16:                     InputCollection const
Chris@16:                 >::type iterator_type;
Chris@16:             for(iterator_type it1 = boost::begin(collection);
Chris@16:                 it1 != boost::end(collection);
Chris@16:                 ++it1)
Chris@16:             {
Chris@16:                 iterator_type it2 = it1;
Chris@16:                 for(++it2; it2 != boost::end(collection); ++it2)
Chris@16:                 {
Chris@16:                     visitor.apply(*it1, *it2);
Chris@16:                 }
Chris@16:             }
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@101:     template
Chris@101:     <
Chris@101:         typename InputCollection1,
Chris@101:         typename InputCollection2,
Chris@101:         typename VisitPolicy
Chris@101:     >
Chris@101:     static inline void apply(InputCollection1 const& collection1,
Chris@101:                 InputCollection2 const& collection2,
Chris@16:                 VisitPolicy& visitor,
Chris@16:                 std::size_t min_elements = 16,
Chris@101:                 VisitBoxPolicy box_visitor = detail::partition::visit_no_policy()
Chris@16:                 )
Chris@16:     {
Chris@16:         if (std::size_t(boost::size(collection1)) > min_elements
Chris@16:             && std::size_t(boost::size(collection2)) > min_elements)
Chris@16:         {
Chris@16:             index_vector_type index_vector1, index_vector2;
Chris@16:             Box total;
Chris@16:             assign_inverse(total);
Chris@101:             expand_to_collection<ExpandPolicy1, IncludePolicy1>(collection1,
Chris@101:                     total, index_vector1);
Chris@101:             expand_to_collection<ExpandPolicy2, IncludePolicy2>(collection2,
Chris@101:                     total, index_vector2);
Chris@16: 
Chris@16:             detail::partition::partition_two_collections
Chris@16:                 <
Chris@101:                     0, Box, OverlapsPolicy1, OverlapsPolicy2,
Chris@101:                     ExpandPolicy1, ExpandPolicy2, VisitBoxPolicy
Chris@16:                 >::apply(total,
Chris@16:                     collection1, index_vector1,
Chris@16:                     collection2, index_vector2,
Chris@16:                     0, min_elements, visitor, box_visitor);
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@16:             typedef typename boost::range_iterator
Chris@16:                 <
Chris@101:                     InputCollection1 const
Chris@101:                 >::type iterator_type1;
Chris@101:             typedef typename boost::range_iterator
Chris@101:                 <
Chris@101:                     InputCollection2 const
Chris@101:                 >::type iterator_type2;
Chris@101:             for(iterator_type1 it1 = boost::begin(collection1);
Chris@16:                 it1 != boost::end(collection1);
Chris@16:                 ++it1)
Chris@16:             {
Chris@101:                 for(iterator_type2 it2 = boost::begin(collection2);
Chris@16:                     it2 != boost::end(collection2);
Chris@16:                     ++it2)
Chris@16:                 {
Chris@16:                     visitor.apply(*it1, *it2);
Chris@16:                 }
Chris@16:             }
Chris@16:         }
Chris@16:     }
Chris@101: };
Chris@16: 
Chris@16: 
Chris@16: }} // namespace boost::geometry
Chris@16: 
Chris@16: #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP