algorithms/detail/partition.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2011-2015 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
0005
0006 // This file was modified by Oracle on 2015-2020.
0007 // Modifications copyright (c) 2015-2020 Oracle and/or its affiliates.
0008
0009 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0010 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0011
0012 // Use, modification and distribution is subject to the Boost Software License,
0013 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0014 // http://www.boost.org/LICENSE_1_0.txt)
0015
0016 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP
0017 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP
0018
0019
0020 #include <cstddef>
0021 #include <type_traits>
0022 #include <vector>
0023
0024 #include <boost/range/begin.hpp>
0025 #include <boost/range/empty.hpp>
0026 #include <boost/range/end.hpp>
0027 #include <boost/range/size.hpp>
0028
0029 #include <boost/geometry/algorithms/assign.hpp>
0030 #include <boost/geometry/core/access.hpp>
0031 #include <boost/geometry/core/coordinate_type.hpp>
0032
0033
0034 namespace boost { namespace geometry
0035 {
0036
0037 namespace detail { namespace partition
0038 {
0039
0040 template <typename T, bool IsIntegral = std::is_integral<T>::value>
0041 struct divide_interval
0042 {
0043     static inline T apply(T const& mi, T const& ma)
0044     {
0045         static T const two = 2;
0046         return (mi + ma) / two;
0047     }
0048 };
0049
0050 template <typename T>
0051 struct divide_interval<T, true>
0052 {
0053     static inline T apply(T const& mi, T const& ma)
0054     {
0055         // Avoid overflow
0056         return mi / 2 + ma / 2 + (mi % 2 + ma % 2) / 2;
0057     }
0058 };
0059
0060 struct visit_no_policy
0061 {
0062     template <typename Box>
0063     static inline void apply(Box const&, std::size_t )
0064     {}
0065 };
0066
0067 struct include_all_policy
0068 {
0069     template <typename Item>
0070     static inline bool apply(Item const&)
0071     {
0072         return true;
0073     }
0074 };
0075
0076
0077 template <std::size_t Dimension, typename Box>
0078 inline void divide_box(Box const& box, Box& lower_box, Box& upper_box)
0079 {
0080     using coor_t = coordinate_type_t<Box>;
0081
0082     // Divide input box into two halves
0083     // either left/right (Dimension 0)
0084     // or top/bottom (Dimension 1)
0085     coor_t const mid
0086         = divide_interval<coor_t>::apply(geometry::get<min_corner, Dimension>(box),
0087                                          geometry::get<max_corner, Dimension>(box));
0088
0089     lower_box = box;
0090     upper_box = box;
0091     geometry::set<max_corner, Dimension>(lower_box, mid);
0092     geometry::set<min_corner, Dimension>(upper_box, mid);
0093 }
0094
0095 // Divide forward_range into three subsets: lower, upper and oversized
0096 // (not-fitting)
0097 // (lower == left or bottom, upper == right or top)
0098 template <typename Box, typename IteratorVector, typename OverlapsPolicy>
0099 inline void divide_into_subsets(Box const& lower_box,
0100                                 Box const& upper_box,
0101                                 IteratorVector const& input,
0102                                 IteratorVector& lower,
0103                                 IteratorVector& upper,
0104                                 IteratorVector& exceeding,
0105                                 OverlapsPolicy const& overlaps_policy)
0106 {
0107     for (auto it = boost::begin(input); it != boost::end(input); ++it)
0108     {
0109         bool const lower_overlapping = overlaps_policy.apply(lower_box, **it);
0110         bool const upper_overlapping = overlaps_policy.apply(upper_box, **it);
0111
0112         if (lower_overlapping && upper_overlapping)
0113         {
0114             exceeding.push_back(*it);
0115         }
0116         else if (lower_overlapping)
0117         {
0118             lower.push_back(*it);
0119         }
0120         else if (upper_overlapping)
0121         {
0122             upper.push_back(*it);
0123         }
0124         else
0125         {
0126             // Is nowhere. That is (since 1.58) possible, it might be
0127             // skipped by the OverlapsPolicy to enhance performance
0128         }
0129     }
0130 }
0131
0132 template
0133 <
0134     typename Box,
0135     typename IteratorVector,
0136     typename ExpandPolicy
0137 >
0138 inline void expand_with_elements(Box& total, IteratorVector const& input,
0139                                  ExpandPolicy const& expand_policy)
0140 {
0141     for (auto const& it : input)
0142     {
0143         expand_policy.apply(total, *it);
0144     }
0145 }
0146
0147
0148 // Match forward_range with itself
0149 template <typename IteratorVector, typename VisitPolicy>
0150 inline bool handle_one(IteratorVector const& input, VisitPolicy& visitor)
0151 {
0152     if (boost::empty(input))
0153     {
0154         return true;
0155     }
0156
0157     // Quadratic behaviour at lowest level (lowest quad, or all exceeding)
0158     for (auto it1 = boost::begin(input); it1 != boost::end(input); ++it1)
0159     {
0160         auto it2 = it1;
0161         for (++it2; it2 != boost::end(input); ++it2)
0162         {
0163             if (! visitor.apply(**it1, **it2))
0164             {
0165                 return false; // Bail out if visitor returns false
0166             }
0167         }
0168     }
0169
0170     return true;
0171 }
0172
0173 // Match forward range 1 with forward range 2
0174 template
0175 <
0176     typename IteratorVector1,
0177     typename IteratorVector2,
0178     typename VisitPolicy
0179 >
0180 inline bool handle_two(IteratorVector1 const& input1,
0181                        IteratorVector2 const& input2,
0182                        VisitPolicy& visitor)
0183 {
0184
0185     if (boost::empty(input1) || boost::empty(input2))
0186     {
0187         return true;
0188     }
0189
0190     for (auto const& it1 : input1)
0191     {
0192         for (auto const& it2 : input2)
0193         {
0194             if (! visitor.apply(*it1, *it2))
0195             {
0196                 return false; // Bail out if visitor returns false
0197             }
0198         }
0199     }
0200
0201     return true;
0202 }
0203
0204 template <typename IteratorVector>
0205 inline bool recurse_ok(IteratorVector const& input,
0206                        std::size_t min_elements, std::size_t level)
0207 {
0208     return boost::size(input) >= min_elements
0209         && level < 100;
0210 }
0211
0212 template <typename IteratorVector1, typename IteratorVector2>
0213 inline bool recurse_ok(IteratorVector1 const& input1,
0214                        IteratorVector2 const& input2,
0215                        std::size_t min_elements, std::size_t level)
0216 {
0217     return boost::size(input1) >= min_elements
0218         && recurse_ok(input2, min_elements, level);
0219 }
0220
0221 template
0222 <
0223     typename IteratorVector1,
0224     typename IteratorVector2,
0225     typename IteratorVector3
0226 >
0227 inline bool recurse_ok(IteratorVector1 const& input1,
0228                        IteratorVector2 const& input2,
0229                        IteratorVector3 const& input3,
0230                        std::size_t min_elements, std::size_t level)
0231 {
0232     return boost::size(input1) >= min_elements
0233         && recurse_ok(input2, input3, min_elements, level);
0234 }
0235
0236
0237 template <std::size_t Dimension, typename Box>
0238 class partition_two_ranges;
0239
0240
0241 template <std::size_t Dimension, typename Box>
0242 class partition_one_range
0243 {
0244     template <typename IteratorVector, typename ExpandPolicy>
0245     static inline Box get_new_box(IteratorVector const& input,
0246                                   ExpandPolicy const& expand_policy)
0247     {
0248         Box box;
0249         geometry::assign_inverse(box);
0250         expand_with_elements(box, input, expand_policy);
0251         return box;
0252     }
0253
0254     template
0255     <
0256         typename IteratorVector,
0257         typename VisitPolicy,
0258         typename ExpandPolicy,
0259         typename OverlapsPolicy,
0260         typename VisitBoxPolicy
0261     >
0262     static inline bool next_level(Box const& box,
0263                                   IteratorVector const& input,
0264                                   std::size_t level, std::size_t min_elements,
0265                                   VisitPolicy& visitor,
0266                                   ExpandPolicy const& expand_policy,
0267                                   OverlapsPolicy const& overlaps_policy,
0268                                   VisitBoxPolicy& box_policy)
0269     {
0270         if (recurse_ok(input, min_elements, level))
0271         {
0272             return partition_one_range
0273                 <
0274                     1 - Dimension,
0275                     Box
0276                 >::apply(box, input, level + 1, min_elements,
0277                          visitor, expand_policy, overlaps_policy, box_policy);
0278         }
0279         else
0280         {
0281             return handle_one(input, visitor);
0282         }
0283     }
0284
0285     // Function to switch to two forward ranges if there are
0286     // geometries exceeding the separation line
0287     template
0288     <
0289         typename IteratorVector,
0290         typename VisitPolicy,
0291         typename ExpandPolicy,
0292         typename OverlapsPolicy,
0293         typename VisitBoxPolicy
0294     >
0295     static inline bool next_level2(Box const& box,
0296                                    IteratorVector const& input1,
0297                                    IteratorVector const& input2,
0298                                    std::size_t level, std::size_t min_elements,
0299                                    VisitPolicy& visitor,
0300                                    ExpandPolicy const& expand_policy,
0301                                    OverlapsPolicy const& overlaps_policy,
0302                                    VisitBoxPolicy& box_policy)
0303     {
0304         if (recurse_ok(input1, input2, min_elements, level))
0305         {
0306             return partition_two_ranges
0307                 <
0308                     1 - Dimension, Box
0309                 >::apply(box, input1, input2, level + 1, min_elements,
0310                          visitor, expand_policy, overlaps_policy,
0311                          expand_policy, overlaps_policy, box_policy);
0312         }
0313         else
0314         {
0315             return handle_two(input1, input2, visitor);
0316         }
0317     }
0318
0319 public :
0320     template
0321     <
0322         typename IteratorVector,
0323         typename VisitPolicy,
0324         typename ExpandPolicy,
0325         typename OverlapsPolicy,
0326         typename VisitBoxPolicy
0327     >
0328     static inline bool apply(Box const& box,
0329                              IteratorVector const& input,
0330                              std::size_t level,
0331                              std::size_t min_elements,
0332                              VisitPolicy& visitor,
0333                              ExpandPolicy const& expand_policy,
0334                              OverlapsPolicy const& overlaps_policy,
0335                              VisitBoxPolicy& box_policy)
0336     {
0337         box_policy.apply(box, level);
0338
0339         Box lower_box, upper_box;
0340         divide_box<Dimension>(box, lower_box, upper_box);
0341
0342         IteratorVector lower, upper, exceeding;
0343         divide_into_subsets(lower_box, upper_box,
0344                             input, lower, upper, exceeding,
0345                             overlaps_policy);
0346
0347         if (! boost::empty(exceeding))
0348         {
0349             // Get the box of exceeding-only
0350             Box const exceeding_box = get_new_box(exceeding, expand_policy);
0351
0352             // Recursively do exceeding elements only, in next dimension they
0353             // will probably be less exceeding within the new box
0354             if (! (next_level(exceeding_box, exceeding, level, min_elements,
0355                               visitor, expand_policy, overlaps_policy, box_policy)
0356                    // Switch to two forward ranges, combine exceeding with
0357                    // lower resp upper, but not lower/lower, upper/upper
0358                 && next_level2(exceeding_box, exceeding, lower, level, min_elements,
0359                                visitor, expand_policy, overlaps_policy, box_policy)
0360                 && next_level2(exceeding_box, exceeding, upper, level, min_elements,
0361                                visitor, expand_policy, overlaps_policy, box_policy)) )
0362             {
0363                 return false; // Bail out if visitor returns false
0364             }
0365         }
0366
0367         // Recursively call operation both parts
0368         return next_level(lower_box, lower, level, min_elements,
0369                           visitor, expand_policy, overlaps_policy, box_policy)
0370             && next_level(upper_box, upper, level, min_elements,
0371                           visitor, expand_policy, overlaps_policy, box_policy);
0372     }
0373 };
0374
0375 template
0376 <
0377     std::size_t Dimension,
0378     typename Box
0379 >
0380 class partition_two_ranges
0381 {
0382     template
0383     <
0384         typename IteratorVector1,
0385         typename IteratorVector2,
0386         typename VisitPolicy,
0387         typename ExpandPolicy1,
0388         typename OverlapsPolicy1,
0389         typename ExpandPolicy2,
0390         typename OverlapsPolicy2,
0391         typename VisitBoxPolicy
0392     >
0393     static inline bool next_level(Box const& box,
0394                                   IteratorVector1 const& input1,
0395                                   IteratorVector2 const& input2,
0396                                   std::size_t level, std::size_t min_elements,
0397                                   VisitPolicy& visitor,
0398                                   ExpandPolicy1 const& expand_policy1,
0399                                   OverlapsPolicy1 const& overlaps_policy1,
0400                                   ExpandPolicy2 const& expand_policy2,
0401                                   OverlapsPolicy2 const& overlaps_policy2,
0402                                   VisitBoxPolicy& box_policy)
0403     {
0404         return partition_two_ranges
0405             <
0406                 1 - Dimension, Box
0407             >::apply(box, input1, input2, level + 1, min_elements,
0408                      visitor, expand_policy1, overlaps_policy1,
0409                      expand_policy2, overlaps_policy2, box_policy);
0410     }
0411
0412     template <typename IteratorVector, typename ExpandPolicy>
0413     static inline Box get_new_box(IteratorVector const& input,
0414                                   ExpandPolicy const& expand_policy)
0415     {
0416         Box box;
0417         geometry::assign_inverse(box);
0418         expand_with_elements(box, input, expand_policy);
0419         return box;
0420     }
0421
0422     template
0423     <
0424         typename IteratorVector1, typename IteratorVector2,
0425         typename ExpandPolicy1, typename ExpandPolicy2
0426     >
0427     static inline Box get_new_box(IteratorVector1 const& input1,
0428                                   IteratorVector2 const& input2,
0429                                   ExpandPolicy1 const& expand_policy1,
0430                                   ExpandPolicy2 const& expand_policy2)
0431     {
0432         Box box = get_new_box(input1, expand_policy1);
0433         expand_with_elements(box, input2, expand_policy2);
0434         return box;
0435     }
0436
0437 public :
0438     template
0439     <
0440         typename IteratorVector1,
0441         typename IteratorVector2,
0442         typename VisitPolicy,
0443         typename ExpandPolicy1,
0444         typename OverlapsPolicy1,
0445         typename ExpandPolicy2,
0446         typename OverlapsPolicy2,
0447         typename VisitBoxPolicy
0448     >
0449     static inline bool apply(Box const& box,
0450                              IteratorVector1 const& input1,
0451                              IteratorVector2 const& input2,
0452                              std::size_t level,
0453                              std::size_t min_elements,
0454                              VisitPolicy& visitor,
0455                              ExpandPolicy1 const& expand_policy1,
0456                              OverlapsPolicy1 const& overlaps_policy1,
0457                              ExpandPolicy2 const& expand_policy2,
0458                              OverlapsPolicy2 const& overlaps_policy2,
0459                              VisitBoxPolicy& box_policy)
0460     {
0461         box_policy.apply(box, level);
0462
0463         Box lower_box, upper_box;
0464         divide_box<Dimension>(box, lower_box, upper_box);
0465
0466         IteratorVector1 lower1, upper1, exceeding1;
0467         IteratorVector2 lower2, upper2, exceeding2;
0468         divide_into_subsets(lower_box, upper_box,
0469                             input1, lower1, upper1, exceeding1,
0470                             overlaps_policy1);
0471         divide_into_subsets(lower_box, upper_box,
0472                             input2, lower2, upper2, exceeding2,
0473                             overlaps_policy2);
0474
0475         if (! boost::empty(exceeding1))
0476         {
0477             // All exceeding from 1 with 2:
0478
0479             if (recurse_ok(exceeding1, exceeding2, min_elements, level))
0480             {
0481                 Box const exceeding_box = get_new_box(exceeding1, exceeding2,
0482                                                       expand_policy1, expand_policy2);
0483                 if (! next_level(exceeding_box, exceeding1, exceeding2, level,
0484                                  min_elements, visitor, expand_policy1, overlaps_policy1,
0485                                  expand_policy2, overlaps_policy2, box_policy))
0486                 {
0487                     return false; // Bail out if visitor returns false
0488                 }
0489             }
0490             else
0491             {
0492                 if (! handle_two(exceeding1, exceeding2, visitor))
0493                 {
0494                     return false; // Bail out if visitor returns false
0495                 }
0496             }
0497
0498             // All exceeding from 1 with lower and upper of 2:
0499
0500             // (Check sizes of all three forward ranges to avoid recurse into
0501             // the same combinations again and again)
0502             if (recurse_ok(lower2, upper2, exceeding1, min_elements, level))
0503             {
0504                 Box const exceeding_box = get_new_box(exceeding1, expand_policy1);
0505                 if (! (next_level(exceeding_box, exceeding1, lower2, level,
0506                                   min_elements, visitor, expand_policy1, overlaps_policy1,
0507                                   expand_policy2, overlaps_policy2, box_policy)
0508                     && next_level(exceeding_box, exceeding1, upper2, level,
0509                                   min_elements, visitor, expand_policy1, overlaps_policy1,
0510                                   expand_policy2, overlaps_policy2, box_policy)) )
0511                 {
0512                     return false; // Bail out if visitor returns false
0513                 }
0514             }
0515             else
0516             {
0517                 if (! (handle_two(exceeding1, lower2, visitor)
0518                     && handle_two(exceeding1, upper2, visitor)) )
0519                 {
0520                     return false; // Bail out if visitor returns false
0521                 }
0522             }
0523         }
0524
0525         if (! boost::empty(exceeding2))
0526         {
0527             // All exceeding from 2 with lower and upper of 1:
0528             if (recurse_ok(lower1, upper1, exceeding2, min_elements, level))
0529             {
0530                 Box const exceeding_box = get_new_box(exceeding2, expand_policy2);
0531                 if (! (next_level(exceeding_box, lower1, exceeding2, level,
0532                                   min_elements, visitor, expand_policy1, overlaps_policy1,
0533                                   expand_policy2, overlaps_policy2, box_policy)
0534                     && next_level(exceeding_box, upper1, exceeding2, level,
0535                                   min_elements, visitor, expand_policy1, overlaps_policy1,
0536                                   expand_policy2, overlaps_policy2, box_policy)) )
0537                 {
0538                     return false; // Bail out if visitor returns false
0539                 }
0540             }
0541             else
0542             {
0543                 if (! (handle_two(lower1, exceeding2, visitor)
0544                     && handle_two(upper1, exceeding2, visitor)) )
0545                 {
0546                     return false; // Bail out if visitor returns false
0547                 }
0548             }
0549         }
0550
0551         if (recurse_ok(lower1, lower2, min_elements, level))
0552         {
0553             if (! next_level(lower_box, lower1, lower2, level,
0554                              min_elements, visitor, expand_policy1, overlaps_policy1,
0555                              expand_policy2, overlaps_policy2, box_policy) )
0556             {
0557                 return false; // Bail out if visitor returns false
0558             }
0559         }
0560         else
0561         {
0562             if (! handle_two(lower1, lower2, visitor))
0563             {
0564                 return false; // Bail out if visitor returns false
0565             }
0566         }
0567
0568         if (recurse_ok(upper1, upper2, min_elements, level))
0569         {
0570             if (! next_level(upper_box, upper1, upper2, level,
0571                              min_elements, visitor, expand_policy1, overlaps_policy1,
0572                              expand_policy2, overlaps_policy2, box_policy) )
0573             {
0574                 return false; // Bail out if visitor returns false
0575             }
0576         }
0577         else
0578         {
0579             if (! handle_two(upper1, upper2, visitor))
0580             {
0581                 return false; // Bail out if visitor returns false
0582             }
0583         }
0584
0585         return true;
0586     }
0587 };
0588
0589
0590 }} // namespace detail::partition
0591
0592 template
0593 <
0594     typename Box,
0595     typename IncludePolicy1 = detail::partition::include_all_policy,
0596     typename IncludePolicy2 = detail::partition::include_all_policy
0597 >
0598 class partition
0599 {
0600     static const std::size_t default_min_elements = 16;
0601
0602     template
0603     <
0604         typename IncludePolicy,
0605         typename ForwardRange,
0606         typename IteratorVector,
0607         typename ExpandPolicy
0608     >
0609     static inline void expand_to_range(ForwardRange const& forward_range,
0610                                        Box& total,
0611                                        IteratorVector& iterator_vector,
0612                                        ExpandPolicy const& expand_policy)
0613     {
0614         for (auto it = boost::begin(forward_range); it != boost::end(forward_range); ++it)
0615         {
0616             if (IncludePolicy::apply(*it))
0617             {
0618                 expand_policy.apply(total, *it);
0619                 iterator_vector.push_back(it);
0620             }
0621         }
0622     }
0623
0624 public:
0625     template
0626     <
0627         typename ForwardRange,
0628         typename VisitPolicy,
0629         typename ExpandPolicy,
0630         typename OverlapsPolicy
0631     >
0632     static inline bool apply(ForwardRange const& forward_range,
0633                              VisitPolicy& visitor,
0634                              ExpandPolicy const& expand_policy,
0635                              OverlapsPolicy const& overlaps_policy)
0636     {
0637         return apply(forward_range, visitor, expand_policy, overlaps_policy,
0638                      default_min_elements, detail::partition::visit_no_policy());
0639     }
0640
0641     template
0642     <
0643         typename ForwardRange,
0644         typename VisitPolicy,
0645         typename ExpandPolicy,
0646         typename OverlapsPolicy
0647     >
0648     static inline bool apply(ForwardRange const& forward_range,
0649                              VisitPolicy& visitor,
0650                              ExpandPolicy const& expand_policy,
0651                              OverlapsPolicy const& overlaps_policy,
0652                              std::size_t min_elements)
0653     {
0654         return apply(forward_range, visitor, expand_policy, overlaps_policy,
0655                      min_elements, detail::partition::visit_no_policy());
0656     }
0657
0658     template
0659     <
0660         typename ForwardRange,
0661         typename VisitPolicy,
0662         typename ExpandPolicy,
0663         typename OverlapsPolicy,
0664         typename VisitBoxPolicy
0665     >
0666     static inline bool apply(ForwardRange const& forward_range,
0667                              VisitPolicy& visitor,
0668                              ExpandPolicy const& expand_policy,
0669                              OverlapsPolicy const& overlaps_policy,
0670                              std::size_t min_elements,
0671                              VisitBoxPolicy box_visitor)
0672     {
0673         using iterator_t = typename boost::range_iterator
0674             <
0675                 ForwardRange const
0676             >::type;
0677
0678         if (std::size_t(boost::size(forward_range)) > min_elements)
0679         {
0680             std::vector<iterator_t> iterator_vector;
0681             Box total;
0682             assign_inverse(total);
0683             expand_to_range<IncludePolicy1>(forward_range, total,
0684                                             iterator_vector, expand_policy);
0685
0686             return detail::partition::partition_one_range
0687                 <
0688                     0, Box
0689                 >::apply(total, iterator_vector, 0, min_elements,
0690                          visitor, expand_policy, overlaps_policy, box_visitor);
0691         }
0692         else
0693         {
0694             for (auto it1 = boost::begin(forward_range);
0695                 it1 != boost::end(forward_range);
0696                 ++it1)
0697             {
0698                 auto it2 = it1;
0699                 for (++it2; it2 != boost::end(forward_range); ++it2)
0700                 {
0701                     if (! visitor.apply(*it1, *it2))
0702                     {
0703                         return false; // Bail out if visitor returns false
0704                     }
0705                 }
0706             }
0707         }
0708
0709         return true;
0710     }
0711
0712     template
0713     <
0714         typename ForwardRange1,
0715         typename ForwardRange2,
0716         typename VisitPolicy,
0717         typename ExpandPolicy1,
0718         typename OverlapsPolicy1
0719     >
0720     static inline bool apply(ForwardRange1 const& forward_range1,
0721                              ForwardRange2 const& forward_range2,
0722                              VisitPolicy& visitor,
0723                              ExpandPolicy1 const& expand_policy1,
0724                              OverlapsPolicy1 const& overlaps_policy1)
0725     {
0726         return apply(forward_range1, forward_range2, visitor,
0727                      expand_policy1, overlaps_policy1, expand_policy1, overlaps_policy1,
0728                      default_min_elements, detail::partition::visit_no_policy());
0729     }
0730
0731     template
0732     <
0733         typename ForwardRange1,
0734         typename ForwardRange2,
0735         typename VisitPolicy,
0736         typename ExpandPolicy1,
0737         typename OverlapsPolicy1,
0738         typename ExpandPolicy2,
0739         typename OverlapsPolicy2
0740     >
0741     static inline bool apply(ForwardRange1 const& forward_range1,
0742                              ForwardRange2 const& forward_range2,
0743                              VisitPolicy& visitor,
0744                              ExpandPolicy1 const& expand_policy1,
0745                              OverlapsPolicy1 const& overlaps_policy1,
0746                              ExpandPolicy2 const& expand_policy2,
0747                              OverlapsPolicy2 const& overlaps_policy2)
0748     {
0749         return apply(forward_range1, forward_range2, visitor,
0750                      expand_policy1, overlaps_policy1, expand_policy2, overlaps_policy2,
0751                      default_min_elements, detail::partition::visit_no_policy());
0752     }
0753
0754     template
0755     <
0756         typename ForwardRange1,
0757         typename ForwardRange2,
0758         typename VisitPolicy,
0759         typename ExpandPolicy1,
0760         typename OverlapsPolicy1,
0761         typename ExpandPolicy2,
0762         typename OverlapsPolicy2
0763     >
0764     static inline bool apply(ForwardRange1 const& forward_range1,
0765                              ForwardRange2 const& forward_range2,
0766                              VisitPolicy& visitor,
0767                              ExpandPolicy1 const& expand_policy1,
0768                              OverlapsPolicy1 const& overlaps_policy1,
0769                              ExpandPolicy2 const& expand_policy2,
0770                              OverlapsPolicy2 const& overlaps_policy2,
0771                              std::size_t min_elements)
0772     {
0773         return apply(forward_range1, forward_range2, visitor,
0774                      expand_policy1, overlaps_policy1, expand_policy2, overlaps_policy2,
0775                      min_elements, detail::partition::visit_no_policy());
0776     }
0777
0778     template
0779     <
0780         typename ForwardRange1,
0781         typename ForwardRange2,
0782         typename VisitPolicy,
0783         typename ExpandPolicy1,
0784         typename OverlapsPolicy1,
0785         typename ExpandPolicy2,
0786         typename OverlapsPolicy2,
0787         typename VisitBoxPolicy
0788     >
0789     static inline bool apply(ForwardRange1 const& forward_range1,
0790                              ForwardRange2 const& forward_range2,
0791                              VisitPolicy& visitor,
0792                              ExpandPolicy1 const& expand_policy1,
0793                              OverlapsPolicy1 const& overlaps_policy1,
0794                              ExpandPolicy2 const& expand_policy2,
0795                              OverlapsPolicy2 const& overlaps_policy2,
0796                              std::size_t min_elements,
0797                              VisitBoxPolicy box_visitor)
0798     {
0799         using iterator1_t = typename boost::range_iterator
0800             <
0801                 ForwardRange1 const
0802             >::type;
0803
0804         using iterator2_t = typename boost::range_iterator
0805             <
0806                 ForwardRange2 const
0807             >::type;
0808
0809         if (std::size_t(boost::size(forward_range1)) > min_elements
0810             && std::size_t(boost::size(forward_range2)) > min_elements)
0811         {
0812             std::vector<iterator1_t> iterator_vector1;
0813             std::vector<iterator2_t> iterator_vector2;
0814             Box total;
0815             assign_inverse(total);
0816             expand_to_range<IncludePolicy1>(forward_range1, total,
0817                                             iterator_vector1, expand_policy1);
0818             expand_to_range<IncludePolicy2>(forward_range2, total,
0819                                             iterator_vector2, expand_policy2);
0820
0821             return detail::partition::partition_two_ranges
0822                 <
0823                     0, Box
0824                 >::apply(total, iterator_vector1, iterator_vector2,
0825                          0, min_elements, visitor, expand_policy1,
0826                          overlaps_policy1, expand_policy2, overlaps_policy2,
0827                          box_visitor);
0828         }
0829         else
0830         {
0831             for (auto it1 = boost::begin(forward_range1);
0832                 it1 != boost::end(forward_range1);
0833                 ++it1)
0834             {
0835                 for (auto it2 = boost::begin(forward_range2);
0836                     it2 != boost::end(forward_range2);
0837                     ++it2)
0838                 {
0839                     if (! visitor.apply(*it1, *it2))
0840                     {
0841                         return false; // Bail out if visitor returns false
0842                     }
0843                 }
0844             }
0845         }
0846
0847         return true;
0848     }
0849 };
0850
0851
0852 }} // namespace boost::geometry
0853
0854 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP