detail/overlay/get_turn_info.hpp

0001 // Boost.Geometry
0002
0003 // Copyright (c) 2007-2023 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2017-2023 Adam Wulkiewicz, Lodz, Poland.
0005
0006 // This file was modified by Oracle on 2015-2022.
0007 // Modifications copyright (c) 2015-2022 Oracle and/or its affiliates.
0008 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0009
0010 // Use, modification and distribution is subject to the Boost Software License,
0011 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0012 // http://www.boost.org/LICENSE_1_0.txt)
0013
0014 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HPP
0015 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HPP
0016
0017 #include <boost/core/ignore_unused.hpp>
0018 #include <boost/throw_exception.hpp>
0019
0020 #include <boost/geometry/core/access.hpp>
0021 #include <boost/geometry/core/assert.hpp>
0022 #include <boost/geometry/core/config.hpp>
0023 #include <boost/geometry/core/exception.hpp>
0024
0025 #include <boost/geometry/algorithms/convert.hpp>
0026 #include <boost/geometry/algorithms/detail/overlay/get_distance_measure.hpp>
0027 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
0028 #include <boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp>
0029
0030 #include <boost/geometry/util/constexpr.hpp>
0031
0032
0033 namespace boost { namespace geometry
0034 {
0035
0036 #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
0037 class turn_info_exception : public geometry::exception
0038 {
0039     std::string message;
0040 public:
0041
0042     // NOTE: "char" will be replaced by enum in future version
0043     inline turn_info_exception(char const method)
0044     {
0045         message = "Boost.Geometry Turn exception: ";
0046         message += method;
0047     }
0048
0049     virtual char const* What() const noexcept
0050     {
0051         return message.c_str();
0052     }
0053 };
0054 #endif
0055
0056 #ifndef DOXYGEN_NO_DETAIL
0057 namespace detail { namespace overlay
0058 {
0059
0060
0061 struct policy_verify_nothing
0062 {
0063     static bool const use_side_verification = false;
0064     static bool const use_start_turn = false;
0065     static bool const use_handle_as_touch = false;
0066     static bool const use_handle_as_equal = false;
0067     static bool const use_handle_imperfect_touch = false;
0068 };
0069
0070 struct policy_verify_all
0071 {
0072     static bool const use_side_verification = true;
0073     static bool const use_start_turn = true;
0074     static bool const use_handle_as_touch = true;
0075     static bool const use_handle_as_equal = true;
0076     static bool const use_handle_imperfect_touch = true;
0077 };
0078
0079
0080 #if defined(BOOST_GEOMETRY_USE_RESCALING)
0081 using verify_policy_aa = policy_verify_nothing;
0082 #else
0083 using verify_policy_aa = policy_verify_all;
0084 #endif
0085
0086 using verify_policy_ll = policy_verify_nothing;
0087 using verify_policy_la = policy_verify_nothing;
0088
0089
0090 struct base_turn_handler
0091 {
0092     // Returns true if both sides are opposite
0093     static inline bool opposite(int side1, int side2)
0094     {
0095         // We cannot state side1 == -side2, because 0 == -0
0096         // So either side1*side2==-1 or side1==-side2 && side1 != 0
0097         return side1 * side2 == -1;
0098     }
0099
0100     // Same side of a segment (not being 0)
0101     static inline bool same(int side1, int side2)
0102     {
0103         return side1 * side2 == 1;
0104     }
0105
0106     // Both get the same operation
0107     template <typename TurnInfo>
0108     static inline void both(TurnInfo& ti, operation_type const op)
0109     {
0110         ti.operations[0].operation = op;
0111         ti.operations[1].operation = op;
0112     }
0113
0114     // If condition, first union/second intersection, else vice versa
0115     template <typename TurnInfo>
0116     static inline void ui_else_iu(bool condition, TurnInfo& ti)
0117     {
0118         ti.operations[0].operation = condition
0119                     ? operation_union : operation_intersection;
0120         ti.operations[1].operation = condition
0121                     ? operation_intersection : operation_union;
0122     }
0123
0124     // If condition, both union, else both intersection
0125     template <typename TurnInfo>
0126     static inline void uu_else_ii(bool condition, TurnInfo& ti)
0127     {
0128         both(ti, condition ? operation_union : operation_intersection);
0129     }
0130
0131     template <typename TurnInfo, typename IntersectionInfo>
0132     static inline void assign_point(TurnInfo& ti,
0133                 method_type method,
0134                 IntersectionInfo const& info, unsigned int index)
0135     {
0136         ti.method = method;
0137
0138         BOOST_GEOMETRY_ASSERT(index < info.count);
0139
0140         geometry::convert(info.intersections[index], ti.point);
0141         ti.operations[0].fraction = info.fractions[index].robust_ra;
0142         ti.operations[1].fraction = info.fractions[index].robust_rb;
0143     }
0144
0145     template <typename TurnInfo, typename IntersectionInfo, typename DirInfo>
0146     static inline void assign_point_and_correct(TurnInfo& ti,
0147                 method_type method,
0148                 IntersectionInfo const& info, DirInfo const& dir_info)
0149     {
0150         ti.method = method;
0151
0152         // For touch/touch interior always take the intersection point 0
0153         // (usually there is only one - but if collinear is handled as touch, both could be taken).
0154         static int const index = 0;
0155
0156         geometry::convert(info.intersections[index], ti.point);
0157
0158         for (int i = 0; i < 2; i++)
0159         {
0160             if (dir_info.arrival[i] == 1)
0161             {
0162                 // The segment arrives at the intersection point, its fraction should be 1
0163                 // (due to precision it might be nearly so, but not completely, in rare cases)
0164                 ti.operations[i].fraction = {1, 1};
0165             }
0166             else if (dir_info.arrival[i] == -1)
0167             {
0168                 // The segment leaves from the intersection point, likewise its fraction should be 0
0169                 ti.operations[i].fraction = {0, 1};
0170             }
0171             else
0172             {
0173                 ti.operations[i].fraction = i == 0 ? info.fractions[index].robust_ra
0174                                                    : info.fractions[index].robust_rb;
0175             }
0176         }
0177     }
0178
0179     template <typename IntersectionInfo>
0180     static inline unsigned int non_opposite_to_index(IntersectionInfo const& info)
0181     {
0182         return info.fractions[0].robust_rb < info.fractions[1].robust_rb
0183             ? 1 : 0;
0184     }
0185
0186 };
0187
0188 template<typename VerifyPolicy>
0189 struct turn_info_verification_functions
0190 {
0191     template <typename Point1, typename Point2>
0192     static inline
0193     typename select_coordinate_type<Point1, Point2>::type
0194     distance_measure(Point1 const& a, Point2 const& b)
0195     {
0196         // TODO: revise this using comparable distance for various
0197         // coordinate systems
0198         using coor_t = typename select_coordinate_type<Point1, Point2>::type;
0199
0200         coor_t const dx = get<0>(a) - get<0>(b);
0201         coor_t const dy = get<1>(a) - get<1>(b);
0202         return dx * dx + dy * dy;
0203     }
0204
0205     template
0206     <
0207             std::size_t IndexP,
0208             std::size_t IndexQ,
0209             typename UniqueSubRange1,
0210             typename UniqueSubRange2,
0211             typename UmbrellaStrategy,
0212             typename TurnInfo
0213     >
0214     static inline void set_both_verified(
0215             UniqueSubRange1 const& range_p,
0216             UniqueSubRange2 const& range_q,
0217             UmbrellaStrategy const& umbrella_strategy,
0218             std::size_t index_p, std::size_t index_q,
0219             TurnInfo& ti)
0220     {
0221         BOOST_GEOMETRY_ASSERT(IndexP + IndexQ == 1);
0222         BOOST_GEOMETRY_ASSERT(index_p > 0 && index_p <= 2);
0223         BOOST_GEOMETRY_ASSERT(index_q > 0 && index_q <= 2);
0224
0225         using distance_measure_result_type = typename geometry::coordinate_type<decltype(ti.point)>::type;
0226
0227         bool const p_in_range = index_p < range_p.size();
0228         bool const q_in_range = index_q < range_q.size();
0229         ti.operations[IndexP].remaining_distance
0230             = p_in_range
0231               ? distance_measure(ti.point, range_p.at(index_p))
0232               : distance_measure_result_type{0};
0233         ti.operations[IndexQ].remaining_distance
0234             = q_in_range
0235               ? distance_measure(ti.point, range_q.at(index_q))
0236               : distance_measure_result_type{0};
0237
0238         if (p_in_range && q_in_range)
0239         {
0240             // pk/q2 is considered as collinear, but there might be
0241             // a tiny measurable difference. If so, use that.
0242             // Calculate pk // qj-qk
0243             bool const p_closer
0244                 = ti.operations[IndexP].remaining_distance
0245                   <  ti.operations[IndexQ].remaining_distance;
0246             auto const dm
0247                 = p_closer
0248                 ? get_distance_measure(range_q.at(index_q - 1),
0249                                        range_q.at(index_q), range_p.at(index_p),
0250                                        umbrella_strategy)
0251                 : get_distance_measure(range_p.at(index_p - 1),
0252                                        range_p.at(index_p), range_q.at(index_q),
0253                                        umbrella_strategy);
0254
0255             if (! dm.is_zero())
0256             {
0257                 // Not truely collinear, distinguish for union/intersection
0258                 // If p goes left (positive), take that for a union
0259                 bool const p_left
0260                     = p_closer ? dm.is_positive() : dm.is_negative();
0261
0262                 ti.operations[IndexP].operation = p_left
0263                             ? operation_union : operation_intersection;
0264                 ti.operations[IndexQ].operation = p_left
0265                             ? operation_intersection : operation_union;
0266                 return;
0267             }
0268         }
0269
0270         base_turn_handler::both(ti, operation_continue);
0271     }
0272
0273     template
0274     <
0275             std::size_t IndexP,
0276             std::size_t IndexQ,
0277             typename UniqueSubRange1,
0278             typename UniqueSubRange2,
0279             typename UmbrellaStrategy,
0280             typename TurnInfo
0281     >
0282     static inline void both_collinear(
0283             UniqueSubRange1 const& range_p,
0284             UniqueSubRange2 const& range_q,
0285             UmbrellaStrategy const& umbrella_strategy,
0286             std::size_t index_p, std::size_t index_q,
0287             TurnInfo& ti)
0288     {
0289         if BOOST_GEOMETRY_CONSTEXPR (VerifyPolicy::use_side_verification)
0290         {
0291             set_both_verified<IndexP, IndexQ>(range_p, range_q, umbrella_strategy,
0292                                               index_p, index_q, ti);
0293         }
0294         else
0295         {
0296             base_turn_handler::both(ti, operation_continue);
0297         }
0298     }
0299
0300     template
0301     <
0302         typename UniqueSubRange1,
0303         typename UniqueSubRange2,
0304         typename UmbrellaStrategy
0305     >
0306     static inline int verified_side(int side,
0307                                     UniqueSubRange1 const& range_p,
0308                                     UniqueSubRange2 const& range_q,
0309                                     UmbrellaStrategy const& umbrella_strategy,
0310                                     int index_p, int index_q)
0311     {
0312         if BOOST_GEOMETRY_CONSTEXPR (VerifyPolicy::use_side_verification)
0313         {
0314             if (side == 0)
0315             {
0316                 if (index_p >= 1 && range_p.is_last_segment())
0317                 {
0318                     return 0;
0319                 }
0320                 if (index_q >= 2 && range_q.is_last_segment())
0321                 {
0322                     return 0;
0323                 }
0324
0325                 auto const dm = get_distance_measure(range_p.at(index_p),
0326                                                      range_p.at(index_p + 1),
0327                                                      range_q.at(index_q),
0328                                                      umbrella_strategy);
0329                 static decltype(dm.measure) const zero = 0;
0330                 return dm.measure == zero ? 0 : dm.measure > zero ? 1 : -1;
0331             }
0332         }
0333
0334         return side;
0335     }
0336
0337 };
0338
0339
0340 template
0341 <
0342     typename TurnInfo,
0343     typename VerifyPolicy
0344 >
0345 struct touch_interior : public base_turn_handler
0346 {
0347     using fun = turn_info_verification_functions<VerifyPolicy>;
0348
0349     template
0350     <
0351         typename IntersectionInfo,
0352         typename UniqueSubRange
0353     >
0354     static bool handle_as_touch(IntersectionInfo const& info,
0355                                 UniqueSubRange const& non_touching_range)
0356     {
0357         if BOOST_GEOMETRY_CONSTEXPR (! VerifyPolicy::use_handle_as_touch)
0358         {
0359             return false;
0360         }
0361         else // else prevents unreachable code warning
0362         {
0363             //
0364             //
0365             //                         ^  Q(i)                ^ P(i)
0366             //                          \                    /
0367             //                           \                  /
0368             //                            \                /
0369             //                             \              /
0370             //                              \            /
0371             //                               \          /
0372             //                                \        /
0373             //                                 \      /
0374             //                                  \    /
0375             //                                   \  / it is about buffer_rt_r
0376             //                  P(k)              v/  they touch here "in the middle", but at the intersection...
0377             //                  <---------------->v   there is no follow up IP
0378             //                                   /
0379             //                                  /
0380             //                                 /
0381             //                                /
0382             //                               /
0383             //                              /
0384             //                             v Q(k)
0385             //
0386
0387             // Measure where the IP is located. If it is really close to the end,
0388             // then there is no space for the next IP (on P(1)/Q(2). A "from"
0389             // intersection will be generated, but those are never handled.
0390             // Therefore handle it as a normal touch (two segments arrive at the
0391             // intersection point). It currently checks for zero, but even a
0392             // distance a little bit larger would do.
0393             auto const dm = fun::distance_measure(info.intersections[0], non_touching_range.at(1));
0394             decltype(dm) const zero = 0;
0395             bool const result = math::equals(dm, zero);
0396             return result;
0397         }
0398     }
0399
0400     // Index: 0, P is the interior, Q is touching and vice versa
0401     template
0402     <
0403         unsigned int Index,
0404         typename UniqueSubRange1,
0405         typename UniqueSubRange2,
0406         typename IntersectionInfo,
0407         typename DirInfo,
0408         typename SidePolicy,
0409         typename UmbrellaStrategy
0410     >
0411     static inline void apply(UniqueSubRange1 const& range_p,
0412                 UniqueSubRange2 const& range_q,
0413                 TurnInfo& ti,
0414                 IntersectionInfo const& intersection_info,
0415                 DirInfo const& dir_info,
0416                 SidePolicy const& side,
0417                 UmbrellaStrategy const& umbrella_strategy)
0418     {
0419         assign_point_and_correct(ti, method_touch_interior, intersection_info, dir_info);
0420
0421         // Both segments of q touch segment p somewhere in its interior
0422         // 1) We know: if q comes from LEFT or RIGHT
0423         // (i.e. dir_info.sides.get<Index,0>() == 1 or -1)
0424         // 2) Important is: if q_k goes to LEFT, RIGHT, COLLINEAR
0425         //    and, if LEFT/COLL, if it is lying LEFT or RIGHT w.r.t. q_i
0426
0427         BOOST_STATIC_ASSERT(Index <= 1);
0428         static unsigned int const index_p = Index;
0429         static unsigned int const index_q = 1 - Index;
0430
0431         bool const has_pk = ! range_p.is_last_segment();
0432         bool const has_qk = ! range_q.is_last_segment();
0433         int const side_qi_p = dir_info.sides.template get<index_q, 0>();
0434         int const side_qk_p = has_qk ? side.qk_wrt_p1() : 0;
0435
0436         if (side_qi_p == -side_qk_p)
0437         {
0438             // Q crosses P from left->right or from right->left (test "ML1")
0439             // Union: folow P (left->right) or Q (right->left)
0440             // Intersection: other turn
0441             unsigned int index = side_qk_p == -1 ? index_p : index_q;
0442             ti.operations[index].operation = operation_union;
0443             ti.operations[1 - index].operation = operation_intersection;
0444             return;
0445         }
0446
0447         int const side_qk_q = has_qk ? side.qk_wrt_q1() : 0;
0448
0449         // Only necessary if rescaling is turned off:
0450         int const side_pj_q2 = has_qk ? side.pj_wrt_q2() : 0;
0451
0452         if (side_qi_p == -1 && side_qk_p == -1 && side_qk_q == 1)
0453         {
0454             // Q turns left on the right side of P (test "MR3")
0455             // Both directions for "intersection"
0456             both(ti, operation_intersection);
0457             ti.touch_only = true;
0458         }
0459         else if (side_qi_p == 1 && side_qk_p == 1 && side_qk_q == -1)
0460         {
0461             if (has_qk && side_pj_q2 == -1)
0462             {
0463                 // Q turns right on the left side of P (test "ML3")
0464                 // Union: take both operations
0465                 // Intersection: skip
0466                 both(ti, operation_union);
0467             }
0468             else
0469             {
0470                 // q2 is collinear with p1, so it does not turn back. This
0471                 // can happen in floating point precision. In this case,
0472                 // block one of the operations to avoid taking that path.
0473                 ti.operations[index_p].operation = operation_union;
0474                 ti.operations[index_q].operation = operation_blocked;
0475             }
0476             ti.touch_only = true;
0477         }
0478         else if (side_qi_p == side_qk_p && side_qi_p == side_qk_q)
0479         {
0480             // Q turns left on the left side of P (test "ML2")
0481             // or Q turns right on the right side of P (test "MR2")
0482             // Union: take left turn (Q if Q turns left, P if Q turns right)
0483             // Intersection: other turn
0484             unsigned int index = side_qk_q == 1 ? index_q : index_p;
0485             if (has_qk && side_pj_q2 == 0)
0486             {
0487                 // Even though sides xk w.r.t. 1 are distinct, pj is collinear
0488                 // with q. Therefore swap the path
0489                 index = 1 - index;
0490             }
0491
0492             if (has_pk && has_qk && opposite(side_pj_q2, side_qi_p))
0493             {
0494                 // Without rescaling, floating point requires extra measures
0495                 int const side_qj_p1 = side.qj_wrt_p1();
0496                 int const side_qj_p2 = side.qj_wrt_p2();
0497
0498                 if (same(side_qj_p1, side_qj_p2))
0499                 {
0500                     int const side_pj_q1 = side.pj_wrt_q1();
0501                     if (opposite(side_pj_q1, side_pj_q2))
0502                     {
0503                         index = 1 - index;
0504                     }
0505                 }
0506             }
0507
0508             ti.operations[index].operation = operation_union;
0509             ti.operations[1 - index].operation = operation_intersection;
0510             ti.touch_only = true;
0511         }
0512         else if (side_qk_p == 0)
0513         {
0514             // Q intersects on interior of P and continues collinearly
0515             if (side_qk_q == side_qi_p)
0516             {
0517                 fun::template both_collinear<index_p, index_q>(range_p, range_q, umbrella_strategy,
0518                                                                1, 2, ti);
0519             }
0520             else
0521             {
0522                 // Opposite direction, which is never travelled.
0523                 // If Q turns left, P continues for intersection
0524                 // If Q turns right, P continues for union
0525                 ti.operations[index_p].operation = side_qk_q == 1
0526                     ? operation_intersection
0527                     : operation_union;
0528                 ti.operations[index_q].operation = operation_blocked;
0529             }
0530         }
0531         else
0532         {
0533             // Should not occur!
0534             ti.method = method_error;
0535         }
0536     }
0537 };
0538
0539
0540 template
0541 <
0542     typename TurnInfo,
0543     typename VerifyPolicy
0544 >
0545 struct touch : public base_turn_handler
0546 {
0547     using fun = turn_info_verification_functions<VerifyPolicy>;
0548
0549     static inline bool between(int side1, int side2, int turn)
0550     {
0551         return side1 == side2 && ! opposite(side1, turn);
0552     }
0553
0554     template
0555     <
0556         typename UniqueSubRange1,
0557         typename UniqueSubRange2,
0558         typename UmbrellaStrategy
0559     >
0560     static inline bool handle_imperfect_touch(UniqueSubRange1 const& range_p,
0561                                               UniqueSubRange2 const& range_q,
0562                                               int side_pk_q2,
0563                                               UmbrellaStrategy const& umbrella_strategy,
0564                                               TurnInfo& ti)
0565     {
0566         if BOOST_GEOMETRY_CONSTEXPR (! VerifyPolicy::use_handle_imperfect_touch)
0567         {
0568             return false;
0569         }
0570         else // else prevents unreachable code warning
0571         {
0572             //  Q
0573             //  ^
0574             // ||
0575             // ||
0576             // |^----
0577             // >----->P
0578             // *            * they touch here (P/Q are (nearly) on top)
0579             //
0580             // Q continues from where P comes.
0581             // P continues from where Q comes
0582             // This is often a blocking situation,
0583             // unless there are FP issues: there might be a distance
0584             // between Pj and Qj, in that case handle it as a union.
0585             //
0586             // Exaggerated:
0587             //  Q
0588             //  ^           Q is nearly vertical
0589             //   \          but not completely - and still ends above P
0590             // |  \qj       In this case it should block P and
0591             // |  ^------   set Q to Union
0592             // >----->P     qj is LEFT of P1 and pi is LEFT of Q2
0593             //              (the other way round is also possible)
0594
0595             auto has_distance = [&](auto const& r1, auto const& r2) -> bool
0596             {
0597                 auto const d1 = get_distance_measure(r1.at(0), r1.at(1), r2.at(1), umbrella_strategy);
0598                 auto const d2 = get_distance_measure(r2.at(1), r2.at(2), r1.at(0), umbrella_strategy);
0599                 return d1.measure > 0 && d2.measure > 0;
0600             };
0601
0602             if (side_pk_q2 == -1 && has_distance(range_p, range_q))
0603             {
0604                 // Even though there is a touch, Q(j) is left of P1
0605                 // and P(i) is still left from Q2.
0606                 // Q continues to the right.
0607                 // It can continue.
0608                 ti.operations[0].operation = operation_blocked;
0609                 // Q turns right -> union (both independent),
0610                 // Q turns left -> intersection
0611                 ti.operations[1].operation = operation_union;
0612                 ti.touch_only = true;
0613                 return true;
0614             }
0615
0616             if (side_pk_q2 == 1 && has_distance(range_q, range_p))
0617             {
0618                 // Similarly, but the other way round.
0619                 // Q continues to the left.
0620                 ti.operations[0].operation = operation_union;
0621                 ti.operations[1].operation = operation_blocked;
0622                 ti.touch_only = true;
0623                 return true;
0624             }
0625             return false;
0626         }
0627     }
0628
0629     template
0630     <
0631         typename UniqueSubRange1,
0632         typename UniqueSubRange2,
0633         typename IntersectionInfo,
0634         typename DirInfo,
0635         typename SideCalculator,
0636         typename UmbrellaStrategy
0637     >
0638     static inline void apply(UniqueSubRange1 const& range_p,
0639                 UniqueSubRange2 const& range_q,
0640                 TurnInfo& ti,
0641                 IntersectionInfo const& intersection_info,
0642                 DirInfo const& dir_info,
0643                 SideCalculator const& side,
0644                 UmbrellaStrategy const& umbrella_strategy)
0645     {
0646         assign_point_and_correct(ti, method_touch, intersection_info, dir_info);
0647
0648         bool const has_pk = ! range_p.is_last_segment();
0649         bool const has_qk = ! range_q.is_last_segment();
0650
0651         int const side_pk_q1 = has_pk ? side.pk_wrt_q1() : 0;
0652
0653         int const side_qi_p1 = fun::verified_side(dir_info.sides.template get<1, 0>(),
0654                                                   range_p, range_q, umbrella_strategy, 0, 0);
0655         int const side_qk_p1 = has_qk
0656                              ? fun::verified_side(side.qk_wrt_p1(), range_p, range_q,
0657                                                   umbrella_strategy, 0, 2)
0658                              : 0;
0659
0660         // If Qi and Qk are both at same side of Pi-Pj,
0661         // or collinear (so: not opposite sides)
0662         if (! opposite(side_qi_p1, side_qk_p1))
0663         {
0664             int const side_pk_q2 = has_pk && has_qk ? side.pk_wrt_q2() : 0;
0665             int const side_pk_p  = has_pk ? side.pk_wrt_p1() : 0;
0666             int const side_qk_q  = has_qk ? side.qk_wrt_q1() : 0;
0667
0668             bool const q_turns_left = side_qk_q == 1;
0669
0670             bool const block_q = side_qk_p1 == 0
0671                         && ! same(side_qi_p1, side_qk_q)
0672                         ;
0673
0674             // If Pk at same side as Qi/Qk
0675             // (the "or" is for collinear case)
0676             // or Q is fully collinear && P turns not to left
0677             if (side_pk_p == side_qi_p1
0678                 || side_pk_p == side_qk_p1
0679                 || (side_qi_p1 == 0 && side_qk_p1 == 0 && side_pk_p != -1))
0680             {
0681                 if (side_qk_p1 == 0 && side_pk_q1 == 0
0682                     && has_pk && has_qk
0683                     && handle_imperfect_touch(range_p, range_q, side_pk_q2, umbrella_strategy, ti))
0684                 {
0685                     // If q continues collinearly (opposite) with p, it should be blocked
0686                     // but (FP) not if there is just a tiny space in between
0687                     return;
0688                 }
0689                 // Collinear -> lines join, continue
0690                 // (#BRL2)
0691                 if (side_pk_q2 == 0 && ! block_q)
0692                 {
0693                     fun::template both_collinear<0, 1>(range_p, range_q, umbrella_strategy,
0694                                                        2, 2, ti);
0695                     return;
0696                 }
0697
0698                 // Collinear opposite case -> block P
0699                 // (#BRL4, #BLR8)
0700                 if (side_pk_q1 == 0)
0701                 {
0702                     ti.operations[0].operation = operation_blocked;
0703                     // Q turns right -> union (both independent),
0704                     // Q turns left -> intersection
0705                     ti.operations[1].operation = block_q ? operation_blocked
0706                         : q_turns_left ? operation_intersection
0707                         : operation_union;
0708                     return;
0709                 }
0710
0711                 // Pk between Qi and Qk
0712                 // (#BRL3, #BRL7)
0713                 if (between(side_pk_q1, side_pk_q2, side_qk_q))
0714                 {
0715                     ui_else_iu(q_turns_left, ti);
0716                     if (block_q)
0717                     {
0718                         ti.operations[1].operation = operation_blocked;
0719                     }
0720                     return;
0721                 }
0722
0723                 // Pk between Qk and P, so left of Qk (if Q turns right) and vv
0724                 // (#BRL1)
0725                 if (side_pk_q2 == -side_qk_q)
0726                 {
0727                     ui_else_iu(! q_turns_left, ti);
0728                     ti.touch_only = true;
0729                     return;
0730                 }
0731
0732                 //
0733                 // (#BRL5, #BRL9)
0734                 if (side_pk_q1 == -side_qk_q)
0735                 {
0736                     uu_else_ii(! q_turns_left, ti);
0737                     if (block_q)
0738                     {
0739                         ti.operations[1].operation = operation_blocked;
0740                     }
0741                     else
0742                     {
0743                         ti.touch_only = true;
0744                     }
0745                     return;
0746                 }
0747             }
0748             else
0749             {
0750                 // Pk at other side than Qi/Pk
0751                 ti.operations[0].operation = q_turns_left
0752                             ? operation_intersection
0753                             : operation_union;
0754                 ti.operations[1].operation = block_q
0755                             ? operation_blocked
0756                             : side_qi_p1 == 1 || side_qk_p1 == 1
0757                             ? operation_union
0758                             : operation_intersection;
0759                 if (! block_q)
0760                 {
0761                     ti.touch_only = true;
0762                 }
0763
0764                 return;
0765             }
0766         }
0767         else
0768         {
0769             // The qi/qk are opposite to each other, w.r.t. p1
0770             // From left to right or from right to left
0771             int const side_pk_p = has_pk
0772                                 ? fun::verified_side(side.pk_wrt_p1(), range_p, range_p,
0773                                                      umbrella_strategy, 0, 2)
0774                                 : 0;
0775             bool const right_to_left = side_qk_p1 == 1;
0776
0777             // If p turns into direction of qi (1,2)
0778             if (side_pk_p == side_qi_p1)
0779             {
0780                 // Collinear opposite case -> block P
0781                 if (side_pk_q1 == 0)
0782                 {
0783                     ti.operations[0].operation = operation_blocked;
0784                     ti.operations[1].operation = right_to_left
0785                                 ? operation_union : operation_intersection;
0786                     return;
0787                 }
0788
0789                 if (side_pk_q1 == side_qk_p1)
0790                 {
0791                     uu_else_ii(right_to_left, ti);
0792                     ti.touch_only = true;
0793                     return;
0794                 }
0795             }
0796
0797             // If p turns into direction of qk (4,5)
0798             if (side_pk_p == side_qk_p1)
0799             {
0800                 int const side_pk_q2 = has_pk ? side.pk_wrt_q2() : 0;
0801
0802                 // Collinear case -> lines join, continue
0803                 if (side_pk_q2 == 0)
0804                 {
0805                     both(ti, operation_continue);
0806                     return;
0807                 }
0808                 if (side_pk_q2 == side_qk_p1)
0809                 {
0810                     ui_else_iu(right_to_left, ti);
0811                     ti.touch_only = true;
0812                     return;
0813                 }
0814             }
0815             // otherwise (3)
0816             ui_else_iu(! right_to_left, ti);
0817             return;
0818         }
0819     }
0820 };
0821
0822
0823 template
0824 <
0825     typename TurnInfo,
0826     typename VerifyPolicy
0827 >
0828 struct equal : public base_turn_handler
0829 {
0830     using fun = turn_info_verification_functions<VerifyPolicy>;
0831
0832     template
0833     <
0834         typename UniqueSubRange1,
0835         typename UniqueSubRange2,
0836         typename IntersectionInfo,
0837         typename DirInfo,
0838         typename SideCalculator,
0839         typename UmbrellaStrategy
0840     >
0841     static inline void apply(UniqueSubRange1 const& range_p,
0842                 UniqueSubRange2 const& range_q,
0843                 TurnInfo& ti,
0844                 IntersectionInfo const& info,
0845                 DirInfo const& ,
0846                 SideCalculator const& side,
0847                 UmbrellaStrategy const& umbrella_strategy)
0848     {
0849         // Copy the intersection point in TO direction
0850         assign_point(ti, method_equal, info, non_opposite_to_index(info));
0851
0852         bool const has_pk = ! range_p.is_last_segment();
0853         bool const has_qk = ! range_q.is_last_segment();
0854
0855         int const side_pk_q2 = has_pk && has_qk ? side.pk_wrt_q2() : 0;
0856         int const side_pk_p = has_pk ? side.pk_wrt_p1() : 0;
0857         int const side_qk_p = has_qk ? side.qk_wrt_p1() : 0;
0858
0859         if (has_pk && has_qk && side_pk_p == side_qk_p)
0860         {
0861             // They turn to the same side, or continue both collinearly
0862             // To check for union/intersection, try to check side values
0863             int const side_qk_p2 = side.qk_wrt_p2();
0864
0865             if (opposite(side_qk_p2, side_pk_q2))
0866             {
0867                 ui_else_iu(side_pk_q2 == 1, ti);
0868                 return;
0869             }
0870         }
0871
0872         // If pk is collinear with qj-qk, they continue collinearly.
0873         // This can be on either side of p1 (== q1), or collinear
0874         // The second condition checks if they do not continue
0875         // oppositely
0876         if (side_pk_q2 == 0 && side_pk_p == side_qk_p)
0877         {
0878             fun::template both_collinear<0, 1>(range_p, range_q, umbrella_strategy, 2, 2, ti);
0879             return;
0880         }
0881
0882
0883         // If they turn to same side (not opposite sides)
0884         if (! opposite(side_pk_p, side_qk_p))
0885         {
0886             // If pk is left of q2 or collinear: p: union, q: intersection
0887             ui_else_iu(side_pk_q2 != -1, ti);
0888         }
0889         else
0890         {
0891             // They turn opposite sides. If p turns left (or collinear),
0892             // p: union, q: intersection
0893             ui_else_iu(side_pk_p != -1, ti);
0894         }
0895     }
0896 };
0897
0898 template
0899 <
0900     typename TurnInfo,
0901     typename VerifyPolicy
0902 >
0903 struct start : public base_turn_handler
0904 {
0905     template
0906     <
0907         typename UniqueSubRange1,
0908         typename UniqueSubRange2,
0909         typename IntersectionInfo,
0910         typename DirInfo,
0911         typename SideCalculator,
0912         typename UmbrellaStrategy
0913     >
0914     static inline bool apply(UniqueSubRange1 const& /*range_p*/,
0915                 UniqueSubRange2 const& /*range_q*/,
0916                 TurnInfo& ti,
0917                 IntersectionInfo const& info,
0918                 DirInfo const& dir_info,
0919                 SideCalculator const& side,
0920                 UmbrellaStrategy const& )
0921     {
0922         if BOOST_GEOMETRY_CONSTEXPR (! VerifyPolicy::use_start_turn)
0923         {
0924             return false;
0925         }
0926         else // else prevents unreachable code warning
0927         {
0928             // Start turns have either how_a = -1, or how_b = -1 (either p leaves or q leaves)
0929             BOOST_GEOMETRY_ASSERT(dir_info.how_a != dir_info.how_b);
0930             BOOST_GEOMETRY_ASSERT(dir_info.how_a == -1 || dir_info.how_b == -1);
0931             BOOST_GEOMETRY_ASSERT(dir_info.how_a == 0 || dir_info.how_b == 0);
0932
0933             if (dir_info.how_b == -1)
0934             {
0935                 // p --------------->
0936                 //             |
0937                 //             | q         q leaves
0938                 //             v
0939                 //
0940
0941                 int const side_qj_p1 = side.qj_wrt_p1();
0942                 ui_else_iu(side_qj_p1 == -1, ti);
0943             }
0944             else if (dir_info.how_a == -1)
0945             {
0946                 // p leaves
0947                 int const side_pj_q1 = side.pj_wrt_q1();
0948                 ui_else_iu(side_pj_q1 == 1, ti);
0949             }
0950
0951             // Copy intersection point
0952             assign_point_and_correct(ti, method_start, info, dir_info);
0953             return true;
0954         }
0955     }
0956 };
0957
0958
0959 template
0960 <
0961     typename TurnInfo,
0962     typename AssignPolicy
0963 >
0964 struct equal_opposite : public base_turn_handler
0965 {
0966     template
0967     <
0968         typename UniqueSubRange1,
0969         typename UniqueSubRange2,
0970         typename OutputIterator,
0971         typename IntersectionInfo
0972     >
0973     static inline void apply(
0974                 UniqueSubRange1 const& /*range_p*/,
0975                 UniqueSubRange2 const& /*range_q*/,
0976                 /* by value: */ TurnInfo tp,
0977                 OutputIterator& out,
0978                 IntersectionInfo const& intersection_info)
0979     {
0980         // For equal-opposite segments, normally don't do anything.
0981         if BOOST_GEOMETRY_CONSTEXPR (AssignPolicy::include_opposite)
0982         {
0983             tp.method = method_equal;
0984             for (unsigned int i = 0; i < 2; i++)
0985             {
0986                 tp.operations[i].operation = operation_opposite;
0987             }
0988             for (unsigned int i = 0; i < intersection_info.i_info().count; i++)
0989             {
0990                 assign_point(tp, method_none, intersection_info.i_info(), i);
0991                 *out++ = tp;
0992             }
0993         }
0994     }
0995 };
0996
0997 template
0998 <
0999     typename TurnInfo,
1000     typename VerifyPolicy
1001 >
1002 struct 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
1146 template
1147 <
1148     typename TurnInfo,
1149     typename AssignPolicy
1150 >
1151 struct collinear_opposite : public base_turn_handler
1152 {
1153 private :
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
1223 public:
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
1317 template
1318 <
1319     typename TurnInfo
1320 >
1321 struct 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
1342 struct 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  */
1358 struct 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
1366 struct 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  */
1385 template<typename AssignPolicy>
1386 struct 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