1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland.
6 // This file was modified by Oracle on 2014, 2016.
7 // Modifications copyright (c) 2014, 2016 Oracle and/or its affiliates.
9 // Use, modification and distribution is subject to the Boost Software License,
10 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
11 // http://www.boost.org/LICENSE_1_0.txt)
13 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
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/cartesian/cart_intersect.hpp>
49 #include <boost/geometry/strategies/intersection_strategies.hpp>
50 #include <boost/geometry/strategies/intersection_result.hpp>
52 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
53 #include <boost/geometry/algorithms/detail/disjoint/point_point.hpp>
55 #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
56 #include <boost/geometry/algorithms/detail/partition.hpp>
57 #include <boost/geometry/algorithms/detail/recalculate.hpp>
58 #include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp>
60 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
61 #include <boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp>
62 #include <boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp>
63 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
65 #include <boost/geometry/algorithms/detail/sections/range_by_section.hpp>
66 #include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
67 #include <boost/geometry/algorithms/detail/sections/section_functions.hpp>
69 #ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
71 # include <boost/geometry/io/dsv/write.hpp>
75 namespace boost { namespace geometry
78 // Silence warning C4127: conditional expression is constant
81 #pragma warning(disable : 4127)
85 #ifndef DOXYGEN_NO_DETAIL
86 namespace detail { namespace get_turns
90 struct no_interrupt_policy
92 static bool const enabled = false;
94 template <typename Range>
95 static inline bool apply(Range const&)
104 typename Geometry1, typename Geometry2,
105 bool Reverse1, bool Reverse2,
106 typename Section1, typename Section2,
109 class get_turns_in_sections
111 typedef typename closeable_view
113 typename range_type<Geometry1>::type const,
114 closure<Geometry1>::value
116 typedef typename closeable_view
118 typename range_type<Geometry2>::type const,
119 closure<Geometry2>::value
122 typedef typename reversible_view
125 Reverse1 ? iterate_reverse : iterate_forward
127 typedef typename reversible_view
130 Reverse2 ? iterate_reverse : iterate_forward
133 typedef typename boost::range_iterator
136 >::type range1_iterator;
138 typedef typename boost::range_iterator
141 >::type range2_iterator;
144 template <typename Geometry, typename Section>
145 static inline bool neighbouring(Section const& section,
146 signed_size_type index1, signed_size_type index2)
149 // (square: range_count=5, indices 0,1,2,3
150 // -> 0-3 are adjacent, don't check on intersections)
151 // Also tested for open polygons, and/or duplicates
152 // About first condition: will be optimized by compiler (static)
153 // It checks if it is areal (box,ring,(multi)polygon
154 signed_size_type const n = static_cast<signed_size_type>(section.range_count);
156 boost::ignore_unused_variable_warning(n);
157 boost::ignore_unused_variable_warning(index1);
158 boost::ignore_unused_variable_warning(index2);
160 return boost::is_same
164 typename geometry::tag<Geometry>::type,
176 // Returns true if terminated, false if interrupted
177 template <typename Turns, typename RobustPolicy, typename InterruptPolicy>
178 static inline bool apply(
179 int source_id1, Geometry1 const& geometry1, Section1 const& sec1,
180 int source_id2, Geometry2 const& geometry2, Section2 const& sec2,
182 RobustPolicy const& robust_policy,
184 InterruptPolicy& interrupt_policy)
186 boost::ignore_unused_variable_warning(interrupt_policy);
188 if ((sec1.duplicate && (sec1.count + 1) < sec1.range_count)
189 || (sec2.duplicate && (sec2.count + 1) < sec2.range_count))
191 // Skip sections containig only duplicates.
192 // They are still important (can indicate non-disjointness)
193 // but they will be found processing adjacent sections.
194 // Do NOT skip if they are the ONLY section
198 cview_type1 cview1(range_by_section(geometry1, sec1));
199 cview_type2 cview2(range_by_section(geometry2, sec2));
200 view_type1 view1(cview1);
201 view_type2 view2(cview2);
203 range1_iterator begin_range_1 = boost::begin(view1);
204 range1_iterator end_range_1 = boost::end(view1);
206 range2_iterator begin_range_2 = boost::begin(view2);
207 range2_iterator end_range_2 = boost::end(view2);
209 int const dir1 = sec1.directions[0];
210 int const dir2 = sec2.directions[0];
211 signed_size_type index1 = sec1.begin_index;
212 signed_size_type ndi1 = sec1.non_duplicate_index;
214 bool const same_source =
215 source_id1 == source_id2
216 && sec1.ring_id.multi_index == sec2.ring_id.multi_index
217 && sec1.ring_id.ring_index == sec2.ring_id.ring_index;
219 range1_iterator prev1, it1, end1;
221 get_start_point_iterator(sec1, view1, prev1, it1, end1,
222 index1, ndi1, dir1, sec2.bounding_box, robust_policy);
224 // We need a circular iterator because it might run through the closing point.
225 // One circle is actually enough but this one is just convenient.
226 ever_circling_iterator<range1_iterator> next1(begin_range_1, end_range_1, it1, true);
229 // Walk through section and stop if we exceed the other box
230 // section 2: [--------------]
231 // section 1: |----|---|---|---|---|
232 for (prev1 = it1++, next1++;
233 it1 != end1 && ! detail::section::exceeding<0>(dir1, *prev1, sec2.bounding_box, robust_policy);
234 ++prev1, ++it1, ++index1, ++next1, ++ndi1)
236 ever_circling_iterator<range1_iterator> nd_next1(
237 begin_range_1, end_range_1, next1, true);
238 advance_to_non_duplicate_next(nd_next1, it1, sec1, robust_policy);
240 signed_size_type index2 = sec2.begin_index;
241 signed_size_type ndi2 = sec2.non_duplicate_index;
243 range2_iterator prev2, it2, end2;
245 get_start_point_iterator(sec2, view2, prev2, it2, end2,
246 index2, ndi2, dir2, sec1.bounding_box, robust_policy);
247 ever_circling_iterator<range2_iterator> next2(begin_range_2, end_range_2, it2, true);
250 for (prev2 = it2++, next2++;
251 it2 != end2 && ! detail::section::exceeding<0>(dir2, *prev2, sec1.bounding_box, robust_policy);
252 ++prev2, ++it2, ++index2, ++next2, ++ndi2)
254 bool skip = same_source;
257 // If sources are the same (possibly self-intersecting):
258 // skip if it is a neighbouring segment.
259 // (including first-last segment
260 // and two segments with one or more degenerate/duplicate
261 // (zero-length) segments in between)
263 // Also skip if index1 < index2 to avoid getting all
264 // intersections twice (only do this on same source!)
266 skip = (skip_larger && index1 >= index2)
268 || neighbouring<Geometry1>(sec1, index1, index2)
274 // Move to the "non duplicate next"
275 ever_circling_iterator<range2_iterator> nd_next2(
276 begin_range_2, end_range_2, next2, true);
277 advance_to_non_duplicate_next(nd_next2, it2, sec2, robust_policy);
279 typedef typename boost::range_value<Turns>::type turn_info;
282 ti.operations[0].seg_id
283 = segment_identifier(source_id1, sec1.ring_id.multi_index,
284 sec1.ring_id.ring_index, index1);
285 ti.operations[1].seg_id
286 = segment_identifier(source_id2, sec2.ring_id.multi_index,
287 sec2.ring_id.ring_index, index2);
289 std::size_t const size_before = boost::size(turns);
291 bool const is_1_first = sec1.is_non_duplicate_first && index1 == sec1.begin_index;
292 bool const is_1_last = sec1.is_non_duplicate_last && index1+1 >= sec1.end_index;
293 bool const is_2_first = sec2.is_non_duplicate_first && index2 == sec2.begin_index;
294 bool const is_2_last = sec2.is_non_duplicate_last && index2+1 >= sec2.end_index;
296 TurnPolicy::apply(*prev1, *it1, *nd_next1, *prev2, *it2, *nd_next2,
297 is_1_first, is_1_last, is_2_first, is_2_last,
298 ti, robust_policy, std::back_inserter(turns));
300 if (InterruptPolicy::enabled)
302 if (interrupt_policy.apply(
303 std::make_pair(range::pos(turns, size_before),
317 typedef typename geometry::point_type<Geometry1>::type point1_type;
318 typedef typename geometry::point_type<Geometry2>::type point2_type;
319 typedef typename model::referring_segment<point1_type const> segment1_type;
320 typedef typename model::referring_segment<point2_type const> segment2_type;
322 template <typename Iterator, typename RangeIterator, typename Section, typename RobustPolicy>
323 static inline void advance_to_non_duplicate_next(Iterator& next,
324 RangeIterator const& it, Section const& section, RobustPolicy const& robust_policy)
326 typedef typename robust_point_type<point1_type, RobustPolicy>::type robust_point_type;
327 robust_point_type robust_point_from_it;
328 robust_point_type robust_point_from_next;
329 geometry::recalculate(robust_point_from_it, *it, robust_policy);
330 geometry::recalculate(robust_point_from_next, *next, robust_policy);
332 // To see where the next segments bend to, in case of touch/intersections
333 // on end points, we need (in case of degenerate/duplicate points) an extra
334 // iterator which moves to the REAL next point, so non duplicate.
335 // This needs an extra comparison (disjoint).
336 // (Note that within sections, non duplicate points are already asserted,
337 // by the sectionalize process).
339 // So advance to the "non duplicate next"
340 // (the check is defensive, to avoid endless loops)
341 std::size_t check = 0;
342 while(! detail::disjoint::disjoint_point_point
344 robust_point_from_it, robust_point_from_next
346 && check++ < section.range_count)
349 geometry::recalculate(robust_point_from_next, *next, robust_policy);
353 // It is NOT possible to have section-iterators here
354 // because of the logistics of "index" (the section-iterator automatically
355 // skips to the begin-point, we loose the index or have to recalculate it)
356 // So we mimic it here
357 template <typename Range, typename Section, typename Box, typename RobustPolicy>
358 static inline void get_start_point_iterator(Section & section,
360 typename boost::range_iterator<Range const>::type& it,
361 typename boost::range_iterator<Range const>::type& prev,
362 typename boost::range_iterator<Range const>::type& end,
363 signed_size_type& index, signed_size_type& ndi,
364 int dir, Box const& other_bounding_box, RobustPolicy const& robust_policy)
366 it = boost::begin(range) + section.begin_index;
367 end = boost::begin(range) + section.end_index + 1;
369 // Mimic section-iterator:
370 // Skip to point such that section interects other box
372 for(; it != end && detail::section::preceding<0>(dir, *it, other_bounding_box, robust_policy);
373 prev = it++, index++, ndi++)
375 // Go back one step because we want to start completely preceding
382 typename Geometry1, typename Geometry2,
383 bool Reverse1, bool Reverse2,
386 typename RobustPolicy,
387 typename InterruptPolicy
389 struct section_visitor
392 Geometry1 const& m_geometry1;
394 Geometry2 const& m_geometry2;
395 RobustPolicy const& m_rescale_policy;
397 InterruptPolicy& m_interrupt_policy;
399 section_visitor(int id1, Geometry1 const& g1,
400 int id2, Geometry2 const& g2,
401 RobustPolicy const& robust_policy,
402 Turns& turns, InterruptPolicy& ip)
403 : m_source_id1(id1), m_geometry1(g1)
404 , m_source_id2(id2), m_geometry2(g2)
405 , m_rescale_policy(robust_policy)
407 , m_interrupt_policy(ip)
410 template <typename Section>
411 inline bool apply(Section const& sec1, Section const& sec2)
413 if (! detail::disjoint::disjoint_box_box(sec1.bounding_box, sec2.bounding_box))
415 return get_turns_in_sections
423 m_source_id1, m_geometry1, sec1,
424 m_source_id2, m_geometry2, sec2,
427 m_turns, m_interrupt_policy);
436 typename Geometry1, typename Geometry2,
437 bool Reverse1, bool Reverse2,
440 class get_turns_generic
444 template <typename RobustPolicy, typename Turns, typename InterruptPolicy>
445 static inline void apply(
446 int source_id1, Geometry1 const& geometry1,
447 int source_id2, Geometry2 const& geometry2,
448 RobustPolicy const& robust_policy,
450 InterruptPolicy& interrupt_policy)
452 // First create monotonic sections...
453 typedef typename boost::range_value<Turns>::type ip_type;
454 typedef typename ip_type::point_type point_type;
458 typename geometry::robust_point_type
460 point_type, RobustPolicy
463 typedef geometry::sections<box_type, 2> sections_type;
465 sections_type sec1, sec2;
466 typedef boost::mpl::vector_c<std::size_t, 0, 1> dimensions;
468 geometry::sectionalize<Reverse1, dimensions>(geometry1, robust_policy,
470 geometry::sectionalize<Reverse2, dimensions>(geometry2, robust_policy,
473 // ... and then partition them, intersecting overlapping sections in visitor method
476 Geometry1, Geometry2,
478 Turns, TurnPolicy, RobustPolicy, InterruptPolicy
479 > visitor(source_id1, geometry1, source_id2, geometry2, robust_policy, turns, interrupt_policy);
484 detail::section::get_section_box,
485 detail::section::overlaps_section_box
486 >::apply(sec1, sec2, visitor);
491 // Get turns for a range with a box, following Cohen-Sutherland (cs) approach
494 typename Range, typename Box,
495 bool ReverseRange, bool ReverseBox,
500 typedef typename geometry::point_type<Range>::type point_type;
501 typedef typename geometry::point_type<Box>::type box_point_type;
503 typedef typename closeable_view
506 closure<Range>::value
509 typedef typename reversible_view
512 ReverseRange ? iterate_reverse : iterate_forward
515 typedef typename boost::range_iterator
518 >::type iterator_type;
521 template <typename RobustPolicy, typename Turns, typename InterruptPolicy>
522 static inline void apply(
523 int source_id1, Range const& range,
524 int source_id2, Box const& box,
525 RobustPolicy const& robust_policy,
527 InterruptPolicy& interrupt_policy,
528 signed_size_type multi_index = -1,
529 signed_size_type ring_index = -1)
531 if ( boost::size(range) <= 1)
536 boost::array<box_point_type,4> bp;
537 assign_box_corners_oriented<ReverseBox>(box, bp);
539 cview_type cview(range);
540 view_type view(cview);
542 typedef typename boost::range_size<view_type>::type size_type;
543 size_type segments_count1 = boost::size(view) - 1;
545 iterator_type it = boost::begin(view);
547 ever_circling_iterator<iterator_type> next(
548 boost::begin(view), boost::end(view), it, true);
554 //char previous_side[2] = {0, 0};
556 signed_size_type index = 0;
558 for (iterator_type prev = it++;
559 it != boost::end(view);
560 prev = it++, next++, index++)
562 segment_identifier seg_id(source_id1,
563 multi_index, ring_index, index);
567 previous_side[0] = get_side<0>(box, *prev);
568 previous_side[1] = get_side<1>(box, *prev);
571 char current_side[2];
572 current_side[0] = get_side<0>(box, *it);
573 current_side[1] = get_side<1>(box, *it);
575 // There can NOT be intersections if
576 // 1) EITHER the two points are lying on one side of the box (! 0 && the same)
577 // 2) OR same in Y-direction
578 // 3) OR all points are inside the box (0)
580 (current_side[0] != 0 && current_side[0] == previous_side[0])
581 || (current_side[1] != 0 && current_side[1] == previous_side[1])
582 || (current_side[0] == 0
583 && current_side[1] == 0
584 && previous_side[0] == 0
585 && previous_side[1] == 0)
590 get_turns_with_box(seg_id, source_id2,
592 bp[0], bp[1], bp[2], bp[3],
593 // NOTE: some dummy values could be passed below since this would be called only for Polygons and Boxes
595 size_type(index) == segments_count1,
597 turns, interrupt_policy);
598 // Future performance enhancement:
599 // return if told by the interrupt policy
605 template<std::size_t Index, typename Point>
606 static inline int get_side(Box const& box, Point const& point)
609 // Outside -> -1 (left/below) or 1 (right/above)
610 // On border -> -2 (left/lower) or 2 (right/upper)
611 // The only purpose of the value is to not be the same,
612 // and to denote if it is inside (0)
614 typename coordinate_type<Point>::type const& c = get<Index>(point);
615 typename coordinate_type<Box>::type const& left = get<min_corner, Index>(box);
616 typename coordinate_type<Box>::type const& right = get<max_corner, Index>(box);
618 if (geometry::math::equals(c, left)) return -2;
619 else if (geometry::math::equals(c, right)) return 2;
620 else if (c < left) return -1;
621 else if (c > right) return 1;
625 template <typename RobustPolicy, typename Turns, typename InterruptPolicy>
626 static inline void get_turns_with_box(segment_identifier const& seg_id, int source_id2,
627 // Points from a range:
628 point_type const& rp0,
629 point_type const& rp1,
630 point_type const& rp2,
631 // Points from the box
632 box_point_type const& bp0,
633 box_point_type const& bp1,
634 box_point_type const& bp2,
635 box_point_type const& bp3,
636 bool const is_range_first,
637 bool const is_range_last,
638 RobustPolicy const& robust_policy,
641 InterruptPolicy& interrupt_policy)
643 boost::ignore_unused_variable_warning(interrupt_policy);
645 // Depending on code some relations can be left out
647 typedef typename boost::range_value<Turns>::type turn_info;
650 ti.operations[0].seg_id = seg_id;
652 ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 0);
653 TurnPolicy::apply(rp0, rp1, rp2, bp0, bp1, bp2,
654 is_range_first, is_range_last,
656 ti, robust_policy, std::back_inserter(turns));
658 ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 1);
659 TurnPolicy::apply(rp0, rp1, rp2, bp1, bp2, bp3,
660 is_range_first, is_range_last,
662 ti, robust_policy, std::back_inserter(turns));
664 ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 2);
665 TurnPolicy::apply(rp0, rp1, rp2, bp2, bp3, bp0,
666 is_range_first, is_range_last,
668 ti, robust_policy, std::back_inserter(turns));
670 ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 3);
671 TurnPolicy::apply(rp0, rp1, rp2, bp3, bp0, bp1,
672 is_range_first, is_range_last,
674 ti, robust_policy, std::back_inserter(turns));
676 if (InterruptPolicy::enabled)
678 interrupt_policy.apply(turns);
688 typename Polygon, typename Box,
689 bool Reverse, bool ReverseBox,
692 struct get_turns_polygon_cs
694 template <typename RobustPolicy, typename Turns, typename InterruptPolicy>
695 static inline void apply(
696 int source_id1, Polygon const& polygon,
697 int source_id2, Box const& box,
698 RobustPolicy const& robust_policy,
699 Turns& turns, InterruptPolicy& interrupt_policy,
700 signed_size_type multi_index = -1)
702 typedef typename geometry::ring_type<Polygon>::type ring_type;
704 typedef detail::get_turns::get_turns_cs
711 intersector_type::apply(
712 source_id1, geometry::exterior_ring(polygon),
715 turns, interrupt_policy,
718 signed_size_type i = 0;
720 typename interior_return_type<Polygon const>::type
721 rings = interior_rings(polygon);
722 for (typename detail::interior_iterator<Polygon const>::type
723 it = boost::begin(rings); it != boost::end(rings); ++it, ++i)
725 intersector_type::apply(
729 turns, interrupt_policy,
739 typename Multi, typename Box,
740 bool Reverse, bool ReverseBox,
743 struct get_turns_multi_polygon_cs
745 template <typename RobustPolicy, typename Turns, typename InterruptPolicy>
746 static inline void apply(
747 int source_id1, Multi const& multi,
748 int source_id2, Box const& box,
749 RobustPolicy const& robust_policy,
750 Turns& turns, InterruptPolicy& interrupt_policy)
752 typedef typename boost::range_iterator
755 >::type iterator_type;
757 signed_size_type i = 0;
758 for (iterator_type it = boost::begin(multi);
759 it != boost::end(multi);
762 // Call its single version
765 typename boost::range_value<Multi>::type, Box,
768 >::apply(source_id1, *it, source_id2, box,
769 robust_policy, turns, interrupt_policy, i);
775 // GET_TURN_INFO_TYPE
777 template <typename Geometry>
778 struct topological_tag_base
780 typedef typename tag_cast<typename tag<Geometry>::type, pointlike_tag, linear_tag, areal_tag>::type type;
783 template <typename Geometry1, typename Geometry2, typename AssignPolicy,
784 typename Tag1 = typename tag<Geometry1>::type, typename Tag2 = typename tag<Geometry2>::type,
785 typename TagBase1 = typename topological_tag_base<Geometry1>::type, typename TagBase2 = typename topological_tag_base<Geometry2>::type>
786 struct get_turn_info_type
787 : overlay::get_turn_info<AssignPolicy>
790 template <typename Geometry1, typename Geometry2, typename AssignPolicy, typename Tag1, typename Tag2>
791 struct get_turn_info_type<Geometry1, Geometry2, AssignPolicy, Tag1, Tag2, linear_tag, linear_tag>
792 : overlay::get_turn_info_linear_linear<AssignPolicy>
795 template <typename Geometry1, typename Geometry2, typename AssignPolicy, typename Tag1, typename Tag2>
796 struct get_turn_info_type<Geometry1, Geometry2, AssignPolicy, Tag1, Tag2, linear_tag, areal_tag>
797 : overlay::get_turn_info_linear_areal<AssignPolicy>
800 template <typename Geometry1, typename Geometry2, typename SegmentRatio,
801 typename Tag1 = typename tag<Geometry1>::type, typename Tag2 = typename tag<Geometry2>::type,
802 typename TagBase1 = typename topological_tag_base<Geometry1>::type, typename TagBase2 = typename topological_tag_base<Geometry2>::type>
803 struct turn_operation_type
805 typedef overlay::turn_operation<typename point_type<Geometry1>::type, SegmentRatio> type;
808 template <typename Geometry1, typename Geometry2, typename SegmentRatio, typename Tag1, typename Tag2>
809 struct turn_operation_type<Geometry1, Geometry2, SegmentRatio, Tag1, Tag2, linear_tag, linear_tag>
811 typedef overlay::turn_operation_linear<typename point_type<Geometry1>::type, SegmentRatio> type;
814 template <typename Geometry1, typename Geometry2, typename SegmentRatio, typename Tag1, typename Tag2>
815 struct turn_operation_type<Geometry1, Geometry2, SegmentRatio, Tag1, Tag2, linear_tag, areal_tag>
817 typedef overlay::turn_operation_linear<typename point_type<Geometry1>::type, SegmentRatio> type;
820 }} // namespace detail::get_turns
821 #endif // DOXYGEN_NO_DETAIL
824 #ifndef DOXYGEN_NO_DISPATCH
828 // Because this is "detail" method, and most implementations will use "generic",
829 // we take the freedom to derive it from "generic".
832 typename GeometryTag1, typename GeometryTag2,
833 typename Geometry1, typename Geometry2,
834 bool Reverse1, bool Reverse2,
838 : detail::get_turns::get_turns_generic
840 Geometry1, Geometry2,
849 typename Polygon, typename Box,
850 bool ReversePolygon, bool ReverseBox,
855 polygon_tag, box_tag,
857 ReversePolygon, ReverseBox,
859 > : detail::get_turns::get_turns_polygon_cs
862 ReversePolygon, ReverseBox,
870 typename Ring, typename Box,
871 bool ReverseRing, bool ReverseBox,
878 ReverseRing, ReverseBox,
880 > : detail::get_turns::get_turns_cs
882 Ring, Box, ReverseRing, ReverseBox,
891 typename MultiPolygon,
893 bool ReverseMultiPolygon, bool ReverseBox,
898 multi_polygon_tag, box_tag,
900 ReverseMultiPolygon, ReverseBox,
903 : detail::get_turns::get_turns_multi_polygon_cs
906 ReverseMultiPolygon, ReverseBox,
914 typename GeometryTag1, typename GeometryTag2,
915 typename Geometry1, typename Geometry2,
916 bool Reverse1, bool Reverse2,
919 struct get_turns_reversed
921 template <typename RobustPolicy, typename Turns, typename InterruptPolicy>
922 static inline void apply(
923 int source_id1, Geometry1 const& g1,
924 int source_id2, Geometry2 const& g2,
925 RobustPolicy const& robust_policy,
927 InterruptPolicy& interrupt_policy)
931 GeometryTag2, GeometryTag1,
932 Geometry2, Geometry1,
935 >::apply(source_id2, g2, source_id1, g1, robust_policy,
936 turns, interrupt_policy);
941 } // namespace dispatch
942 #endif // DOXYGEN_NO_DISPATCH
947 \brief \brief_calc2{turn points}
949 \tparam Geometry1 \tparam_geometry
950 \tparam Geometry2 \tparam_geometry
951 \tparam Turns type of turn-container (e.g. vector of "intersection/turn point"'s)
952 \param geometry1 \param_geometry
953 \param geometry2 \param_geometry
954 \param robust_policy policy to handle robustness issues
955 \param turns container which will contain turn points
956 \param interrupt_policy policy determining if process is stopped
957 when intersection is found
961 bool Reverse1, bool Reverse2,
962 typename AssignPolicy,
965 typename RobustPolicy,
967 typename InterruptPolicy
969 inline void get_turns(Geometry1 const& geometry1,
970 Geometry2 const& geometry2,
971 RobustPolicy const& robust_policy,
973 InterruptPolicy& interrupt_policy)
975 concepts::check_concepts_and_equal_dimensions<Geometry1 const, Geometry2 const>();
977 typedef detail::overlay::get_turn_info<AssignPolicy> TurnPolicy;
978 //typedef detail::get_turns::get_turn_info_type<Geometry1, Geometry2, AssignPolicy> TurnPolicy;
982 reverse_dispatch<Geometry1, Geometry2>::type::value,
983 dispatch::get_turns_reversed
985 typename tag<Geometry1>::type,
986 typename tag<Geometry2>::type,
987 Geometry1, Geometry2,
993 typename tag<Geometry1>::type,
994 typename tag<Geometry2>::type,
995 Geometry1, Geometry2,
1003 turns, interrupt_policy);
1006 #if defined(_MSC_VER)
1007 #pragma warning(pop)
1010 }} // namespace boost::geometry
1012 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP