1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2011-2015 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
6 // This file was modified by Oracle on 2015, 2017, 2018, 2019.
7 // Modifications copyright (c) 2015-2019 Oracle and/or its affiliates.
9 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
10 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
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)
16 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP
17 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP
21 #include <boost/range.hpp>
22 #include <boost/type_traits/is_integral.hpp>
24 #include <boost/geometry/core/access.hpp>
25 #include <boost/geometry/core/coordinate_type.hpp>
26 #include <boost/geometry/algorithms/assign.hpp>
29 namespace boost { namespace geometry
32 namespace detail { namespace partition
35 template <typename T, bool IsIntegral = boost::is_integral<T>::value>
36 struct divide_interval
38 static inline T apply(T const& mi, T const& ma)
40 static T const two = 2;
41 return (mi + ma) / two;
46 struct divide_interval<T, true>
48 static inline T apply(T const& mi, T const& ma)
51 return mi / 2 + ma / 2 + (mi % 2 + ma % 2) / 2;
55 template <int Dimension, typename Box>
56 inline void divide_box(Box const& box, Box& lower_box, Box& upper_box)
58 typedef typename coordinate_type<Box>::type ctype;
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));
67 geometry::set<max_corner, Dimension>(lower_box, mid);
68 geometry::set<min_corner, Dimension>(upper_box, mid);
71 // Divide forward_range into three subsets: lower, upper and oversized
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,
77 IteratorVector const& input,
78 IteratorVector& lower,
79 IteratorVector& upper,
80 IteratorVector& exceeding,
81 OverlapsPolicy const& overlaps_policy)
83 typedef typename boost::range_iterator
88 for(it_type it = boost::begin(input); it != boost::end(input); ++it)
90 bool const lower_overlapping = overlaps_policy.apply(lower_box, **it);
91 bool const upper_overlapping = overlaps_policy.apply(upper_box, **it);
93 if (lower_overlapping && upper_overlapping)
95 exceeding.push_back(*it);
97 else if (lower_overlapping)
101 else if (upper_overlapping)
103 upper.push_back(*it);
107 // Is nowhere. That is (since 1.58) possible, it might be
108 // skipped by the OverlapsPolicy to enhance performance
116 typename IteratorVector,
117 typename ExpandPolicy
119 inline void expand_with_elements(Box& total, IteratorVector const& input,
120 ExpandPolicy const& expand_policy)
122 typedef typename boost::range_iterator<IteratorVector const>::type it_type;
123 for(it_type it = boost::begin(input); it != boost::end(input); ++it)
125 expand_policy.apply(total, **it);
130 // Match forward_range with itself
131 template <typename IteratorVector, typename VisitPolicy>
132 inline bool handle_one(IteratorVector const& input, VisitPolicy& visitor)
134 if (boost::empty(input))
139 typedef typename boost::range_iterator<IteratorVector const>::type it_type;
141 // Quadratic behaviour at lowest level (lowest quad, or all exceeding)
142 for (it_type it1 = boost::begin(input); it1 != boost::end(input); ++it1)
145 for (++it2; it2 != boost::end(input); ++it2)
147 if (! visitor.apply(**it1, **it2))
149 return false; // interrupt
157 // Match forward range 1 with forward range 2
160 typename IteratorVector1,
161 typename IteratorVector2,
164 inline bool handle_two(IteratorVector1 const& input1,
165 IteratorVector2 const& input2,
166 VisitPolicy& visitor)
168 typedef typename boost::range_iterator
170 IteratorVector1 const
171 >::type iterator_type1;
173 typedef typename boost::range_iterator
175 IteratorVector2 const
176 >::type iterator_type2;
178 if (boost::empty(input1) || boost::empty(input2))
183 for(iterator_type1 it1 = boost::begin(input1);
184 it1 != boost::end(input1);
187 for(iterator_type2 it2 = boost::begin(input2);
188 it2 != boost::end(input2);
191 if (! visitor.apply(**it1, **it2))
193 return false; // interrupt
201 template <typename IteratorVector>
202 inline bool recurse_ok(IteratorVector const& input,
203 std::size_t min_elements, std::size_t level)
205 return boost::size(input) >= min_elements
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)
214 return boost::size(input1) >= min_elements
215 && recurse_ok(input2, min_elements, level);
220 typename IteratorVector1,
221 typename IteratorVector2,
222 typename IteratorVector3
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)
229 return boost::size(input1) >= min_elements
230 && recurse_ok(input2, input3, min_elements, level);
234 template <int Dimension, typename Box>
235 class partition_two_ranges;
238 template <int Dimension, typename Box>
239 class partition_one_range
241 template <typename IteratorVector, typename ExpandPolicy>
242 static inline Box get_new_box(IteratorVector const& input,
243 ExpandPolicy const& expand_policy)
246 geometry::assign_inverse(box);
247 expand_with_elements(box, input, expand_policy);
253 typename IteratorVector,
254 typename VisitPolicy,
255 typename ExpandPolicy,
256 typename OverlapsPolicy,
257 typename VisitBoxPolicy
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)
267 if (recurse_ok(input, min_elements, level))
269 return partition_one_range
273 >::apply(box, input, level + 1, min_elements,
274 visitor, expand_policy, overlaps_policy, box_policy);
278 return handle_one(input, visitor);
282 // Function to switch to two forward ranges if there are
283 // geometries exceeding the separation line
286 typename IteratorVector,
287 typename VisitPolicy,
288 typename ExpandPolicy,
289 typename OverlapsPolicy,
290 typename VisitBoxPolicy
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)
301 if (recurse_ok(input1, input2, min_elements, level))
303 return partition_two_ranges
306 >::apply(box, input1, input2, level + 1, min_elements,
307 visitor, expand_policy, overlaps_policy,
308 expand_policy, overlaps_policy, box_policy);
312 return handle_two(input1, input2, visitor);
319 typename IteratorVector,
320 typename VisitPolicy,
321 typename ExpandPolicy,
322 typename OverlapsPolicy,
323 typename VisitBoxPolicy
325 static inline bool apply(Box const& box,
326 IteratorVector const& input,
328 std::size_t min_elements,
329 VisitPolicy& visitor,
330 ExpandPolicy const& expand_policy,
331 OverlapsPolicy const& overlaps_policy,
332 VisitBoxPolicy& box_policy)
334 box_policy.apply(box, level);
336 Box lower_box, upper_box;
337 divide_box<Dimension>(box, lower_box, upper_box);
339 IteratorVector lower, upper, exceeding;
340 divide_into_subsets(lower_box, upper_box,
341 input, lower, upper, exceeding,
344 if (! boost::empty(exceeding))
346 // Get the box of exceeding-only
347 Box exceeding_box = get_new_box(exceeding, expand_policy);
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)) )
360 return false; // interrupt
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);
377 class partition_two_ranges
381 typename IteratorVector1,
382 typename IteratorVector2,
383 typename VisitPolicy,
384 typename ExpandPolicy1,
385 typename OverlapsPolicy1,
386 typename ExpandPolicy2,
387 typename OverlapsPolicy2,
388 typename VisitBoxPolicy
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)
401 return partition_two_ranges
404 >::apply(box, input1, input2, level + 1, min_elements,
405 visitor, expand_policy1, overlaps_policy1,
406 expand_policy2, overlaps_policy2, box_policy);
409 template <typename IteratorVector, typename ExpandPolicy>
410 static inline Box get_new_box(IteratorVector const& input,
411 ExpandPolicy const& expand_policy)
414 geometry::assign_inverse(box);
415 expand_with_elements(box, input, expand_policy);
421 typename IteratorVector1, typename IteratorVector2,
422 typename ExpandPolicy1, typename ExpandPolicy2
424 static inline Box get_new_box(IteratorVector1 const& input1,
425 IteratorVector2 const& input2,
426 ExpandPolicy1 const& expand_policy1,
427 ExpandPolicy2 const& expand_policy2)
429 Box box = get_new_box(input1, expand_policy1);
430 expand_with_elements(box, input2, expand_policy2);
437 typename IteratorVector1,
438 typename IteratorVector2,
439 typename VisitPolicy,
440 typename ExpandPolicy1,
441 typename OverlapsPolicy1,
442 typename ExpandPolicy2,
443 typename OverlapsPolicy2,
444 typename VisitBoxPolicy
446 static inline bool apply(Box const& box,
447 IteratorVector1 const& input1,
448 IteratorVector2 const& input2,
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)
458 box_policy.apply(box, level);
460 Box lower_box, upper_box;
461 divide_box<Dimension>(box, lower_box, upper_box);
463 IteratorVector1 lower1, upper1, exceeding1;
464 IteratorVector2 lower2, upper2, exceeding2;
465 divide_into_subsets(lower_box, upper_box,
466 input1, lower1, upper1, exceeding1,
468 divide_into_subsets(lower_box, upper_box,
469 input2, lower2, upper2, exceeding2,
472 if (! boost::empty(exceeding1))
474 // All exceeding from 1 with 2:
476 if (recurse_ok(exceeding1, exceeding2, min_elements, level))
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))
484 return false; // interrupt
489 if (! handle_two(exceeding1, exceeding2, visitor))
491 return false; // interrupt
495 // All exceeding from 1 with lower and upper of 2:
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))
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)) )
509 return false; // interrupt
514 if (! (handle_two(exceeding1, lower2, visitor)
515 && handle_two(exceeding1, upper2, visitor)) )
517 return false; // interrupt
522 if (! boost::empty(exceeding2))
524 // All exceeding from 2 with lower and upper of 1:
525 if (recurse_ok(lower1, upper1, exceeding2, min_elements, level))
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)) )
535 return false; // interrupt
540 if (! (handle_two(lower1, exceeding2, visitor)
541 && handle_two(upper1, exceeding2, visitor)) )
543 return false; // interrupt
548 if (recurse_ok(lower1, lower2, min_elements, level))
550 if (! next_level(lower_box, lower1, lower2, level,
551 min_elements, visitor, expand_policy1, overlaps_policy1,
552 expand_policy2, overlaps_policy2, box_policy) )
554 return false; // interrupt
559 if (! handle_two(lower1, lower2, visitor))
561 return false; // interrupt
565 if (recurse_ok(upper1, upper2, min_elements, level))
567 if (! next_level(upper_box, upper1, upper2, level,
568 min_elements, visitor, expand_policy1, overlaps_policy1,
569 expand_policy2, overlaps_policy2, box_policy) )
571 return false; // interrupt
576 if (! handle_two(upper1, upper2, visitor))
578 return false; // interrupt
586 struct visit_no_policy
588 template <typename Box>
589 static inline void apply(Box const&, std::size_t )
593 struct include_all_policy
595 template <typename Item>
596 static inline bool apply(Item const&)
603 }} // namespace detail::partition
608 typename IncludePolicy1 = detail::partition::include_all_policy,
609 typename IncludePolicy2 = detail::partition::include_all_policy
613 static const std::size_t default_min_elements = 16;
617 typename IncludePolicy,
618 typename ForwardRange,
619 typename IteratorVector,
620 typename ExpandPolicy
622 static inline void expand_to_range(ForwardRange const& forward_range,
624 IteratorVector& iterator_vector,
625 ExpandPolicy const& expand_policy)
627 for(typename boost::range_iterator<ForwardRange const>::type
628 it = boost::begin(forward_range);
629 it != boost::end(forward_range);
632 if (IncludePolicy::apply(*it))
634 expand_policy.apply(total, *it);
635 iterator_vector.push_back(it);
643 typename ForwardRange,
644 typename VisitPolicy,
645 typename ExpandPolicy,
646 typename OverlapsPolicy
648 static inline bool apply(ForwardRange const& forward_range,
649 VisitPolicy& visitor,
650 ExpandPolicy const& expand_policy,
651 OverlapsPolicy const& overlaps_policy)
653 return apply(forward_range, visitor, expand_policy, overlaps_policy,
654 default_min_elements, detail::partition::visit_no_policy());
659 typename ForwardRange,
660 typename VisitPolicy,
661 typename ExpandPolicy,
662 typename OverlapsPolicy
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)
670 return apply(forward_range, visitor, expand_policy, overlaps_policy,
671 min_elements, detail::partition::visit_no_policy());
676 typename ForwardRange,
677 typename VisitPolicy,
678 typename ExpandPolicy,
679 typename OverlapsPolicy,
680 typename VisitBoxPolicy
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)
689 typedef typename boost::range_iterator
692 >::type iterator_type;
694 if (std::size_t(boost::size(forward_range)) > min_elements)
696 std::vector<iterator_type> iterator_vector;
698 assign_inverse(total);
699 expand_to_range<IncludePolicy1>(forward_range, total,
700 iterator_vector, expand_policy);
702 return detail::partition::partition_one_range
705 >::apply(total, iterator_vector, 0, min_elements,
706 visitor, expand_policy, overlaps_policy, box_visitor);
710 for(iterator_type it1 = boost::begin(forward_range);
711 it1 != boost::end(forward_range);
714 iterator_type it2 = it1;
715 for(++it2; it2 != boost::end(forward_range); ++it2)
717 if (! visitor.apply(*it1, *it2))
719 return false; // interrupt
730 typename ForwardRange1,
731 typename ForwardRange2,
732 typename VisitPolicy,
733 typename ExpandPolicy1,
734 typename OverlapsPolicy1
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)
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());
749 typename ForwardRange1,
750 typename ForwardRange2,
751 typename VisitPolicy,
752 typename ExpandPolicy1,
753 typename OverlapsPolicy1,
754 typename ExpandPolicy2,
755 typename OverlapsPolicy2
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)
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());
772 typename ForwardRange1,
773 typename ForwardRange2,
774 typename VisitPolicy,
775 typename ExpandPolicy1,
776 typename OverlapsPolicy1,
777 typename ExpandPolicy2,
778 typename OverlapsPolicy2
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)
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());
796 typename ForwardRange1,
797 typename ForwardRange2,
798 typename VisitPolicy,
799 typename ExpandPolicy1,
800 typename OverlapsPolicy1,
801 typename ExpandPolicy2,
802 typename OverlapsPolicy2,
803 typename VisitBoxPolicy
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)
815 typedef typename boost::range_iterator
818 >::type iterator_type1;
820 typedef typename boost::range_iterator
823 >::type iterator_type2;
825 if (std::size_t(boost::size(forward_range1)) > min_elements
826 && std::size_t(boost::size(forward_range2)) > min_elements)
828 std::vector<iterator_type1> iterator_vector1;
829 std::vector<iterator_type2> iterator_vector2;
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);
837 return detail::partition::partition_two_ranges
840 >::apply(total, iterator_vector1, iterator_vector2,
841 0, min_elements, visitor, expand_policy1,
842 overlaps_policy1, expand_policy2, overlaps_policy2,
847 for(iterator_type1 it1 = boost::begin(forward_range1);
848 it1 != boost::end(forward_range1);
851 for(iterator_type2 it2 = boost::begin(forward_range2);
852 it2 != boost::end(forward_range2);
855 if (! visitor.apply(*it1, *it2))
857 return false; // interrupt
868 }} // namespace boost::geometry
870 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP