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