1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2014-2017 Adam Wulkiewicz, Lodz, Poland.
6 // This file was modified by Oracle on 2014, 2016, 2017.
7 // Modifications copyright (c) 2014-2017 Oracle and/or its affiliates.
9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
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)
15 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
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>
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>
36 #include <boost/geometry/geometries/concepts/check.hpp>
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>
43 #include <boost/geometry/geometries/box.hpp>
44 #include <boost/geometry/geometries/segment.hpp>
46 #include <boost/geometry/iterators/ever_circling_iterator.hpp>
48 #include <boost/geometry/strategies/intersection_strategies.hpp>
49 #include <boost/geometry/strategies/intersection_result.hpp>
51 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
52 #include <boost/geometry/algorithms/detail/disjoint/point_point.hpp>
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>
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>
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>
68 #ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
70 # include <boost/geometry/io/dsv/write.hpp>
74 namespace boost { namespace geometry
77 // Silence warning C4127: conditional expression is constant
80 #pragma warning(disable : 4127)
84 #ifndef DOXYGEN_NO_DETAIL
85 namespace detail { namespace get_turns
89 struct no_interrupt_policy
91 static bool const enabled = false;
93 // variable required by self_get_turn_points::get_turns
94 static bool const has_intersections = false;
96 template <typename Range>
97 static inline bool apply(Range const&)
106 typename Geometry1, typename Geometry2,
107 bool Reverse1, bool Reverse2,
108 typename Section1, typename Section2,
111 class get_turns_in_sections
113 typedef typename closeable_view
115 typename range_type<Geometry1>::type const,
116 closure<Geometry1>::value
118 typedef typename closeable_view
120 typename range_type<Geometry2>::type const,
121 closure<Geometry2>::value
124 typedef typename reversible_view
127 Reverse1 ? iterate_reverse : iterate_forward
129 typedef typename reversible_view
132 Reverse2 ? iterate_reverse : iterate_forward
135 typedef typename boost::range_iterator
138 >::type range1_iterator;
140 typedef typename boost::range_iterator
143 >::type range2_iterator;
146 template <typename Geometry, typename Section>
147 static inline bool adjacent(Section const& section,
148 signed_size_type index1, signed_size_type index2)
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);
158 boost::ignore_unused_variable_warning(n);
159 boost::ignore_unused_variable_warning(index1);
160 boost::ignore_unused_variable_warning(index2);
162 return boost::is_same
166 typename geometry::tag<Geometry>::type,
178 // Returns true if terminated, false if interrupted
179 template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
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, bool skip_adjacent,
184 IntersectionStrategy const& intersection_strategy,
185 RobustPolicy const& robust_policy,
187 InterruptPolicy& interrupt_policy)
189 boost::ignore_unused_variable_warning(interrupt_policy);
191 if ((sec1.duplicate && (sec1.count + 1) < sec1.range_count)
192 || (sec2.duplicate && (sec2.count + 1) < sec2.range_count))
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
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);
206 range1_iterator begin_range_1 = boost::begin(view1);
207 range1_iterator end_range_1 = boost::end(view1);
209 range2_iterator begin_range_2 = boost::begin(view2);
210 range2_iterator end_range_2 = boost::end(view2);
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;
217 range1_iterator prev1, it1, end1;
219 get_start_point_iterator(sec1, view1, prev1, it1, end1,
220 index1, ndi1, dir1, sec2.bounding_box, robust_policy);
222 // We need a circular iterator because it might run through the closing point.
223 // One circle is actually enough but this one is just convenient.
224 ever_circling_iterator<range1_iterator> next1(begin_range_1, end_range_1, it1, true);
227 // Walk through section and stop if we exceed the other box
228 // section 2: [--------------]
229 // section 1: |----|---|---|---|---|
230 for (prev1 = it1++, next1++;
231 it1 != end1 && ! detail::section::exceeding<0>(dir1, *prev1, sec1.bounding_box, sec2.bounding_box, robust_policy);
232 ++prev1, ++it1, ++index1, ++next1, ++ndi1)
234 ever_circling_iterator<range1_iterator> nd_next1(
235 begin_range_1, end_range_1, next1, true);
236 advance_to_non_duplicate_next(nd_next1, it1, sec1, robust_policy);
238 signed_size_type index2 = sec2.begin_index;
239 signed_size_type ndi2 = sec2.non_duplicate_index;
241 range2_iterator prev2, it2, end2;
243 get_start_point_iterator(sec2, view2, prev2, it2, end2,
244 index2, ndi2, dir2, sec1.bounding_box, robust_policy);
245 ever_circling_iterator<range2_iterator> next2(begin_range_2, end_range_2, it2, true);
248 for (prev2 = it2++, next2++;
249 it2 != end2 && ! detail::section::exceeding<0>(dir2, *prev2, sec2.bounding_box, sec1.bounding_box, robust_policy);
250 ++prev2, ++it2, ++index2, ++next2, ++ndi2)
254 if (source_id1 == source_id2
255 && sec1.ring_id.multi_index == sec2.ring_id.multi_index
256 && sec1.ring_id.ring_index == sec2.ring_id.ring_index)
258 // Sources and rings are the same
260 if (skip_larger && index1 >= index2)
262 // Skip to avoid getting all intersections twice
265 else if (skip_adjacent)
267 // In some cases (dissolve, has_self_intersections)
268 // neighbouring segments should be checked
269 // (for example to detect spikes properly)
271 // skip if it is a neighbouring segment.
272 // (including, for areas, first-last segment
273 // and two segments with one or more degenerate/duplicate
274 // (zero-length) segments in between)
275 skip = ndi2 == ndi1 + 1
276 || adjacent<Geometry1>(sec1, index1, index2);
282 // Move to the "non duplicate next"
283 ever_circling_iterator<range2_iterator> nd_next2(
284 begin_range_2, end_range_2, next2, true);
285 advance_to_non_duplicate_next(nd_next2, it2, sec2, robust_policy);
287 typedef typename boost::range_value<Turns>::type turn_info;
290 ti.operations[0].seg_id
291 = segment_identifier(source_id1, sec1.ring_id.multi_index,
292 sec1.ring_id.ring_index, index1);
293 ti.operations[1].seg_id
294 = segment_identifier(source_id2, sec2.ring_id.multi_index,
295 sec2.ring_id.ring_index, index2);
297 std::size_t const size_before = boost::size(turns);
299 bool const is_1_first = sec1.is_non_duplicate_first && index1 == sec1.begin_index;
300 bool const is_1_last = sec1.is_non_duplicate_last && index1+1 >= sec1.end_index;
301 bool const is_2_first = sec2.is_non_duplicate_first && index2 == sec2.begin_index;
302 bool const is_2_last = sec2.is_non_duplicate_last && index2+1 >= sec2.end_index;
304 TurnPolicy::apply(*prev1, *it1, *nd_next1, *prev2, *it2, *nd_next2,
305 is_1_first, is_1_last, is_2_first, is_2_last,
306 ti, intersection_strategy, robust_policy,
307 std::back_inserter(turns));
309 if (InterruptPolicy::enabled)
311 if (interrupt_policy.apply(
312 std::make_pair(range::pos(turns, size_before),
326 typedef typename geometry::point_type<Geometry1>::type point1_type;
327 typedef typename geometry::point_type<Geometry2>::type point2_type;
328 typedef typename model::referring_segment<point1_type const> segment1_type;
329 typedef typename model::referring_segment<point2_type const> segment2_type;
331 template <typename Iterator, typename RangeIterator, typename Section, typename RobustPolicy>
332 static inline void advance_to_non_duplicate_next(Iterator& next,
333 RangeIterator const& it, Section const& section, RobustPolicy const& robust_policy)
335 typedef typename robust_point_type<point1_type, RobustPolicy>::type robust_point_type;
336 robust_point_type robust_point_from_it;
337 robust_point_type robust_point_from_next;
338 geometry::recalculate(robust_point_from_it, *it, robust_policy);
339 geometry::recalculate(robust_point_from_next, *next, robust_policy);
341 // To see where the next segments bend to, in case of touch/intersections
342 // on end points, we need (in case of degenerate/duplicate points) an extra
343 // iterator which moves to the REAL next point, so non duplicate.
344 // This needs an extra comparison (disjoint).
345 // (Note that within sections, non duplicate points are already asserted,
346 // by the sectionalize process).
348 // So advance to the "non duplicate next"
349 // (the check is defensive, to avoid endless loops)
350 std::size_t check = 0;
351 while(! detail::disjoint::disjoint_point_point
353 robust_point_from_it, robust_point_from_next
355 && check++ < section.range_count)
358 geometry::recalculate(robust_point_from_next, *next, robust_policy);
362 // It is NOT possible to have section-iterators here
363 // because of the logistics of "index" (the section-iterator automatically
364 // skips to the begin-point, we loose the index or have to recalculate it)
365 // So we mimic it here
366 template <typename Range, typename Section, typename Box, typename RobustPolicy>
367 static inline void get_start_point_iterator(Section const& section,
369 typename boost::range_iterator<Range const>::type& it,
370 typename boost::range_iterator<Range const>::type& prev,
371 typename boost::range_iterator<Range const>::type& end,
372 signed_size_type& index, signed_size_type& ndi,
373 int dir, Box const& other_bounding_box, RobustPolicy const& robust_policy)
375 it = boost::begin(range) + section.begin_index;
376 end = boost::begin(range) + section.end_index + 1;
378 // Mimic section-iterator:
379 // Skip to point such that section interects other box
381 for(; it != end && detail::section::preceding<0>(dir, *it, section.bounding_box, other_bounding_box, robust_policy);
382 prev = it++, index++, ndi++)
384 // Go back one step because we want to start completely preceding
391 typename Geometry1, typename Geometry2,
392 bool Reverse1, bool Reverse2,
394 typename IntersectionStrategy,
395 typename RobustPolicy,
397 typename InterruptPolicy
399 struct section_visitor
402 Geometry1 const& m_geometry1;
404 Geometry2 const& m_geometry2;
405 IntersectionStrategy const& m_intersection_strategy;
406 RobustPolicy const& m_rescale_policy;
408 InterruptPolicy& m_interrupt_policy;
410 section_visitor(int id1, Geometry1 const& g1,
411 int id2, Geometry2 const& g2,
412 IntersectionStrategy const& intersection_strategy,
413 RobustPolicy const& robust_policy,
416 : m_source_id1(id1), m_geometry1(g1)
417 , m_source_id2(id2), m_geometry2(g2)
418 , m_intersection_strategy(intersection_strategy)
419 , m_rescale_policy(robust_policy)
421 , m_interrupt_policy(ip)
424 template <typename Section>
425 inline bool apply(Section const& sec1, Section const& sec2)
427 if (! detail::disjoint::disjoint_box_box(sec1.bounding_box, sec2.bounding_box))
429 // false if interrupted
430 return get_turns_in_sections
437 >::apply(m_source_id1, m_geometry1, sec1,
438 m_source_id2, m_geometry2, sec2,
440 m_intersection_strategy,
442 m_turns, m_interrupt_policy);
451 typename Geometry1, typename Geometry2,
452 bool Reverse1, bool Reverse2,
455 class get_turns_generic
459 template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
460 static inline void apply(
461 int source_id1, Geometry1 const& geometry1,
462 int source_id2, Geometry2 const& geometry2,
463 IntersectionStrategy const& intersection_strategy,
464 RobustPolicy const& robust_policy,
466 InterruptPolicy& interrupt_policy)
468 // First create monotonic sections...
469 typedef typename boost::range_value<Turns>::type ip_type;
470 typedef typename ip_type::point_type point_type;
474 typename geometry::robust_point_type
476 point_type, RobustPolicy
479 typedef geometry::sections<box_type, 2> sections_type;
481 sections_type sec1, sec2;
482 typedef boost::mpl::vector_c<std::size_t, 0, 1> dimensions;
484 typename IntersectionStrategy::envelope_strategy_type const
485 envelope_strategy = intersection_strategy.get_envelope_strategy();
487 geometry::sectionalize<Reverse1, dimensions>(geometry1, robust_policy,
488 sec1, envelope_strategy, 0);
489 geometry::sectionalize<Reverse2, dimensions>(geometry2, robust_policy,
490 sec2, envelope_strategy, 1);
492 // ... and then partition them, intersecting overlapping sections in visitor method
495 Geometry1, Geometry2,
498 IntersectionStrategy, RobustPolicy,
499 Turns, InterruptPolicy
500 > visitor(source_id1, geometry1, source_id2, geometry2,
501 intersection_strategy, robust_policy,
502 turns, interrupt_policy);
507 >::apply(sec1, sec2, visitor,
508 detail::section::get_section_box(),
509 detail::section::overlaps_section_box());
514 // Get turns for a range with a box, following Cohen-Sutherland (cs) approach
517 typename Range, typename Box,
518 bool ReverseRange, bool ReverseBox,
523 typedef typename geometry::point_type<Range>::type point_type;
524 typedef typename geometry::point_type<Box>::type box_point_type;
526 typedef typename closeable_view
529 closure<Range>::value
532 typedef typename reversible_view
535 ReverseRange ? iterate_reverse : iterate_forward
538 typedef typename boost::range_iterator
541 >::type iterator_type;
544 template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
545 static inline void apply(
546 int source_id1, Range const& range,
547 int source_id2, Box const& box,
548 IntersectionStrategy const& intersection_strategy,
549 RobustPolicy const& robust_policy,
551 InterruptPolicy& interrupt_policy,
552 signed_size_type multi_index = -1,
553 signed_size_type ring_index = -1)
555 if ( boost::size(range) <= 1)
560 boost::array<box_point_type,4> bp;
561 assign_box_corners_oriented<ReverseBox>(box, bp);
563 cview_type cview(range);
564 view_type view(cview);
566 typedef typename boost::range_size<view_type>::type size_type;
567 size_type segments_count1 = boost::size(view) - 1;
569 iterator_type it = boost::begin(view);
571 ever_circling_iterator<iterator_type> next(
572 boost::begin(view), boost::end(view), it, true);
578 //char previous_side[2] = {0, 0};
580 signed_size_type index = 0;
582 for (iterator_type prev = it++;
583 it != boost::end(view);
584 prev = it++, next++, index++)
586 segment_identifier seg_id(source_id1,
587 multi_index, ring_index, index);
591 previous_side[0] = get_side<0>(box, *prev);
592 previous_side[1] = get_side<1>(box, *prev);
595 char current_side[2];
596 current_side[0] = get_side<0>(box, *it);
597 current_side[1] = get_side<1>(box, *it);
599 // There can NOT be intersections if
600 // 1) EITHER the two points are lying on one side of the box (! 0 && the same)
601 // 2) OR same in Y-direction
602 // 3) OR all points are inside the box (0)
604 (current_side[0] != 0 && current_side[0] == previous_side[0])
605 || (current_side[1] != 0 && current_side[1] == previous_side[1])
606 || (current_side[0] == 0
607 && current_side[1] == 0
608 && previous_side[0] == 0
609 && previous_side[1] == 0)
614 get_turns_with_box(seg_id, source_id2,
616 bp[0], bp[1], bp[2], bp[3],
617 // NOTE: some dummy values could be passed below since this would be called only for Polygons and Boxes
619 size_type(index) == segments_count1,
620 intersection_strategy,
624 // Future performance enhancement:
625 // return if told by the interrupt policy
631 template<std::size_t Index, typename Point>
632 static inline int get_side(Box const& box, Point const& point)
635 // Outside -> -1 (left/below) or 1 (right/above)
636 // On border -> -2 (left/lower) or 2 (right/upper)
637 // The only purpose of the value is to not be the same,
638 // and to denote if it is inside (0)
640 typename coordinate_type<Point>::type const& c = get<Index>(point);
641 typename coordinate_type<Box>::type const& left = get<min_corner, Index>(box);
642 typename coordinate_type<Box>::type const& right = get<max_corner, Index>(box);
644 if (geometry::math::equals(c, left)) return -2;
645 else if (geometry::math::equals(c, right)) return 2;
646 else if (c < left) return -1;
647 else if (c > right) return 1;
651 template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
652 static inline void get_turns_with_box(segment_identifier const& seg_id, int source_id2,
653 // Points from a range:
654 point_type const& rp0,
655 point_type const& rp1,
656 point_type const& rp2,
657 // Points from the box
658 box_point_type const& bp0,
659 box_point_type const& bp1,
660 box_point_type const& bp2,
661 box_point_type const& bp3,
662 bool const is_range_first,
663 bool const is_range_last,
664 IntersectionStrategy const& intersection_strategy,
665 RobustPolicy const& robust_policy,
668 InterruptPolicy& interrupt_policy)
670 boost::ignore_unused_variable_warning(interrupt_policy);
672 // Depending on code some relations can be left out
674 typedef typename boost::range_value<Turns>::type turn_info;
677 ti.operations[0].seg_id = seg_id;
679 ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 0);
680 TurnPolicy::apply(rp0, rp1, rp2, bp0, bp1, bp2,
681 is_range_first, is_range_last,
683 ti, intersection_strategy, robust_policy,
684 std::back_inserter(turns));
686 ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 1);
687 TurnPolicy::apply(rp0, rp1, rp2, bp1, bp2, bp3,
688 is_range_first, is_range_last,
690 ti, intersection_strategy, robust_policy,
691 std::back_inserter(turns));
693 ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 2);
694 TurnPolicy::apply(rp0, rp1, rp2, bp2, bp3, bp0,
695 is_range_first, is_range_last,
697 ti, intersection_strategy, robust_policy,
698 std::back_inserter(turns));
700 ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 3);
701 TurnPolicy::apply(rp0, rp1, rp2, bp3, bp0, bp1,
702 is_range_first, is_range_last,
704 ti, intersection_strategy, robust_policy,
705 std::back_inserter(turns));
707 if (InterruptPolicy::enabled)
709 interrupt_policy.apply(turns);
719 typename Polygon, typename Box,
720 bool Reverse, bool ReverseBox,
723 struct get_turns_polygon_cs
725 template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
726 static inline void apply(
727 int source_id1, Polygon const& polygon,
728 int source_id2, Box const& box,
729 IntersectionStrategy const& intersection_strategy,
730 RobustPolicy const& robust_policy,
732 InterruptPolicy& interrupt_policy,
733 signed_size_type multi_index = -1)
735 typedef typename geometry::ring_type<Polygon>::type ring_type;
737 typedef detail::get_turns::get_turns_cs
744 intersector_type::apply(
745 source_id1, geometry::exterior_ring(polygon),
747 intersection_strategy,
753 signed_size_type i = 0;
755 typename interior_return_type<Polygon const>::type
756 rings = interior_rings(polygon);
757 for (typename detail::interior_iterator<Polygon const>::type
758 it = boost::begin(rings); it != boost::end(rings); ++it, ++i)
760 intersector_type::apply(
763 intersection_strategy,
765 turns, interrupt_policy,
775 typename Multi, typename Box,
776 bool Reverse, bool ReverseBox,
779 struct get_turns_multi_polygon_cs
781 template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
782 static inline void apply(
783 int source_id1, Multi const& multi,
784 int source_id2, Box const& box,
785 IntersectionStrategy const& intersection_strategy,
786 RobustPolicy const& robust_policy,
788 InterruptPolicy& interrupt_policy)
790 typedef typename boost::range_iterator
793 >::type iterator_type;
795 signed_size_type i = 0;
796 for (iterator_type it = boost::begin(multi);
797 it != boost::end(multi);
800 // Call its single version
803 typename boost::range_value<Multi>::type, Box,
806 >::apply(source_id1, *it, source_id2, box,
807 intersection_strategy, robust_policy,
808 turns, interrupt_policy, i);
814 // GET_TURN_INFO_TYPE
816 template <typename Geometry>
817 struct topological_tag_base
819 typedef typename tag_cast<typename tag<Geometry>::type, pointlike_tag, linear_tag, areal_tag>::type type;
822 template <typename Geometry1, typename Geometry2, typename AssignPolicy,
823 typename Tag1 = typename tag<Geometry1>::type, typename Tag2 = typename tag<Geometry2>::type,
824 typename TagBase1 = typename topological_tag_base<Geometry1>::type, typename TagBase2 = typename topological_tag_base<Geometry2>::type>
825 struct get_turn_info_type
826 : overlay::get_turn_info<AssignPolicy>
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, linear_tag>
831 : overlay::get_turn_info_linear_linear<AssignPolicy>
834 template <typename Geometry1, typename Geometry2, typename AssignPolicy, typename Tag1, typename Tag2>
835 struct get_turn_info_type<Geometry1, Geometry2, AssignPolicy, Tag1, Tag2, linear_tag, areal_tag>
836 : overlay::get_turn_info_linear_areal<AssignPolicy>
839 template <typename Geometry1, typename Geometry2, typename SegmentRatio,
840 typename Tag1 = typename tag<Geometry1>::type, typename Tag2 = typename tag<Geometry2>::type,
841 typename TagBase1 = typename topological_tag_base<Geometry1>::type, typename TagBase2 = typename topological_tag_base<Geometry2>::type>
842 struct turn_operation_type
844 typedef overlay::turn_operation<typename point_type<Geometry1>::type, SegmentRatio> type;
847 template <typename Geometry1, typename Geometry2, typename SegmentRatio, typename Tag1, typename Tag2>
848 struct turn_operation_type<Geometry1, Geometry2, SegmentRatio, Tag1, Tag2, linear_tag, linear_tag>
850 typedef overlay::turn_operation_linear<typename point_type<Geometry1>::type, SegmentRatio> type;
853 template <typename Geometry1, typename Geometry2, typename SegmentRatio, typename Tag1, typename Tag2>
854 struct turn_operation_type<Geometry1, Geometry2, SegmentRatio, Tag1, Tag2, linear_tag, areal_tag>
856 typedef overlay::turn_operation_linear<typename point_type<Geometry1>::type, SegmentRatio> type;
859 }} // namespace detail::get_turns
860 #endif // DOXYGEN_NO_DETAIL
863 #ifndef DOXYGEN_NO_DISPATCH
867 // Because this is "detail" method, and most implementations will use "generic",
868 // we take the freedom to derive it from "generic".
871 typename GeometryTag1, typename GeometryTag2,
872 typename Geometry1, typename Geometry2,
873 bool Reverse1, bool Reverse2,
877 : detail::get_turns::get_turns_generic
879 Geometry1, Geometry2,
888 typename Polygon, typename Box,
889 bool ReversePolygon, bool ReverseBox,
894 polygon_tag, box_tag,
896 ReversePolygon, ReverseBox,
898 > : detail::get_turns::get_turns_polygon_cs
901 ReversePolygon, ReverseBox,
909 typename Ring, typename Box,
910 bool ReverseRing, bool ReverseBox,
917 ReverseRing, ReverseBox,
919 > : detail::get_turns::get_turns_cs
921 Ring, Box, ReverseRing, ReverseBox,
930 typename MultiPolygon,
932 bool ReverseMultiPolygon, bool ReverseBox,
937 multi_polygon_tag, box_tag,
939 ReverseMultiPolygon, ReverseBox,
942 : detail::get_turns::get_turns_multi_polygon_cs
945 ReverseMultiPolygon, ReverseBox,
953 typename GeometryTag1, typename GeometryTag2,
954 typename Geometry1, typename Geometry2,
955 bool Reverse1, bool Reverse2,
958 struct get_turns_reversed
960 template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
961 static inline void apply(int source_id1, Geometry1 const& g1,
962 int source_id2, Geometry2 const& g2,
963 IntersectionStrategy const& intersection_strategy,
964 RobustPolicy const& robust_policy,
966 InterruptPolicy& interrupt_policy)
970 GeometryTag2, GeometryTag1,
971 Geometry2, Geometry1,
974 >::apply(source_id2, g2, source_id1, g1,
975 intersection_strategy, robust_policy,
976 turns, interrupt_policy);
981 } // namespace dispatch
982 #endif // DOXYGEN_NO_DISPATCH
987 \brief \brief_calc2{turn points}
989 \tparam Geometry1 \tparam_geometry
990 \tparam Geometry2 \tparam_geometry
991 \tparam Turns type of turn-container (e.g. vector of "intersection/turn point"'s)
992 \param geometry1 \param_geometry
993 \param geometry2 \param_geometry
994 \param intersection_strategy segments intersection strategy
995 \param robust_policy policy to handle robustness issues
996 \param turns container which will contain turn points
997 \param interrupt_policy policy determining if process is stopped
998 when intersection is found
1002 bool Reverse1, bool Reverse2,
1003 typename AssignPolicy,
1006 typename IntersectionStrategy,
1007 typename RobustPolicy,
1009 typename InterruptPolicy
1011 inline void get_turns(Geometry1 const& geometry1,
1012 Geometry2 const& geometry2,
1013 IntersectionStrategy const& intersection_strategy,
1014 RobustPolicy const& robust_policy,
1016 InterruptPolicy& interrupt_policy)
1018 concepts::check_concepts_and_equal_dimensions<Geometry1 const, Geometry2 const>();
1020 typedef detail::overlay::get_turn_info<AssignPolicy> TurnPolicy;
1021 //typedef detail::get_turns::get_turn_info_type<Geometry1, Geometry2, AssignPolicy> TurnPolicy;
1025 reverse_dispatch<Geometry1, Geometry2>::type::value,
1026 dispatch::get_turns_reversed
1028 typename tag<Geometry1>::type,
1029 typename tag<Geometry2>::type,
1030 Geometry1, Geometry2,
1036 typename tag<Geometry1>::type,
1037 typename tag<Geometry2>::type,
1038 Geometry1, Geometry2,
1042 >::type::apply(0, geometry1,
1044 intersection_strategy,
1046 turns, interrupt_policy);
1049 #if defined(_MSC_VER)
1050 #pragma warning(pop)
1053 }} // namespace boost::geometry
1055 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP