1// Boost.Geometry
2
3// Copyright (c) 2007-2023 Barend Gehrels, Amsterdam, the Netherlands.
4// Copyright (c) 2017-2023 Adam Wulkiewicz, Lodz, Poland.
5
6// This file was modified by Oracle on 2015-2022.
7// Modifications copyright (c) 2015-2022 Oracle and/or its affiliates.
8// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
9
10// Use, modification and distribution is subject to the Boost Software License,
11// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
12// http://www.boost.org/LICENSE_1_0.txt)
13
14#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HPP
15#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HPP
16
17#include <boost/core/ignore_unused.hpp>
18#include <boost/throw_exception.hpp>
19
20#include <boost/geometry/core/access.hpp>
21#include <boost/geometry/core/assert.hpp>
22#include <boost/geometry/core/config.hpp>
23#include <boost/geometry/core/exception.hpp>
24
25#include <boost/geometry/algorithms/convert.hpp>
26#include <boost/geometry/algorithms/detail/overlay/get_distance_measure.hpp>
27#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
28#include <boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp>
29
30#include <boost/geometry/util/constexpr.hpp>
31
32
33namespace boost { namespace geometry
34{
35
36#if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
37class turn_info_exception : public geometry::exception
38{
39 std::string message;
40public:
41
42 // NOTE: "char" will be replaced by enum in future version
43 inline turn_info_exception(char const method)
44 {
45 message = "Boost.Geometry Turn exception: ";
46 message += method;
47 }
48
49 virtual char const* What() const noexcept
50 {
51 return message.c_str();
52 }
53};
54#endif
55
56#ifndef DOXYGEN_NO_DETAIL
57namespace detail { namespace overlay
58{
59
60
61struct policy_verify_nothing
62{
63 static bool const use_side_verification = false;
64 static bool const use_start_turn = false;
65 static bool const use_handle_as_touch = false;
66 static bool const use_handle_as_equal = false;
67 static bool const use_handle_imperfect_touch = false;
68};
69
70struct policy_verify_all
71{
72 static bool const use_side_verification = true;
73 static bool const use_start_turn = true;
74 static bool const use_handle_as_touch = true;
75 static bool const use_handle_as_equal = true;
76 static bool const use_handle_imperfect_touch = true;
77};
78
79
80#if defined(BOOST_GEOMETRY_USE_RESCALING)
81using verify_policy_aa = policy_verify_nothing;
82#else
83using verify_policy_aa = policy_verify_all;
84#endif
85
86using verify_policy_ll = policy_verify_nothing;
87using verify_policy_la = policy_verify_nothing;
88
89
90struct base_turn_handler
91{
92 // Returns true if both sides are opposite
93 static inline bool opposite(int side1, int side2)
94 {
95 // We cannot state side1 == -side2, because 0 == -0
96 // So either side1*side2==-1 or side1==-side2 && side1 != 0
97 return side1 * side2 == -1;
98 }
99
100 // Same side of a segment (not being 0)
101 static inline bool same(int side1, int side2)
102 {
103 return side1 * side2 == 1;
104 }
105
106 // Both get the same operation
107 template <typename TurnInfo>
108 static inline void both(TurnInfo& ti, operation_type const op)
109 {
110 ti.operations[0].operation = op;
111 ti.operations[1].operation = op;
112 }
113
114 // If condition, first union/second intersection, else vice versa
115 template <typename TurnInfo>
116 static inline void ui_else_iu(bool condition, TurnInfo& ti)
117 {
118 ti.operations[0].operation = condition
119 ? operation_union : operation_intersection;
120 ti.operations[1].operation = condition
121 ? operation_intersection : operation_union;
122 }
123
124 // If condition, both union, else both intersection
125 template <typename TurnInfo>
126 static inline void uu_else_ii(bool condition, TurnInfo& ti)
127 {
128 both(ti, condition ? operation_union : operation_intersection);
129 }
130
131 template <typename TurnInfo, typename IntersectionInfo>
132 static inline void assign_point(TurnInfo& ti,
133 method_type method,
134 IntersectionInfo const& info, unsigned int index)
135 {
136 ti.method = method;
137
138 BOOST_GEOMETRY_ASSERT(index < info.count);
139
140 geometry::convert(info.intersections[index], ti.point);
141 ti.operations[0].fraction = info.fractions[index].robust_ra;
142 ti.operations[1].fraction = info.fractions[index].robust_rb;
143 }
144
145 template <typename TurnInfo, typename IntersectionInfo, typename DirInfo>
146 static inline void assign_point_and_correct(TurnInfo& ti,
147 method_type method,
148 IntersectionInfo const& info, DirInfo const& dir_info)
149 {
150 ti.method = method;
151
152 // For touch/touch interior always take the intersection point 0
153 // (usually there is only one - but if collinear is handled as touch, both could be taken).
154 static int const index = 0;
155
156 geometry::convert(info.intersections[index], ti.point);
157
158 for (int i = 0; i < 2; i++)
159 {
160 if (dir_info.arrival[i] == 1)
161 {
162 // The segment arrives at the intersection point, its fraction should be 1
163 // (due to precision it might be nearly so, but not completely, in rare cases)
164 ti.operations[i].fraction = {1, 1};
165 }
166 else if (dir_info.arrival[i] == -1)
167 {
168 // The segment leaves from the intersection point, likewise its fraction should be 0
169 ti.operations[i].fraction = {0, 1};
170 }
171 else
172 {
173 ti.operations[i].fraction = i == 0 ? info.fractions[index].robust_ra
174 : info.fractions[index].robust_rb;
175 }
176 }
177 }
178
179 template <typename IntersectionInfo>
180 static inline unsigned int non_opposite_to_index(IntersectionInfo const& info)
181 {
182 return info.fractions[0].robust_rb < info.fractions[1].robust_rb
183 ? 1 : 0;
184 }
185
186};
187
188template<typename VerifyPolicy>
189struct turn_info_verification_functions
190{
191 template <typename Point1, typename Point2>
192 static inline
193 typename select_coordinate_type<Point1, Point2>::type
194 distance_measure(Point1 const& a, Point2 const& b)
195 {
196 // TODO: revise this using comparable distance for various
197 // coordinate systems
198 using coor_t = typename select_coordinate_type<Point1, Point2>::type;
199
200 coor_t const dx = get<0>(a) - get<0>(b);
201 coor_t const dy = get<1>(a) - get<1>(b);
202 return dx * dx + dy * dy;
203 }
204
205 template
206 <
207 std::size_t IndexP,
208 std::size_t IndexQ,
209 typename UniqueSubRange1,
210 typename UniqueSubRange2,
211 typename UmbrellaStrategy,
212 typename TurnInfo
213 >
214 static inline void set_both_verified(
215 UniqueSubRange1 const& range_p,
216 UniqueSubRange2 const& range_q,
217 UmbrellaStrategy const& umbrella_strategy,
218 std::size_t index_p, std::size_t index_q,
219 TurnInfo& ti)
220 {
221 BOOST_GEOMETRY_ASSERT(IndexP + IndexQ == 1);
222 BOOST_GEOMETRY_ASSERT(index_p > 0 && index_p <= 2);
223 BOOST_GEOMETRY_ASSERT(index_q > 0 && index_q <= 2);
224
225 using distance_measure_result_type = typename geometry::coordinate_type<decltype(ti.point)>::type;
226
227 bool const p_in_range = index_p < range_p.size();
228 bool const q_in_range = index_q < range_q.size();
229 ti.operations[IndexP].remaining_distance
230 = p_in_range
231 ? distance_measure(ti.point, range_p.at(index_p))
232 : distance_measure_result_type{0};
233 ti.operations[IndexQ].remaining_distance
234 = q_in_range
235 ? distance_measure(ti.point, range_q.at(index_q))
236 : distance_measure_result_type{0};
237
238 if (p_in_range && q_in_range)
239 {
240 // pk/q2 is considered as collinear, but there might be
241 // a tiny measurable difference. If so, use that.
242 // Calculate pk // qj-qk
243 bool const p_closer
244 = ti.operations[IndexP].remaining_distance
245 < ti.operations[IndexQ].remaining_distance;
246 auto const dm
247 = p_closer
248 ? get_distance_measure(range_q.at(index_q - 1),
249 range_q.at(index_q), range_p.at(index_p),
250 umbrella_strategy)
251 : get_distance_measure(range_p.at(index_p - 1),
252 range_p.at(index_p), range_q.at(index_q),
253 umbrella_strategy);
254
255 if (! dm.is_zero())
256 {
257 // Not truely collinear, distinguish for union/intersection
258 // If p goes left (positive), take that for a union
259 bool const p_left
260 = p_closer ? dm.is_positive() : dm.is_negative();
261
262 ti.operations[IndexP].operation = p_left
263 ? operation_union : operation_intersection;
264 ti.operations[IndexQ].operation = p_left
265 ? operation_intersection : operation_union;
266 return;
267 }
268 }
269
270 base_turn_handler::both(ti, operation_continue);
271 }
272
273 template
274 <
275 std::size_t IndexP,
276 std::size_t IndexQ,
277 typename UniqueSubRange1,
278 typename UniqueSubRange2,
279 typename UmbrellaStrategy,
280 typename TurnInfo
281 >
282 static inline void both_collinear(
283 UniqueSubRange1 const& range_p,
284 UniqueSubRange2 const& range_q,
285 UmbrellaStrategy const& umbrella_strategy,
286 std::size_t index_p, std::size_t index_q,
287 TurnInfo& ti)
288 {
289 if BOOST_GEOMETRY_CONSTEXPR (VerifyPolicy::use_side_verification)
290 {
291 set_both_verified<IndexP, IndexQ>(range_p, range_q, umbrella_strategy,
292 index_p, index_q, ti);
293 }
294 else
295 {
296 base_turn_handler::both(ti, operation_continue);
297 }
298 }
299
300 template
301 <
302 typename UniqueSubRange1,
303 typename UniqueSubRange2,
304 typename UmbrellaStrategy
305 >
306 static inline int verified_side(int side,
307 UniqueSubRange1 const& range_p,
308 UniqueSubRange2 const& range_q,
309 UmbrellaStrategy const& umbrella_strategy,
310 int index_p, int index_q)
311 {
312 if BOOST_GEOMETRY_CONSTEXPR (VerifyPolicy::use_side_verification)
313 {
314 if (side == 0)
315 {
316 if (index_p >= 1 && range_p.is_last_segment())
317 {
318 return 0;
319 }
320 if (index_q >= 2 && range_q.is_last_segment())
321 {
322 return 0;
323 }
324
325 auto const dm = get_distance_measure(range_p.at(index_p),
326 range_p.at(index_p + 1),
327 range_q.at(index_q),
328 umbrella_strategy);
329 static decltype(dm.measure) const zero = 0;
330 return dm.measure == zero ? 0 : dm.measure > zero ? 1 : -1;
331 }
332 }
333
334 return side;
335 }
336
337};
338
339
340template
341<
342 typename TurnInfo,
343 typename VerifyPolicy
344>
345struct touch_interior : public base_turn_handler
346{
347 using fun = turn_info_verification_functions<VerifyPolicy>;
348
349 template
350 <
351 typename IntersectionInfo,
352 typename UniqueSubRange
353 >
354 static bool handle_as_touch(IntersectionInfo const& info,
355 UniqueSubRange const& non_touching_range)
356 {
357 if BOOST_GEOMETRY_CONSTEXPR (! VerifyPolicy::use_handle_as_touch)
358 {
359 return false;
360 }
361 else // else prevents unreachable code warning
362 {
363 //
364 //
365 // ^ Q(i) ^ P(i)
366 // \ /
367 // \ /
368 // \ /
369 // \ /
370 // \ /
371 // \ /
372 // \ /
373 // \ /
374 // \ /
375 // \ / it is about buffer_rt_r
376 // P(k) v/ they touch here "in the middle", but at the intersection...
377 // <---------------->v there is no follow up IP
378 // /
379 // /
380 // /
381 // /
382 // /
383 // /
384 // v Q(k)
385 //
386
387 // Measure where the IP is located. If it is really close to the end,
388 // then there is no space for the next IP (on P(1)/Q(2). A "from"
389 // intersection will be generated, but those are never handled.
390 // Therefore handle it as a normal touch (two segments arrive at the
391 // intersection point). It currently checks for zero, but even a
392 // distance a little bit larger would do.
393 auto const dm = fun::distance_measure(info.intersections[0], non_touching_range.at(1));
394 decltype(dm) const zero = 0;
395 bool const result = math::equals(dm, zero);
396 return result;
397 }
398 }
399
400 // Index: 0, P is the interior, Q is touching and vice versa
401 template
402 <
403 unsigned int Index,
404 typename UniqueSubRange1,
405 typename UniqueSubRange2,
406 typename IntersectionInfo,
407 typename DirInfo,
408 typename SidePolicy,
409 typename UmbrellaStrategy
410 >
411 static inline void apply(UniqueSubRange1 const& range_p,
412 UniqueSubRange2 const& range_q,
413 TurnInfo& ti,
414 IntersectionInfo const& intersection_info,
415 DirInfo const& dir_info,
416 SidePolicy const& side,
417 UmbrellaStrategy const& umbrella_strategy)
418 {
419 assign_point_and_correct(ti, method_touch_interior, intersection_info, dir_info);
420
421 // Both segments of q touch segment p somewhere in its interior
422 // 1) We know: if q comes from LEFT or RIGHT
423 // (i.e. dir_info.sides.get<Index,0>() == 1 or -1)
424 // 2) Important is: if q_k goes to LEFT, RIGHT, COLLINEAR
425 // and, if LEFT/COLL, if it is lying LEFT or RIGHT w.r.t. q_i
426
427 BOOST_STATIC_ASSERT(Index <= 1);
428 static unsigned int const index_p = Index;
429 static unsigned int const index_q = 1 - Index;
430
431 bool const has_pk = ! range_p.is_last_segment();
432 bool const has_qk = ! range_q.is_last_segment();
433 int const side_qi_p = dir_info.sides.template get<index_q, 0>();
434 int const side_qk_p = has_qk ? side.qk_wrt_p1() : 0;
435
436 if (side_qi_p == -side_qk_p)
437 {
438 // Q crosses P from left->right or from right->left (test "ML1")
439 // Union: folow P (left->right) or Q (right->left)
440 // Intersection: other turn
441 unsigned int index = side_qk_p == -1 ? index_p : index_q;
442 ti.operations[index].operation = operation_union;
443 ti.operations[1 - index].operation = operation_intersection;
444 return;
445 }
446
447 int const side_qk_q = has_qk ? side.qk_wrt_q1() : 0;
448
449 // Only necessary if rescaling is turned off:
450 int const side_pj_q2 = has_qk ? side.pj_wrt_q2() : 0;
451
452 if (side_qi_p == -1 && side_qk_p == -1 && side_qk_q == 1)
453 {
454 // Q turns left on the right side of P (test "MR3")
455 // Both directions for "intersection"
456 both(ti, operation_intersection);
457 ti.touch_only = true;
458 }
459 else if (side_qi_p == 1 && side_qk_p == 1 && side_qk_q == -1)
460 {
461 if (has_qk && side_pj_q2 == -1)
462 {
463 // Q turns right on the left side of P (test "ML3")
464 // Union: take both operations
465 // Intersection: skip
466 both(ti, operation_union);
467 }
468 else
469 {
470 // q2 is collinear with p1, so it does not turn back. This
471 // can happen in floating point precision. In this case,
472 // block one of the operations to avoid taking that path.
473 ti.operations[index_p].operation = operation_union;
474 ti.operations[index_q].operation = operation_blocked;
475 }
476 ti.touch_only = true;
477 }
478 else if (side_qi_p == side_qk_p && side_qi_p == side_qk_q)
479 {
480 // Q turns left on the left side of P (test "ML2")
481 // or Q turns right on the right side of P (test "MR2")
482 // Union: take left turn (Q if Q turns left, P if Q turns right)
483 // Intersection: other turn
484 unsigned int index = side_qk_q == 1 ? index_q : index_p;
485 if (has_qk && side_pj_q2 == 0)
486 {
487 // Even though sides xk w.r.t. 1 are distinct, pj is collinear
488 // with q. Therefore swap the path
489 index = 1 - index;
490 }
491
492 if (has_pk && has_qk && opposite(side1: side_pj_q2, side2: side_qi_p))
493 {
494 // Without rescaling, floating point requires extra measures
495 int const side_qj_p1 = side.qj_wrt_p1();
496 int const side_qj_p2 = side.qj_wrt_p2();
497
498 if (same(side1: side_qj_p1, side2: side_qj_p2))
499 {
500 int const side_pj_q1 = side.pj_wrt_q1();
501 if (opposite(side1: side_pj_q1, side2: side_pj_q2))
502 {
503 index = 1 - index;
504 }
505 }
506 }
507
508 ti.operations[index].operation = operation_union;
509 ti.operations[1 - index].operation = operation_intersection;
510 ti.touch_only = true;
511 }
512 else if (side_qk_p == 0)
513 {
514 // Q intersects on interior of P and continues collinearly
515 if (side_qk_q == side_qi_p)
516 {
517 fun::template both_collinear<index_p, index_q>(range_p, range_q, umbrella_strategy,
518 1, 2, ti);
519 }
520 else
521 {
522 // Opposite direction, which is never travelled.
523 // If Q turns left, P continues for intersection
524 // If Q turns right, P continues for union
525 ti.operations[index_p].operation = side_qk_q == 1
526 ? operation_intersection
527 : operation_union;
528 ti.operations[index_q].operation = operation_blocked;
529 }
530 }
531 else
532 {
533 // Should not occur!
534 ti.method = method_error;
535 }
536 }
537};
538
539
540template
541<
542 typename TurnInfo,
543 typename VerifyPolicy
544>
545struct touch : public base_turn_handler
546{
547 using fun = turn_info_verification_functions<VerifyPolicy>;
548
549 static inline bool between(int side1, int side2, int turn)
550 {
551 return side1 == side2 && ! opposite(side1, side2: turn);
552 }
553
554 template
555 <
556 typename UniqueSubRange1,
557 typename UniqueSubRange2,
558 typename UmbrellaStrategy
559 >
560 static inline bool handle_imperfect_touch(UniqueSubRange1 const& range_p,
561 UniqueSubRange2 const& range_q,
562 int side_pk_q2,
563 UmbrellaStrategy const& umbrella_strategy,
564 TurnInfo& ti)
565 {
566 if BOOST_GEOMETRY_CONSTEXPR (! VerifyPolicy::use_handle_imperfect_touch)
567 {
568 return false;
569 }
570 else // else prevents unreachable code warning
571 {
572 // Q
573 // ^
574 // ||
575 // ||
576 // |^----
577 // >----->P
578 // * * they touch here (P/Q are (nearly) on top)
579 //
580 // Q continues from where P comes.
581 // P continues from where Q comes
582 // This is often a blocking situation,
583 // unless there are FP issues: there might be a distance
584 // between Pj and Qj, in that case handle it as a union.
585 //
586 // Exaggerated:
587 // Q
588 // ^ Q is nearly vertical
589 // \ but not completely - and still ends above P
590 // | \qj In this case it should block P and
591 // | ^------ set Q to Union
592 // >----->P qj is LEFT of P1 and pi is LEFT of Q2
593 // (the other way round is also possible)
594
595 auto has_distance = [&](auto const& r1, auto const& r2) -> bool
596 {
597 auto const d1 = get_distance_measure(r1.at(0), r1.at(1), r2.at(1), umbrella_strategy);
598 auto const d2 = get_distance_measure(r2.at(1), r2.at(2), r1.at(0), umbrella_strategy);
599 return d1.measure > 0 && d2.measure > 0;
600 };
601
602 if (side_pk_q2 == -1 && has_distance(range_p, range_q))
603 {
604 // Even though there is a touch, Q(j) is left of P1
605 // and P(i) is still left from Q2.
606 // Q continues to the right.
607 // It can continue.
608 ti.operations[0].operation = operation_blocked;
609 // Q turns right -> union (both independent),
610 // Q turns left -> intersection
611 ti.operations[1].operation = operation_union;
612 ti.touch_only = true;
613 return true;
614 }
615
616 if (side_pk_q2 == 1 && has_distance(range_q, range_p))
617 {
618 // Similarly, but the other way round.
619 // Q continues to the left.
620 ti.operations[0].operation = operation_union;
621 ti.operations[1].operation = operation_blocked;
622 ti.touch_only = true;
623 return true;
624 }
625 return false;
626 }
627 }
628
629 template
630 <
631 typename UniqueSubRange1,
632 typename UniqueSubRange2,
633 typename IntersectionInfo,
634 typename DirInfo,
635 typename SideCalculator,
636 typename UmbrellaStrategy
637 >
638 static inline void apply(UniqueSubRange1 const& range_p,
639 UniqueSubRange2 const& range_q,
640 TurnInfo& ti,
641 IntersectionInfo const& intersection_info,
642 DirInfo const& dir_info,
643 SideCalculator const& side,
644 UmbrellaStrategy const& umbrella_strategy)
645 {
646 assign_point_and_correct(ti, method_touch, intersection_info, dir_info);
647
648 bool const has_pk = ! range_p.is_last_segment();
649 bool const has_qk = ! range_q.is_last_segment();
650
651 int const side_pk_q1 = has_pk ? side.pk_wrt_q1() : 0;
652
653 int const side_qi_p1 = fun::verified_side(dir_info.sides.template get<1, 0>(),
654 range_p, range_q, umbrella_strategy, 0, 0);
655 int const side_qk_p1 = has_qk
656 ? fun::verified_side(side.qk_wrt_p1(), range_p, range_q,
657 umbrella_strategy, 0, 2)
658 : 0;
659
660 // If Qi and Qk are both at same side of Pi-Pj,
661 // or collinear (so: not opposite sides)
662 if (! opposite(side1: side_qi_p1, side2: side_qk_p1))
663 {
664 int const side_pk_q2 = has_pk && has_qk ? side.pk_wrt_q2() : 0;
665 int const side_pk_p = has_pk ? side.pk_wrt_p1() : 0;
666 int const side_qk_q = has_qk ? side.qk_wrt_q1() : 0;
667
668 bool const q_turns_left = side_qk_q == 1;
669
670 bool const block_q = side_qk_p1 == 0
671 && ! same(side1: side_qi_p1, side2: side_qk_q)
672 ;
673
674 // If Pk at same side as Qi/Qk
675 // (the "or" is for collinear case)
676 // or Q is fully collinear && P turns not to left
677 if (side_pk_p == side_qi_p1
678 || side_pk_p == side_qk_p1
679 || (side_qi_p1 == 0 && side_qk_p1 == 0 && side_pk_p != -1))
680 {
681 if (side_qk_p1 == 0 && side_pk_q1 == 0
682 && has_pk && has_qk
683 && handle_imperfect_touch(range_p, range_q, side_pk_q2, umbrella_strategy, ti))
684 {
685 // If q continues collinearly (opposite) with p, it should be blocked
686 // but (FP) not if there is just a tiny space in between
687 return;
688 }
689 // Collinear -> lines join, continue
690 // (#BRL2)
691 if (side_pk_q2 == 0 && ! block_q)
692 {
693 fun::template both_collinear<0, 1>(range_p, range_q, umbrella_strategy,
694 2, 2, ti);
695 return;
696 }
697
698 // Collinear opposite case -> block P
699 // (#BRL4, #BLR8)
700 if (side_pk_q1 == 0)
701 {
702 ti.operations[0].operation = operation_blocked;
703 // Q turns right -> union (both independent),
704 // Q turns left -> intersection
705 ti.operations[1].operation = block_q ? operation_blocked
706 : q_turns_left ? operation_intersection
707 : operation_union;
708 return;
709 }
710
711 // Pk between Qi and Qk
712 // (#BRL3, #BRL7)
713 if (between(side1: side_pk_q1, side2: side_pk_q2, turn: side_qk_q))
714 {
715 ui_else_iu(q_turns_left, ti);
716 if (block_q)
717 {
718 ti.operations[1].operation = operation_blocked;
719 }
720 return;
721 }
722
723 // Pk between Qk and P, so left of Qk (if Q turns right) and vv
724 // (#BRL1)
725 if (side_pk_q2 == -side_qk_q)
726 {
727 ui_else_iu(! q_turns_left, ti);
728 ti.touch_only = true;
729 return;
730 }
731
732 //
733 // (#BRL5, #BRL9)
734 if (side_pk_q1 == -side_qk_q)
735 {
736 uu_else_ii(! q_turns_left, ti);
737 if (block_q)
738 {
739 ti.operations[1].operation = operation_blocked;
740 }
741 else
742 {
743 ti.touch_only = true;
744 }
745 return;
746 }
747 }
748 else
749 {
750 // Pk at other side than Qi/Pk
751 ti.operations[0].operation = q_turns_left
752 ? operation_intersection
753 : operation_union;
754 ti.operations[1].operation = block_q
755 ? operation_blocked
756 : side_qi_p1 == 1 || side_qk_p1 == 1
757 ? operation_union
758 : operation_intersection;
759 if (! block_q)
760 {
761 ti.touch_only = true;
762 }
763
764 return;
765 }
766 }
767 else
768 {
769 // The qi/qk are opposite to each other, w.r.t. p1
770 // From left to right or from right to left
771 int const side_pk_p = has_pk
772 ? fun::verified_side(side.pk_wrt_p1(), range_p, range_p,
773 umbrella_strategy, 0, 2)
774 : 0;
775 bool const right_to_left = side_qk_p1 == 1;
776
777 // If p turns into direction of qi (1,2)
778 if (side_pk_p == side_qi_p1)
779 {
780 // Collinear opposite case -> block P
781 if (side_pk_q1 == 0)
782 {
783 ti.operations[0].operation = operation_blocked;
784 ti.operations[1].operation = right_to_left
785 ? operation_union : operation_intersection;
786 return;
787 }
788
789 if (side_pk_q1 == side_qk_p1)
790 {
791 uu_else_ii(right_to_left, ti);
792 ti.touch_only = true;
793 return;
794 }
795 }
796
797 // If p turns into direction of qk (4,5)
798 if (side_pk_p == side_qk_p1)
799 {
800 int const side_pk_q2 = has_pk ? side.pk_wrt_q2() : 0;
801
802 // Collinear case -> lines join, continue
803 if (side_pk_q2 == 0)
804 {
805 both(ti, operation_continue);
806 return;
807 }
808 if (side_pk_q2 == side_qk_p1)
809 {
810 ui_else_iu(right_to_left, ti);
811 ti.touch_only = true;
812 return;
813 }
814 }
815 // otherwise (3)
816 ui_else_iu(! right_to_left, ti);
817 return;
818 }
819 }
820};
821
822
823template
824<
825 typename TurnInfo,
826 typename VerifyPolicy
827>
828struct equal : public base_turn_handler
829{
830 using fun = turn_info_verification_functions<VerifyPolicy>;
831
832 template
833 <
834 typename UniqueSubRange1,
835 typename UniqueSubRange2,
836 typename IntersectionInfo,
837 typename DirInfo,
838 typename SideCalculator,
839 typename UmbrellaStrategy
840 >
841 static inline void apply(UniqueSubRange1 const& range_p,
842 UniqueSubRange2 const& range_q,
843 TurnInfo& ti,
844 IntersectionInfo const& info,
845 DirInfo const& ,
846 SideCalculator const& side,
847 UmbrellaStrategy const& umbrella_strategy)
848 {
849 // Copy the intersection point in TO direction
850 assign_point(ti, method_equal, info, non_opposite_to_index(info));
851
852 bool const has_pk = ! range_p.is_last_segment();
853 bool const has_qk = ! range_q.is_last_segment();
854
855 int const side_pk_q2 = has_pk && has_qk ? side.pk_wrt_q2() : 0;
856 int const side_pk_p = has_pk ? side.pk_wrt_p1() : 0;
857 int const side_qk_p = has_qk ? side.qk_wrt_p1() : 0;
858
859 if (has_pk && has_qk && side_pk_p == side_qk_p)
860 {
861 // They turn to the same side, or continue both collinearly
862 // To check for union/intersection, try to check side values
863 int const side_qk_p2 = side.qk_wrt_p2();
864
865 if (opposite(side1: side_qk_p2, side2: side_pk_q2))
866 {
867 ui_else_iu(side_pk_q2 == 1, ti);
868 return;
869 }
870 }
871
872 // If pk is collinear with qj-qk, they continue collinearly.
873 // This can be on either side of p1 (== q1), or collinear
874 // The second condition checks if they do not continue
875 // oppositely
876 if (side_pk_q2 == 0 && side_pk_p == side_qk_p)
877 {
878 fun::template both_collinear<0, 1>(range_p, range_q, umbrella_strategy, 2, 2, ti);
879 return;
880 }
881
882
883 // If they turn to same side (not opposite sides)
884 if (! opposite(side1: side_pk_p, side2: side_qk_p))
885 {
886 // If pk is left of q2 or collinear: p: union, q: intersection
887 ui_else_iu(side_pk_q2 != -1, ti);
888 }
889 else
890 {
891 // They turn opposite sides. If p turns left (or collinear),
892 // p: union, q: intersection
893 ui_else_iu(side_pk_p != -1, ti);
894 }
895 }
896};
897
898template
899<
900 typename TurnInfo,
901 typename VerifyPolicy
902>
903struct start : public base_turn_handler
904{
905 template
906 <
907 typename UniqueSubRange1,
908 typename UniqueSubRange2,
909 typename IntersectionInfo,
910 typename DirInfo,
911 typename SideCalculator,
912 typename UmbrellaStrategy
913 >
914 static inline bool apply(UniqueSubRange1 const& /*range_p*/,
915 UniqueSubRange2 const& /*range_q*/,
916 TurnInfo& ti,
917 IntersectionInfo const& info,
918 DirInfo const& dir_info,
919 SideCalculator const& side,
920 UmbrellaStrategy const& )
921 {
922 if BOOST_GEOMETRY_CONSTEXPR (! VerifyPolicy::use_start_turn)
923 {
924 return false;
925 }
926 else // else prevents unreachable code warning
927 {
928 // Start turns have either how_a = -1, or how_b = -1 (either p leaves or q leaves)
929 BOOST_GEOMETRY_ASSERT(dir_info.how_a != dir_info.how_b);
930 BOOST_GEOMETRY_ASSERT(dir_info.how_a == -1 || dir_info.how_b == -1);
931 BOOST_GEOMETRY_ASSERT(dir_info.how_a == 0 || dir_info.how_b == 0);
932
933 if (dir_info.how_b == -1)
934 {
935 // p --------------->
936 // |
937 // | q q leaves
938 // v
939 //
940
941 int const side_qj_p1 = side.qj_wrt_p1();
942 ui_else_iu(side_qj_p1 == -1, ti);
943 }
944 else if (dir_info.how_a == -1)
945 {
946 // p leaves
947 int const side_pj_q1 = side.pj_wrt_q1();
948 ui_else_iu(side_pj_q1 == 1, ti);
949 }
950
951 // Copy intersection point
952 assign_point_and_correct(ti, method_start, info, dir_info);
953 return true;
954 }
955 }
956};
957
958
959template
960<
961 typename TurnInfo,
962 typename AssignPolicy
963>
964struct equal_opposite : public base_turn_handler
965{
966 template
967 <
968 typename UniqueSubRange1,
969 typename UniqueSubRange2,
970 typename OutputIterator,
971 typename IntersectionInfo
972 >
973 static inline void apply(
974 UniqueSubRange1 const& /*range_p*/,
975 UniqueSubRange2 const& /*range_q*/,
976 /* by value: */ TurnInfo tp,
977 OutputIterator& out,
978 IntersectionInfo const& intersection_info)
979 {
980 // For equal-opposite segments, normally don't do anything.
981 if BOOST_GEOMETRY_CONSTEXPR (AssignPolicy::include_opposite)
982 {
983 tp.method = method_equal;
984 for (unsigned int i = 0; i < 2; i++)
985 {
986 tp.operations[i].operation = operation_opposite;
987 }
988 for (unsigned int i = 0; i < intersection_info.i_info().count; i++)
989 {
990 assign_point(tp, method_none, intersection_info.i_info(), i);
991 *out++ = tp;
992 }
993 }
994 }
995};
996
997template
998<
999 typename TurnInfo,
1000 typename VerifyPolicy
1001>
1002struct collinear : public base_turn_handler
1003{
1004 using fun = turn_info_verification_functions<VerifyPolicy>;
1005
1006 template
1007 <
1008 typename IntersectionInfo,
1009 typename UniqueSubRange1,
1010 typename UniqueSubRange2,
1011 typename DirInfo
1012 >
1013 static bool handle_as_equal(IntersectionInfo const& info,
1014 UniqueSubRange1 const& range_p,
1015 UniqueSubRange2 const& range_q,
1016 DirInfo const& dir_info)
1017 {
1018 if BOOST_GEOMETRY_CONSTEXPR (! VerifyPolicy::use_handle_as_equal)
1019 {
1020 return false;
1021 }
1022 else // else prevents unreachable code warning
1023 {
1024 int const arrival_p = dir_info.arrival[0];
1025 int const arrival_q = dir_info.arrival[1];
1026 if (arrival_p * arrival_q != -1 || info.count != 2)
1027 {
1028 // Code below assumes that either p or q arrives in the other segment
1029 return false;
1030 }
1031
1032 auto const dm = arrival_p == 1
1033 ? fun::distance_measure(info.intersections[1], range_q.at(1))
1034 : fun::distance_measure(info.intersections[1], range_p.at(1));
1035 decltype(dm) const zero = 0;
1036 return math::equals(dm, zero);
1037 }
1038 }
1039
1040 /*
1041 Either P arrives within Q (arrival_p == -1) or Q arrives within P.
1042
1043 Typical situation:
1044 ^q2
1045 /
1046 ^q1
1047 / ____ ip[1]
1048 //|p1 } this section of p/q is colllinear
1049 q0// | } ____ ip[0]
1050 / |
1051 / v
1052 p0 p2
1053
1054 P arrives (at p1) in segment Q (between q0 and q1).
1055 Therefore arrival_p == 1
1056 P (p2) goes to the right (-1). Follow P for intersection, or follow Q for union.
1057 Therefore if (arrival_p==1) and side_p==-1, result = iu
1058
1059 Complete table:
1060
1061 arrival P pk//p1 qk//q1 product case result
1062 1 1 1 CLL1 ui
1063 -1 1 -1 CLL2 iu
1064 1 1 1 CLR1 ui
1065 -1 -1 1 CLR2 ui
1066
1067 1 -1 -1 CRL1 iu
1068 -1 1 -1 CRL2 iu
1069 1 -1 -1 CRR1 iu
1070 -1 -1 1 CRR2 ui
1071
1072 1 0 0 CC1 cc
1073 -1 0 0 CC2 cc
1074
1075 Resulting in the rule:
1076 The arrival-info multiplied by the relevant side delivers the result.
1077 product = arrival * (pk//p1 or qk//q1)
1078
1079 Stated otherwise:
1080 - if P arrives: look at turn P
1081 - if Q arrives: look at turn Q
1082 - if P arrives and P turns left: union for P
1083 - if P arrives and P turns right: intersection for P
1084 - if Q arrives and Q turns left: union for Q (=intersection for P)
1085 - if Q arrives and Q turns right: intersection for Q (=union for P)
1086 */
1087 template
1088 <
1089 typename UniqueSubRange1,
1090 typename UniqueSubRange2,
1091 typename IntersectionInfo,
1092 typename DirInfo,
1093 typename SidePolicy
1094 >
1095 static inline void apply(
1096 UniqueSubRange1 const& range_p,
1097 UniqueSubRange2 const& range_q,
1098 TurnInfo& ti,
1099 IntersectionInfo const& info,
1100 DirInfo const& dir_info,
1101 SidePolicy const& side)
1102 {
1103 // Copy the intersection point in TO direction
1104 assign_point(ti, method_collinear, info, non_opposite_to_index(info));
1105
1106 int const arrival_p = dir_info.arrival[0];
1107 // Should not be 0, this is checked before
1108 BOOST_GEOMETRY_ASSERT(arrival_p != 0);
1109
1110 bool const has_pk = ! range_p.is_last_segment();
1111 bool const has_qk = ! range_q.is_last_segment();
1112 int const side_p = has_pk ? side.pk_wrt_p1() : 0;
1113 int const side_q = has_qk ? side.qk_wrt_q1() : 0;
1114
1115 // If p arrives, use p, else use q
1116 int const side_p_or_q = arrival_p == 1
1117 ? side_p
1118 : side_q
1119 ;
1120
1121 // Calculate product according to comments above.
1122 int const product = arrival_p * side_p_or_q;
1123
1124 if (product == 0)
1125 {
1126 both(ti, operation_continue);
1127 }
1128 else
1129 {
1130 ui_else_iu(product == 1, ti);
1131 }
1132
1133 // Calculate remaining distance. If it continues collinearly it is
1134 // measured until the end of the next segment
1135 ti.operations[0].remaining_distance
1136 = side_p == 0 && has_pk
1137 ? fun::distance_measure(ti.point, range_p.at(2))
1138 : fun::distance_measure(ti.point, range_p.at(1));
1139 ti.operations[1].remaining_distance
1140 = side_q == 0 && has_qk
1141 ? fun::distance_measure(ti.point, range_q.at(2))
1142 : fun::distance_measure(ti.point, range_q.at(1));
1143 }
1144};
1145
1146template
1147<
1148 typename TurnInfo,
1149 typename AssignPolicy
1150>
1151struct collinear_opposite : public base_turn_handler
1152{
1153private :
1154 /*
1155 arrival P arrival Q pk//p1 qk//q1 case result2 result
1156 --------------------------------------------------------------
1157 1 1 1 -1 CLO1 ix xu
1158 1 1 1 0 CLO2 ix (xx)
1159 1 1 1 1 CLO3 ix xi
1160
1161 1 1 0 -1 CCO1 (xx) xu
1162 1 1 0 0 CCO2 (xx) (xx)
1163 1 1 0 1 CCO3 (xx) xi
1164
1165 1 1 -1 -1 CRO1 ux xu
1166 1 1 -1 0 CRO2 ux (xx)
1167 1 1 -1 1 CRO3 ux xi
1168
1169 -1 1 -1 CXO1 xu
1170 -1 1 0 CXO2 (xx)
1171 -1 1 1 CXO3 xi
1172
1173 1 -1 1 CXO1 ix
1174 1 -1 0 CXO2 (xx)
1175 1 -1 -1 CXO3 ux
1176 */
1177
1178 template <unsigned int Index, typename IntersectionInfo>
1179 static inline bool set_tp(int side_rk_r, TurnInfo& tp,
1180 IntersectionInfo const& intersection_info)
1181 {
1182 BOOST_STATIC_ASSERT(Index <= 1);
1183
1184 operation_type blocked = operation_blocked;
1185 switch(side_rk_r)
1186 {
1187 case 1 :
1188 // Turning left on opposite collinear: intersection
1189 tp.operations[Index].operation = operation_intersection;
1190 break;
1191 case -1 :
1192 // Turning right on opposite collinear: union
1193 tp.operations[Index].operation = operation_union;
1194 break;
1195 case 0 :
1196 // No turn on opposite collinear: block, do not traverse
1197 // But this "xx" is usually ignored, it is useless to include
1198 // two operations blocked, so the whole point does not need
1199 // to be generated.
1200 // So return false to indicate nothing is to be done.
1201 if BOOST_GEOMETRY_CONSTEXPR (AssignPolicy::include_opposite)
1202 {
1203 tp.operations[Index].operation = operation_opposite;
1204 blocked = operation_opposite;
1205 }
1206 else
1207 {
1208 return false;
1209 }
1210 break;
1211 }
1212
1213 // The other direction is always blocked when collinear opposite
1214 tp.operations[1 - Index].operation = blocked;
1215
1216 // If P arrives within Q, set info on P (which is done above, index=0),
1217 // this turn-info belongs to the second intersection point, index=1
1218 // (see e.g. figure CLO1)
1219 assign_point(tp, method_collinear, intersection_info, 1 - Index);
1220 return true;
1221 }
1222
1223public:
1224 static inline void empty_transformer(TurnInfo &) {}
1225
1226 template
1227 <
1228 typename UniqueSubRange1,
1229 typename UniqueSubRange2,
1230 typename OutputIterator,
1231 typename IntersectionInfo,
1232 typename SidePolicy
1233 >
1234 static inline void apply(
1235 UniqueSubRange1 const& range_p,
1236 UniqueSubRange2 const& range_q,
1237
1238 // Opposite collinear can deliver 2 intersection points,
1239 TurnInfo const& tp_model,
1240 OutputIterator& out,
1241
1242 IntersectionInfo const& intersection_info,
1243 SidePolicy const& side)
1244 {
1245 apply(range_p, range_q,
1246 tp_model, out, intersection_info, side, empty_transformer);
1247 }
1248
1249 template
1250 <
1251 typename UniqueSubRange1,
1252 typename UniqueSubRange2,
1253 typename OutputIterator,
1254 typename IntersectionInfo,
1255 typename SidePolicy,
1256 typename TurnTransformer
1257 >
1258 static inline void apply(
1259 UniqueSubRange1 const& range_p,
1260 UniqueSubRange2 const& range_q,
1261
1262 // Opposite collinear can deliver 2 intersection points,
1263 TurnInfo const& tp_model,
1264 OutputIterator& out,
1265
1266 IntersectionInfo const& info,
1267 SidePolicy const& side,
1268 TurnTransformer turn_transformer)
1269 {
1270 TurnInfo tp = tp_model;
1271
1272 int const arrival_p = info.d_info().arrival[0];
1273 int const arrival_q = info.d_info().arrival[1];
1274
1275 // If P arrives within Q, there is a turn dependent on P
1276 if ( arrival_p == 1
1277 && ! range_p.is_last_segment()
1278 && set_tp<0>(side.pk_wrt_p1(), tp, info.i_info()) )
1279 {
1280 turn_transformer(tp);
1281
1282 *out++ = tp;
1283 }
1284
1285 // If Q arrives within P, there is a turn dependent on Q
1286 if ( arrival_q == 1
1287 && ! range_q.is_last_segment()
1288 && set_tp<1>(side.qk_wrt_q1(), tp, info.i_info()) )
1289 {
1290 turn_transformer(tp);
1291
1292 *out++ = tp;
1293 }
1294
1295 if BOOST_GEOMETRY_CONSTEXPR (AssignPolicy::include_opposite)
1296 {
1297 // Handle cases not yet handled above
1298 if ((arrival_q == -1 && arrival_p == 0)
1299 || (arrival_p == -1 && arrival_q == 0))
1300 {
1301 for (unsigned int i = 0; i < 2; i++)
1302 {
1303 tp.operations[i].operation = operation_opposite;
1304 }
1305 for (unsigned int i = 0; i < info.i_info().count; i++)
1306 {
1307 assign_point(tp, method_collinear, info.i_info(), i);
1308 *out++ = tp;
1309 }
1310 }
1311 }
1312
1313 }
1314};
1315
1316
1317template
1318<
1319 typename TurnInfo
1320>
1321struct crosses : public base_turn_handler
1322{
1323 template <typename IntersectionInfo, typename DirInfo>
1324 static inline void apply(TurnInfo& ti,
1325 IntersectionInfo const& intersection_info,
1326 DirInfo const& dir_info)
1327 {
1328 assign_point(ti, method_crosses, intersection_info, 0);
1329
1330 // In all cases:
1331 // If Q crosses P from left to right
1332 // Union: take P
1333 // Intersection: take Q
1334 // Otherwise: vice versa
1335 int const side_qi_p1 = dir_info.sides.template get<1, 0>();
1336 unsigned int const index = side_qi_p1 == 1 ? 0 : 1;
1337 ti.operations[index].operation = operation_union;
1338 ti.operations[1 - index].operation = operation_intersection;
1339 }
1340};
1341
1342struct only_convert : public base_turn_handler
1343{
1344 template<typename TurnInfo, typename IntersectionInfo>
1345 static inline void apply(TurnInfo& ti, IntersectionInfo const& intersection_info)
1346 {
1347 assign_point(ti, method_none, intersection_info, 0);
1348 ti.operations[0].operation = operation_continue;
1349 ti.operations[1].operation = operation_continue;
1350 }
1351};
1352
1353/*!
1354\brief Policy doing nothing
1355\details get_turn_info can have an optional policy include extra
1356 truns. By default it does not, and this class is that default.
1357 */
1358struct assign_null_policy
1359{
1360 static bool const include_no_turn = false;
1361 static bool const include_degenerate = false;
1362 static bool const include_opposite = false;
1363 static bool const include_start_turn = false;
1364};
1365
1366struct assign_policy_only_start_turns
1367{
1368 static bool const include_no_turn = false;
1369 static bool const include_degenerate = false;
1370 static bool const include_opposite = false;
1371 static bool const include_start_turn = true;
1372};
1373
1374/*!
1375 \brief Turn information: intersection point, method, and turn information
1376 \details Information necessary for traversal phase (a phase
1377 of the overlay process). The information is gathered during the
1378 get_turns (segment intersection) phase.
1379 \tparam AssignPolicy policy to assign extra info,
1380 e.g. to calculate distance from segment's first points
1381 to intersection points.
1382 It also defines if a certain class of points
1383 (degenerate, non-turns) should be included.
1384 */
1385template<typename AssignPolicy>
1386struct get_turn_info
1387{
1388 // Intersect a segment p with a segment q
1389 // Both p and q are modelled as sub_ranges to provide more points
1390 // to be able to give more information about the turn (left/right)
1391 template
1392 <
1393 typename UniqueSubRange1,
1394 typename UniqueSubRange2,
1395 typename TurnInfo,
1396 typename UmbrellaStrategy,
1397 typename RobustPolicy,
1398 typename OutputIterator
1399 >
1400 static inline OutputIterator apply(
1401 UniqueSubRange1 const& range_p,
1402 UniqueSubRange2 const& range_q,
1403 TurnInfo const& tp_model,
1404 UmbrellaStrategy const& umbrella_strategy,
1405 RobustPolicy const& robust_policy,
1406 OutputIterator out)
1407 {
1408 typedef intersection_info
1409 <
1410 UniqueSubRange1, UniqueSubRange2,
1411 typename TurnInfo::point_type,
1412 UmbrellaStrategy,
1413 RobustPolicy
1414 > inters_info;
1415
1416 inters_info inters(range_p, range_q, umbrella_strategy, robust_policy);
1417
1418 char const method = inters.d_info().how;
1419
1420 if (method == 'd')
1421 {
1422 // Disjoint
1423 return out;
1424 }
1425
1426 // Copy, to copy possibly extended fields
1427 TurnInfo tp = tp_model;
1428
1429 bool const handle_as_touch_interior = method == 'm';
1430 bool const handle_as_cross = method == 'i';
1431 bool handle_as_touch = method == 't';
1432 bool handle_as_equal = method == 'e';
1433 bool const handle_as_collinear = method == 'c';
1434 bool const handle_as_degenerate = method == '0';
1435 bool const handle_as_start = method == 's';
1436
1437 // (angle, from)
1438 bool do_only_convert = method == 'a' || method == 'f';
1439
1440 if (handle_as_start)
1441 {
1442 // It is in some cases necessary to handle a start turn
1443 using handler = start<TurnInfo, verify_policy_aa>;
1444 if (BOOST_GEOMETRY_CONDITION(AssignPolicy::include_start_turn)
1445 && handler::apply(range_p, range_q, tp,
1446 inters.i_info(), inters.d_info(), inters.sides(),
1447 umbrella_strategy))
1448 {
1449 *out++ = tp;
1450 }
1451 else
1452 {
1453 do_only_convert = true;
1454 }
1455 }
1456
1457 if (handle_as_touch_interior)
1458 {
1459 using handler = touch_interior<TurnInfo, verify_policy_aa>;
1460
1461 if ( inters.d_info().arrival[1] == 1 )
1462 {
1463 // Q arrives
1464 if (handler::handle_as_touch(inters.i_info(), range_p))
1465 {
1466 handle_as_touch = true;
1467 }
1468 else
1469 {
1470 handler::template apply<0>(range_p, range_q, tp, inters.i_info(), inters.d_info(),
1471 inters.sides(), umbrella_strategy);
1472 *out++ = tp;
1473 }
1474 }
1475 else
1476 {
1477 // P arrives, swap p/q
1478 if (handler::handle_as_touch(inters.i_info(), range_q))
1479 {
1480 handle_as_touch = true;
1481 }
1482 else
1483 {
1484 handler::template apply<1>(range_q, range_p, tp, inters.i_info(), inters.d_info(),
1485 inters.swapped_sides(), umbrella_strategy);
1486 *out++ = tp;
1487 }
1488 }
1489 }
1490
1491 if (handle_as_cross)
1492 {
1493 crosses<TurnInfo>::apply(tp, inters.i_info(), inters.d_info());
1494 *out++ = tp;
1495 }
1496
1497 if (handle_as_touch)
1498 {
1499 // Touch: both segments arrive at the intersection point
1500 using handler = touch<TurnInfo, verify_policy_aa>;
1501 handler::apply(range_p, range_q, tp, inters.i_info(), inters.d_info(), inters.sides(),
1502 umbrella_strategy);
1503 *out++ = tp;
1504 }
1505
1506 if (handle_as_collinear)
1507 {
1508 // Collinear
1509 if ( ! inters.d_info().opposite )
1510 {
1511 using handler = collinear<TurnInfo, verify_policy_aa>;
1512 if (inters.d_info().arrival[0] == 0
1513 || handler::handle_as_equal(inters.i_info(), range_p, range_q, inters.d_info()))
1514 {
1515 // Both segments arrive at the second intersection point
1516 handle_as_equal = true;
1517 }
1518 else
1519 {
1520 handler::apply(range_p, range_q, tp, inters.i_info(),
1521 inters.d_info(), inters.sides());
1522 *out++ = tp;
1523 }
1524 }
1525 else
1526 {
1527 collinear_opposite
1528 <
1529 TurnInfo,
1530 AssignPolicy
1531 >::apply(range_p, range_q, tp, out, inters, inters.sides());
1532 // Zero, or two, turn points are assigned to *out++
1533 }
1534 }
1535
1536 if (handle_as_equal)
1537 {
1538 if ( ! inters.d_info().opposite )
1539 {
1540 // Both equal
1541 // or collinear-and-ending at intersection point
1542 using handler = equal<TurnInfo, verify_policy_aa>;
1543 handler::apply(range_p, range_q, tp,
1544 inters.i_info(), inters.d_info(), inters.sides(),
1545 umbrella_strategy);
1546 if (handle_as_collinear)
1547 {
1548 // Keep info as collinear,
1549 // so override already assigned method
1550 tp.method = method_collinear;
1551 }
1552 *out++ = tp;
1553 }
1554 else
1555 {
1556 equal_opposite
1557 <
1558 TurnInfo,
1559 AssignPolicy
1560 >::apply(range_p, range_q, tp, out, inters);
1561 // Zero, or two, turn points are assigned to *out++
1562 }
1563 }
1564
1565 if ((handle_as_degenerate
1566 && BOOST_GEOMETRY_CONDITION(AssignPolicy::include_degenerate))
1567 || (do_only_convert
1568 && BOOST_GEOMETRY_CONDITION(AssignPolicy::include_no_turn)))
1569 {
1570 if (inters.i_info().count > 0)
1571 {
1572 only_convert::apply(tp, inters.i_info());
1573 *out++ = tp;
1574 }
1575 }
1576
1577 return out;
1578 }
1579};
1580
1581
1582}} // namespace detail::overlay
1583#endif //DOXYGEN_NO_DETAIL
1584
1585
1586}} // namespace boost::geometry
1587
1588
1589#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HPP
1590

source code of boost/libs/geometry/include/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp