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-2024.
0007 // Modifications copyright (c) 2015-2024 Oracle and/or its affiliates.
0008 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0009 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0010
0011 // Use, modification and distribution is subject to the Boost Software License,
0012 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0013 // http://www.boost.org/LICENSE_1_0.txt)
0014
0015 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HPP
0016 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HPP
0017
0018 #include <boost/core/ignore_unused.hpp>
0019 #include <boost/throw_exception.hpp>
0020
0021 #include <boost/geometry/core/access.hpp>
0022 #include <boost/geometry/core/assert.hpp>
0023 #include <boost/geometry/core/config.hpp>
0024 #include <boost/geometry/core/exception.hpp>
0025
0026 #include <boost/geometry/algorithms/convert.hpp>
0027 #include <boost/geometry/algorithms/detail/overlay/get_distance_measure.hpp>
0028 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
0029 #include <boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp>
0030
0031 #include <boost/geometry/util/constexpr.hpp>
0032
0033
0034 namespace boost { namespace geometry
0035 {
0036
0037 #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
0038 class turn_info_exception : public geometry::exception
0039 {
0040     std::string message;
0041 public:
0042
0043     // NOTE: "char" will be replaced by enum in future version
0044     inline turn_info_exception(char const method)
0045     {
0046         message = "Boost.Geometry Turn exception: ";
0047         message += method;
0048     }
0049
0050     virtual char const* What() const noexcept
0051     {
0052         return message.c_str();
0053     }
0054 };
0055 #endif
0056
0057 #ifndef DOXYGEN_NO_DETAIL
0058 namespace detail { namespace overlay
0059 {
0060
0061
0062 struct policy_verify_nothing
0063 {
0064     static bool const use_side_verification = false;
0065     static bool const use_start_turn = false;
0066     static bool const use_handle_as_touch = false;
0067     static bool const use_handle_as_equal = false;
0068     static bool const use_handle_imperfect_touch = false;
0069 };
0070
0071 struct policy_verify_all
0072 {
0073     static bool const use_side_verification = true;
0074     static bool const use_start_turn = true;
0075     static bool const use_handle_as_touch = true;
0076     static bool const use_handle_as_equal = true;
0077     static bool const use_handle_imperfect_touch = true;
0078 };
0079
0080 using verify_policy_aa = policy_verify_all;
0081 using verify_policy_ll = policy_verify_nothing;
0082 using verify_policy_la = policy_verify_nothing;
0083
0084 struct base_turn_handler
0085 {
0086     // Returns true if both sides are opposite
0087     static inline bool opposite(int side1, int side2)
0088     {
0089         // We cannot state side1 == -side2, because 0 == -0
0090         // So either side1*side2==-1 or side1==-side2 && side1 != 0
0091         return side1 * side2 == -1;
0092     }
0093
0094     // Same side of a segment (not being 0)
0095     static inline bool same(int side1, int side2)
0096     {
0097         return side1 * side2 == 1;
0098     }
0099
0100     // Both get the same operation
0101     template <typename TurnInfo>
0102     static inline void both(TurnInfo& ti, operation_type const op)
0103     {
0104         ti.operations[0].operation = op;
0105         ti.operations[1].operation = op;
0106     }
0107
0108     // If condition, first union/second intersection, else vice versa
0109     template <typename TurnInfo>
0110     static inline void ui_else_iu(bool condition, TurnInfo& ti)
0111     {
0112         ti.operations[0].operation = condition
0113                     ? operation_union : operation_intersection;
0114         ti.operations[1].operation = condition
0115                     ? operation_intersection : operation_union;
0116     }
0117
0118     // If condition, both union, else both intersection
0119     template <typename TurnInfo>
0120     static inline void uu_else_ii(bool condition, TurnInfo& ti)
0121     {
0122         both(ti, condition ? operation_union : operation_intersection);
0123     }
0124
0125     template <typename TurnInfo, typename IntersectionInfo>
0126     static inline void assign_point(TurnInfo& ti,
0127                 method_type method,
0128                 IntersectionInfo const& info, unsigned int index)
0129     {
0130         ti.method = method;
0131
0132         BOOST_GEOMETRY_ASSERT(index < info.count);
0133
0134         geometry::convert(info.intersections[index], ti.point);
0135         ti.operations[0].fraction = info.fractions[index].ra;
0136         ti.operations[1].fraction = info.fractions[index].rb;
0137     }
0138
0139     template <typename TurnInfo, typename IntersectionInfo, typename DirInfo>
0140     static inline void assign_point_and_correct(TurnInfo& ti,
0141                 method_type method,
0142                 IntersectionInfo const& info, DirInfo const& dir_info)
0143     {
0144         ti.method = method;
0145
0146         // For touch/touch interior always take the intersection point 0
0147         // (usually there is only one - but if collinear is handled as touch, both could be taken).
0148         static int const index = 0;
0149
0150         geometry::convert(info.intersections[index], ti.point);
0151
0152         for (int i = 0; i < 2; i++)
0153         {
0154             if (dir_info.arrival[i] == 1)
0155             {
0156                 // The segment arrives at the intersection point, its fraction should be 1
0157                 // (due to precision it might be nearly so, but not completely, in rare cases)
0158                 ti.operations[i].fraction = {1, 1};
0159             }
0160             else if (dir_info.arrival[i] == -1)
0161             {
0162                 // The segment leaves from the intersection point, likewise its fraction should be 0
0163                 ti.operations[i].fraction = {0, 1};
0164             }
0165             else
0166             {
0167                 ti.operations[i].fraction = i == 0 ? info.fractions[index].ra
0168                                                    : info.fractions[index].rb;
0169             }
0170         }
0171     }
0172
0173     template <typename IntersectionInfo>
0174     static inline unsigned int non_opposite_to_index(IntersectionInfo const& info)
0175     {
0176         return info.fractions[0].rb < info.fractions[1].rb
0177             ? 1 : 0;
0178     }
0179
0180 };
0181
0182 template<typename VerifyPolicy>
0183 struct turn_info_verification_functions
0184 {
0185     template <typename Point1, typename Point2>
0186     static inline
0187     typename select_coordinate_type<Point1, Point2>::type
0188     distance_measure(Point1 const& a, Point2 const& b)
0189     {
0190         // TODO: revise this using comparable distance for various
0191         // coordinate systems
0192         using coor_t = typename select_coordinate_type<Point1, Point2>::type;
0193
0194         coor_t const dx = get<0>(a) - get<0>(b);
0195         coor_t const dy = get<1>(a) - get<1>(b);
0196         return dx * dx + dy * dy;
0197     }
0198
0199     template
0200     <
0201             std::size_t IndexP,
0202             std::size_t IndexQ,
0203             typename UniqueSubRange1,
0204             typename UniqueSubRange2,
0205             typename UmbrellaStrategy,
0206             typename TurnInfo
0207     >
0208     static inline void set_both_verified(
0209             UniqueSubRange1 const& range_p,
0210             UniqueSubRange2 const& range_q,
0211             UmbrellaStrategy const& umbrella_strategy,
0212             std::size_t index_p, std::size_t index_q,
0213             TurnInfo& ti)
0214     {
0215         BOOST_GEOMETRY_ASSERT(IndexP + IndexQ == 1);
0216         BOOST_GEOMETRY_ASSERT(index_p > 0 && index_p <= 2);
0217         BOOST_GEOMETRY_ASSERT(index_q > 0 && index_q <= 2);
0218
0219         using distance_measure_result_type = geometry::coordinate_type_t<decltype(ti.point)>;
0220
0221         bool const p_in_range = index_p < range_p.size();
0222         bool const q_in_range = index_q < range_q.size();
0223         ti.operations[IndexP].remaining_distance
0224             = p_in_range
0225               ? distance_measure(ti.point, range_p.at(index_p))
0226               : distance_measure_result_type{0};
0227         ti.operations[IndexQ].remaining_distance
0228             = q_in_range
0229               ? distance_measure(ti.point, range_q.at(index_q))
0230               : distance_measure_result_type{0};
0231
0232         if (p_in_range && q_in_range)
0233         {
0234             // pk/q2 is considered as collinear, but there might be
0235             // a tiny measurable difference. If so, use that.
0236             // Calculate pk // qj-qk
0237             bool const p_closer
0238                 = ti.operations[IndexP].remaining_distance
0239                   <  ti.operations[IndexQ].remaining_distance;
0240             auto const dm
0241                 = p_closer
0242                 ? get_distance_measure(range_q.at(index_q - 1),
0243                                        range_q.at(index_q), range_p.at(index_p),
0244                                        umbrella_strategy)
0245                 : get_distance_measure(range_p.at(index_p - 1),
0246                                        range_p.at(index_p), range_q.at(index_q),
0247                                        umbrella_strategy);
0248
0249             if (! dm.is_zero())
0250             {
0251                 // Not truely collinear, distinguish for union/intersection
0252                 // If p goes left (positive), take that for a union
0253                 bool const p_left
0254                     = p_closer ? dm.is_positive() : dm.is_negative();
0255
0256                 ti.operations[IndexP].operation = p_left
0257                             ? operation_union : operation_intersection;
0258                 ti.operations[IndexQ].operation = p_left
0259                             ? operation_intersection : operation_union;
0260                 return;
0261             }
0262         }
0263
0264         base_turn_handler::both(ti, operation_continue);
0265     }
0266
0267     template
0268     <
0269             std::size_t IndexP,
0270             std::size_t IndexQ,
0271             typename UniqueSubRange1,
0272             typename UniqueSubRange2,
0273             typename UmbrellaStrategy,
0274             typename TurnInfo
0275     >
0276     static inline void both_collinear(
0277             UniqueSubRange1 const& range_p,
0278             UniqueSubRange2 const& range_q,
0279             UmbrellaStrategy const& umbrella_strategy,
0280             std::size_t index_p, std::size_t index_q,
0281             TurnInfo& ti)
0282     {
0283         if BOOST_GEOMETRY_CONSTEXPR (VerifyPolicy::use_side_verification)
0284         {
0285             set_both_verified<IndexP, IndexQ>(range_p, range_q, umbrella_strategy,
0286                                               index_p, index_q, ti);
0287         }
0288         else
0289         {
0290             base_turn_handler::both(ti, operation_continue);
0291         }
0292     }
0293
0294     template
0295     <
0296         typename UniqueSubRange1,
0297         typename UniqueSubRange2,
0298         typename UmbrellaStrategy
0299     >
0300     static inline int verified_side(int side,
0301                                     UniqueSubRange1 const& range_p,
0302                                     UniqueSubRange2 const& range_q,
0303                                     UmbrellaStrategy const& umbrella_strategy,
0304                                     int index_p, int index_q)
0305     {
0306         if BOOST_GEOMETRY_CONSTEXPR (VerifyPolicy::use_side_verification)
0307         {
0308             if (side == 0)
0309             {
0310                 if (index_p >= 1 && range_p.is_last_segment())
0311                 {
0312                     return 0;
0313                 }
0314                 if (index_q >= 2 && range_q.is_last_segment())
0315                 {
0316                     return 0;
0317                 }
0318
0319                 auto const dm = get_distance_measure(range_p.at(index_p),
0320                                                      range_p.at(index_p + 1),
0321                                                      range_q.at(index_q),
0322                                                      umbrella_strategy);
0323                 static decltype(dm.measure) const zero = 0;
0324                 return dm.measure == zero ? 0 : dm.measure > zero ? 1 : -1;
0325             }
0326         }
0327
0328         return side;
0329     }
0330
0331 };
0332
0333
0334 template
0335 <
0336     typename TurnInfo,
0337     typename VerifyPolicy
0338 >
0339 struct touch_interior : public base_turn_handler
0340 {
0341     using fun = turn_info_verification_functions<VerifyPolicy>;
0342
0343     template
0344     <
0345         typename IntersectionInfo,
0346         typename SideCalculator,
0347         typename UniqueSubRange1,
0348         typename UniqueSubRange2
0349     >
0350     static bool handle_as_touch(IntersectionInfo const& info,
0351                                 SideCalculator const& side,
0352                                 UniqueSubRange1 const& non_touching_range,
0353                                 UniqueSubRange2 const& other_range)
0354     {
0355         if BOOST_GEOMETRY_CONSTEXPR (! VerifyPolicy::use_handle_as_touch)
0356         {
0357             return false;
0358         }
0359         else // else prevents unreachable code warning
0360         {
0361             bool const has_k = ! non_touching_range.is_last_segment()
0362                 && ! other_range.is_last_segment();
0363             if (has_k
0364                 && (same(side.pj_wrt_q1(), side.qj_wrt_p2())
0365                  || same(side.pj_wrt_q2(), side.qj_wrt_p1())))
0366             {
0367                 // At a touch, the touching points (pj and qj) should be collinear
0368                 // with both other segments.
0369                 // If that is not the case (both left or both right), it should not be handled as a touch,
0370                 // (though the intersection point might be close to the end),
0371                 // because segments might cross each other or touch the other in the middle.
0372                 return false;
0373             }
0374
0375             //
0376             //
0377             //                         ^  Q(i)                ^ P(i)
0378             //                          \                    /
0379             //                           \                  /
0380             //                            \                /
0381             //                             \              /
0382             //                              \            /
0383             //                               \          /
0384             //                                \        /
0385             //                                 \      /
0386             //                                  \    /
0387             //                                   \  / it is about buffer_rt_r
0388             //                  P(k)              v/  they touch here "in the middle", but at the intersection...
0389             //                  <---------------->v   there is no follow up IP
0390             //                                   /
0391             //                                  /
0392             //                                 /
0393             //                                /
0394             //                               /
0395             //                              /
0396             //                             v Q(k)
0397             //
0398
0399             // Measure where the IP is located. If it is really close to the end,
0400             // then there is no space for the next IP (on P(1)/Q(2). A "from"
0401             // intersection will be generated, but those are never handled.
0402             // Therefore handle it as a normal touch (two segments arrive at the
0403             // intersection point). It currently checks for zero, but even a
0404             // distance a little bit larger would do.
0405             auto const dm = fun::distance_measure(info.intersections[0], non_touching_range.at(1));
0406             decltype(dm) const zero = 0;
0407             bool const result = math::equals(dm, zero);
0408             return result;
0409         }
0410     }
0411
0412     // Index: 0, P is the interior, Q is touching and vice versa
0413     template
0414     <
0415         unsigned int Index,
0416         typename UniqueSubRange1,
0417         typename UniqueSubRange2,
0418         typename IntersectionInfo,
0419         typename DirInfo,
0420         typename SidePolicy,
0421         typename UmbrellaStrategy
0422     >
0423     static inline void apply(UniqueSubRange1 const& range_p,
0424                 UniqueSubRange2 const& range_q,
0425                 TurnInfo& ti,
0426                 IntersectionInfo const& intersection_info,
0427                 DirInfo const& dir_info,
0428                 SidePolicy const& side,
0429                 UmbrellaStrategy const& umbrella_strategy)
0430     {
0431         assign_point_and_correct(ti, method_touch_interior, intersection_info, dir_info);
0432
0433         // Both segments of q touch segment p somewhere in its interior
0434         // 1) We know: if q comes from LEFT or RIGHT
0435         // (i.e. dir_info.sides.get<Index,0>() == 1 or -1)
0436         // 2) Important is: if q_k goes to LEFT, RIGHT, COLLINEAR
0437         //    and, if LEFT/COLL, if it is lying LEFT or RIGHT w.r.t. q_i
0438
0439         BOOST_STATIC_ASSERT(Index <= 1);
0440         static unsigned int const index_p = Index;
0441         static unsigned int const index_q = 1 - Index;
0442
0443         bool const has_pk = ! range_p.is_last_segment();
0444         bool const has_qk = ! range_q.is_last_segment();
0445         int const side_qi_p = dir_info.sides.template get<index_q, 0>();
0446         int const side_qk_p = has_qk ? side.qk_wrt_p1() : 0;
0447
0448         if (side_qi_p == -side_qk_p)
0449         {
0450             // Q crosses P from left->right or from right->left (test "ML1")
0451             // Union: folow P (left->right) or Q (right->left)
0452             // Intersection: other turn
0453             unsigned int index = side_qk_p == -1 ? index_p : index_q;
0454             ti.operations[index].operation = operation_union;
0455             ti.operations[1 - index].operation = operation_intersection;
0456             return;
0457         }
0458
0459         int const side_qk_q = has_qk ? side.qk_wrt_q1() : 0;
0460
0461         // Only necessary if rescaling is turned off:
0462         int const side_pj_q2 = has_qk ? side.pj_wrt_q2() : 0;
0463
0464         if (side_qi_p == -1 && side_qk_p == -1 && side_qk_q == 1)
0465         {
0466             // Q turns left on the right side of P (test "MR3")
0467             // Both directions for "intersection"
0468             both(ti, operation_intersection);
0469             ti.touch_only = true;
0470         }
0471         else if (side_qi_p == 1 && side_qk_p == 1 && side_qk_q == -1)
0472         {
0473             if (has_qk && side_pj_q2 == -1)
0474             {
0475                 // Q turns right on the left side of P (test "ML3")
0476                 // Union: take both operations
0477                 // Intersection: skip
0478                 both(ti, operation_union);
0479             }
0480             else
0481             {
0482                 // q2 is collinear with p1, so it does not turn back. This
0483                 // can happen in floating point precision. In this case,
0484                 // block one of the operations to avoid taking that path.
0485                 ti.operations[index_p].operation = operation_union;
0486                 ti.operations[index_q].operation = operation_blocked;
0487             }
0488             ti.touch_only = true;
0489         }
0490         else if (side_qi_p == side_qk_p && side_qi_p == side_qk_q)
0491         {
0492             // Q turns left on the left side of P (test "ML2")
0493             // or Q turns right on the right side of P (test "MR2")
0494             // Union: take left turn (Q if Q turns left, P if Q turns right)
0495             // Intersection: other turn
0496             unsigned int index = side_qk_q == 1 ? index_q : index_p;
0497             if (has_qk && side_pj_q2 == 0)
0498             {
0499                 // Even though sides xk w.r.t. 1 are distinct, pj is collinear
0500                 // with q. Therefore swap the path
0501                 index = 1 - index;
0502             }
0503
0504             if (has_pk && has_qk && opposite(side_pj_q2, side_qi_p))
0505             {
0506                 // Without rescaling, floating point requires extra measures
0507                 int const side_qj_p1 = side.qj_wrt_p1();
0508                 int const side_qj_p2 = side.qj_wrt_p2();
0509
0510                 if (same(side_qj_p1, side_qj_p2))
0511                 {
0512                     int const side_pj_q1 = side.pj_wrt_q1();
0513                     if (opposite(side_pj_q1, side_pj_q2))
0514                     {
0515                         index = 1 - index;
0516                     }
0517                 }
0518             }
0519
0520             ti.operations[index].operation = operation_union;
0521             ti.operations[1 - index].operation = operation_intersection;
0522             ti.touch_only = true;
0523         }
0524         else if (side_qk_p == 0)
0525         {
0526             // Q intersects on interior of P and continues collinearly
0527             if (side_qk_q == side_qi_p)
0528             {
0529                 fun::template both_collinear<index_p, index_q>(range_p, range_q, umbrella_strategy,
0530                                                                1, 2, ti);
0531             }
0532             else
0533             {
0534                 // Opposite direction, which is never travelled.
0535                 // If Q turns left, P continues for intersection
0536                 // If Q turns right, P continues for union
0537                 ti.operations[index_p].operation = side_qk_q == 1
0538                     ? operation_intersection
0539                     : operation_union;
0540                 ti.operations[index_q].operation = operation_blocked;
0541             }
0542         }
0543         else
0544         {
0545             // Should not occur!
0546             ti.method = method_error;
0547         }
0548     }
0549 };
0550
0551
0552 template
0553 <
0554     typename TurnInfo,
0555     typename VerifyPolicy
0556 >
0557 struct touch : public base_turn_handler
0558 {
0559     using fun = turn_info_verification_functions<VerifyPolicy>;
0560
0561     static inline bool between(int side1, int side2, int turn)
0562     {
0563         return side1 == side2 && ! opposite(side1, turn);
0564     }
0565
0566     template
0567     <
0568         typename UniqueSubRange1,
0569         typename UniqueSubRange2,
0570         typename UmbrellaStrategy
0571     >
0572     static inline bool handle_imperfect_touch(UniqueSubRange1 const& range_p,
0573                                               UniqueSubRange2 const& range_q,
0574                                               int side_pk_q2,
0575                                               UmbrellaStrategy const& umbrella_strategy,
0576                                               TurnInfo& ti)
0577     {
0578         if BOOST_GEOMETRY_CONSTEXPR (! VerifyPolicy::use_handle_imperfect_touch)
0579         {
0580             return false;
0581         }
0582         else // else prevents unreachable code warning
0583         {
0584             //  Q
0585             //  ^
0586             // ||
0587             // ||
0588             // |^----
0589             // >----->P
0590             // *            * they touch here (P/Q are (nearly) on top of each other)
0591             //
0592             // Q continues from where P comes.
0593             // P continues from where Q comes
0594             // This is often a blocking situation,
0595             // unless there are FP issues: there might be a distance
0596             // between Pj and Qj, in that case handle it as a union.
0597             //
0598             // Exaggerated:
0599             //  Q
0600             //  ^           Q is nearly vertical
0601             //   \          but not completely - and still ends above P
0602             // |  \qj       In this case it should block P and
0603             // |  ^------   set Q to Union
0604             // >----->P     qj is LEFT of P1 and pi is LEFT of Q2
0605             //              (the other way round is also possible)
0606
0607             // There are also cases like this:
0608             //      P
0609             //      ^
0610             //      ||
0611             //      ||
0612             // P----^-----<Q
0613             // This code is not for these cases because of the condition opposite(side.pi_wrt_q1(), side.qk_wrt_p2())
0614
0615             auto has_distance = [&](auto const& r1, auto const& r2) -> bool
0616             {
0617                 auto const d1 = get_distance_measure(r1.at(0), r1.at(1), r2.at(1), umbrella_strategy);
0618                 auto const d2 = get_distance_measure(r2.at(1), r2.at(2), r1.at(0), umbrella_strategy);
0619                 return d1.measure > 0 && d2.measure > 0;
0620             };
0621
0622             if (side_pk_q2 == -1 && has_distance(range_p, range_q))
0623             {
0624                 // Even though there is a touch, Q(j) is left of P1
0625                 // and P(i) is still left from Q2.
0626                 // Q continues to the right.
0627                 // It can continue.
0628                 ti.operations[0].operation = operation_blocked;
0629                 // Q turns right -> union (both independent),
0630                 // Q turns left -> intersection
0631                 ti.operations[1].operation = operation_union;
0632                 ti.touch_only = true;
0633                 return true;
0634             }
0635
0636             if (side_pk_q2 == 1 && has_distance(range_q, range_p))
0637             {
0638                 // Similarly, but the other way round.
0639                 // Q continues to the left.
0640                 ti.operations[0].operation = operation_union;
0641                 ti.operations[1].operation = operation_blocked;
0642                 ti.touch_only = true;
0643                 return true;
0644             }
0645             return false;
0646         }
0647     }
0648
0649     template
0650     <
0651         typename UniqueSubRange1,
0652         typename UniqueSubRange2,
0653         typename IntersectionInfo,
0654         typename DirInfo,
0655         typename SideCalculator,
0656         typename UmbrellaStrategy
0657     >
0658     static inline void apply(UniqueSubRange1 const& range_p,
0659                 UniqueSubRange2 const& range_q,
0660                 TurnInfo& ti,
0661                 IntersectionInfo const& intersection_info,
0662                 DirInfo const& dir_info,
0663                 SideCalculator const& side,
0664                 UmbrellaStrategy const& umbrella_strategy)
0665     {
0666         assign_point_and_correct(ti, method_touch, intersection_info, dir_info);
0667
0668         bool const has_pk = ! range_p.is_last_segment();
0669         bool const has_qk = ! range_q.is_last_segment();
0670
0671         int const side_pk_q1 = has_pk ? side.pk_wrt_q1() : 0;
0672
0673         int const side_qi_p1 = fun::verified_side(dir_info.sides.template get<1, 0>(),
0674                                                   range_p, range_q, umbrella_strategy, 0, 0);
0675         int const side_qk_p1 = has_qk
0676                              ? fun::verified_side(side.qk_wrt_p1(), range_p, range_q,
0677                                                   umbrella_strategy, 0, 2)
0678                              : 0;
0679
0680         // If Qi and Qk are both at same side of Pi-Pj,
0681         // or collinear (so: not opposite sides)
0682         if (! opposite(side_qi_p1, side_qk_p1))
0683         {
0684             int const side_pk_q2 = has_pk && has_qk ? side.pk_wrt_q2() : 0;
0685             int const side_pk_p  = has_pk ? side.pk_wrt_p1() : 0;
0686             int const side_qk_q  = has_qk ? side.qk_wrt_q1() : 0;
0687
0688             bool const q_turns_left = side_qk_q == 1;
0689
0690             bool const block_q = side_qk_p1 == 0
0691                         && ! same(side_qi_p1, side_qk_q)
0692                         ;
0693
0694             // If Pk at same side as Qi/Qk
0695             // (the "or" is for collinear case)
0696             // or Q is fully collinear && P turns not to left
0697             if (side_pk_p == side_qi_p1
0698                 || side_pk_p == side_qk_p1
0699                 || (side_qi_p1 == 0 && side_qk_p1 == 0 && side_pk_p != -1))
0700             {
0701                 if (side_qk_p1 == 0 && side_pk_q1 == 0
0702                     && has_pk && has_qk
0703                     && opposite(side.pi_wrt_q1(), side.qk_wrt_p2())
0704                     && handle_imperfect_touch(range_p, range_q, side_pk_q2, umbrella_strategy, ti))
0705                 {
0706                     // If q continues collinearly (opposite) with p, it should be blocked
0707                     // but (FP) not if there is just a tiny space in between
0708                     return;
0709                 }
0710                 // Collinear -> lines join, continue
0711                 // (#BRL2)
0712                 if (side_pk_q2 == 0 && ! block_q)
0713                 {
0714                     fun::template both_collinear<0, 1>(range_p, range_q, umbrella_strategy,
0715                                                        2, 2, ti);
0716                     return;
0717                 }
0718
0719                 // Collinear opposite case -> block P
0720                 // (#BRL4, #BLR8)
0721                 if (side_pk_q1 == 0)
0722                 {
0723                     ti.operations[0].operation = operation_blocked;
0724                     // Q turns right -> union (both independent),
0725                     // Q turns left -> intersection
0726                     ti.operations[1].operation = block_q ? operation_blocked
0727                         : q_turns_left ? operation_intersection
0728                         : operation_union;
0729                     return;
0730                 }
0731
0732                 // Pk between Qi and Qk
0733                 // (#BRL3, #BRL7)
0734                 if (between(side_pk_q1, side_pk_q2, side_qk_q))
0735                 {
0736                     ui_else_iu(q_turns_left, ti);
0737                     if (block_q)
0738                     {
0739                         ti.operations[1].operation = operation_blocked;
0740                     }
0741                     return;
0742                 }
0743
0744                 // Pk between Qk and P, so left of Qk (if Q turns right) and vv
0745                 // (#BRL1)
0746                 if (side_pk_q2 == -side_qk_q)
0747                 {
0748                     ui_else_iu(! q_turns_left, ti);
0749                     ti.touch_only = true;
0750                     return;
0751                 }
0752
0753                 //
0754                 // (#BRL5, #BRL9)
0755                 if (side_pk_q1 == -side_qk_q)
0756                 {
0757                     uu_else_ii(! q_turns_left, ti);
0758                     if (block_q)
0759                     {
0760                         ti.operations[1].operation = operation_blocked;
0761                     }
0762                     else
0763                     {
0764                         ti.touch_only = true;
0765                     }
0766                     return;
0767                 }
0768             }
0769             else
0770             {
0771                 // Pk at other side than Qi/Pk
0772                 ti.operations[0].operation = q_turns_left
0773                             ? operation_intersection
0774                             : operation_union;
0775                 ti.operations[1].operation = block_q
0776                             ? operation_blocked
0777                             : side_qi_p1 == 1 || side_qk_p1 == 1
0778                             ? operation_union
0779                             : operation_intersection;
0780                 if (! block_q)
0781                 {
0782                     ti.touch_only = true;
0783                 }
0784
0785                 return;
0786             }
0787         }
0788         else
0789         {
0790             // The qi/qk are opposite to each other, w.r.t. p1
0791             // From left to right or from right to left
0792             int const side_pk_p = has_pk
0793                                 ? fun::verified_side(side.pk_wrt_p1(), range_p, range_p,
0794                                                      umbrella_strategy, 0, 2)
0795                                 : 0;
0796             bool const right_to_left = side_qk_p1 == 1;
0797
0798             // If p turns into direction of qi (1,2)
0799             if (side_pk_p == side_qi_p1)
0800             {
0801                 // Collinear opposite case -> block P
0802                 if (side_pk_q1 == 0)
0803                 {
0804                     ti.operations[0].operation = operation_blocked;
0805                     ti.operations[1].operation = right_to_left
0806                                 ? operation_union : operation_intersection;
0807                     return;
0808                 }
0809
0810                 if (side_pk_q1 == side_qk_p1)
0811                 {
0812                     uu_else_ii(right_to_left, ti);
0813                     ti.touch_only = true;
0814                     return;
0815                 }
0816             }
0817
0818             // If p turns into direction of qk (4,5)
0819             if (side_pk_p == side_qk_p1)
0820             {
0821                 int const side_pk_q2 = has_pk ? side.pk_wrt_q2() : 0;
0822
0823                 // Collinear case -> lines join, continue
0824                 if (side_pk_q2 == 0)
0825                 {
0826                     both(ti, operation_continue);
0827                     return;
0828                 }
0829                 if (side_pk_q2 == side_qk_p1)
0830                 {
0831                     ui_else_iu(right_to_left, ti);
0832                     ti.touch_only = true;
0833                     return;
0834                 }
0835             }
0836             // otherwise (3)
0837             ui_else_iu(! right_to_left, ti);
0838             return;
0839         }
0840     }
0841 };
0842
0843
0844 template
0845 <
0846     typename TurnInfo,
0847     typename VerifyPolicy
0848 >
0849 struct equal : public base_turn_handler
0850 {
0851     using fun = turn_info_verification_functions<VerifyPolicy>;
0852
0853     template
0854     <
0855         typename UniqueSubRange1,
0856         typename UniqueSubRange2,
0857         typename IntersectionInfo,
0858         typename DirInfo,
0859         typename SideCalculator,
0860         typename UmbrellaStrategy
0861     >
0862     static inline void apply(UniqueSubRange1 const& range_p,
0863                 UniqueSubRange2 const& range_q,
0864                 TurnInfo& ti,
0865                 IntersectionInfo const& info,
0866                 DirInfo const& ,
0867                 SideCalculator const& side,
0868                 UmbrellaStrategy const& umbrella_strategy)
0869     {
0870         // Copy the intersection point in TO direction
0871         assign_point(ti, method_equal, info, non_opposite_to_index(info));
0872
0873         bool const has_pk = ! range_p.is_last_segment();
0874         bool const has_qk = ! range_q.is_last_segment();
0875
0876         int const side_pk_q2 = has_pk && has_qk ? side.pk_wrt_q2() : 0;
0877         int const side_pk_p = has_pk ? side.pk_wrt_p1() : 0;
0878         int const side_qk_p = has_qk ? side.qk_wrt_p1() : 0;
0879
0880         if (has_pk && has_qk && side_pk_p == side_qk_p)
0881         {
0882             // They turn to the same side, or continue both collinearly
0883             // To check for union/intersection, try to check side values
0884             int const side_qk_p2 = side.qk_wrt_p2();
0885
0886             if (opposite(side_qk_p2, side_pk_q2))
0887             {
0888                 ui_else_iu(side_pk_q2 == 1, ti);
0889                 return;
0890             }
0891         }
0892
0893         // If pk is collinear with qj-qk, they continue collinearly.
0894         // This can be on either side of p1 (== q1), or collinear
0895         // The second condition checks if they do not continue
0896         // oppositely
0897         if (side_pk_q2 == 0 && side_pk_p == side_qk_p)
0898         {
0899             fun::template both_collinear<0, 1>(range_p, range_q, umbrella_strategy, 2, 2, ti);
0900             return;
0901         }
0902
0903
0904         // If they turn to same side (not opposite sides)
0905         if (! opposite(side_pk_p, side_qk_p))
0906         {
0907             // If pk is left of q2 or collinear: p: union, q: intersection
0908             ui_else_iu(side_pk_q2 != -1, ti);
0909         }
0910         else
0911         {
0912             // They turn opposite sides. If p turns left (or collinear),
0913             // p: union, q: intersection
0914             ui_else_iu(side_pk_p != -1, ti);
0915         }
0916     }
0917 };
0918
0919 template
0920 <
0921     typename TurnInfo,
0922     typename VerifyPolicy
0923 >
0924 struct start : public base_turn_handler
0925 {
0926     template
0927     <
0928         typename UniqueSubRange1,
0929         typename UniqueSubRange2,
0930         typename IntersectionInfo,
0931         typename DirInfo,
0932         typename SideCalculator,
0933         typename UmbrellaStrategy
0934     >
0935     static inline bool apply(UniqueSubRange1 const& /*range_p*/,
0936                 UniqueSubRange2 const& /*range_q*/,
0937                 TurnInfo& ti,
0938                 IntersectionInfo const& info,
0939                 DirInfo const& dir_info,
0940                 SideCalculator const& side,
0941                 UmbrellaStrategy const& )
0942     {
0943         if BOOST_GEOMETRY_CONSTEXPR (! VerifyPolicy::use_start_turn)
0944         {
0945             return false;
0946         }
0947         else // else prevents unreachable code warning
0948         {
0949             // Start turns have either how_a = -1, or how_b = -1 (either p leaves or q leaves)
0950             BOOST_GEOMETRY_ASSERT(dir_info.how_a != dir_info.how_b);
0951             BOOST_GEOMETRY_ASSERT(dir_info.how_a == -1 || dir_info.how_b == -1);
0952             BOOST_GEOMETRY_ASSERT(dir_info.how_a == 0 || dir_info.how_b == 0);
0953
0954             if (dir_info.how_b == -1)
0955             {
0956                 // p --------------->
0957                 //             |
0958                 //             | q         q leaves
0959                 //             v
0960                 //
0961
0962                 int const side_qj_p1 = side.qj_wrt_p1();
0963                 ui_else_iu(side_qj_p1 == -1, ti);
0964             }
0965             else if (dir_info.how_a == -1)
0966             {
0967                 // p leaves
0968                 int const side_pj_q1 = side.pj_wrt_q1();
0969                 ui_else_iu(side_pj_q1 == 1, ti);
0970             }
0971
0972             // Copy intersection point
0973             assign_point_and_correct(ti, method_start, info, dir_info);
0974             return true;
0975         }
0976     }
0977 };
0978
0979
0980 template
0981 <
0982     typename TurnInfo,
0983     typename AssignPolicy
0984 >
0985 struct equal_opposite : public base_turn_handler
0986 {
0987     template
0988     <
0989         typename UniqueSubRange1,
0990         typename UniqueSubRange2,
0991         typename OutputIterator,
0992         typename IntersectionInfo
0993     >
0994     static inline void apply(
0995                 UniqueSubRange1 const& /*range_p*/,
0996                 UniqueSubRange2 const& /*range_q*/,
0997                 /* by value: */ TurnInfo tp,
0998                 OutputIterator& out,
0999                 IntersectionInfo const& intersection_info)
1000     {
1001         // For equal-opposite segments, normally don't do anything.
1002         if BOOST_GEOMETRY_CONSTEXPR (AssignPolicy::include_opposite)
1003         {
1004             tp.method = method_equal;
1005             for (unsigned int i = 0; i < 2; i++)
1006             {
1007                 tp.operations[i].operation = operation_opposite;
1008             }
1009             for (unsigned int i = 0; i < intersection_info.i_info().count; i++)
1010             {
1011                 assign_point(tp, method_none, intersection_info.i_info(), i);
1012                 *out++ = tp;
1013             }
1014         }
1015     }
1016 };
1017
1018 template
1019 <
1020     typename TurnInfo,
1021     typename VerifyPolicy
1022 >
1023 struct collinear : public base_turn_handler
1024 {
1025     using fun = turn_info_verification_functions<VerifyPolicy>;
1026
1027     template
1028     <
1029         typename IntersectionInfo,
1030         typename UniqueSubRange1,
1031         typename UniqueSubRange2,
1032         typename DirInfo
1033     >
1034     static bool handle_as_equal(IntersectionInfo const& info,
1035                                 UniqueSubRange1 const& range_p,
1036                                 UniqueSubRange2 const& range_q,
1037                                 DirInfo const& dir_info)
1038     {
1039         if BOOST_GEOMETRY_CONSTEXPR (! VerifyPolicy::use_handle_as_equal)
1040         {
1041             return false;
1042         }
1043         else // else prevents unreachable code warning
1044         {
1045             int const arrival_p = dir_info.arrival[0];
1046             int const arrival_q = dir_info.arrival[1];
1047             if (arrival_p * arrival_q != -1 || info.count != 2)
1048             {
1049                 // Code below assumes that either p or q arrives in the other segment
1050                 return false;
1051             }
1052
1053             auto const dm = arrival_p == 1
1054                           ? fun::distance_measure(info.intersections[1], range_q.at(1))
1055                           : fun::distance_measure(info.intersections[1], range_p.at(1));
1056             decltype(dm) const zero = 0;
1057             return math::equals(dm, zero);
1058         }
1059     }
1060
1061     /*
1062         Either P arrives within Q (arrival_p == -1) or Q arrives within P.
1063
1064         Typical situation:
1065               ^q2
1066              /
1067             ^q1
1068            /         ____ ip[1]
1069           //|p1  } this section of p/q is colllinear
1070        q0// |    }   ____ ip[0]
1071          /  |
1072         /   v
1073        p0   p2
1074
1075        P arrives (at p1) in segment Q (between q0 and q1).
1076        Therefore arrival_p == 1
1077        P (p2) goes to the right (-1). Follow P for intersection, or follow Q for union.
1078        Therefore if (arrival_p==1) and side_p==-1, result = iu
1079
1080        Complete table:
1081
1082         arrival P   pk//p1  qk//q1   product   case    result
1083          1           1                1        CLL1    ui
1084         -1                   1       -1        CLL2    iu
1085          1           1                1        CLR1    ui
1086         -1                  -1        1        CLR2    ui
1087
1088          1          -1               -1        CRL1    iu
1089         -1                   1       -1        CRL2    iu
1090          1          -1               -1        CRR1    iu
1091         -1                  -1        1        CRR2    ui
1092
1093          1           0                0        CC1     cc
1094         -1                   0        0        CC2     cc
1095
1096          Resulting in the rule:
1097          The arrival-info multiplied by the relevant side delivers the result.
1098          product = arrival * (pk//p1 or qk//q1)
1099
1100          Stated otherwise:
1101          - if P arrives: look at turn P
1102          - if Q arrives: look at turn Q
1103          - if P arrives and P turns left: union for P
1104          - if P arrives and P turns right: intersection for P
1105          - if Q arrives and Q turns left: union for Q (=intersection for P)
1106          - if Q arrives and Q turns right: intersection for Q (=union for P)
1107     */
1108     template
1109     <
1110         typename UniqueSubRange1,
1111         typename UniqueSubRange2,
1112         typename IntersectionInfo,
1113         typename DirInfo,
1114         typename SidePolicy
1115     >
1116     static inline void apply(
1117                 UniqueSubRange1 const& range_p,
1118                 UniqueSubRange2 const& range_q,
1119                 TurnInfo& ti,
1120                 IntersectionInfo const& info,
1121                 DirInfo const& dir_info,
1122                 SidePolicy const& side)
1123     {
1124         // Copy the intersection point in TO direction
1125         assign_point(ti, method_collinear, info, non_opposite_to_index(info));
1126
1127         int const arrival_p = dir_info.arrival[0];
1128         // Should not be 0, this is checked before
1129         BOOST_GEOMETRY_ASSERT(arrival_p != 0);
1130
1131         bool const has_pk = ! range_p.is_last_segment();
1132         bool const has_qk = ! range_q.is_last_segment();
1133         int const side_p = has_pk ? side.pk_wrt_p1() : 0;
1134         int const side_q = has_qk ? side.qk_wrt_q1() : 0;
1135
1136         // If p arrives, use p, else use q
1137         int const side_p_or_q = arrival_p == 1
1138             ? side_p
1139             : side_q
1140             ;
1141
1142         // Calculate product according to comments above.
1143         int const product = arrival_p * side_p_or_q;
1144
1145         if (product == 0)
1146         {
1147             both(ti, operation_continue);
1148         }
1149         else
1150         {
1151             ui_else_iu(product == 1, ti);
1152         }
1153
1154         // Calculate remaining distance. If it continues collinearly it is
1155         // measured until the end of the next segment
1156         ti.operations[0].remaining_distance
1157                 = side_p == 0 && has_pk
1158                 ? fun::distance_measure(ti.point, range_p.at(2))
1159                 : fun::distance_measure(ti.point, range_p.at(1));
1160         ti.operations[1].remaining_distance
1161                 = side_q == 0 && has_qk
1162                 ? fun::distance_measure(ti.point, range_q.at(2))
1163                 : fun::distance_measure(ti.point, range_q.at(1));
1164     }
1165 };
1166
1167 template
1168 <
1169     typename TurnInfo,
1170     typename AssignPolicy
1171 >
1172 struct collinear_opposite : public base_turn_handler
1173 {
1174 private :
1175     /*
1176         arrival P  arrival Q  pk//p1   qk//q1  case  result2  result
1177         --------------------------------------------------------------
1178          1          1          1       -1      CLO1    ix      xu
1179          1          1          1        0      CLO2    ix      (xx)
1180          1          1          1        1      CLO3    ix      xi
1181
1182          1          1          0       -1      CCO1    (xx)    xu
1183          1          1          0        0      CCO2    (xx)    (xx)
1184          1          1          0        1      CCO3    (xx)    xi
1185
1186          1          1         -1       -1      CRO1    ux      xu
1187          1          1         -1        0      CRO2    ux      (xx)
1188          1          1         -1        1      CRO3    ux      xi
1189
1190         -1          1                  -1      CXO1    xu
1191         -1          1                   0      CXO2    (xx)
1192         -1          1                   1      CXO3    xi
1193
1194          1         -1          1               CXO1    ix
1195          1         -1          0               CXO2    (xx)
1196          1         -1         -1               CXO3    ux
1197     */
1198
1199     template <unsigned int Index, typename IntersectionInfo>
1200     static inline bool set_tp(int side_rk_r, TurnInfo& tp,
1201                               IntersectionInfo const& intersection_info)
1202     {
1203         BOOST_STATIC_ASSERT(Index <= 1);
1204
1205         operation_type blocked = operation_blocked;
1206         switch(side_rk_r)
1207         {
1208             case 1 :
1209                 // Turning left on opposite collinear: intersection
1210                 tp.operations[Index].operation = operation_intersection;
1211                 break;
1212             case -1 :
1213                 // Turning right on opposite collinear: union
1214                 tp.operations[Index].operation = operation_union;
1215                 break;
1216             case 0 :
1217                 // No turn on opposite collinear: block, do not traverse
1218                 // But this "xx" is usually ignored, it is useless to include
1219                 // two operations blocked, so the whole point does not need
1220                 // to be generated.
1221                 // So return false to indicate nothing is to be done.
1222                 if BOOST_GEOMETRY_CONSTEXPR (AssignPolicy::include_opposite)
1223                 {
1224                     tp.operations[Index].operation = operation_opposite;
1225                     blocked = operation_opposite;
1226                 }
1227                 else
1228                 {
1229                     return false;
1230                 }
1231                 break;
1232         }
1233
1234         // The other direction is always blocked when collinear opposite
1235         tp.operations[1 - Index].operation = blocked;
1236
1237         // If P arrives within Q, set info on P (which is done above, index=0),
1238         // this turn-info belongs to the second intersection point, index=1
1239         // (see e.g. figure CLO1)
1240         assign_point(tp, method_collinear, intersection_info, 1 - Index);
1241         return true;
1242     }
1243
1244 public:
1245     static inline void empty_transformer(TurnInfo &) {}
1246
1247     template
1248     <
1249         typename UniqueSubRange1,
1250         typename UniqueSubRange2,
1251         typename OutputIterator,
1252         typename IntersectionInfo,
1253         typename SidePolicy
1254     >
1255     static inline void apply(
1256                 UniqueSubRange1 const& range_p,
1257                 UniqueSubRange2 const& range_q,
1258
1259                 // Opposite collinear can deliver 2 intersection points,
1260                 TurnInfo const& tp_model,
1261                 OutputIterator& out,
1262
1263                 IntersectionInfo const& intersection_info,
1264                 SidePolicy const& side)
1265     {
1266         apply(range_p, range_q,
1267               tp_model, out, intersection_info, side, empty_transformer);
1268     }
1269
1270     template
1271     <
1272         typename UniqueSubRange1,
1273         typename UniqueSubRange2,
1274         typename OutputIterator,
1275         typename IntersectionInfo,
1276         typename SidePolicy,
1277         typename TurnTransformer
1278     >
1279     static inline void apply(
1280                 UniqueSubRange1 const& range_p,
1281                 UniqueSubRange2 const& range_q,
1282
1283                 // Opposite collinear can deliver 2 intersection points,
1284                 TurnInfo const& tp_model,
1285                 OutputIterator& out,
1286
1287                 IntersectionInfo const& info,
1288                 SidePolicy const& side,
1289                 TurnTransformer turn_transformer)
1290     {
1291         TurnInfo tp = tp_model;
1292
1293         int const arrival_p = info.d_info().arrival[0];
1294         int const arrival_q = info.d_info().arrival[1];
1295
1296         // If P arrives within Q, there is a turn dependent on P
1297         if ( arrival_p == 1
1298           && ! range_p.is_last_segment()
1299           && set_tp<0>(side.pk_wrt_p1(), tp, info.i_info()) )
1300         {
1301             turn_transformer(tp);
1302
1303             *out++ = tp;
1304         }
1305
1306         // If Q arrives within P, there is a turn dependent on Q
1307         if ( arrival_q == 1
1308           && ! range_q.is_last_segment()
1309           && set_tp<1>(side.qk_wrt_q1(), tp, info.i_info()) )
1310         {
1311             turn_transformer(tp);
1312
1313             *out++ = tp;
1314         }
1315
1316         if BOOST_GEOMETRY_CONSTEXPR (AssignPolicy::include_opposite)
1317         {
1318             // Handle cases not yet handled above
1319             if ((arrival_q == -1 && arrival_p == 0)
1320                 || (arrival_p == -1 && arrival_q == 0))
1321             {
1322                 for (unsigned int i = 0; i < 2; i++)
1323                 {
1324                     tp.operations[i].operation = operation_opposite;
1325                 }
1326                 for (unsigned int i = 0; i < info.i_info().count; i++)
1327                 {
1328                     assign_point(tp, method_collinear, info.i_info(), i);
1329                     *out++ = tp;
1330                 }
1331             }
1332         }
1333
1334     }
1335 };
1336
1337
1338 template
1339 <
1340     typename TurnInfo
1341 >
1342 struct crosses : public base_turn_handler
1343 {
1344     template <typename IntersectionInfo, typename DirInfo>
1345     static inline void apply(TurnInfo& ti,
1346                 IntersectionInfo const& intersection_info,
1347                 DirInfo const& dir_info)
1348     {
1349         assign_point(ti, method_crosses, intersection_info, 0);
1350
1351         // In all cases:
1352         // If Q crosses P from left to right
1353         // Union: take P
1354         // Intersection: take Q
1355         // Otherwise: vice versa
1356         int const side_qi_p1 = dir_info.sides.template get<1, 0>();
1357         unsigned int const index = side_qi_p1 == 1 ? 0 : 1;
1358         ti.operations[index].operation = operation_union;
1359         ti.operations[1 - index].operation = operation_intersection;
1360     }
1361 };
1362
1363 struct only_convert : public base_turn_handler
1364 {
1365     template<typename TurnInfo, typename IntersectionInfo>
1366     static inline void apply(TurnInfo& ti, IntersectionInfo const& intersection_info)
1367     {
1368         assign_point(ti, method_none, intersection_info, 0);
1369         ti.operations[0].operation = operation_continue;
1370         ti.operations[1].operation = operation_continue;
1371     }
1372 };
1373
1374 /*!
1375 \brief Policy doing nothing
1376 \details get_turn_info can have an optional policy include extra
1377     truns. By default it does not, and this class is that default.
1378  */
1379 struct assign_null_policy
1380 {
1381     static bool const include_no_turn = false;
1382     static bool const include_degenerate = false;
1383     static bool const include_opposite = false;
1384     static bool const include_start_turn = false;
1385 };
1386
1387 struct assign_policy_only_start_turns
1388 {
1389     static bool const include_no_turn = false;
1390     static bool const include_degenerate = false;
1391     static bool const include_opposite = false;
1392     static bool const include_start_turn = true;
1393 };
1394
1395 /*!
1396     \brief Turn information: intersection point, method, and turn information
1397     \details Information necessary for traversal phase (a phase
1398         of the overlay process). The information is gathered during the
1399         get_turns (segment intersection) phase.
1400     \tparam AssignPolicy policy to assign extra info,
1401         e.g. to calculate distance from segment's first points
1402         to intersection points.
1403         It also defines if a certain class of points
1404         (degenerate, non-turns) should be included.
1405  */
1406 template<typename AssignPolicy>
1407 struct get_turn_info
1408 {
1409     // Intersect a segment p with a segment q
1410     // Both p and q are modelled as sub_ranges to provide more points
1411     // to be able to give more information about the turn (left/right)
1412     template
1413     <
1414         typename UniqueSubRange1,
1415         typename UniqueSubRange2,
1416         typename TurnInfo,
1417         typename UmbrellaStrategy,
1418         typename OutputIterator
1419     >
1420     static inline OutputIterator apply(
1421                 UniqueSubRange1 const& range_p,
1422                 UniqueSubRange2 const& range_q,
1423                 TurnInfo const& tp_model,
1424                 UmbrellaStrategy const& umbrella_strategy,
1425                 OutputIterator out)
1426     {
1427         using inters_info = intersection_info
1428             <
1429                 UniqueSubRange1, UniqueSubRange2,
1430                 typename TurnInfo::point_type,
1431                 UmbrellaStrategy
1432             >;
1433
1434         inters_info inters(range_p, range_q, umbrella_strategy);
1435
1436         char const method = inters.d_info().how;
1437
1438         if (method == 'd')
1439         {
1440             // Disjoint
1441             return out;
1442         }
1443
1444         // Copy, to copy possibly extended fields
1445         TurnInfo tp = tp_model;
1446
1447         bool const handle_as_touch_interior = method == 'm';
1448         bool const handle_as_cross = method == 'i';
1449         bool handle_as_touch = method == 't';
1450         bool handle_as_equal = method == 'e';
1451         bool const handle_as_collinear = method == 'c';
1452         bool const handle_as_degenerate = method == '0';
1453         bool const handle_as_start = method == 's';
1454
1455         // (angle, from)
1456         bool do_only_convert = method == 'a' || method == 'f';
1457
1458         if (handle_as_start)
1459         {
1460             // It is in some cases necessary to handle a start turn
1461             using handler = start<TurnInfo, verify_policy_aa>;
1462             if (BOOST_GEOMETRY_CONDITION(AssignPolicy::include_start_turn)
1463                 && handler::apply(range_p, range_q, tp,
1464                                inters.i_info(), inters.d_info(), inters.sides(),
1465                                umbrella_strategy))
1466             {
1467                 *out++ = tp;
1468             }
1469             else
1470             {
1471               do_only_convert = true;
1472             }
1473         }
1474
1475         if (handle_as_touch_interior)
1476         {
1477             using handler = touch_interior<TurnInfo, verify_policy_aa>;
1478
1479             if ( inters.d_info().arrival[1] == 1 )
1480             {
1481                 // Q arrives
1482                 if (handler::handle_as_touch(inters.i_info(), inters.sides(), range_p, range_q))
1483                 {
1484                     handle_as_touch = true;
1485                 }
1486                 else
1487                 {
1488                     handler::template apply<0>(range_p, range_q, tp, inters.i_info(), inters.d_info(),
1489                                 inters.sides(), umbrella_strategy);
1490                     *out++ = tp;
1491                 }
1492             }
1493             else
1494             {
1495                 // P arrives, swap p/q
1496                 if (handler::handle_as_touch(inters.i_info(), inters.swapped_sides(), range_q, range_p))
1497                 {
1498                     handle_as_touch = true;
1499                 }
1500                 else
1501                 {
1502                     handler::template apply<1>(range_q, range_p, tp, inters.i_info(), inters.d_info(),
1503                                 inters.swapped_sides(), umbrella_strategy);
1504                     *out++ = tp;
1505                 }
1506             }
1507         }
1508
1509         if (handle_as_cross)
1510         {
1511             crosses<TurnInfo>::apply(tp, inters.i_info(), inters.d_info());
1512             *out++ = tp;
1513         }
1514
1515         if (handle_as_touch)
1516         {
1517             // Touch: both segments arrive at the intersection point
1518             using handler = touch<TurnInfo, verify_policy_aa>;
1519             handler::apply(range_p, range_q, tp, inters.i_info(), inters.d_info(), inters.sides(),
1520                            umbrella_strategy);
1521             *out++ = tp;
1522         }
1523
1524         if (handle_as_collinear)
1525         {
1526             // Collinear
1527             if ( ! inters.d_info().opposite )
1528             {
1529                 using handler = collinear<TurnInfo, verify_policy_aa>;
1530                 if (inters.d_info().arrival[0] == 0
1531                     || handler::handle_as_equal(inters.i_info(), range_p, range_q, inters.d_info()))
1532                 {
1533                     // Both segments arrive at the second intersection point
1534                     handle_as_equal = true;
1535                 }
1536                 else
1537                 {
1538                     handler::apply(range_p, range_q, tp, inters.i_info(),
1539                                    inters.d_info(), inters.sides());
1540                     *out++ = tp;
1541                 }
1542             }
1543             else
1544             {
1545                 collinear_opposite
1546                     <
1547                         TurnInfo,
1548                         AssignPolicy
1549                     >::apply(range_p, range_q, tp, out, inters, inters.sides());
1550                 // Zero, or two, turn points are assigned to *out++
1551             }
1552         }
1553
1554         if (handle_as_equal)
1555         {
1556             if ( ! inters.d_info().opposite )
1557             {
1558                 // Both equal
1559                 // or collinear-and-ending at intersection point
1560                 using handler = equal<TurnInfo, verify_policy_aa>;
1561                 handler::apply(range_p, range_q, tp,
1562                         inters.i_info(), inters.d_info(), inters.sides(),
1563                         umbrella_strategy);
1564                 if (handle_as_collinear)
1565                 {
1566                     // Keep info as collinear,
1567                     // so override already assigned method
1568                     tp.method = method_collinear;
1569                 }
1570                 *out++ = tp;
1571             }
1572             else
1573             {
1574                 equal_opposite
1575                     <
1576                         TurnInfo,
1577                         AssignPolicy
1578                     >::apply(range_p, range_q, tp, out, inters);
1579                 // Zero, or two, turn points are assigned to *out++
1580             }
1581         }
1582
1583         if ((handle_as_degenerate
1584              && BOOST_GEOMETRY_CONDITION(AssignPolicy::include_degenerate))
1585             || (do_only_convert
1586                 && BOOST_GEOMETRY_CONDITION(AssignPolicy::include_no_turn)))
1587         {
1588             if (inters.i_info().count > 0)
1589             {
1590                 only_convert::apply(tp, inters.i_info());
1591                 *out++ = tp;
1592             }
1593         }
1594
1595         return out;
1596     }
1597 };
1598
1599
1600 }} // namespace detail::overlay
1601 #endif //DOXYGEN_NO_DETAIL
1602
1603
1604 }} // namespace boost::geometry
1605
1606
1607 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HPP