1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2
3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2014-2017 Adam Wulkiewicz, Lodz, Poland.
5
6 // This file was modified by Oracle on 2014, 2016, 2017.
7 // Modifications copyright (c) 2014-2017 Oracle and/or its affiliates.
8
9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
10
11 // Use, modification and distribution is subject to the Boost Software License,
12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
13 // http://www.boost.org/LICENSE_1_0.txt)
14
15 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
17
18
19 #include <cstddef>
20 #include <map>
21
22 #include <boost/array.hpp>
23 #include <boost/concept_check.hpp>
24 #include <boost/mpl/if.hpp>
25 #include <boost/mpl/vector_c.hpp>
26 #include <boost/range.hpp>
27
28 #include <boost/geometry/core/access.hpp>
29 #include <boost/geometry/core/coordinate_dimension.hpp>
30 #include <boost/geometry/core/exterior_ring.hpp>
31 #include <boost/geometry/core/interior_rings.hpp>
32 #include <boost/geometry/core/reverse_dispatch.hpp>
33 #include <boost/geometry/core/ring_type.hpp>
34 #include <boost/geometry/core/tags.hpp>
35
36 #include <boost/geometry/geometries/concepts/check.hpp>
37
38 #include <boost/geometry/util/math.hpp>
39 #include <boost/geometry/views/closeable_view.hpp>
40 #include <boost/geometry/views/reversible_view.hpp>
41 #include <boost/geometry/views/detail/range_type.hpp>
42
43 #include <boost/geometry/geometries/box.hpp>
44 #include <boost/geometry/geometries/segment.hpp>
45
46 #include <boost/geometry/iterators/ever_circling_iterator.hpp>
47
48 #include <boost/geometry/strategies/intersection_strategies.hpp>
49 #include <boost/geometry/strategies/intersection_result.hpp>
50
51 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
52 #include <boost/geometry/algorithms/detail/disjoint/point_point.hpp>
53
54 #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
55 #include <boost/geometry/algorithms/detail/partition.hpp>
56 #include <boost/geometry/algorithms/detail/recalculate.hpp>
57 #include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp>
58
59 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
60 #include <boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp>
61 #include <boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp>
62 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
63
64 #include <boost/geometry/algorithms/detail/sections/range_by_section.hpp>
65 #include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
66 #include <boost/geometry/algorithms/detail/sections/section_functions.hpp>
67
68 #ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
69 # include <sstream>
70 # include <boost/geometry/io/dsv/write.hpp>
71 #endif
72
73
74 namespace boost { namespace geometry
75 {
76
77 // Silence warning C4127: conditional expression is constant
78 #if defined(_MSC_VER)
79 #pragma warning(push)
80 #pragma warning(disable : 4127)
81 #endif
82
83
84 #ifndef DOXYGEN_NO_DETAIL
85 namespace detail { namespace get_turns
86 {
87
88
89 struct no_interrupt_policy
90 {
91 static bool const enabled = false;
92
93 // variable required by self_get_turn_points::get_turns
94 static bool const has_intersections = false;
95
96 template <typename Range>
applyboost::geometry::detail::get_turns::no_interrupt_policy97 static inline bool apply(Range const&)
98 {
99 return false;
100 }
101 };
102
103
104 template
105 <
106 typename Geometry1, typename Geometry2,
107 bool Reverse1, bool Reverse2,
108 typename Section1, typename Section2,
109 typename TurnPolicy
110 >
111 class get_turns_in_sections
112 {
113 typedef typename closeable_view
114 <
115 typename range_type<Geometry1>::type const,
116 closure<Geometry1>::value
117 >::type cview_type1;
118 typedef typename closeable_view
119 <
120 typename range_type<Geometry2>::type const,
121 closure<Geometry2>::value
122 >::type cview_type2;
123
124 typedef typename reversible_view
125 <
126 cview_type1 const,
127 Reverse1 ? iterate_reverse : iterate_forward
128 >::type view_type1;
129 typedef typename reversible_view
130 <
131 cview_type2 const,
132 Reverse2 ? iterate_reverse : iterate_forward
133 >::type view_type2;
134
135 typedef typename boost::range_iterator
136 <
137 view_type1 const
138 >::type range1_iterator;
139
140 typedef typename boost::range_iterator
141 <
142 view_type2 const
143 >::type range2_iterator;
144
145
146 template <typename Geometry, typename Section>
neighbouring(Section const & section,signed_size_type index1,signed_size_type index2)147 static inline bool neighbouring(Section const& section,
148 signed_size_type index1, signed_size_type index2)
149 {
150 // About n-2:
151 // (square: range_count=5, indices 0,1,2,3
152 // -> 0-3 are adjacent, don't check on intersections)
153 // Also tested for open polygons, and/or duplicates
154 // About first condition: will be optimized by compiler (static)
155 // It checks if it is areal (box,ring,(multi)polygon
156 signed_size_type const n = static_cast<signed_size_type>(section.range_count);
157
158 boost::ignore_unused_variable_warning(n);
159 boost::ignore_unused_variable_warning(index1);
160 boost::ignore_unused_variable_warning(index2);
161
162 return boost::is_same
163 <
164 typename tag_cast
165 <
166 typename geometry::tag<Geometry>::type,
167 areal_tag
168 >::type,
169 areal_tag
170 >::value
171 && index1 == 0
172 && index2 >= n - 2
173 ;
174 }
175
176
177 public :
178 // Returns true if terminated, false if interrupted
179 template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
apply(int source_id1,Geometry1 const & geometry1,Section1 const & sec1,int source_id2,Geometry2 const & geometry2,Section2 const & sec2,bool skip_larger,IntersectionStrategy const & intersection_strategy,RobustPolicy const & robust_policy,Turns & turns,InterruptPolicy & interrupt_policy)180 static inline bool apply(
181 int source_id1, Geometry1 const& geometry1, Section1 const& sec1,
182 int source_id2, Geometry2 const& geometry2, Section2 const& sec2,
183 bool skip_larger,
184 IntersectionStrategy const& intersection_strategy,
185 RobustPolicy const& robust_policy,
186 Turns& turns,
187 InterruptPolicy& interrupt_policy)
188 {
189 boost::ignore_unused_variable_warning(interrupt_policy);
190
191 if ((sec1.duplicate && (sec1.count + 1) < sec1.range_count)
192 || (sec2.duplicate && (sec2.count + 1) < sec2.range_count))
193 {
194 // Skip sections containig only duplicates.
195 // They are still important (can indicate non-disjointness)
196 // but they will be found processing adjacent sections.
197 // Do NOT skip if they are the ONLY section
198 return true;
199 }
200
201 cview_type1 cview1(range_by_section(geometry1, sec1));
202 cview_type2 cview2(range_by_section(geometry2, sec2));
203 view_type1 view1(cview1);
204 view_type2 view2(cview2);
205
206 range1_iterator begin_range_1 = boost::begin(view1);
207 range1_iterator end_range_1 = boost::end(view1);
208
209 range2_iterator begin_range_2 = boost::begin(view2);
210 range2_iterator end_range_2 = boost::end(view2);
211
212 int const dir1 = sec1.directions[0];
213 int const dir2 = sec2.directions[0];
214 signed_size_type index1 = sec1.begin_index;
215 signed_size_type ndi1 = sec1.non_duplicate_index;
216
217 bool const same_source =
218 source_id1 == source_id2
219 && sec1.ring_id.multi_index == sec2.ring_id.multi_index
220 && sec1.ring_id.ring_index == sec2.ring_id.ring_index;
221
222 range1_iterator prev1, it1, end1;
223
224 get_start_point_iterator(sec1, view1, prev1, it1, end1,
225 index1, ndi1, dir1, sec2.bounding_box, robust_policy);
226
227 // We need a circular iterator because it might run through the closing point.
228 // One circle is actually enough but this one is just convenient.
229 ever_circling_iterator<range1_iterator> next1(begin_range_1, end_range_1, it1, true);
230 next1++;
231
232 // Walk through section and stop if we exceed the other box
233 // section 2: [--------------]
234 // section 1: |----|---|---|---|---|
235 for (prev1 = it1++, next1++;
236 it1 != end1 && ! detail::section::exceeding<0>(dir1, *prev1, sec1.bounding_box, sec2.bounding_box, robust_policy);
237 ++prev1, ++it1, ++index1, ++next1, ++ndi1)
238 {
239 ever_circling_iterator<range1_iterator> nd_next1(
240 begin_range_1, end_range_1, next1, true);
241 advance_to_non_duplicate_next(nd_next1, it1, sec1, robust_policy);
242
243 signed_size_type index2 = sec2.begin_index;
244 signed_size_type ndi2 = sec2.non_duplicate_index;
245
246 range2_iterator prev2, it2, end2;
247
248 get_start_point_iterator(sec2, view2, prev2, it2, end2,
249 index2, ndi2, dir2, sec1.bounding_box, robust_policy);
250 ever_circling_iterator<range2_iterator> next2(begin_range_2, end_range_2, it2, true);
251 next2++;
252
253 for (prev2 = it2++, next2++;
254 it2 != end2 && ! detail::section::exceeding<0>(dir2, *prev2, sec2.bounding_box, sec1.bounding_box, robust_policy);
255 ++prev2, ++it2, ++index2, ++next2, ++ndi2)
256 {
257 bool skip = same_source;
258 if (skip)
259 {
260 // If sources are the same (possibly self-intersecting):
261 // skip if it is a neighbouring segment.
262 // (including first-last segment
263 // and two segments with one or more degenerate/duplicate
264 // (zero-length) segments in between)
265
266 // Also skip if index1 < index2 to avoid getting all
267 // intersections twice (only do this on same source!)
268
269 skip = (skip_larger && index1 >= index2)
270 || ndi2 == ndi1 + 1
271 || neighbouring<Geometry1>(sec1, index1, index2)
272 ;
273 }
274
275 if (! skip)
276 {
277 // Move to the "non duplicate next"
278 ever_circling_iterator<range2_iterator> nd_next2(
279 begin_range_2, end_range_2, next2, true);
280 advance_to_non_duplicate_next(nd_next2, it2, sec2, robust_policy);
281
282 typedef typename boost::range_value<Turns>::type turn_info;
283
284 turn_info ti;
285 ti.operations[0].seg_id
286 = segment_identifier(source_id1, sec1.ring_id.multi_index,
287 sec1.ring_id.ring_index, index1);
288 ti.operations[1].seg_id
289 = segment_identifier(source_id2, sec2.ring_id.multi_index,
290 sec2.ring_id.ring_index, index2);
291
292 std::size_t const size_before = boost::size(turns);
293
294 bool const is_1_first = sec1.is_non_duplicate_first && index1 == sec1.begin_index;
295 bool const is_1_last = sec1.is_non_duplicate_last && index1+1 >= sec1.end_index;
296 bool const is_2_first = sec2.is_non_duplicate_first && index2 == sec2.begin_index;
297 bool const is_2_last = sec2.is_non_duplicate_last && index2+1 >= sec2.end_index;
298
299 TurnPolicy::apply(*prev1, *it1, *nd_next1, *prev2, *it2, *nd_next2,
300 is_1_first, is_1_last, is_2_first, is_2_last,
301 ti, intersection_strategy, robust_policy,
302 std::back_inserter(turns));
303
304 if (InterruptPolicy::enabled)
305 {
306 if (interrupt_policy.apply(
307 std::make_pair(range::pos(turns, size_before),
308 boost::end(turns))))
309 {
310 return false;
311 }
312 }
313 }
314 }
315 }
316 return true;
317 }
318
319
320 private :
321 typedef typename geometry::point_type<Geometry1>::type point1_type;
322 typedef typename geometry::point_type<Geometry2>::type point2_type;
323 typedef typename model::referring_segment<point1_type const> segment1_type;
324 typedef typename model::referring_segment<point2_type const> segment2_type;
325
326 template <typename Iterator, typename RangeIterator, typename Section, typename RobustPolicy>
advance_to_non_duplicate_next(Iterator & next,RangeIterator const & it,Section const & section,RobustPolicy const & robust_policy)327 static inline void advance_to_non_duplicate_next(Iterator& next,
328 RangeIterator const& it, Section const& section, RobustPolicy const& robust_policy)
329 {
330 typedef typename robust_point_type<point1_type, RobustPolicy>::type robust_point_type;
331 robust_point_type robust_point_from_it;
332 robust_point_type robust_point_from_next;
333 geometry::recalculate(robust_point_from_it, *it, robust_policy);
334 geometry::recalculate(robust_point_from_next, *next, robust_policy);
335
336 // To see where the next segments bend to, in case of touch/intersections
337 // on end points, we need (in case of degenerate/duplicate points) an extra
338 // iterator which moves to the REAL next point, so non duplicate.
339 // This needs an extra comparison (disjoint).
340 // (Note that within sections, non duplicate points are already asserted,
341 // by the sectionalize process).
342
343 // So advance to the "non duplicate next"
344 // (the check is defensive, to avoid endless loops)
345 std::size_t check = 0;
346 while(! detail::disjoint::disjoint_point_point
347 (
348 robust_point_from_it, robust_point_from_next
349 )
350 && check++ < section.range_count)
351 {
352 next++;
353 geometry::recalculate(robust_point_from_next, *next, robust_policy);
354 }
355 }
356
357 // It is NOT possible to have section-iterators here
358 // because of the logistics of "index" (the section-iterator automatically
359 // skips to the begin-point, we loose the index or have to recalculate it)
360 // So we mimic it here
361 template <typename Range, typename Section, typename Box, typename RobustPolicy>
get_start_point_iterator(Section const & section,Range const & range,typename boost::range_iterator<Range const>::type & it,typename boost::range_iterator<Range const>::type & prev,typename boost::range_iterator<Range const>::type & end,signed_size_type & index,signed_size_type & ndi,int dir,Box const & other_bounding_box,RobustPolicy const & robust_policy)362 static inline void get_start_point_iterator(Section const& section,
363 Range const& range,
364 typename boost::range_iterator<Range const>::type& it,
365 typename boost::range_iterator<Range const>::type& prev,
366 typename boost::range_iterator<Range const>::type& end,
367 signed_size_type& index, signed_size_type& ndi,
368 int dir, Box const& other_bounding_box, RobustPolicy const& robust_policy)
369 {
370 it = boost::begin(range) + section.begin_index;
371 end = boost::begin(range) + section.end_index + 1;
372
373 // Mimic section-iterator:
374 // Skip to point such that section interects other box
375 prev = it++;
376 for(; it != end && detail::section::preceding<0>(dir, *it, section.bounding_box, other_bounding_box, robust_policy);
377 prev = it++, index++, ndi++)
378 {}
379 // Go back one step because we want to start completely preceding
380 it = prev;
381 }
382 };
383
384 template
385 <
386 typename Geometry1, typename Geometry2,
387 bool Reverse1, bool Reverse2,
388 typename TurnPolicy,
389 typename IntersectionStrategy,
390 typename RobustPolicy,
391 typename Turns,
392 typename InterruptPolicy
393 >
394 struct section_visitor
395 {
396 int m_source_id1;
397 Geometry1 const& m_geometry1;
398 int m_source_id2;
399 Geometry2 const& m_geometry2;
400 IntersectionStrategy const& m_intersection_strategy;
401 RobustPolicy const& m_rescale_policy;
402 Turns& m_turns;
403 InterruptPolicy& m_interrupt_policy;
404
section_visitorboost::geometry::detail::get_turns::section_visitor405 section_visitor(int id1, Geometry1 const& g1,
406 int id2, Geometry2 const& g2,
407 IntersectionStrategy const& intersection_strategy,
408 RobustPolicy const& robust_policy,
409 Turns& turns,
410 InterruptPolicy& ip)
411 : m_source_id1(id1), m_geometry1(g1)
412 , m_source_id2(id2), m_geometry2(g2)
413 , m_intersection_strategy(intersection_strategy)
414 , m_rescale_policy(robust_policy)
415 , m_turns(turns)
416 , m_interrupt_policy(ip)
417 {}
418
419 template <typename Section>
applyboost::geometry::detail::get_turns::section_visitor420 inline bool apply(Section const& sec1, Section const& sec2)
421 {
422 if (! detail::disjoint::disjoint_box_box(sec1.bounding_box, sec2.bounding_box))
423 {
424 // false if interrupted
425 return get_turns_in_sections
426 <
427 Geometry1,
428 Geometry2,
429 Reverse1, Reverse2,
430 Section, Section,
431 TurnPolicy
432 >::apply(m_source_id1, m_geometry1, sec1,
433 m_source_id2, m_geometry2, sec2,
434 false,
435 m_intersection_strategy,
436 m_rescale_policy,
437 m_turns, m_interrupt_policy);
438 }
439 return true;
440 }
441
442 };
443
444 template
445 <
446 typename Geometry1, typename Geometry2,
447 bool Reverse1, bool Reverse2,
448 typename TurnPolicy
449 >
450 class get_turns_generic
451 {
452
453 public:
454 template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
apply(int source_id1,Geometry1 const & geometry1,int source_id2,Geometry2 const & geometry2,IntersectionStrategy const & intersection_strategy,RobustPolicy const & robust_policy,Turns & turns,InterruptPolicy & interrupt_policy)455 static inline void apply(
456 int source_id1, Geometry1 const& geometry1,
457 int source_id2, Geometry2 const& geometry2,
458 IntersectionStrategy const& intersection_strategy,
459 RobustPolicy const& robust_policy,
460 Turns& turns,
461 InterruptPolicy& interrupt_policy)
462 {
463 // First create monotonic sections...
464 typedef typename boost::range_value<Turns>::type ip_type;
465 typedef typename ip_type::point_type point_type;
466
467 typedef model::box
468 <
469 typename geometry::robust_point_type
470 <
471 point_type, RobustPolicy
472 >::type
473 > box_type;
474 typedef geometry::sections<box_type, 2> sections_type;
475
476 sections_type sec1, sec2;
477 typedef boost::mpl::vector_c<std::size_t, 0, 1> dimensions;
478
479 typename IntersectionStrategy::envelope_strategy_type const
480 envelope_strategy = intersection_strategy.get_envelope_strategy();
481
482 geometry::sectionalize<Reverse1, dimensions>(geometry1, robust_policy,
483 sec1, envelope_strategy, 0);
484 geometry::sectionalize<Reverse2, dimensions>(geometry2, robust_policy,
485 sec2, envelope_strategy, 1);
486
487 // ... and then partition them, intersecting overlapping sections in visitor method
488 section_visitor
489 <
490 Geometry1, Geometry2,
491 Reverse1, Reverse2,
492 TurnPolicy,
493 IntersectionStrategy, RobustPolicy,
494 Turns, InterruptPolicy
495 > visitor(source_id1, geometry1, source_id2, geometry2,
496 intersection_strategy, robust_policy,
497 turns, interrupt_policy);
498
499 geometry::partition
500 <
501 box_type
502 >::apply(sec1, sec2, visitor,
503 detail::section::get_section_box(),
504 detail::section::overlaps_section_box());
505 }
506 };
507
508
509 // Get turns for a range with a box, following Cohen-Sutherland (cs) approach
510 template
511 <
512 typename Range, typename Box,
513 bool ReverseRange, bool ReverseBox,
514 typename TurnPolicy
515 >
516 struct get_turns_cs
517 {
518 typedef typename geometry::point_type<Range>::type point_type;
519 typedef typename geometry::point_type<Box>::type box_point_type;
520
521 typedef typename closeable_view
522 <
523 Range const,
524 closure<Range>::value
525 >::type cview_type;
526
527 typedef typename reversible_view
528 <
529 cview_type const,
530 ReverseRange ? iterate_reverse : iterate_forward
531 >::type view_type;
532
533 typedef typename boost::range_iterator
534 <
535 view_type const
536 >::type iterator_type;
537
538
539 template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
applyboost::geometry::detail::get_turns::get_turns_cs540 static inline void apply(
541 int source_id1, Range const& range,
542 int source_id2, Box const& box,
543 IntersectionStrategy const& intersection_strategy,
544 RobustPolicy const& robust_policy,
545 Turns& turns,
546 InterruptPolicy& interrupt_policy,
547 signed_size_type multi_index = -1,
548 signed_size_type ring_index = -1)
549 {
550 if ( boost::size(range) <= 1)
551 {
552 return;
553 }
554
555 boost::array<box_point_type,4> bp;
556 assign_box_corners_oriented<ReverseBox>(box, bp);
557
558 cview_type cview(range);
559 view_type view(cview);
560
561 typedef typename boost::range_size<view_type>::type size_type;
562 size_type segments_count1 = boost::size(view) - 1;
563
564 iterator_type it = boost::begin(view);
565
566 ever_circling_iterator<iterator_type> next(
567 boost::begin(view), boost::end(view), it, true);
568 next++;
569 next++;
570
571 //bool first = true;
572
573 //char previous_side[2] = {0, 0};
574
575 signed_size_type index = 0;
576
577 for (iterator_type prev = it++;
578 it != boost::end(view);
579 prev = it++, next++, index++)
580 {
581 segment_identifier seg_id(source_id1,
582 multi_index, ring_index, index);
583
584 /*if (first)
585 {
586 previous_side[0] = get_side<0>(box, *prev);
587 previous_side[1] = get_side<1>(box, *prev);
588 }
589
590 char current_side[2];
591 current_side[0] = get_side<0>(box, *it);
592 current_side[1] = get_side<1>(box, *it);
593
594 // There can NOT be intersections if
595 // 1) EITHER the two points are lying on one side of the box (! 0 && the same)
596 // 2) OR same in Y-direction
597 // 3) OR all points are inside the box (0)
598 if (! (
599 (current_side[0] != 0 && current_side[0] == previous_side[0])
600 || (current_side[1] != 0 && current_side[1] == previous_side[1])
601 || (current_side[0] == 0
602 && current_side[1] == 0
603 && previous_side[0] == 0
604 && previous_side[1] == 0)
605 )
606 )*/
607 if (true)
608 {
609 get_turns_with_box(seg_id, source_id2,
610 *prev, *it, *next,
611 bp[0], bp[1], bp[2], bp[3],
612 // NOTE: some dummy values could be passed below since this would be called only for Polygons and Boxes
613 index == 0,
614 size_type(index) == segments_count1,
615 intersection_strategy,
616 robust_policy,
617 turns,
618 interrupt_policy);
619 // Future performance enhancement:
620 // return if told by the interrupt policy
621 }
622 }
623 }
624
625 private:
626 template<std::size_t Index, typename Point>
get_sideboost::geometry::detail::get_turns::get_turns_cs627 static inline int get_side(Box const& box, Point const& point)
628 {
629 // Inside -> 0
630 // Outside -> -1 (left/below) or 1 (right/above)
631 // On border -> -2 (left/lower) or 2 (right/upper)
632 // The only purpose of the value is to not be the same,
633 // and to denote if it is inside (0)
634
635 typename coordinate_type<Point>::type const& c = get<Index>(point);
636 typename coordinate_type<Box>::type const& left = get<min_corner, Index>(box);
637 typename coordinate_type<Box>::type const& right = get<max_corner, Index>(box);
638
639 if (geometry::math::equals(c, left)) return -2;
640 else if (geometry::math::equals(c, right)) return 2;
641 else if (c < left) return -1;
642 else if (c > right) return 1;
643 else return 0;
644 }
645
646 template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
get_turns_with_boxboost::geometry::detail::get_turns::get_turns_cs647 static inline void get_turns_with_box(segment_identifier const& seg_id, int source_id2,
648 // Points from a range:
649 point_type const& rp0,
650 point_type const& rp1,
651 point_type const& rp2,
652 // Points from the box
653 box_point_type const& bp0,
654 box_point_type const& bp1,
655 box_point_type const& bp2,
656 box_point_type const& bp3,
657 bool const is_range_first,
658 bool const is_range_last,
659 IntersectionStrategy const& intersection_strategy,
660 RobustPolicy const& robust_policy,
661 // Output
662 Turns& turns,
663 InterruptPolicy& interrupt_policy)
664 {
665 boost::ignore_unused_variable_warning(interrupt_policy);
666
667 // Depending on code some relations can be left out
668
669 typedef typename boost::range_value<Turns>::type turn_info;
670
671 turn_info ti;
672 ti.operations[0].seg_id = seg_id;
673
674 ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 0);
675 TurnPolicy::apply(rp0, rp1, rp2, bp0, bp1, bp2,
676 is_range_first, is_range_last,
677 true, false,
678 ti, intersection_strategy, robust_policy,
679 std::back_inserter(turns));
680
681 ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 1);
682 TurnPolicy::apply(rp0, rp1, rp2, bp1, bp2, bp3,
683 is_range_first, is_range_last,
684 false, false,
685 ti, intersection_strategy, robust_policy,
686 std::back_inserter(turns));
687
688 ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 2);
689 TurnPolicy::apply(rp0, rp1, rp2, bp2, bp3, bp0,
690 is_range_first, is_range_last,
691 false, false,
692 ti, intersection_strategy, robust_policy,
693 std::back_inserter(turns));
694
695 ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 3);
696 TurnPolicy::apply(rp0, rp1, rp2, bp3, bp0, bp1,
697 is_range_first, is_range_last,
698 false, true,
699 ti, intersection_strategy, robust_policy,
700 std::back_inserter(turns));
701
702 if (InterruptPolicy::enabled)
703 {
704 interrupt_policy.apply(turns);
705 }
706
707 }
708
709 };
710
711
712 template
713 <
714 typename Polygon, typename Box,
715 bool Reverse, bool ReverseBox,
716 typename TurnPolicy
717 >
718 struct get_turns_polygon_cs
719 {
720 template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
applyboost::geometry::detail::get_turns::get_turns_polygon_cs721 static inline void apply(
722 int source_id1, Polygon const& polygon,
723 int source_id2, Box const& box,
724 IntersectionStrategy const& intersection_strategy,
725 RobustPolicy const& robust_policy,
726 Turns& turns,
727 InterruptPolicy& interrupt_policy,
728 signed_size_type multi_index = -1)
729 {
730 typedef typename geometry::ring_type<Polygon>::type ring_type;
731
732 typedef detail::get_turns::get_turns_cs
733 <
734 ring_type, Box,
735 Reverse, ReverseBox,
736 TurnPolicy
737 > intersector_type;
738
739 intersector_type::apply(
740 source_id1, geometry::exterior_ring(polygon),
741 source_id2, box,
742 intersection_strategy,
743 robust_policy,
744 turns,
745 interrupt_policy,
746 multi_index, -1);
747
748 signed_size_type i = 0;
749
750 typename interior_return_type<Polygon const>::type
751 rings = interior_rings(polygon);
752 for (typename detail::interior_iterator<Polygon const>::type
753 it = boost::begin(rings); it != boost::end(rings); ++it, ++i)
754 {
755 intersector_type::apply(
756 source_id1, *it,
757 source_id2, box,
758 intersection_strategy,
759 robust_policy,
760 turns, interrupt_policy,
761 multi_index, i);
762 }
763
764 }
765 };
766
767
768 template
769 <
770 typename Multi, typename Box,
771 bool Reverse, bool ReverseBox,
772 typename TurnPolicy
773 >
774 struct get_turns_multi_polygon_cs
775 {
776 template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
applyboost::geometry::detail::get_turns::get_turns_multi_polygon_cs777 static inline void apply(
778 int source_id1, Multi const& multi,
779 int source_id2, Box const& box,
780 IntersectionStrategy const& intersection_strategy,
781 RobustPolicy const& robust_policy,
782 Turns& turns,
783 InterruptPolicy& interrupt_policy)
784 {
785 typedef typename boost::range_iterator
786 <
787 Multi const
788 >::type iterator_type;
789
790 signed_size_type i = 0;
791 for (iterator_type it = boost::begin(multi);
792 it != boost::end(multi);
793 ++it, ++i)
794 {
795 // Call its single version
796 get_turns_polygon_cs
797 <
798 typename boost::range_value<Multi>::type, Box,
799 Reverse, ReverseBox,
800 TurnPolicy
801 >::apply(source_id1, *it, source_id2, box,
802 intersection_strategy, robust_policy,
803 turns, interrupt_policy, i);
804 }
805 }
806 };
807
808
809 // GET_TURN_INFO_TYPE
810
811 template <typename Geometry>
812 struct topological_tag_base
813 {
814 typedef typename tag_cast<typename tag<Geometry>::type, pointlike_tag, linear_tag, areal_tag>::type type;
815 };
816
817 template <typename Geometry1, typename Geometry2, typename AssignPolicy,
818 typename Tag1 = typename tag<Geometry1>::type, typename Tag2 = typename tag<Geometry2>::type,
819 typename TagBase1 = typename topological_tag_base<Geometry1>::type, typename TagBase2 = typename topological_tag_base<Geometry2>::type>
820 struct get_turn_info_type
821 : overlay::get_turn_info<AssignPolicy>
822 {};
823
824 template <typename Geometry1, typename Geometry2, typename AssignPolicy, typename Tag1, typename Tag2>
825 struct get_turn_info_type<Geometry1, Geometry2, AssignPolicy, Tag1, Tag2, linear_tag, linear_tag>
826 : overlay::get_turn_info_linear_linear<AssignPolicy>
827 {};
828
829 template <typename Geometry1, typename Geometry2, typename AssignPolicy, typename Tag1, typename Tag2>
830 struct get_turn_info_type<Geometry1, Geometry2, AssignPolicy, Tag1, Tag2, linear_tag, areal_tag>
831 : overlay::get_turn_info_linear_areal<AssignPolicy>
832 {};
833
834 template <typename Geometry1, typename Geometry2, typename SegmentRatio,
835 typename Tag1 = typename tag<Geometry1>::type, typename Tag2 = typename tag<Geometry2>::type,
836 typename TagBase1 = typename topological_tag_base<Geometry1>::type, typename TagBase2 = typename topological_tag_base<Geometry2>::type>
837 struct turn_operation_type
838 {
839 typedef overlay::turn_operation<typename point_type<Geometry1>::type, SegmentRatio> type;
840 };
841
842 template <typename Geometry1, typename Geometry2, typename SegmentRatio, typename Tag1, typename Tag2>
843 struct turn_operation_type<Geometry1, Geometry2, SegmentRatio, Tag1, Tag2, linear_tag, linear_tag>
844 {
845 typedef overlay::turn_operation_linear<typename point_type<Geometry1>::type, SegmentRatio> type;
846 };
847
848 template <typename Geometry1, typename Geometry2, typename SegmentRatio, typename Tag1, typename Tag2>
849 struct turn_operation_type<Geometry1, Geometry2, SegmentRatio, Tag1, Tag2, linear_tag, areal_tag>
850 {
851 typedef overlay::turn_operation_linear<typename point_type<Geometry1>::type, SegmentRatio> type;
852 };
853
854 }} // namespace detail::get_turns
855 #endif // DOXYGEN_NO_DETAIL
856
857
858 #ifndef DOXYGEN_NO_DISPATCH
859 namespace dispatch
860 {
861
862 // Because this is "detail" method, and most implementations will use "generic",
863 // we take the freedom to derive it from "generic".
864 template
865 <
866 typename GeometryTag1, typename GeometryTag2,
867 typename Geometry1, typename Geometry2,
868 bool Reverse1, bool Reverse2,
869 typename TurnPolicy
870 >
871 struct get_turns
872 : detail::get_turns::get_turns_generic
873 <
874 Geometry1, Geometry2,
875 Reverse1, Reverse2,
876 TurnPolicy
877 >
878 {};
879
880
881 template
882 <
883 typename Polygon, typename Box,
884 bool ReversePolygon, bool ReverseBox,
885 typename TurnPolicy
886 >
887 struct get_turns
888 <
889 polygon_tag, box_tag,
890 Polygon, Box,
891 ReversePolygon, ReverseBox,
892 TurnPolicy
893 > : detail::get_turns::get_turns_polygon_cs
894 <
895 Polygon, Box,
896 ReversePolygon, ReverseBox,
897 TurnPolicy
898 >
899 {};
900
901
902 template
903 <
904 typename Ring, typename Box,
905 bool ReverseRing, bool ReverseBox,
906 typename TurnPolicy
907 >
908 struct get_turns
909 <
910 ring_tag, box_tag,
911 Ring, Box,
912 ReverseRing, ReverseBox,
913 TurnPolicy
914 > : detail::get_turns::get_turns_cs
915 <
916 Ring, Box, ReverseRing, ReverseBox,
917 TurnPolicy
918 >
919
920 {};
921
922
923 template
924 <
925 typename MultiPolygon,
926 typename Box,
927 bool ReverseMultiPolygon, bool ReverseBox,
928 typename TurnPolicy
929 >
930 struct get_turns
931 <
932 multi_polygon_tag, box_tag,
933 MultiPolygon, Box,
934 ReverseMultiPolygon, ReverseBox,
935 TurnPolicy
936 >
937 : detail::get_turns::get_turns_multi_polygon_cs
938 <
939 MultiPolygon, Box,
940 ReverseMultiPolygon, ReverseBox,
941 TurnPolicy
942 >
943 {};
944
945
946 template
947 <
948 typename GeometryTag1, typename GeometryTag2,
949 typename Geometry1, typename Geometry2,
950 bool Reverse1, bool Reverse2,
951 typename TurnPolicy
952 >
953 struct get_turns_reversed
954 {
955 template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
applyboost::geometry::dispatch::get_turns_reversed956 static inline void apply(int source_id1, Geometry1 const& g1,
957 int source_id2, Geometry2 const& g2,
958 IntersectionStrategy const& intersection_strategy,
959 RobustPolicy const& robust_policy,
960 Turns& turns,
961 InterruptPolicy& interrupt_policy)
962 {
963 get_turns
964 <
965 GeometryTag2, GeometryTag1,
966 Geometry2, Geometry1,
967 Reverse2, Reverse1,
968 TurnPolicy
969 >::apply(source_id2, g2, source_id1, g1,
970 intersection_strategy, robust_policy,
971 turns, interrupt_policy);
972 }
973 };
974
975
976 } // namespace dispatch
977 #endif // DOXYGEN_NO_DISPATCH
978
979
980
981 /*!
982 \brief \brief_calc2{turn points}
983 \ingroup overlay
984 \tparam Geometry1 \tparam_geometry
985 \tparam Geometry2 \tparam_geometry
986 \tparam Turns type of turn-container (e.g. vector of "intersection/turn point"'s)
987 \param geometry1 \param_geometry
988 \param geometry2 \param_geometry
989 \param intersection_strategy segments intersection strategy
990 \param robust_policy policy to handle robustness issues
991 \param turns container which will contain turn points
992 \param interrupt_policy policy determining if process is stopped
993 when intersection is found
994 */
995 template
996 <
997 bool Reverse1, bool Reverse2,
998 typename AssignPolicy,
999 typename Geometry1,
1000 typename Geometry2,
1001 typename IntersectionStrategy,
1002 typename RobustPolicy,
1003 typename Turns,
1004 typename InterruptPolicy
1005 >
get_turns(Geometry1 const & geometry1,Geometry2 const & geometry2,IntersectionStrategy const & intersection_strategy,RobustPolicy const & robust_policy,Turns & turns,InterruptPolicy & interrupt_policy)1006 inline void get_turns(Geometry1 const& geometry1,
1007 Geometry2 const& geometry2,
1008 IntersectionStrategy const& intersection_strategy,
1009 RobustPolicy const& robust_policy,
1010 Turns& turns,
1011 InterruptPolicy& interrupt_policy)
1012 {
1013 concepts::check_concepts_and_equal_dimensions<Geometry1 const, Geometry2 const>();
1014
1015 typedef detail::overlay::get_turn_info<AssignPolicy> TurnPolicy;
1016 //typedef detail::get_turns::get_turn_info_type<Geometry1, Geometry2, AssignPolicy> TurnPolicy;
1017
1018 boost::mpl::if_c
1019 <
1020 reverse_dispatch<Geometry1, Geometry2>::type::value,
1021 dispatch::get_turns_reversed
1022 <
1023 typename tag<Geometry1>::type,
1024 typename tag<Geometry2>::type,
1025 Geometry1, Geometry2,
1026 Reverse1, Reverse2,
1027 TurnPolicy
1028 >,
1029 dispatch::get_turns
1030 <
1031 typename tag<Geometry1>::type,
1032 typename tag<Geometry2>::type,
1033 Geometry1, Geometry2,
1034 Reverse1, Reverse2,
1035 TurnPolicy
1036 >
1037 >::type::apply(0, geometry1,
1038 1, geometry2,
1039 intersection_strategy,
1040 robust_policy,
1041 turns, interrupt_policy);
1042 }
1043
1044 #if defined(_MSC_VER)
1045 #pragma warning(pop)
1046 #endif
1047
1048 }} // namespace boost::geometry
1049
1050 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
1051