1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
6 // This file was modified by Oracle on 2015, 2017, 2018, 2019.
7 // Modifications copyright (c) 2015-2019 Oracle and/or its affiliates.
9 // Contributed and/or modified by 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_TURN_INFO_HPP
16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HPP
19 #include <boost/core/ignore_unused.hpp>
20 #include <boost/throw_exception.hpp>
22 #include <boost/geometry/core/access.hpp>
23 #include <boost/geometry/core/assert.hpp>
24 #include <boost/geometry/core/config.hpp>
25 #include <boost/geometry/core/exception.hpp>
27 #include <boost/geometry/algorithms/convert.hpp>
28 #include <boost/geometry/algorithms/detail/overlay/get_distance_measure.hpp>
29 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
31 #include <boost/geometry/geometries/segment.hpp>
33 #include <boost/geometry/policies/robustness/robust_point_type.hpp>
34 #include <boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp>
36 // Silence warning C4127: conditional expression is constant
39 #pragma warning(disable : 4127)
43 namespace boost { namespace geometry
46 #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
47 class turn_info_exception : public geometry::exception
52 // NOTE: "char" will be replaced by enum in future version
53 inline turn_info_exception(char const method)
55 message = "Boost.Geometry Turn exception: ";
59 virtual ~turn_info_exception() throw()
62 virtual char const* what() const throw()
64 return message.c_str();
69 #ifndef DOXYGEN_NO_DETAIL
70 namespace detail { namespace overlay
73 struct base_turn_handler
75 // Returns true if both sides are opposite
76 static inline bool opposite(int side1, int side2)
78 // We cannot state side1 == -side2, because 0 == -0
79 // So either side1*side2==-1 or side1==-side2 && side1 != 0
80 return side1 * side2 == -1;
83 // Same side of a segment (not being 0)
84 static inline bool same(int side1, int side2)
86 return side1 * side2 == 1;
89 // Both get the same operation
90 template <typename TurnInfo>
91 static inline void both(TurnInfo& ti, operation_type const op)
93 ti.operations[0].operation = op;
94 ti.operations[1].operation = op;
97 // If condition, first union/second intersection, else vice versa
98 template <typename TurnInfo>
99 static inline void ui_else_iu(bool condition, TurnInfo& ti)
101 ti.operations[0].operation = condition
102 ? operation_union : operation_intersection;
103 ti.operations[1].operation = condition
104 ? operation_intersection : operation_union;
107 // If condition, both union, else both intersection
108 template <typename TurnInfo>
109 static inline void uu_else_ii(bool condition, TurnInfo& ti)
111 both(ti, condition ? operation_union : operation_intersection);
114 template <typename TurnInfo, typename IntersectionInfo>
115 static inline void assign_point(TurnInfo& ti,
117 IntersectionInfo const& info, unsigned int index)
121 BOOST_GEOMETRY_ASSERT(index < info.count);
123 geometry::convert(info.intersections[index], ti.point);
124 ti.operations[0].fraction = info.fractions[index].robust_ra;
125 ti.operations[1].fraction = info.fractions[index].robust_rb;
128 template <typename IntersectionInfo>
129 static inline unsigned int non_opposite_to_index(IntersectionInfo const& info)
131 return info.fractions[0].robust_rb < info.fractions[1].robust_rb
135 template <typename Point1, typename Point2>
136 static inline typename geometry::coordinate_type<Point1>::type
137 distance_measure(Point1 const& a, Point2 const& b)
139 // TODO: use comparable distance for point-point instead - but that
140 // causes currently cycling include problems
141 typedef typename geometry::coordinate_type<Point1>::type ctype;
142 ctype const dx = get<0>(a) - get<0>(b);
143 ctype const dy = get<1>(a) - get<1>(b);
144 return dx * dx + dy * dy;
151 typename UniqueSubRange1,
152 typename UniqueSubRange2,
153 typename UmbrellaStrategy,
156 static inline void both_collinear(
157 UniqueSubRange1 const& range_p,
158 UniqueSubRange2 const& range_q,
159 UmbrellaStrategy const&,
160 std::size_t index_p, std::size_t index_q,
163 boost::ignore_unused(range_p, range_q);
164 BOOST_GEOMETRY_ASSERT(IndexP + IndexQ == 1);
165 BOOST_GEOMETRY_ASSERT(index_p > 0 && index_p <= 2);
166 BOOST_GEOMETRY_ASSERT(index_q > 0 && index_q <= 2);
168 #if ! defined(BOOST_GEOMETRY_USE_RESCALING)
169 ti.operations[IndexP].remaining_distance = distance_measure(ti.point, range_p.at(index_p));
170 ti.operations[IndexQ].remaining_distance = distance_measure(ti.point, range_q.at(index_q));
172 // pk/q2 is considered as collinear, but there might be
173 // a tiny measurable difference. If so, use that.
174 // Calculate pk // qj-qk
175 typedef detail::distance_measure
177 typename select_coordinate_type
179 typename UniqueSubRange1::point_type,
180 typename UniqueSubRange2::point_type
184 const bool p_closer =
185 ti.operations[IndexP].remaining_distance
186 < ti.operations[IndexQ].remaining_distance;
189 ? get_distance_measure<typename UmbrellaStrategy::cs_tag>(range_q.at(index_q - 1),
190 range_q.at(index_q), range_p.at(index_p))
191 : get_distance_measure<typename UmbrellaStrategy::cs_tag>(range_p.at(index_p - 1),
192 range_p.at(index_p), range_q.at(index_q));
196 // Not truely collinear, distinguish for union/intersection
197 // If p goes left (positive), take that for a union
199 bool p_left = p_closer ? dm.is_positive() : dm.is_negative();
201 ti.operations[IndexP].operation = p_left
202 ? operation_union : operation_intersection;
203 ti.operations[IndexQ].operation = p_left
204 ? operation_intersection : operation_union;
209 both(ti, operation_continue);
219 struct touch_interior : public base_turn_handler
221 // Index: 0, P is the interior, Q is touching and vice versa
225 typename UniqueSubRange1,
226 typename UniqueSubRange2,
227 typename IntersectionInfo,
230 typename UmbrellaStrategy
232 static inline void apply(UniqueSubRange1 const& range_p,
233 UniqueSubRange2 const& range_q,
235 IntersectionInfo const& intersection_info,
236 DirInfo const& dir_info,
237 SidePolicy const& side,
238 UmbrellaStrategy const& umbrella_strategy)
240 assign_point(ti, method_touch_interior, intersection_info, 0);
242 // Both segments of q touch segment p somewhere in its interior
243 // 1) We know: if q comes from LEFT or RIGHT
244 // (i.e. dir_info.sides.get<Index,0>() == 1 or -1)
245 // 2) Important is: if q_k goes to LEFT, RIGHT, COLLINEAR
246 // and, if LEFT/COLL, if it is lying LEFT or RIGHT w.r.t. q_i
248 BOOST_STATIC_ASSERT(Index <= 1);
249 static unsigned int const index_p = Index;
250 static unsigned int const index_q = 1 - Index;
252 bool const has_pk = ! range_p.is_last_segment();
253 bool const has_qk = ! range_q.is_last_segment();
254 int const side_qi_p = dir_info.sides.template get<index_q, 0>();
255 int const side_qk_p = has_qk ? side.qk_wrt_p1() : 0;
257 if (side_qi_p == -side_qk_p)
259 // Q crosses P from left->right or from right->left (test "ML1")
260 // Union: folow P (left->right) or Q (right->left)
261 // Intersection: other turn
262 unsigned int index = side_qk_p == -1 ? index_p : index_q;
263 ti.operations[index].operation = operation_union;
264 ti.operations[1 - index].operation = operation_intersection;
268 int const side_qk_q = has_qk ? side.qk_wrt_q1() : 0;
270 // Only necessary if rescaling is turned off:
271 int const side_pj_q2 = has_qk ? side.pj_wrt_q2() : 0;
273 if (side_qi_p == -1 && side_qk_p == -1 && side_qk_q == 1)
275 // Q turns left on the right side of P (test "MR3")
276 // Both directions for "intersection"
277 both(ti, operation_intersection);
278 ti.touch_only = true;
280 else if (side_qi_p == 1 && side_qk_p == 1 && side_qk_q == -1)
282 if (has_qk && side_pj_q2 == -1)
284 // Q turns right on the left side of P (test "ML3")
285 // Union: take both operations
286 // Intersection: skip
287 both(ti, operation_union);
291 // q2 is collinear with p1, so it does not turn back. This
292 // can happen in floating point precision. In this case,
293 // block one of the operations to avoid taking that path.
294 ti.operations[index_p].operation = operation_union;
295 ti.operations[index_q].operation = operation_blocked;
297 ti.touch_only = true;
299 else if (side_qi_p == side_qk_p && side_qi_p == side_qk_q)
301 // Q turns left on the left side of P (test "ML2")
302 // or Q turns right on the right side of P (test "MR2")
303 // Union: take left turn (Q if Q turns left, P if Q turns right)
304 // Intersection: other turn
305 unsigned int index = side_qk_q == 1 ? index_q : index_p;
306 if (has_qk && side_pj_q2 == 0)
308 // Even though sides xk w.r.t. 1 are distinct, pj is collinear
309 // with q. Therefore swap the path
313 if (has_pk && has_qk && opposite(side_pj_q2, side_qi_p))
315 // Without rescaling, floating point requires extra measures
316 int const side_qj_p1 = side.qj_wrt_p1();
317 int const side_qj_p2 = side.qj_wrt_p2();
319 if (same(side_qj_p1, side_qj_p2))
321 int const side_pj_q1 = side.pj_wrt_q1();
322 if (opposite(side_pj_q1, side_pj_q2))
329 ti.operations[index].operation = operation_union;
330 ti.operations[1 - index].operation = operation_intersection;
331 ti.touch_only = true;
333 else if (side_qk_p == 0)
335 // Q intersects on interior of P and continues collinearly
336 if (side_qk_q == side_qi_p)
338 both_collinear<index_p, index_q>(range_p, range_q, umbrella_strategy, 1, 2, ti);
343 // Opposite direction, which is never travelled.
344 // If Q turns left, P continues for intersection
345 // If Q turns right, P continues for union
346 ti.operations[index_p].operation = side_qk_q == 1
347 ? operation_intersection
349 ti.operations[index_q].operation = operation_blocked;
355 ti.method = method_error;
365 struct touch : public base_turn_handler
367 static inline bool between(int side1, int side2, int turn)
369 return side1 == side2 && ! opposite(side1, turn);
372 /*static inline void block_second(bool block, TurnInfo& ti)
376 ti.operations[1].operation = operation_blocked;
383 typename UniqueSubRange1,
384 typename UniqueSubRange2,
385 typename IntersectionInfo,
387 typename SideCalculator,
388 typename UmbrellaStrategy
390 static inline void apply(UniqueSubRange1 const& range_p,
391 UniqueSubRange2 const& range_q,
393 IntersectionInfo const& intersection_info,
394 DirInfo const& dir_info,
395 SideCalculator const& side,
396 UmbrellaStrategy const& umbrella_strategy)
398 assign_point(ti, method_touch, intersection_info, 0);
400 bool const has_pk = ! range_p.is_last_segment();
401 bool const has_qk = ! range_q.is_last_segment();
403 int const side_qi_p1 = dir_info.sides.template get<1, 0>();
404 int const side_qk_p1 = has_qk ? side.qk_wrt_p1() : 0;
407 // If Qi and Qk are both at same side of Pi-Pj,
408 // or collinear (so: not opposite sides)
409 if (! opposite(side_qi_p1, side_qk_p1))
411 int const side_pk_q2 = has_pk && has_qk ? side.pk_wrt_q2() : 0;
412 int const side_pk_p = has_pk ? side.pk_wrt_p1() : 0;
413 int const side_qk_q = has_qk ? side.qk_wrt_q1() : 0;
415 bool const q_turns_left = side_qk_q == 1;
416 bool const block_q = side_qk_p1 == 0
417 && ! same(side_qi_p1, side_qk_q)
420 // If Pk at same side as Qi/Qk
421 // (the "or" is for collinear case)
422 // or Q is fully collinear && P turns not to left
423 if (side_pk_p == side_qi_p1
424 || side_pk_p == side_qk_p1
425 || (side_qi_p1 == 0 && side_qk_p1 == 0 && side_pk_p != -1)
428 // Collinear -> lines join, continue
430 if (side_pk_q2 == 0 && ! block_q)
432 both_collinear<0, 1>(range_p, range_q, umbrella_strategy, 2, 2, ti);
436 int const side_pk_q1 = has_pk && has_qk ? side.pk_wrt_q1() : 0;
438 // Collinear opposite case -> block P
442 ti.operations[0].operation = operation_blocked;
443 // Q turns right -> union (both independent),
444 // Q turns left -> intersection
445 ti.operations[1].operation = block_q ? operation_blocked
446 : q_turns_left ? operation_intersection
451 // Pk between Qi and Qk
453 if (between(side_pk_q1, side_pk_q2, side_qk_q))
455 ui_else_iu(q_turns_left, ti);
458 ti.operations[1].operation = operation_blocked;
460 //block_second(block_q, ti);
464 // Pk between Qk and P, so left of Qk (if Q turns right) and vv
466 if (side_pk_q2 == -side_qk_q)
468 ui_else_iu(! q_turns_left, ti);
469 ti.touch_only = true;
475 if (side_pk_q1 == -side_qk_q)
477 uu_else_ii(! q_turns_left, ti);
480 ti.operations[1].operation = operation_blocked;
484 ti.touch_only = true;
486 //block_second(block_q, ti);
492 // Pk at other side than Qi/Pk
493 ti.operations[0].operation = q_turns_left
494 ? operation_intersection
496 ti.operations[1].operation = block_q
498 : side_qi_p1 == 1 || side_qk_p1 == 1
500 : operation_intersection;
503 ti.touch_only = true;
511 // From left to right or from right to left
512 int const side_pk_p = has_pk ? side.pk_wrt_p1() : 0;
513 bool const right_to_left = side_qk_p1 == 1;
515 // If p turns into direction of qi (1,2)
516 if (side_pk_p == side_qi_p1)
518 int const side_pk_q1 = has_pk ? side.pk_wrt_q1() : 0;
520 // Collinear opposite case -> block P
523 ti.operations[0].operation = operation_blocked;
524 ti.operations[1].operation = right_to_left
525 ? operation_union : operation_intersection;
529 if (side_pk_q1 == side_qk_p1)
531 uu_else_ii(right_to_left, ti);
532 ti.touch_only = true;
537 // If p turns into direction of qk (4,5)
538 if (side_pk_p == side_qk_p1)
540 int const side_pk_q2 = has_pk ? side.pk_wrt_q2() : 0;
542 // Collinear case -> lines join, continue
545 both(ti, operation_continue);
548 if (side_pk_q2 == side_qk_p1)
550 ui_else_iu(right_to_left, ti);
551 ti.touch_only = true;
556 ui_else_iu(! right_to_left, ti);
567 struct equal : public base_turn_handler
571 typename UniqueSubRange1,
572 typename UniqueSubRange2,
573 typename IntersectionInfo,
575 typename SideCalculator,
576 typename UmbrellaStrategy
578 static inline void apply(UniqueSubRange1 const& range_p,
579 UniqueSubRange2 const& range_q,
581 IntersectionInfo const& info,
583 SideCalculator const& side,
584 UmbrellaStrategy const& umbrella_strategy)
586 // Copy the intersection point in TO direction
587 assign_point(ti, method_equal, info, non_opposite_to_index(info));
589 bool const has_pk = ! range_p.is_last_segment();
590 bool const has_qk = ! range_q.is_last_segment();
592 int const side_pk_q2 = has_pk && has_qk ? side.pk_wrt_q2() : 0;
593 int const side_pk_p = has_pk ? side.pk_wrt_p1() : 0;
594 int const side_qk_p = has_qk ? side.qk_wrt_p1() : 0;
596 #if ! defined(BOOST_GEOMETRY_USE_RESCALING)
598 if (has_pk && has_qk && side_pk_p == side_qk_p)
600 // They turn to the same side, or continue both collinearly
601 // Without rescaling, to check for union/intersection,
602 // try to check side values (without any thresholds)
603 typedef typename select_coordinate_type
605 typename UniqueSubRange1::point_type,
606 typename UniqueSubRange2::point_type
607 >::type coordinate_type;
609 typedef detail::distance_measure<coordinate_type> dm_type;
611 dm_type const dm_qk_p
612 = get_distance_measure<typename UmbrellaStrategy::cs_tag>(range_q.at(1), range_q.at(2), range_p.at(2));
613 dm_type const dm_pk_q
614 = get_distance_measure<typename UmbrellaStrategy::cs_tag>(range_p.at(1), range_p.at(2), range_q.at(2));
616 if (dm_pk_q.measure != dm_qk_p.measure)
618 // A (possibly very small) difference is detected, which
619 // can be used to distinguish between union/intersection
620 ui_else_iu(dm_pk_q.measure < dm_qk_p.measure, ti);
626 // If pk is collinear with qj-qk, they continue collinearly.
627 // This can be on either side of p1 (== q1), or collinear
628 // The second condition checks if they do not continue
630 if (side_pk_q2 == 0 && side_pk_p == side_qk_p)
632 both_collinear<0, 1>(range_p, range_q, umbrella_strategy, 2, 2, ti);
637 // If they turn to same side (not opposite sides)
638 if (! opposite(side_pk_p, side_qk_p))
640 // If pk is left of q2 or collinear: p: union, q: intersection
641 ui_else_iu(side_pk_q2 != -1, ti);
645 // They turn opposite sides. If p turns left (or collinear),
646 // p: union, q: intersection
647 ui_else_iu(side_pk_p != -1, ti);
655 typename AssignPolicy
657 struct equal_opposite : public base_turn_handler
661 typename UniqueSubRange1,
662 typename UniqueSubRange2,
663 typename OutputIterator,
664 typename IntersectionInfo
666 static inline void apply(
667 UniqueSubRange1 const& /*range_p*/,
668 UniqueSubRange2 const& /*range_q*/,
669 /* by value: */ TurnInfo tp,
671 IntersectionInfo const& intersection_info)
673 // For equal-opposite segments, normally don't do anything.
674 if (AssignPolicy::include_opposite)
676 tp.method = method_equal;
677 for (unsigned int i = 0; i < 2; i++)
679 tp.operations[i].operation = operation_opposite;
681 for (unsigned int i = 0; i < intersection_info.i_info().count; i++)
683 assign_point(tp, method_none, intersection_info.i_info(), i);
694 struct collinear : public base_turn_handler
697 arrival P pk//p1 qk//q1 product* case result
711 *product = arrival * (pk//p1 or qk//q1)
714 - if P arrives: look at turn P
715 - if Q arrives: look at turn Q
716 - if P arrives and P turns left: union for P
717 - if P arrives and P turns right: intersection for P
718 - if Q arrives and Q turns left: union for Q (=intersection for P)
719 - if Q arrives and Q turns right: intersection for Q (=union for P)
721 ROBUSTNESS: p and q are collinear, so you would expect
722 that side qk//p1 == pk//q1. But that is not always the case
723 in near-epsilon ranges. Then decision logic is different.
724 If p arrives, q is further, so the angle qk//p1 is (normally)
725 more precise than pk//p1
730 typename UniqueSubRange1,
731 typename UniqueSubRange2,
732 typename IntersectionInfo,
736 static inline void apply(
737 UniqueSubRange1 const& range_p,
738 UniqueSubRange2 const& range_q,
740 IntersectionInfo const& info,
741 DirInfo const& dir_info,
742 SidePolicy const& side)
744 // Copy the intersection point in TO direction
745 assign_point(ti, method_collinear, info, non_opposite_to_index(info));
747 int const arrival = dir_info.arrival[0];
748 // Should not be 0, this is checked before
749 BOOST_GEOMETRY_ASSERT(arrival != 0);
751 bool const has_pk = ! range_p.is_last_segment();
752 bool const has_qk = ! range_q.is_last_segment();
753 int const side_p = has_pk ? side.pk_wrt_p1() : 0;
754 int const side_q = has_qk ? side.qk_wrt_q1() : 0;
756 // If p arrives, use p, else use q
757 int const side_p_or_q = arrival == 1
762 // See comments above,
763 // resulting in a strange sort of mathematic rule here:
764 // The arrival-info multiplied by the relevant side
765 // delivers a consistent result.
767 int const product = arrival * side_p_or_q;
771 both(ti, operation_continue);
775 ui_else_iu(product == 1, ti);
778 // Calculate remaining distance. If it continues collinearly it is
779 // measured until the end of the next segment
780 ti.operations[0].remaining_distance
781 = side_p == 0 && has_pk
782 ? distance_measure(ti.point, range_p.at(2))
783 : distance_measure(ti.point, range_p.at(1));
784 ti.operations[1].remaining_distance
785 = side_q == 0 && has_qk
786 ? distance_measure(ti.point, range_q.at(2))
787 : distance_measure(ti.point, range_q.at(1));
794 typename AssignPolicy
796 struct collinear_opposite : public base_turn_handler
800 arrival P arrival Q pk//p1 qk//q1 case result2 result
801 --------------------------------------------------------------
806 1 1 0 -1 CCO1 (xx) xu
807 1 1 0 0 CCO2 (xx) (xx)
811 1 1 -1 0 CRO2 ux (xx)
826 typename IntersectionInfo
828 static inline bool set_tp(int side_rk_r, bool handle_robustness,
830 TurnInfo& tp, IntersectionInfo const& intersection_info)
832 BOOST_STATIC_ASSERT(Index <= 1);
834 boost::ignore_unused(handle_robustness, side_rk_s);
836 operation_type blocked = operation_blocked;
841 // Turning left on opposite collinear: intersection
842 tp.operations[Index].operation = operation_intersection;
845 // Turning right on opposite collinear: union
846 tp.operations[Index].operation = operation_union;
849 // No turn on opposite collinear: block, do not traverse
850 // But this "xx" is usually ignored, it is useless to include
851 // two operations blocked, so the whole point does not need
853 // So return false to indicate nothing is to be done.
854 if (AssignPolicy::include_opposite)
856 tp.operations[Index].operation = operation_opposite;
857 blocked = operation_opposite;
866 // The other direction is always blocked when collinear opposite
867 tp.operations[1 - Index].operation = blocked;
869 // If P arrives within Q, set info on P (which is done above, index=0),
870 // this turn-info belongs to the second intersection point, index=1
871 // (see e.g. figure CLO1)
872 assign_point(tp, method_collinear, intersection_info, 1 - Index);
877 static inline void empty_transformer(TurnInfo &) {}
881 typename UniqueSubRange1,
882 typename UniqueSubRange2,
883 typename OutputIterator,
884 typename IntersectionInfo,
887 static inline void apply(
888 UniqueSubRange1 const& range_p,
889 UniqueSubRange2 const& range_q,
891 // Opposite collinear can deliver 2 intersection points,
892 TurnInfo const& tp_model,
895 IntersectionInfo const& intersection_info,
896 SidePolicy const& side)
898 apply(range_p, range_q,
899 tp_model, out, intersection_info, side, empty_transformer);
906 typename UniqueSubRange1,
907 typename UniqueSubRange2,
908 typename OutputIterator,
909 typename IntersectionInfo,
911 typename TurnTransformer
913 static inline void apply(
914 UniqueSubRange1 const& range_p,
915 UniqueSubRange2 const& range_q,
917 // Opposite collinear can deliver 2 intersection points,
918 TurnInfo const& tp_model,
921 IntersectionInfo const& info,
922 SidePolicy const& side,
923 TurnTransformer turn_transformer)
925 TurnInfo tp = tp_model;
927 int const p_arrival = info.d_info().arrival[0];
928 int const q_arrival = info.d_info().arrival[1];
930 // If P arrives within Q, there is a turn dependent on P
932 && ! range_p.is_last_segment()
933 && set_tp<0>(side.pk_wrt_p1(), true, side.pk_wrt_q1(), tp, info.i_info()) )
935 turn_transformer(tp);
940 // If Q arrives within P, there is a turn dependent on Q
942 && ! range_q.is_last_segment()
943 && set_tp<1>(side.qk_wrt_q1(), false, side.qk_wrt_p1(), tp, info.i_info()) )
945 turn_transformer(tp);
950 if (AssignPolicy::include_opposite)
952 // Handle cases not yet handled above
953 if ((q_arrival == -1 && p_arrival == 0)
954 || (p_arrival == -1 && q_arrival == 0))
956 for (unsigned int i = 0; i < 2; i++)
958 tp.operations[i].operation = operation_opposite;
960 for (unsigned int i = 0; i < info.i_info().count; i++)
962 assign_point(tp, method_collinear, info.i_info(), i);
976 struct crosses : public base_turn_handler
978 template <typename IntersectionInfo, typename DirInfo>
979 static inline void apply(TurnInfo& ti,
980 IntersectionInfo const& intersection_info,
981 DirInfo const& dir_info)
983 assign_point(ti, method_crosses, intersection_info, 0);
986 // If Q crosses P from left to right
988 // Intersection: take Q
989 // Otherwise: vice versa
990 int const side_qi_p1 = dir_info.sides.template get<1, 0>();
991 unsigned int const index = side_qi_p1 == 1 ? 0 : 1;
992 ti.operations[index].operation = operation_union;
993 ti.operations[1 - index].operation = operation_intersection;
997 struct only_convert : public base_turn_handler
999 template<typename TurnInfo, typename IntersectionInfo>
1000 static inline void apply(TurnInfo& ti, IntersectionInfo const& intersection_info)
1002 assign_point(ti, method_none, intersection_info, 0); // was collinear
1003 ti.operations[0].operation = operation_continue;
1004 ti.operations[1].operation = operation_continue;
1009 \brief Policy doing nothing
1010 \details get_turn_info can have an optional policy include extra
1011 truns. By default it does not, and this class is that default.
1013 struct assign_null_policy
1015 static bool const include_no_turn = false;
1016 static bool const include_degenerate = false;
1017 static bool const include_opposite = false;
1021 \brief Turn information: intersection point, method, and turn information
1022 \details Information necessary for traversal phase (a phase
1023 of the overlay process). The information is gathered during the
1024 get_turns (segment intersection) phase.
1025 \tparam AssignPolicy policy to assign extra info,
1026 e.g. to calculate distance from segment's first points
1027 to intersection points.
1028 It also defines if a certain class of points
1029 (degenerate, non-turns) should be included.
1031 template<typename AssignPolicy>
1032 struct get_turn_info
1034 // Intersect a segment p with a segment q
1035 // Both p and q are modelled as sub_ranges to provide more points
1036 // to be able to give more information about the turn (left/right)
1039 typename UniqueSubRange1,
1040 typename UniqueSubRange2,
1042 typename UmbrellaStrategy,
1043 typename RobustPolicy,
1044 typename OutputIterator
1046 static inline OutputIterator apply(
1047 UniqueSubRange1 const& range_p,
1048 UniqueSubRange2 const& range_q,
1049 TurnInfo const& tp_model,
1050 UmbrellaStrategy const& umbrella_strategy,
1051 RobustPolicy const& robust_policy,
1054 typedef intersection_info
1056 UniqueSubRange1, UniqueSubRange2,
1057 typename TurnInfo::point_type,
1062 inters_info inters(range_p, range_q, umbrella_strategy, robust_policy);
1064 char const method = inters.d_info().how;
1066 // Copy, to copy possibly extended fields
1067 TurnInfo tp = tp_model;
1069 bool do_only_convert = false;
1071 // Select method and apply
1074 case 'a' : // "angle"
1075 case 'f' : // "from"
1076 case 's' : // "start"
1077 do_only_convert = true;
1080 case 'd' : // disjoint: never do anything
1085 typedef touch_interior
1090 // If Q (1) arrives (1)
1091 if ( inters.d_info().arrival[1] == 1 )
1093 handler::template apply<0>(range_p, range_q, tp, inters.i_info(), inters.d_info(),
1094 inters.sides(), umbrella_strategy);
1099 handler::template apply<1>(range_q, range_p, tp, inters.i_info(), inters.d_info(),
1100 inters.get_swapped_sides(), umbrella_strategy);
1107 crosses<TurnInfo>::apply(tp, inters.i_info(), inters.d_info());
1113 // Both touch (both arrive there)
1114 touch<TurnInfo>::apply(range_p, range_q, tp, inters.i_info(), inters.d_info(), inters.sides(), umbrella_strategy);
1120 if ( ! inters.d_info().opposite )
1123 // or collinear-and-ending at intersection point
1124 equal<TurnInfo>::apply(range_p, range_q, tp, inters.i_info(), inters.d_info(), inters.sides(), umbrella_strategy);
1133 >::apply(range_p, range_q, tp, out, inters);
1140 if ( ! inters.d_info().opposite )
1143 if ( inters.d_info().arrival[0] == 0 )
1145 // Collinear, but similar thus handled as equal
1146 equal<TurnInfo>::apply(range_p, range_q, tp,
1147 inters.i_info(), inters.d_info(), inters.sides(), umbrella_strategy);
1149 // override assigned method
1150 tp.method = method_collinear;
1154 collinear<TurnInfo>::apply(range_p, range_q, tp,
1155 inters.i_info(), inters.d_info(), inters.sides());
1166 >::apply(range_p, range_q,
1167 tp, out, inters, inters.sides());
1173 // degenerate points
1174 if (AssignPolicy::include_degenerate)
1176 only_convert::apply(tp, inters.i_info());
1183 #if defined(BOOST_GEOMETRY_DEBUG_ROBUSTNESS)
1184 std::cout << "TURN: Unknown method: " << method << std::endl;
1186 #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
1187 BOOST_THROW_EXCEPTION(turn_info_exception(method));
1194 && AssignPolicy::include_no_turn
1195 && inters.i_info().count > 0)
1197 only_convert::apply(tp, inters.i_info());
1206 }} // namespace detail::overlay
1207 #endif //DOXYGEN_NO_DETAIL
1210 }} // namespace boost::geometry
1213 #if defined(_MSC_VER)
1214 #pragma warning(pop)
1217 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HPP