boost/geometry/algorithms/detail/partition.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2011-2015 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
   5
   6 // This file was modified by Oracle on 2015, 2017, 2018, 2019.
   7 // Modifications copyright (c) 2015-2019 Oracle and/or its affiliates.
   8
   9 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
  10 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  11
  12 // Use, modification and distribution is subject to the Boost Software License,
  13 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  14 // http://www.boost.org/LICENSE_1_0.txt)
  15
  16 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP
  17 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP
  18
  19 #include <cstddef>
  20 #include <vector>
  21 #include <boost/range.hpp>
  22 #include <boost/type_traits/is_integral.hpp>
  23
  24 #include <boost/geometry/core/access.hpp>
  25 #include <boost/geometry/core/coordinate_type.hpp>
  26 #include <boost/geometry/algorithms/assign.hpp>
  27
  28
  29 namespace boost { namespace geometry
  30 {
  31
  32 namespace detail { namespace partition
  33 {
  34
  35 template <typename T, bool IsIntegral = boost::is_integral<T>::value>
  36 struct divide_interval
  37 {
  38     static inline T apply(T const& mi, T const& ma)
  39     {
  40         static T const two = 2;
  41         return (mi + ma) / two;
  42     }
  43 };
  44
  45 template <typename T>
  46 struct divide_interval<T, true>
  47 {
  48     static inline T apply(T const& mi, T const& ma)
  49     {
  50         // avoid overflow
  51         return mi / 2 + ma / 2 + (mi % 2 + ma % 2) / 2;
  52     }
  53 };
  54
  55 template <int Dimension, typename Box>
  56 inline void divide_box(Box const& box, Box& lower_box, Box& upper_box)
  57 {
  58     typedef typename coordinate_type<Box>::type ctype;
  59
  60     // Divide input box into two parts, e.g. left/right
  61     ctype mid = divide_interval<ctype>::apply(
  62                     geometry::get<min_corner, Dimension>(box),
  63                     geometry::get<max_corner, Dimension>(box));
  64
  65     lower_box = box;
  66     upper_box = box;
  67     geometry::set<max_corner, Dimension>(lower_box, mid);
  68     geometry::set<min_corner, Dimension>(upper_box, mid);
  69 }
  70
  71 // Divide forward_range into three subsets: lower, upper and oversized
  72 // (not-fitting)
  73 // (lower == left or bottom, upper == right or top)
  74 template <typename Box, typename IteratorVector, typename OverlapsPolicy>
  75 inline void divide_into_subsets(Box const& lower_box,
  76                                 Box const& upper_box,
  77                                 IteratorVector const& input,
  78                                 IteratorVector& lower,
  79                                 IteratorVector& upper,
  80                                 IteratorVector& exceeding,
  81                                 OverlapsPolicy const& overlaps_policy)
  82 {
  83     typedef typename boost::range_iterator
  84         <
  85             IteratorVector const
  86         >::type it_type;
  87
  88     for(it_type it = boost::begin(input); it != boost::end(input); ++it)
  89     {
  90         bool const lower_overlapping = overlaps_policy.apply(lower_box, **it);
  91         bool const upper_overlapping = overlaps_policy.apply(upper_box, **it);
  92
  93         if (lower_overlapping && upper_overlapping)
  94         {
  95             exceeding.push_back(*it);
  96         }
  97         else if (lower_overlapping)
  98         {
  99             lower.push_back(*it);
 100         }
 101         else if (upper_overlapping)
 102         {
 103             upper.push_back(*it);
 104         }
 105         else
 106         {
 107             // Is nowhere. That is (since 1.58) possible, it might be
 108             // skipped by the OverlapsPolicy to enhance performance
 109         }
 110     }
 111 }
 112
 113 template
 114 <
 115     typename Box,
 116     typename IteratorVector,
 117     typename ExpandPolicy
 118 >
 119 inline void expand_with_elements(Box& total, IteratorVector const& input,
 120                                  ExpandPolicy const& expand_policy)
 121 {
 122     typedef typename boost::range_iterator<IteratorVector const>::type it_type;
 123     for(it_type it = boost::begin(input); it != boost::end(input); ++it)
 124     {
 125         expand_policy.apply(total, **it);
 126     }
 127 }
 128
 129
 130 // Match forward_range with itself
 131 template <typename IteratorVector, typename VisitPolicy>
 132 inline bool handle_one(IteratorVector const& input, VisitPolicy& visitor)
 133 {
 134     if (boost::empty(input))
 135     {
 136         return true;
 137     }
 138
 139     typedef typename boost::range_iterator<IteratorVector const>::type it_type;
 140
 141     // Quadratic behaviour at lowest level (lowest quad, or all exceeding)
 142     for (it_type it1 = boost::begin(input); it1 != boost::end(input); ++it1)
 143     {
 144         it_type it2 = it1;
 145         for (++it2; it2 != boost::end(input); ++it2)
 146         {
 147             if (! visitor.apply(**it1, **it2))
 148             {
 149                 return false; // interrupt
 150             }
 151         }
 152     }
 153
 154     return true;
 155 }
 156
 157 // Match forward range 1 with forward range 2
 158 template
 159 <
 160     typename IteratorVector1,
 161     typename IteratorVector2,
 162     typename VisitPolicy
 163 >
 164 inline bool handle_two(IteratorVector1 const& input1,
 165                        IteratorVector2 const& input2,
 166                        VisitPolicy& visitor)
 167 {
 168     typedef typename boost::range_iterator
 169         <
 170             IteratorVector1 const
 171         >::type iterator_type1;
 172
 173     typedef typename boost::range_iterator
 174         <
 175             IteratorVector2 const
 176         >::type iterator_type2;
 177
 178     if (boost::empty(input1) || boost::empty(input2))
 179     {
 180         return true;
 181     }
 182
 183     for(iterator_type1 it1 = boost::begin(input1);
 184         it1 != boost::end(input1);
 185         ++it1)
 186     {
 187         for(iterator_type2 it2 = boost::begin(input2);
 188             it2 != boost::end(input2);
 189             ++it2)
 190         {
 191             if (! visitor.apply(**it1, **it2))
 192             {
 193                 return false; // interrupt
 194             }
 195         }
 196     }
 197
 198     return true;
 199 }
 200
 201 template <typename IteratorVector>
 202 inline bool recurse_ok(IteratorVector const& input,
 203                        std::size_t min_elements, std::size_t level)
 204 {
 205     return boost::size(input) >= min_elements
 206         && level < 100;
 207 }
 208
 209 template <typename IteratorVector1, typename IteratorVector2>
 210 inline bool recurse_ok(IteratorVector1 const& input1,
 211                        IteratorVector2 const& input2,
 212                        std::size_t min_elements, std::size_t level)
 213 {
 214     return boost::size(input1) >= min_elements
 215         && recurse_ok(input2, min_elements, level);
 216 }
 217
 218 template
 219 <
 220     typename IteratorVector1,
 221     typename IteratorVector2,
 222     typename IteratorVector3
 223 >
 224 inline bool recurse_ok(IteratorVector1 const& input1,
 225                        IteratorVector2 const& input2,
 226                        IteratorVector3 const& input3,
 227                        std::size_t min_elements, std::size_t level)
 228 {
 229     return boost::size(input1) >= min_elements
 230         && recurse_ok(input2, input3, min_elements, level);
 231 }
 232
 233
 234 template <int Dimension, typename Box>
 235 class partition_two_ranges;
 236
 237
 238 template <int Dimension, typename Box>
 239 class partition_one_range
 240 {
 241     template <typename IteratorVector, typename ExpandPolicy>
 242     static inline Box get_new_box(IteratorVector const& input,
 243                                   ExpandPolicy const& expand_policy)
 244     {
 245         Box box;
 246         geometry::assign_inverse(box);
 247         expand_with_elements(box, input, expand_policy);
 248         return box;
 249     }
 250
 251     template
 252     <
 253         typename IteratorVector,
 254         typename VisitPolicy,
 255         typename ExpandPolicy,
 256         typename OverlapsPolicy,
 257         typename VisitBoxPolicy
 258     >
 259     static inline bool next_level(Box const& box,
 260                                   IteratorVector const& input,
 261                                   std::size_t level, std::size_t min_elements,
 262                                   VisitPolicy& visitor,
 263                                   ExpandPolicy const& expand_policy,
 264                                   OverlapsPolicy const& overlaps_policy,
 265                                   VisitBoxPolicy& box_policy)
 266     {
 267         if (recurse_ok(input, min_elements, level))
 268         {
 269             return partition_one_range
 270                 <
 271                     1 - Dimension,
 272                     Box
 273                 >::apply(box, input, level + 1, min_elements,
 274                          visitor, expand_policy, overlaps_policy, box_policy);
 275         }
 276         else
 277         {
 278             return handle_one(input, visitor);
 279         }
 280     }
 281
 282     // Function to switch to two forward ranges if there are
 283     // geometries exceeding the separation line
 284     template
 285     <
 286         typename IteratorVector,
 287         typename VisitPolicy,
 288         typename ExpandPolicy,
 289         typename OverlapsPolicy,
 290         typename VisitBoxPolicy
 291     >
 292     static inline bool next_level2(Box const& box,
 293                                    IteratorVector const& input1,
 294                                    IteratorVector const& input2,
 295                                    std::size_t level, std::size_t min_elements,
 296                                    VisitPolicy& visitor,
 297                                    ExpandPolicy const& expand_policy,
 298                                    OverlapsPolicy const& overlaps_policy,
 299                                    VisitBoxPolicy& box_policy)
 300     {
 301         if (recurse_ok(input1, input2, min_elements, level))
 302         {
 303             return partition_two_ranges
 304                 <
 305                     1 - Dimension, Box
 306                 >::apply(box, input1, input2, level + 1, min_elements,
 307                          visitor, expand_policy, overlaps_policy,
 308                          expand_policy, overlaps_policy, box_policy);
 309         }
 310         else
 311         {
 312             return handle_two(input1, input2, visitor);
 313         }
 314     }
 315
 316 public :
 317     template
 318     <
 319         typename IteratorVector,
 320         typename VisitPolicy,
 321         typename ExpandPolicy,
 322         typename OverlapsPolicy,
 323         typename VisitBoxPolicy
 324     >
 325     static inline bool apply(Box const& box,
 326                              IteratorVector const& input,
 327                              std::size_t level,
 328                              std::size_t min_elements,
 329                              VisitPolicy& visitor,
 330                              ExpandPolicy const& expand_policy,
 331                              OverlapsPolicy const& overlaps_policy,
 332                              VisitBoxPolicy& box_policy)
 333     {
 334         box_policy.apply(box, level);
 335
 336         Box lower_box, upper_box;
 337         divide_box<Dimension>(box, lower_box, upper_box);
 338
 339         IteratorVector lower, upper, exceeding;
 340         divide_into_subsets(lower_box, upper_box,
 341                             input, lower, upper, exceeding,
 342                             overlaps_policy);
 343
 344         if (! boost::empty(exceeding))
 345         {
 346             // Get the box of exceeding-only
 347             Box exceeding_box = get_new_box(exceeding, expand_policy);
 348
 349                    // Recursively do exceeding elements only, in next dimension they
 350                    // will probably be less exceeding within the new box
 351             if (! (next_level(exceeding_box, exceeding, level, min_elements,
 352                               visitor, expand_policy, overlaps_policy, box_policy)
 353                    // Switch to two forward ranges, combine exceeding with
 354                    // lower resp upper, but not lower/lower, upper/upper
 355                 && next_level2(exceeding_box, exceeding, lower, level, min_elements,
 356                                visitor, expand_policy, overlaps_policy, box_policy)
 357                 && next_level2(exceeding_box, exceeding, upper, level, min_elements,
 358                                visitor, expand_policy, overlaps_policy, box_policy)) )
 359             {
 360                 return false; // interrupt
 361             }
 362         }
 363
 364         // Recursively call operation both parts
 365         return next_level(lower_box, lower, level, min_elements,
 366                           visitor, expand_policy, overlaps_policy, box_policy)
 367             && next_level(upper_box, upper, level, min_elements,
 368                           visitor, expand_policy, overlaps_policy, box_policy);
 369     }
 370 };
 371
 372 template
 373 <
 374     int Dimension,
 375     typename Box
 376 >
 377 class partition_two_ranges
 378 {
 379     template
 380     <
 381         typename IteratorVector1,
 382         typename IteratorVector2,
 383         typename VisitPolicy,
 384         typename ExpandPolicy1,
 385         typename OverlapsPolicy1,
 386         typename ExpandPolicy2,
 387         typename OverlapsPolicy2,
 388         typename VisitBoxPolicy
 389     >
 390     static inline bool next_level(Box const& box,
 391                                   IteratorVector1 const& input1,
 392                                   IteratorVector2 const& input2,
 393                                   std::size_t level, std::size_t min_elements,
 394                                   VisitPolicy& visitor,
 395                                   ExpandPolicy1 const& expand_policy1,
 396                                   OverlapsPolicy1 const& overlaps_policy1,
 397                                   ExpandPolicy2 const& expand_policy2,
 398                                   OverlapsPolicy2 const& overlaps_policy2,
 399                                   VisitBoxPolicy& box_policy)
 400     {
 401         return partition_two_ranges
 402             <
 403                 1 - Dimension, Box
 404             >::apply(box, input1, input2, level + 1, min_elements,
 405                      visitor, expand_policy1, overlaps_policy1,
 406                      expand_policy2, overlaps_policy2, box_policy);
 407     }
 408
 409     template <typename IteratorVector, typename ExpandPolicy>
 410     static inline Box get_new_box(IteratorVector const& input,
 411                                   ExpandPolicy const& expand_policy)
 412     {
 413         Box box;
 414         geometry::assign_inverse(box);
 415         expand_with_elements(box, input, expand_policy);
 416         return box;
 417     }
 418
 419     template
 420     <
 421         typename IteratorVector1, typename IteratorVector2,
 422         typename ExpandPolicy1, typename ExpandPolicy2
 423     >
 424     static inline Box get_new_box(IteratorVector1 const& input1,
 425                                   IteratorVector2 const& input2,
 426                                   ExpandPolicy1 const& expand_policy1,
 427                                   ExpandPolicy2 const& expand_policy2)
 428     {
 429         Box box = get_new_box(input1, expand_policy1);
 430         expand_with_elements(box, input2, expand_policy2);
 431         return box;
 432     }
 433
 434 public :
 435     template
 436     <
 437         typename IteratorVector1,
 438         typename IteratorVector2,
 439         typename VisitPolicy,
 440         typename ExpandPolicy1,
 441         typename OverlapsPolicy1,
 442         typename ExpandPolicy2,
 443         typename OverlapsPolicy2,
 444         typename VisitBoxPolicy
 445     >
 446     static inline bool apply(Box const& box,
 447                              IteratorVector1 const& input1,
 448                              IteratorVector2 const& input2,
 449                              std::size_t level,
 450                              std::size_t min_elements,
 451                              VisitPolicy& visitor,
 452                              ExpandPolicy1 const& expand_policy1,
 453                              OverlapsPolicy1 const& overlaps_policy1,
 454                              ExpandPolicy2 const& expand_policy2,
 455                              OverlapsPolicy2 const& overlaps_policy2,
 456                              VisitBoxPolicy& box_policy)
 457     {
 458         box_policy.apply(box, level);
 459
 460         Box lower_box, upper_box;
 461         divide_box<Dimension>(box, lower_box, upper_box);
 462
 463         IteratorVector1 lower1, upper1, exceeding1;
 464         IteratorVector2 lower2, upper2, exceeding2;
 465         divide_into_subsets(lower_box, upper_box,
 466                             input1, lower1, upper1, exceeding1,
 467                             overlaps_policy1);
 468         divide_into_subsets(lower_box, upper_box,
 469                             input2, lower2, upper2, exceeding2,
 470                             overlaps_policy2);
 471
 472         if (! boost::empty(exceeding1))
 473         {
 474             // All exceeding from 1 with 2:
 475
 476             if (recurse_ok(exceeding1, exceeding2, min_elements, level))
 477             {
 478                 Box exceeding_box = get_new_box(exceeding1, exceeding2,
 479                                                 expand_policy1, expand_policy2);
 480                 if (! next_level(exceeding_box, exceeding1, exceeding2, level,
 481                                  min_elements, visitor, expand_policy1, overlaps_policy1,
 482                                  expand_policy2, overlaps_policy2, box_policy))
 483                 {
 484                     return false; // interrupt
 485                 }
 486             }
 487             else
 488             {
 489                 if (! handle_two(exceeding1, exceeding2, visitor))
 490                 {
 491                     return false; // interrupt
 492                 }
 493             }
 494
 495             // All exceeding from 1 with lower and upper of 2:
 496
 497             // (Check sizes of all three forward ranges to avoid recurse into
 498             // the same combinations again and again)
 499             if (recurse_ok(lower2, upper2, exceeding1, min_elements, level))
 500             {
 501                 Box exceeding_box = get_new_box(exceeding1, expand_policy1);
 502                 if (! (next_level(exceeding_box, exceeding1, lower2, level,
 503                                   min_elements, visitor, expand_policy1, overlaps_policy1,
 504                                   expand_policy2, overlaps_policy2, box_policy)
 505                     && next_level(exceeding_box, exceeding1, upper2, level,
 506                                   min_elements, visitor, expand_policy1, overlaps_policy1,
 507                                   expand_policy2, overlaps_policy2, box_policy)) )
 508                 {
 509                     return false; // interrupt
 510                 }
 511             }
 512             else
 513             {
 514                 if (! (handle_two(exceeding1, lower2, visitor)
 515                     && handle_two(exceeding1, upper2, visitor)) )
 516                 {
 517                     return false; // interrupt
 518                 }
 519             }
 520         }
 521
 522         if (! boost::empty(exceeding2))
 523         {
 524             // All exceeding from 2 with lower and upper of 1:
 525             if (recurse_ok(lower1, upper1, exceeding2, min_elements, level))
 526             {
 527                 Box exceeding_box = get_new_box(exceeding2, expand_policy2);
 528                 if (! (next_level(exceeding_box, lower1, exceeding2, level,
 529                                   min_elements, visitor, expand_policy1, overlaps_policy1,
 530                                   expand_policy2, overlaps_policy2, box_policy)
 531                     && next_level(exceeding_box, upper1, exceeding2, level,
 532                                   min_elements, visitor, expand_policy1, overlaps_policy1,
 533                                   expand_policy2, overlaps_policy2, box_policy)) )
 534                 {
 535                     return false; // interrupt
 536                 }
 537             }
 538             else
 539             {
 540                 if (! (handle_two(lower1, exceeding2, visitor)
 541                     && handle_two(upper1, exceeding2, visitor)) )
 542                 {
 543                     return false; // interrupt
 544                 }
 545             }
 546         }
 547
 548         if (recurse_ok(lower1, lower2, min_elements, level))
 549         {
 550             if (! next_level(lower_box, lower1, lower2, level,
 551                              min_elements, visitor, expand_policy1, overlaps_policy1,
 552                              expand_policy2, overlaps_policy2, box_policy) )
 553             {
 554                 return false; // interrupt
 555             }
 556         }
 557         else
 558         {
 559             if (! handle_two(lower1, lower2, visitor))
 560             {
 561                 return false; // interrupt
 562             }
 563         }
 564
 565         if (recurse_ok(upper1, upper2, min_elements, level))
 566         {
 567             if (! next_level(upper_box, upper1, upper2, level,
 568                              min_elements, visitor, expand_policy1, overlaps_policy1,
 569                              expand_policy2, overlaps_policy2, box_policy) )
 570             {
 571                 return false; // interrupt
 572             }
 573         }
 574         else
 575         {
 576             if (! handle_two(upper1, upper2, visitor))
 577             {
 578                 return false; // interrupt
 579             }
 580         }
 581
 582         return true;
 583     }
 584 };
 585
 586 struct visit_no_policy
 587 {
 588     template <typename Box>
 589     static inline void apply(Box const&, std::size_t )
 590     {}
 591 };
 592
 593 struct include_all_policy
 594 {
 595     template <typename Item>
 596     static inline bool apply(Item const&)
 597     {
 598         return true;
 599     }
 600 };
 601
 602
 603 }} // namespace detail::partition
 604
 605 template
 606 <
 607     typename Box,
 608     typename IncludePolicy1 = detail::partition::include_all_policy,
 609     typename IncludePolicy2 = detail::partition::include_all_policy
 610 >
 611 class partition
 612 {
 613     static const std::size_t default_min_elements = 16;
 614
 615     template
 616     <
 617         typename IncludePolicy,
 618         typename ForwardRange,
 619         typename IteratorVector,
 620         typename ExpandPolicy
 621     >
 622     static inline void expand_to_range(ForwardRange const& forward_range,
 623                                        Box& total,
 624                                        IteratorVector& iterator_vector,
 625                                        ExpandPolicy const& expand_policy)
 626     {
 627         for(typename boost::range_iterator<ForwardRange const>::type
 628                 it = boost::begin(forward_range);
 629             it != boost::end(forward_range);
 630             ++it)
 631         {
 632             if (IncludePolicy::apply(*it))
 633             {
 634                 expand_policy.apply(total, *it);
 635                 iterator_vector.push_back(it);
 636             }
 637         }
 638     }
 639
 640 public:
 641     template
 642     <
 643         typename ForwardRange,
 644         typename VisitPolicy,
 645         typename ExpandPolicy,
 646         typename OverlapsPolicy
 647     >
 648     static inline bool apply(ForwardRange const& forward_range,
 649                              VisitPolicy& visitor,
 650                              ExpandPolicy const& expand_policy,
 651                              OverlapsPolicy const& overlaps_policy)
 652     {
 653         return apply(forward_range, visitor, expand_policy, overlaps_policy,
 654                      default_min_elements, detail::partition::visit_no_policy());
 655     }
 656
 657     template
 658     <
 659         typename ForwardRange,
 660         typename VisitPolicy,
 661         typename ExpandPolicy,
 662         typename OverlapsPolicy
 663     >
 664     static inline bool apply(ForwardRange const& forward_range,
 665                              VisitPolicy& visitor,
 666                              ExpandPolicy const& expand_policy,
 667                              OverlapsPolicy const& overlaps_policy,
 668                              std::size_t min_elements)
 669     {
 670         return apply(forward_range, visitor, expand_policy, overlaps_policy,
 671                      min_elements, detail::partition::visit_no_policy());
 672     }
 673
 674     template
 675     <
 676         typename ForwardRange,
 677         typename VisitPolicy,
 678         typename ExpandPolicy,
 679         typename OverlapsPolicy,
 680         typename VisitBoxPolicy
 681     >
 682     static inline bool apply(ForwardRange const& forward_range,
 683                              VisitPolicy& visitor,
 684                              ExpandPolicy const& expand_policy,
 685                              OverlapsPolicy const& overlaps_policy,
 686                              std::size_t min_elements,
 687                              VisitBoxPolicy box_visitor)
 688     {
 689         typedef typename boost::range_iterator
 690             <
 691                 ForwardRange const
 692             >::type iterator_type;
 693
 694         if (std::size_t(boost::size(forward_range)) > min_elements)
 695         {
 696             std::vector<iterator_type> iterator_vector;
 697             Box total;
 698             assign_inverse(total);
 699             expand_to_range<IncludePolicy1>(forward_range, total,
 700                                             iterator_vector, expand_policy);
 701
 702             return detail::partition::partition_one_range
 703                 <
 704                     0, Box
 705                 >::apply(total, iterator_vector, 0, min_elements,
 706                          visitor, expand_policy, overlaps_policy, box_visitor);
 707         }
 708         else
 709         {
 710             for(iterator_type it1 = boost::begin(forward_range);
 711                 it1 != boost::end(forward_range);
 712                 ++it1)
 713             {
 714                 iterator_type it2 = it1;
 715                 for(++it2; it2 != boost::end(forward_range); ++it2)
 716                 {
 717                     if (! visitor.apply(*it1, *it2))
 718                     {
 719                         return false; // interrupt
 720                     }
 721                 }
 722             }
 723         }
 724
 725         return true;
 726     }
 727
 728     template
 729     <
 730         typename ForwardRange1,
 731         typename ForwardRange2,
 732         typename VisitPolicy,
 733         typename ExpandPolicy1,
 734         typename OverlapsPolicy1
 735     >
 736     static inline bool apply(ForwardRange1 const& forward_range1,
 737                              ForwardRange2 const& forward_range2,
 738                              VisitPolicy& visitor,
 739                              ExpandPolicy1 const& expand_policy1,
 740                              OverlapsPolicy1 const& overlaps_policy1)
 741     {
 742         return apply(forward_range1, forward_range2, visitor,
 743                      expand_policy1, overlaps_policy1, expand_policy1, overlaps_policy1,
 744                      default_min_elements, detail::partition::visit_no_policy());
 745     }
 746
 747     template
 748     <
 749         typename ForwardRange1,
 750         typename ForwardRange2,
 751         typename VisitPolicy,
 752         typename ExpandPolicy1,
 753         typename OverlapsPolicy1,
 754         typename ExpandPolicy2,
 755         typename OverlapsPolicy2
 756     >
 757     static inline bool apply(ForwardRange1 const& forward_range1,
 758                              ForwardRange2 const& forward_range2,
 759                              VisitPolicy& visitor,
 760                              ExpandPolicy1 const& expand_policy1,
 761                              OverlapsPolicy1 const& overlaps_policy1,
 762                              ExpandPolicy2 const& expand_policy2,
 763                              OverlapsPolicy2 const& overlaps_policy2)
 764     {
 765         return apply(forward_range1, forward_range2, visitor,
 766                      expand_policy1, overlaps_policy1, expand_policy2, overlaps_policy2,
 767                      default_min_elements, detail::partition::visit_no_policy());
 768     }
 769
 770     template
 771     <
 772         typename ForwardRange1,
 773         typename ForwardRange2,
 774         typename VisitPolicy,
 775         typename ExpandPolicy1,
 776         typename OverlapsPolicy1,
 777         typename ExpandPolicy2,
 778         typename OverlapsPolicy2
 779     >
 780     static inline bool apply(ForwardRange1 const& forward_range1,
 781                              ForwardRange2 const& forward_range2,
 782                              VisitPolicy& visitor,
 783                              ExpandPolicy1 const& expand_policy1,
 784                              OverlapsPolicy1 const& overlaps_policy1,
 785                              ExpandPolicy2 const& expand_policy2,
 786                              OverlapsPolicy2 const& overlaps_policy2,
 787                              std::size_t min_elements)
 788     {
 789         return apply(forward_range1, forward_range2, visitor,
 790                      expand_policy1, overlaps_policy1, expand_policy2, overlaps_policy2,
 791                      min_elements, detail::partition::visit_no_policy());
 792     }
 793
 794     template
 795     <
 796         typename ForwardRange1,
 797         typename ForwardRange2,
 798         typename VisitPolicy,
 799         typename ExpandPolicy1,
 800         typename OverlapsPolicy1,
 801         typename ExpandPolicy2,
 802         typename OverlapsPolicy2,
 803         typename VisitBoxPolicy
 804     >
 805     static inline bool apply(ForwardRange1 const& forward_range1,
 806                              ForwardRange2 const& forward_range2,
 807                              VisitPolicy& visitor,
 808                              ExpandPolicy1 const& expand_policy1,
 809                              OverlapsPolicy1 const& overlaps_policy1,
 810                              ExpandPolicy2 const& expand_policy2,
 811                              OverlapsPolicy2 const& overlaps_policy2,
 812                              std::size_t min_elements,
 813                              VisitBoxPolicy box_visitor)
 814     {
 815         typedef typename boost::range_iterator
 816             <
 817                 ForwardRange1 const
 818             >::type iterator_type1;
 819
 820         typedef typename boost::range_iterator
 821             <
 822                 ForwardRange2 const
 823             >::type iterator_type2;
 824
 825         if (std::size_t(boost::size(forward_range1)) > min_elements
 826             && std::size_t(boost::size(forward_range2)) > min_elements)
 827         {
 828             std::vector<iterator_type1> iterator_vector1;
 829             std::vector<iterator_type2> iterator_vector2;
 830             Box total;
 831             assign_inverse(total);
 832             expand_to_range<IncludePolicy1>(forward_range1, total,
 833                                             iterator_vector1, expand_policy1);
 834             expand_to_range<IncludePolicy2>(forward_range2, total,
 835                                             iterator_vector2, expand_policy2);
 836
 837             return detail::partition::partition_two_ranges
 838                 <
 839                     0, Box
 840                 >::apply(total, iterator_vector1, iterator_vector2,
 841                          0, min_elements, visitor, expand_policy1,
 842                          overlaps_policy1, expand_policy2, overlaps_policy2,
 843                          box_visitor);
 844         }
 845         else
 846         {
 847             for(iterator_type1 it1 = boost::begin(forward_range1);
 848                 it1 != boost::end(forward_range1);
 849                 ++it1)
 850             {
 851                 for(iterator_type2 it2 = boost::begin(forward_range2);
 852                     it2 != boost::end(forward_range2);
 853                     ++it2)
 854                 {
 855                     if (! visitor.apply(*it1, *it2))
 856                     {
 857                         return false; // interrupt
 858                     }
 859                 }
 860             }
 861         }
 862
 863         return true;
 864     }
 865 };
 866
 867
 868 }} // namespace boost::geometry
 869
 870 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP