detail/overlay/get_turn_info.hpp

0001 // Boost.Geometry
0002
0003 // Copyright (c) 2007-2023 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2017 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/condition.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_CONDITION(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 (side == 0
0313             && BOOST_GEOMETRY_CONDITION(VerifyPolicy::use_side_verification))
0314         {
0315             if (index_p >= 1 && range_p.is_last_segment())
0316             {
0317                 return 0;
0318             }
0319             if (index_q >= 2 && range_q.is_last_segment())
0320             {
0321                 return 0;
0322             }
0323
0324             auto const dm = get_distance_measure(range_p.at(index_p),
0325                                                  range_p.at(index_p + 1),
0326                                                  range_q.at(index_q),
0327                                                  umbrella_strategy);
0328             static decltype(dm.measure) const zero = 0;
0329             return dm.measure == zero ? 0 : dm.measure > zero ? 1 : -1;
0330         }
0331         else
0332         {
0333             return side;
0334         }
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_CONDITION(VerifyPolicy::use_handle_as_touch))
0358         {
0359             return false;
0360         }
0361
0362         //
0363         //
0364         //                         ^  Q(i)                ^ P(i)
0365         //                          \                    /
0366         //                           \                  /
0367         //                            \                /
0368         //                             \              /
0369         //                              \            /
0370         //                               \          /
0371         //                                \        /
0372         //                                 \      /
0373         //                                  \    /
0374         //                                   \  / it is about buffer_rt_r
0375         //                  P(k)              v/  they touch here "in the middle", but at the intersection...
0376         //                  <---------------->v   there is no follow up IP
0377         //                                   /
0378         //                                  /
0379         //                                 /
0380         //                                /
0381         //                               /
0382         //                              /
0383         //                             v Q(k)
0384         //
0385
0386         // Measure where the IP is located. If it is really close to the end,
0387         // then there is no space for the next IP (on P(1)/Q(2). A "from"
0388         // intersection will be generated, but those are never handled.
0389         // Therefore handle it as a normal touch (two segments arrive at the
0390         // intersection point). It currently checks for zero, but even a
0391         // distance a little bit larger would do.
0392         auto const dm = fun::distance_measure(info.intersections[0], non_touching_range.at(1));
0393         decltype(dm) const zero = 0;
0394         bool const result = math::equals(dm, zero);
0395         return result;
0396     }
0397
0398     // Index: 0, P is the interior, Q is touching and vice versa
0399     template
0400     <
0401         unsigned int Index,
0402         typename UniqueSubRange1,
0403         typename UniqueSubRange2,
0404         typename IntersectionInfo,
0405         typename DirInfo,
0406         typename SidePolicy,
0407         typename UmbrellaStrategy
0408     >
0409     static inline void apply(UniqueSubRange1 const& range_p,
0410                 UniqueSubRange2 const& range_q,
0411                 TurnInfo& ti,
0412                 IntersectionInfo const& intersection_info,
0413                 DirInfo const& dir_info,
0414                 SidePolicy const& side,
0415                 UmbrellaStrategy const& umbrella_strategy)
0416     {
0417         assign_point_and_correct(ti, method_touch_interior, intersection_info, dir_info);
0418
0419         // Both segments of q touch segment p somewhere in its interior
0420         // 1) We know: if q comes from LEFT or RIGHT
0421         // (i.e. dir_info.sides.get<Index,0>() == 1 or -1)
0422         // 2) Important is: if q_k goes to LEFT, RIGHT, COLLINEAR
0423         //    and, if LEFT/COLL, if it is lying LEFT or RIGHT w.r.t. q_i
0424
0425         BOOST_STATIC_ASSERT(Index <= 1);
0426         static unsigned int const index_p = Index;
0427         static unsigned int const index_q = 1 - Index;
0428
0429         bool const has_pk = ! range_p.is_last_segment();
0430         bool const has_qk = ! range_q.is_last_segment();
0431         int const side_qi_p = dir_info.sides.template get<index_q, 0>();
0432         int const side_qk_p = has_qk ? side.qk_wrt_p1() : 0;
0433
0434         if (side_qi_p == -side_qk_p)
0435         {
0436             // Q crosses P from left->right or from right->left (test "ML1")
0437             // Union: folow P (left->right) or Q (right->left)
0438             // Intersection: other turn
0439             unsigned int index = side_qk_p == -1 ? index_p : index_q;
0440             ti.operations[index].operation = operation_union;
0441             ti.operations[1 - index].operation = operation_intersection;
0442             return;
0443         }
0444
0445         int const side_qk_q = has_qk ? side.qk_wrt_q1() : 0;
0446
0447         // Only necessary if rescaling is turned off:
0448         int const side_pj_q2 = has_qk ? side.pj_wrt_q2() : 0;
0449
0450         if (side_qi_p == -1 && side_qk_p == -1 && side_qk_q == 1)
0451         {
0452             // Q turns left on the right side of P (test "MR3")
0453             // Both directions for "intersection"
0454             both(ti, operation_intersection);
0455             ti.touch_only = true;
0456         }
0457         else if (side_qi_p == 1 && side_qk_p == 1 && side_qk_q == -1)
0458         {
0459             if (has_qk && side_pj_q2 == -1)
0460             {
0461                 // Q turns right on the left side of P (test "ML3")
0462                 // Union: take both operations
0463                 // Intersection: skip
0464                 both(ti, operation_union);
0465             }
0466             else
0467             {
0468                 // q2 is collinear with p1, so it does not turn back. This
0469                 // can happen in floating point precision. In this case,
0470                 // block one of the operations to avoid taking that path.
0471                 ti.operations[index_p].operation = operation_union;
0472                 ti.operations[index_q].operation = operation_blocked;
0473             }
0474             ti.touch_only = true;
0475         }
0476         else if (side_qi_p == side_qk_p && side_qi_p == side_qk_q)
0477         {
0478             // Q turns left on the left side of P (test "ML2")
0479             // or Q turns right on the right side of P (test "MR2")
0480             // Union: take left turn (Q if Q turns left, P if Q turns right)
0481             // Intersection: other turn
0482             unsigned int index = side_qk_q == 1 ? index_q : index_p;
0483             if (has_qk && side_pj_q2 == 0)
0484             {
0485                 // Even though sides xk w.r.t. 1 are distinct, pj is collinear
0486                 // with q. Therefore swap the path
0487                 index = 1 - index;
0488             }
0489
0490             if (has_pk && has_qk && opposite(side_pj_q2, side_qi_p))
0491             {
0492                 // Without rescaling, floating point requires extra measures
0493                 int const side_qj_p1 = side.qj_wrt_p1();
0494                 int const side_qj_p2 = side.qj_wrt_p2();
0495
0496                 if (same(side_qj_p1, side_qj_p2))
0497                 {
0498                     int const side_pj_q1 = side.pj_wrt_q1();
0499                     if (opposite(side_pj_q1, side_pj_q2))
0500                     {
0501                         index = 1 - index;
0502                     }
0503                 }
0504             }
0505
0506             ti.operations[index].operation = operation_union;
0507             ti.operations[1 - index].operation = operation_intersection;
0508             ti.touch_only = true;
0509         }
0510         else if (side_qk_p == 0)
0511         {
0512             // Q intersects on interior of P and continues collinearly
0513             if (side_qk_q == side_qi_p)
0514             {
0515                 fun::template both_collinear<index_p, index_q>(range_p, range_q, umbrella_strategy,
0516                                                                1, 2, ti);
0517             }
0518             else
0519             {
0520                 // Opposite direction, which is never travelled.
0521                 // If Q turns left, P continues for intersection
0522                 // If Q turns right, P continues for union
0523                 ti.operations[index_p].operation = side_qk_q == 1
0524                     ? operation_intersection
0525                     : operation_union;
0526                 ti.operations[index_q].operation = operation_blocked;
0527             }
0528         }
0529         else
0530         {
0531             // Should not occur!
0532             ti.method = method_error;
0533         }
0534     }
0535 };
0536
0537
0538 template
0539 <
0540     typename TurnInfo,
0541     typename VerifyPolicy
0542 >
0543 struct touch : public base_turn_handler
0544 {
0545     using fun = turn_info_verification_functions<VerifyPolicy>;
0546
0547     static inline bool between(int side1, int side2, int turn)
0548     {
0549         return side1 == side2 && ! opposite(side1, turn);
0550     }
0551
0552     template
0553     <
0554         typename UniqueSubRange1,
0555         typename UniqueSubRange2,
0556         typename UmbrellaStrategy
0557     >
0558     static inline bool handle_imperfect_touch(UniqueSubRange1 const& range_p,
0559                                               UniqueSubRange2 const& range_q,
0560                                               int side_pk_q2,
0561                                               UmbrellaStrategy const& umbrella_strategy,
0562                                               TurnInfo& ti)
0563     {
0564         if (! BOOST_GEOMETRY_CONDITION(VerifyPolicy::use_handle_imperfect_touch))
0565         {
0566             return false;
0567         }
0568
0569         //  Q
0570         //  ^
0571         // ||
0572         // ||
0573         // |^----
0574         // >----->P
0575         // *            * they touch here (P/Q are (nearly) on top)
0576         //
0577         // Q continues from where P comes.
0578         // P continues from where Q comes
0579         // This is often a blocking situation,
0580         // unless there are FP issues: there might be a distance
0581         // between Pj and Qj, in that case handle it as a union.
0582         //
0583         // Exaggerated:
0584         //  Q
0585         //  ^           Q is nearly vertical
0586         //   \          but not completely - and still ends above P
0587         // |  \qj       In this case it should block P and
0588         // |  ^------   set Q to Union
0589         // >----->P     qj is LEFT of P1 and pi is LEFT of Q2
0590         //              (the other way round is also possible)
0591
0592         auto has_distance = [&](auto const& r1, auto const& r2) -> bool
0593         {
0594             auto const d1 = get_distance_measure(r1.at(0), r1.at(1), r2.at(1), umbrella_strategy);
0595             auto const d2 = get_distance_measure(r2.at(1), r2.at(2), r1.at(0), umbrella_strategy);
0596             return d1.measure > 0 && d2.measure > 0;
0597         };
0598
0599         if (side_pk_q2 == -1 && has_distance(range_p, range_q))
0600         {
0601             // Even though there is a touch, Q(j) is left of P1
0602             // and P(i) is still left from Q2.
0603             // Q continues to the right.
0604             // It can continue.
0605             ti.operations[0].operation = operation_blocked;
0606             // Q turns right -> union (both independent),
0607             // Q turns left -> intersection
0608             ti.operations[1].operation = operation_union;
0609             ti.touch_only = true;
0610             return true;
0611         }
0612
0613         if (side_pk_q2 == 1 && has_distance(range_q, range_p))
0614         {
0615             // Similarly, but the other way round.
0616             // Q continues to the left.
0617             ti.operations[0].operation = operation_union;
0618             ti.operations[1].operation = operation_blocked;
0619             ti.touch_only = true;
0620             return true;
0621         }
0622         return false;
0623     }
0624
0625     template
0626     <
0627         typename UniqueSubRange1,
0628         typename UniqueSubRange2,
0629         typename IntersectionInfo,
0630         typename DirInfo,
0631         typename SideCalculator,
0632         typename UmbrellaStrategy
0633     >
0634     static inline void apply(UniqueSubRange1 const& range_p,
0635                 UniqueSubRange2 const& range_q,
0636                 TurnInfo& ti,
0637                 IntersectionInfo const& intersection_info,
0638                 DirInfo const& dir_info,
0639                 SideCalculator const& side,
0640                 UmbrellaStrategy const& umbrella_strategy)
0641     {
0642         assign_point_and_correct(ti, method_touch, intersection_info, dir_info);
0643
0644         bool const has_pk = ! range_p.is_last_segment();
0645         bool const has_qk = ! range_q.is_last_segment();
0646
0647         int const side_pk_q1 = has_pk ? side.pk_wrt_q1() : 0;
0648
0649         int const side_qi_p1 = fun::verified_side(dir_info.sides.template get<1, 0>(),
0650                                                   range_p, range_q, umbrella_strategy, 0, 0);
0651         int const side_qk_p1 = has_qk
0652                              ? fun::verified_side(side.qk_wrt_p1(), range_p, range_q,
0653                                                   umbrella_strategy, 0, 2)
0654                              : 0;
0655
0656         // If Qi and Qk are both at same side of Pi-Pj,
0657         // or collinear (so: not opposite sides)
0658         if (! opposite(side_qi_p1, side_qk_p1))
0659         {
0660             int const side_pk_q2 = has_pk && has_qk ? side.pk_wrt_q2() : 0;
0661             int const side_pk_p  = has_pk ? side.pk_wrt_p1() : 0;
0662             int const side_qk_q  = has_qk ? side.qk_wrt_q1() : 0;
0663
0664             bool const q_turns_left = side_qk_q == 1;
0665
0666             bool const block_q = side_qk_p1 == 0
0667                         && ! same(side_qi_p1, side_qk_q)
0668                         ;
0669
0670             // If Pk at same side as Qi/Qk
0671             // (the "or" is for collinear case)
0672             // or Q is fully collinear && P turns not to left
0673             if (side_pk_p == side_qi_p1
0674                 || side_pk_p == side_qk_p1
0675                 || (side_qi_p1 == 0 && side_qk_p1 == 0 && side_pk_p != -1))
0676             {
0677                 if (side_qk_p1 == 0 && side_pk_q1 == 0
0678                     && has_pk && has_qk
0679                     && handle_imperfect_touch(range_p, range_q, side_pk_q2, umbrella_strategy, ti))
0680                 {
0681                     // If q continues collinearly (opposite) with p, it should be blocked
0682                     // but (FP) not if there is just a tiny space in between
0683                     return;
0684                 }
0685                 // Collinear -> lines join, continue
0686                 // (#BRL2)
0687                 if (side_pk_q2 == 0 && ! block_q)
0688                 {
0689                     fun::template both_collinear<0, 1>(range_p, range_q, umbrella_strategy,
0690                                                        2, 2, ti);
0691                     return;
0692                 }
0693
0694                 // Collinear opposite case -> block P
0695                 // (#BRL4, #BLR8)
0696                 if (side_pk_q1 == 0)
0697                 {
0698                     ti.operations[0].operation = operation_blocked;
0699                     // Q turns right -> union (both independent),
0700                     // Q turns left -> intersection
0701                     ti.operations[1].operation = block_q ? operation_blocked
0702                         : q_turns_left ? operation_intersection
0703                         : operation_union;
0704                     return;
0705                 }
0706
0707                 // Pk between Qi and Qk
0708                 // (#BRL3, #BRL7)
0709                 if (between(side_pk_q1, side_pk_q2, side_qk_q))
0710                 {
0711                     ui_else_iu(q_turns_left, ti);
0712                     if (block_q)
0713                     {
0714                         ti.operations[1].operation = operation_blocked;
0715                     }
0716                     return;
0717                 }
0718
0719                 // Pk between Qk and P, so left of Qk (if Q turns right) and vv
0720                 // (#BRL1)
0721                 if (side_pk_q2 == -side_qk_q)
0722                 {
0723                     ui_else_iu(! q_turns_left, ti);
0724                     ti.touch_only = true;
0725                     return;
0726                 }
0727
0728                 //
0729                 // (#BRL5, #BRL9)
0730                 if (side_pk_q1 == -side_qk_q)
0731                 {
0732                     uu_else_ii(! q_turns_left, ti);
0733                     if (block_q)
0734                     {
0735                         ti.operations[1].operation = operation_blocked;
0736                     }
0737                     else
0738                     {
0739                         ti.touch_only = true;
0740                     }
0741                     return;
0742                 }
0743             }
0744             else
0745             {
0746                 // Pk at other side than Qi/Pk
0747                 ti.operations[0].operation = q_turns_left
0748                             ? operation_intersection
0749                             : operation_union;
0750                 ti.operations[1].operation = block_q
0751                             ? operation_blocked
0752                             : side_qi_p1 == 1 || side_qk_p1 == 1
0753                             ? operation_union
0754                             : operation_intersection;
0755                 if (! block_q)
0756                 {
0757                     ti.touch_only = true;
0758                 }
0759
0760                 return;
0761             }
0762         }
0763         else
0764         {
0765             // The qi/qk are opposite to each other, w.r.t. p1
0766             // From left to right or from right to left
0767             int const side_pk_p = has_pk
0768                                 ? fun::verified_side(side.pk_wrt_p1(), range_p, range_p,
0769                                                      umbrella_strategy, 0, 2)
0770                                 : 0;
0771             bool const right_to_left = side_qk_p1 == 1;
0772
0773             // If p turns into direction of qi (1,2)
0774             if (side_pk_p == side_qi_p1)
0775             {
0776                 // Collinear opposite case -> block P
0777                 if (side_pk_q1 == 0)
0778                 {
0779                     ti.operations[0].operation = operation_blocked;
0780                     ti.operations[1].operation = right_to_left
0781                                 ? operation_union : operation_intersection;
0782                     return;
0783                 }
0784
0785                 if (side_pk_q1 == side_qk_p1)
0786                 {
0787                     uu_else_ii(right_to_left, ti);
0788                     ti.touch_only = true;
0789                     return;
0790                 }
0791             }
0792
0793             // If p turns into direction of qk (4,5)
0794             if (side_pk_p == side_qk_p1)
0795             {
0796                 int const side_pk_q2 = has_pk ? side.pk_wrt_q2() : 0;
0797
0798                 // Collinear case -> lines join, continue
0799                 if (side_pk_q2 == 0)
0800                 {
0801                     both(ti, operation_continue);
0802                     return;
0803                 }
0804                 if (side_pk_q2 == side_qk_p1)
0805                 {
0806                     ui_else_iu(right_to_left, ti);
0807                     ti.touch_only = true;
0808                     return;
0809                 }
0810             }
0811             // otherwise (3)
0812             ui_else_iu(! right_to_left, ti);
0813             return;
0814         }
0815     }
0816 };
0817
0818
0819 template
0820 <
0821     typename TurnInfo,
0822     typename VerifyPolicy
0823 >
0824 struct equal : public base_turn_handler
0825 {
0826     using fun = turn_info_verification_functions<VerifyPolicy>;
0827
0828     template
0829     <
0830         typename UniqueSubRange1,
0831         typename UniqueSubRange2,
0832         typename IntersectionInfo,
0833         typename DirInfo,
0834         typename SideCalculator,
0835         typename UmbrellaStrategy
0836     >
0837     static inline void apply(UniqueSubRange1 const& range_p,
0838                 UniqueSubRange2 const& range_q,
0839                 TurnInfo& ti,
0840                 IntersectionInfo const& info,
0841                 DirInfo const& ,
0842                 SideCalculator const& side,
0843                 UmbrellaStrategy const& umbrella_strategy)
0844     {
0845         // Copy the intersection point in TO direction
0846         assign_point(ti, method_equal, info, non_opposite_to_index(info));
0847
0848         bool const has_pk = ! range_p.is_last_segment();
0849         bool const has_qk = ! range_q.is_last_segment();
0850
0851         int const side_pk_q2 = has_pk && has_qk ? side.pk_wrt_q2() : 0;
0852         int const side_pk_p = has_pk ? side.pk_wrt_p1() : 0;
0853         int const side_qk_p = has_qk ? side.qk_wrt_p1() : 0;
0854
0855         if (has_pk && has_qk && side_pk_p == side_qk_p)
0856         {
0857             // They turn to the same side, or continue both collinearly
0858             // To check for union/intersection, try to check side values
0859             int const side_qk_p2 = side.qk_wrt_p2();
0860
0861             if (opposite(side_qk_p2, side_pk_q2))
0862             {
0863                 ui_else_iu(side_pk_q2 == 1, ti);
0864                 return;
0865             }
0866         }
0867
0868         // If pk is collinear with qj-qk, they continue collinearly.
0869         // This can be on either side of p1 (== q1), or collinear
0870         // The second condition checks if they do not continue
0871         // oppositely
0872         if (side_pk_q2 == 0 && side_pk_p == side_qk_p)
0873         {
0874             fun::template both_collinear<0, 1>(range_p, range_q, umbrella_strategy, 2, 2, ti);
0875             return;
0876         }
0877
0878
0879         // If they turn to same side (not opposite sides)
0880         if (! opposite(side_pk_p, side_qk_p))
0881         {
0882             // If pk is left of q2 or collinear: p: union, q: intersection
0883             ui_else_iu(side_pk_q2 != -1, ti);
0884         }
0885         else
0886         {
0887             // They turn opposite sides. If p turns left (or collinear),
0888             // p: union, q: intersection
0889             ui_else_iu(side_pk_p != -1, ti);
0890         }
0891     }
0892 };
0893
0894 template
0895 <
0896     typename TurnInfo,
0897     typename VerifyPolicy
0898 >
0899 struct start : public base_turn_handler
0900 {
0901     template
0902     <
0903         typename UniqueSubRange1,
0904         typename UniqueSubRange2,
0905         typename IntersectionInfo,
0906         typename DirInfo,
0907         typename SideCalculator,
0908         typename UmbrellaStrategy
0909     >
0910     static inline bool apply(UniqueSubRange1 const& /*range_p*/,
0911                 UniqueSubRange2 const& /*range_q*/,
0912                 TurnInfo& ti,
0913                 IntersectionInfo const& info,
0914                 DirInfo const& dir_info,
0915                 SideCalculator const& side,
0916                 UmbrellaStrategy const& )
0917     {
0918         if (! BOOST_GEOMETRY_CONDITION(VerifyPolicy::use_start_turn))
0919         {
0920             return false;
0921         }
0922
0923         // Start turns have either how_a = -1, or how_b = -1 (either p leaves or q leaves)
0924         BOOST_GEOMETRY_ASSERT(dir_info.how_a != dir_info.how_b);
0925         BOOST_GEOMETRY_ASSERT(dir_info.how_a == -1 || dir_info.how_b == -1);
0926         BOOST_GEOMETRY_ASSERT(dir_info.how_a == 0 || dir_info.how_b == 0);
0927
0928         if (dir_info.how_b == -1)
0929         {
0930             // p --------------->
0931             //             |
0932             //             | q         q leaves
0933             //             v
0934             //
0935
0936             int const side_qj_p1 = side.qj_wrt_p1();
0937             ui_else_iu(side_qj_p1 == -1, ti);
0938         }
0939         else if (dir_info.how_a == -1)
0940         {
0941             // p leaves
0942             int const side_pj_q1 = side.pj_wrt_q1();
0943             ui_else_iu(side_pj_q1 == 1, ti);
0944         }
0945
0946         // Copy intersection point
0947         assign_point_and_correct(ti, method_start, info, dir_info);
0948         return true;
0949     }
0950
0951 };
0952
0953
0954 template
0955 <
0956     typename TurnInfo,
0957     typename AssignPolicy
0958 >
0959 struct equal_opposite : public base_turn_handler
0960 {
0961     template
0962     <
0963         typename UniqueSubRange1,
0964         typename UniqueSubRange2,
0965         typename OutputIterator,
0966         typename IntersectionInfo
0967     >
0968     static inline void apply(
0969                 UniqueSubRange1 const& /*range_p*/,
0970                 UniqueSubRange2 const& /*range_q*/,
0971                 /* by value: */ TurnInfo tp,
0972                 OutputIterator& out,
0973                 IntersectionInfo const& intersection_info)
0974     {
0975         // For equal-opposite segments, normally don't do anything.
0976         if (BOOST_GEOMETRY_CONDITION(AssignPolicy::include_opposite))
0977         {
0978             tp.method = method_equal;
0979             for (unsigned int i = 0; i < 2; i++)
0980             {
0981                 tp.operations[i].operation = operation_opposite;
0982             }
0983             for (unsigned int i = 0; i < intersection_info.i_info().count; i++)
0984             {
0985                 assign_point(tp, method_none, intersection_info.i_info(), i);
0986                 *out++ = tp;
0987             }
0988         }
0989     }
0990 };
0991
0992 template
0993 <
0994     typename TurnInfo,
0995     typename VerifyPolicy
0996 >
0997 struct collinear : public base_turn_handler
0998 {
0999     using fun = turn_info_verification_functions<VerifyPolicy>;
1000
1001     template
1002     <
1003         typename IntersectionInfo,
1004         typename UniqueSubRange1,
1005         typename UniqueSubRange2,
1006         typename DirInfo
1007     >
1008     static bool handle_as_equal(IntersectionInfo const& info,
1009                                 UniqueSubRange1 const& range_p,
1010                                 UniqueSubRange2 const& range_q,
1011                                 DirInfo const& dir_info)
1012     {
1013         if (! BOOST_GEOMETRY_CONDITION(VerifyPolicy::use_handle_as_equal))
1014         {
1015             return false;
1016         }
1017
1018         int const arrival_p = dir_info.arrival[0];
1019         int const arrival_q = dir_info.arrival[1];
1020         if (arrival_p * arrival_q != -1 || info.count != 2)
1021         {
1022             // Code below assumes that either p or q arrives in the other segment
1023             return false;
1024         }
1025
1026        auto const dm = arrival_p == 1
1027               ? fun::distance_measure(info.intersections[1], range_q.at(1))
1028               : fun::distance_measure(info.intersections[1], range_p.at(1));
1029         decltype(dm) const zero = 0;
1030         return math::equals(dm, zero);
1031     }
1032
1033     /*
1034         Either P arrives within Q (arrival_p == -1) or Q arrives within P.
1035
1036         Typical situation:
1037               ^q2
1038              /
1039             ^q1
1040            /         ____ ip[1]
1041           //|p1  } this section of p/q is colllinear
1042        q0// |    }   ____ ip[0]
1043          /  |
1044         /   v
1045        p0   p2
1046
1047        P arrives (at p1) in segment Q (between q0 and q1).
1048        Therefore arrival_p == 1
1049        P (p2) goes to the right (-1). Follow P for intersection, or follow Q for union.
1050        Therefore if (arrival_p==1) and side_p==-1, result = iu
1051
1052        Complete table:
1053
1054         arrival P   pk//p1  qk//q1   product   case    result
1055          1           1                1        CLL1    ui
1056         -1                   1       -1        CLL2    iu
1057          1           1                1        CLR1    ui
1058         -1                  -1        1        CLR2    ui
1059
1060          1          -1               -1        CRL1    iu
1061         -1                   1       -1        CRL2    iu
1062          1          -1               -1        CRR1    iu
1063         -1                  -1        1        CRR2    ui
1064
1065          1           0                0        CC1     cc
1066         -1                   0        0        CC2     cc
1067
1068          Resulting in the rule:
1069          The arrival-info multiplied by the relevant side delivers the result.
1070          product = arrival * (pk//p1 or qk//q1)
1071
1072          Stated otherwise:
1073          - if P arrives: look at turn P
1074          - if Q arrives: look at turn Q
1075          - if P arrives and P turns left: union for P
1076          - if P arrives and P turns right: intersection for P
1077          - if Q arrives and Q turns left: union for Q (=intersection for P)
1078          - if Q arrives and Q turns right: intersection for Q (=union for P)
1079     */
1080     template
1081     <
1082         typename UniqueSubRange1,
1083         typename UniqueSubRange2,
1084         typename IntersectionInfo,
1085         typename DirInfo,
1086         typename SidePolicy
1087     >
1088     static inline void apply(
1089                 UniqueSubRange1 const& range_p,
1090                 UniqueSubRange2 const& range_q,
1091                 TurnInfo& ti,
1092                 IntersectionInfo const& info,
1093                 DirInfo const& dir_info,
1094                 SidePolicy const& side)
1095     {
1096         // Copy the intersection point in TO direction
1097         assign_point(ti, method_collinear, info, non_opposite_to_index(info));
1098
1099         int const arrival_p = dir_info.arrival[0];
1100         // Should not be 0, this is checked before
1101         BOOST_GEOMETRY_ASSERT(arrival_p != 0);
1102
1103         bool const has_pk = ! range_p.is_last_segment();
1104         bool const has_qk = ! range_q.is_last_segment();
1105         int const side_p = has_pk ? side.pk_wrt_p1() : 0;
1106         int const side_q = has_qk ? side.qk_wrt_q1() : 0;
1107
1108         // If p arrives, use p, else use q
1109         int const side_p_or_q = arrival_p == 1
1110             ? side_p
1111             : side_q
1112             ;
1113
1114         // Calculate product according to comments above.
1115         int const product = arrival_p * side_p_or_q;
1116
1117         if (product == 0)
1118         {
1119             both(ti, operation_continue);
1120         }
1121         else
1122         {
1123             ui_else_iu(product == 1, ti);
1124         }
1125
1126         // Calculate remaining distance. If it continues collinearly it is
1127         // measured until the end of the next segment
1128         ti.operations[0].remaining_distance
1129                 = side_p == 0 && has_pk
1130                 ? fun::distance_measure(ti.point, range_p.at(2))
1131                 : fun::distance_measure(ti.point, range_p.at(1));
1132         ti.operations[1].remaining_distance
1133                 = side_q == 0 && has_qk
1134                 ? fun::distance_measure(ti.point, range_q.at(2))
1135                 : fun::distance_measure(ti.point, range_q.at(1));
1136     }
1137 };
1138
1139 template
1140 <
1141     typename TurnInfo,
1142     typename AssignPolicy
1143 >
1144 struct collinear_opposite : public base_turn_handler
1145 {
1146 private :
1147     /*
1148         arrival P  arrival Q  pk//p1   qk//q1  case  result2  result
1149         --------------------------------------------------------------
1150          1          1          1       -1      CLO1    ix      xu
1151          1          1          1        0      CLO2    ix      (xx)
1152          1          1          1        1      CLO3    ix      xi
1153
1154          1          1          0       -1      CCO1    (xx)    xu
1155          1          1          0        0      CCO2    (xx)    (xx)
1156          1          1          0        1      CCO3    (xx)    xi
1157
1158          1          1         -1       -1      CRO1    ux      xu
1159          1          1         -1        0      CRO2    ux      (xx)
1160          1          1         -1        1      CRO3    ux      xi
1161
1162         -1          1                  -1      CXO1    xu
1163         -1          1                   0      CXO2    (xx)
1164         -1          1                   1      CXO3    xi
1165
1166          1         -1          1               CXO1    ix
1167          1         -1          0               CXO2    (xx)
1168          1         -1         -1               CXO3    ux
1169     */
1170
1171     template <unsigned int Index, typename IntersectionInfo>
1172     static inline bool set_tp(int side_rk_r, TurnInfo& tp,
1173                               IntersectionInfo const& intersection_info)
1174     {
1175         BOOST_STATIC_ASSERT(Index <= 1);
1176
1177         operation_type blocked = operation_blocked;
1178         switch(side_rk_r)
1179         {
1180             case 1 :
1181                 // Turning left on opposite collinear: intersection
1182                 tp.operations[Index].operation = operation_intersection;
1183                 break;
1184             case -1 :
1185                 // Turning right on opposite collinear: union
1186                 tp.operations[Index].operation = operation_union;
1187                 break;
1188             case 0 :
1189                 // No turn on opposite collinear: block, do not traverse
1190                 // But this "xx" is usually ignored, it is useless to include
1191                 // two operations blocked, so the whole point does not need
1192                 // to be generated.
1193                 // So return false to indicate nothing is to be done.
1194                 if (BOOST_GEOMETRY_CONDITION(AssignPolicy::include_opposite))
1195                 {
1196                     tp.operations[Index].operation = operation_opposite;
1197                     blocked = operation_opposite;
1198                 }
1199                 else
1200                 {
1201                     return false;
1202                 }
1203                 break;
1204         }
1205
1206         // The other direction is always blocked when collinear opposite
1207         tp.operations[1 - Index].operation = blocked;
1208
1209         // If P arrives within Q, set info on P (which is done above, index=0),
1210         // this turn-info belongs to the second intersection point, index=1
1211         // (see e.g. figure CLO1)
1212         assign_point(tp, method_collinear, intersection_info, 1 - Index);
1213         return true;
1214     }
1215
1216 public:
1217     static inline void empty_transformer(TurnInfo &) {}
1218
1219     template
1220     <
1221         typename UniqueSubRange1,
1222         typename UniqueSubRange2,
1223         typename OutputIterator,
1224         typename IntersectionInfo,
1225         typename SidePolicy
1226     >
1227     static inline void apply(
1228                 UniqueSubRange1 const& range_p,
1229                 UniqueSubRange2 const& range_q,
1230
1231                 // Opposite collinear can deliver 2 intersection points,
1232                 TurnInfo const& tp_model,
1233                 OutputIterator& out,
1234
1235                 IntersectionInfo const& intersection_info,
1236                 SidePolicy const& side)
1237     {
1238         apply(range_p, range_q,
1239               tp_model, out, intersection_info, side, empty_transformer);
1240     }
1241
1242     template
1243     <
1244         typename UniqueSubRange1,
1245         typename UniqueSubRange2,
1246         typename OutputIterator,
1247         typename IntersectionInfo,
1248         typename SidePolicy,
1249         typename TurnTransformer
1250     >
1251     static inline void apply(
1252                 UniqueSubRange1 const& range_p,
1253                 UniqueSubRange2 const& range_q,
1254
1255                 // Opposite collinear can deliver 2 intersection points,
1256                 TurnInfo const& tp_model,
1257                 OutputIterator& out,
1258
1259                 IntersectionInfo const& info,
1260                 SidePolicy const& side,
1261                 TurnTransformer turn_transformer)
1262     {
1263         TurnInfo tp = tp_model;
1264
1265         int const arrival_p = info.d_info().arrival[0];
1266         int const arrival_q = info.d_info().arrival[1];
1267
1268         // If P arrives within Q, there is a turn dependent on P
1269         if ( arrival_p == 1
1270           && ! range_p.is_last_segment()
1271           && set_tp<0>(side.pk_wrt_p1(), tp, info.i_info()) )
1272         {
1273             turn_transformer(tp);
1274
1275             *out++ = tp;
1276         }
1277
1278         // If Q arrives within P, there is a turn dependent on Q
1279         if ( arrival_q == 1
1280           && ! range_q.is_last_segment()
1281           && set_tp<1>(side.qk_wrt_q1(), tp, info.i_info()) )
1282         {
1283             turn_transformer(tp);
1284
1285             *out++ = tp;
1286         }
1287
1288         if (BOOST_GEOMETRY_CONDITION(AssignPolicy::include_opposite))
1289         {
1290             // Handle cases not yet handled above
1291             if ((arrival_q == -1 && arrival_p == 0)
1292                 || (arrival_p == -1 && arrival_q == 0))
1293             {
1294                 for (unsigned int i = 0; i < 2; i++)
1295                 {
1296                     tp.operations[i].operation = operation_opposite;
1297                 }
1298                 for (unsigned int i = 0; i < info.i_info().count; i++)
1299                 {
1300                     assign_point(tp, method_collinear, info.i_info(), i);
1301                     *out++ = tp;
1302                 }
1303             }
1304         }
1305
1306     }
1307 };
1308
1309
1310 template
1311 <
1312     typename TurnInfo
1313 >
1314 struct crosses : public base_turn_handler
1315 {
1316     template <typename IntersectionInfo, typename DirInfo>
1317     static inline void apply(TurnInfo& ti,
1318                 IntersectionInfo const& intersection_info,
1319                 DirInfo const& dir_info)
1320     {
1321         assign_point(ti, method_crosses, intersection_info, 0);
1322
1323         // In all cases:
1324         // If Q crosses P from left to right
1325         // Union: take P
1326         // Intersection: take Q
1327         // Otherwise: vice versa
1328         int const side_qi_p1 = dir_info.sides.template get<1, 0>();
1329         unsigned int const index = side_qi_p1 == 1 ? 0 : 1;
1330         ti.operations[index].operation = operation_union;
1331         ti.operations[1 - index].operation = operation_intersection;
1332     }
1333 };
1334
1335 struct only_convert : public base_turn_handler
1336 {
1337     template<typename TurnInfo, typename IntersectionInfo>
1338     static inline void apply(TurnInfo& ti, IntersectionInfo const& intersection_info)
1339     {
1340         assign_point(ti, method_none, intersection_info, 0);
1341         ti.operations[0].operation = operation_continue;
1342         ti.operations[1].operation = operation_continue;
1343     }
1344 };
1345
1346 /*!
1347 \brief Policy doing nothing
1348 \details get_turn_info can have an optional policy include extra
1349     truns. By default it does not, and this class is that default.
1350  */
1351 struct assign_null_policy
1352 {
1353     static bool const include_no_turn = false;
1354     static bool const include_degenerate = false;
1355     static bool const include_opposite = false;
1356     static bool const include_start_turn = false;
1357 };
1358
1359 struct assign_policy_only_start_turns
1360 {
1361     static bool const include_no_turn = false;
1362     static bool const include_degenerate = false;
1363     static bool const include_opposite = false;
1364     static bool const include_start_turn = true;
1365 };
1366
1367 /*!
1368     \brief Turn information: intersection point, method, and turn information
1369     \details Information necessary for traversal phase (a phase
1370         of the overlay process). The information is gathered during the
1371         get_turns (segment intersection) phase.
1372     \tparam AssignPolicy policy to assign extra info,
1373         e.g. to calculate distance from segment's first points
1374         to intersection points.
1375         It also defines if a certain class of points
1376         (degenerate, non-turns) should be included.
1377  */
1378 template<typename AssignPolicy>
1379 struct get_turn_info
1380 {
1381     // Intersect a segment p with a segment q
1382     // Both p and q are modelled as sub_ranges to provide more points
1383     // to be able to give more information about the turn (left/right)
1384     template
1385     <
1386         typename UniqueSubRange1,
1387         typename UniqueSubRange2,
1388         typename TurnInfo,
1389         typename UmbrellaStrategy,
1390         typename RobustPolicy,
1391         typename OutputIterator
1392     >
1393     static inline OutputIterator apply(
1394                 UniqueSubRange1 const& range_p,
1395                 UniqueSubRange2 const& range_q,
1396                 TurnInfo const& tp_model,
1397                 UmbrellaStrategy const& umbrella_strategy,
1398                 RobustPolicy const& robust_policy,
1399                 OutputIterator out)
1400     {
1401         typedef intersection_info
1402             <
1403                 UniqueSubRange1, UniqueSubRange2,
1404                 typename TurnInfo::point_type,
1405                 UmbrellaStrategy,
1406                 RobustPolicy
1407             > inters_info;
1408
1409         inters_info inters(range_p, range_q, umbrella_strategy, robust_policy);
1410
1411         char const method = inters.d_info().how;
1412
1413         if (method == 'd')
1414         {
1415             // Disjoint
1416             return out;
1417         }
1418
1419         // Copy, to copy possibly extended fields
1420         TurnInfo tp = tp_model;
1421
1422         bool const handle_as_touch_interior = method == 'm';
1423         bool const handle_as_cross = method == 'i';
1424         bool handle_as_touch = method == 't';
1425         bool handle_as_equal = method == 'e';
1426         bool const handle_as_collinear = method == 'c';
1427         bool const handle_as_degenerate = method == '0';
1428         bool const handle_as_start = method == 's';
1429
1430         // (angle, from)
1431         bool do_only_convert = method == 'a' || method == 'f';
1432
1433         if (handle_as_start)
1434         {
1435             // It is in some cases necessary to handle a start turn
1436             using handler = start<TurnInfo, verify_policy_aa>;
1437             if (BOOST_GEOMETRY_CONDITION(AssignPolicy::include_start_turn)
1438                 && handler::apply(range_p, range_q, tp,
1439                                inters.i_info(), inters.d_info(), inters.sides(),
1440                                umbrella_strategy))
1441             {
1442                 *out++ = tp;
1443             }
1444             else
1445             {
1446               do_only_convert = true;
1447             }
1448         }
1449
1450         if (handle_as_touch_interior)
1451         {
1452             using handler = touch_interior<TurnInfo, verify_policy_aa>;
1453
1454             if ( inters.d_info().arrival[1] == 1 )
1455             {
1456                 // Q arrives
1457                 if (handler::handle_as_touch(inters.i_info(), range_p))
1458                 {
1459                     handle_as_touch = true;
1460                 }
1461                 else
1462                 {
1463                     handler::template apply<0>(range_p, range_q, tp, inters.i_info(), inters.d_info(),
1464                                 inters.sides(), umbrella_strategy);
1465                     *out++ = tp;
1466                 }
1467             }
1468             else
1469             {
1470                 // P arrives, swap p/q
1471                 if (handler::handle_as_touch(inters.i_info(), range_q))
1472                 {
1473                     handle_as_touch = true;
1474                 }
1475                 else
1476                 {
1477                     handler::template apply<1>(range_q, range_p, tp, inters.i_info(), inters.d_info(),
1478                                 inters.swapped_sides(), umbrella_strategy);
1479                     *out++ = tp;
1480                 }
1481             }
1482         }
1483
1484         if (handle_as_cross)
1485         {
1486             crosses<TurnInfo>::apply(tp, inters.i_info(), inters.d_info());
1487             *out++ = tp;
1488         }
1489
1490         if (handle_as_touch)
1491         {
1492             // Touch: both segments arrive at the intersection point
1493             using handler = touch<TurnInfo, verify_policy_aa>;
1494             handler::apply(range_p, range_q, tp, inters.i_info(), inters.d_info(), inters.sides(),
1495                            umbrella_strategy);
1496             *out++ = tp;
1497         }
1498
1499         if (handle_as_collinear)
1500         {
1501             // Collinear
1502             if ( ! inters.d_info().opposite )
1503             {
1504                 using handler = collinear<TurnInfo, verify_policy_aa>;
1505                 if (inters.d_info().arrival[0] == 0
1506                     || handler::handle_as_equal(inters.i_info(), range_p, range_q, inters.d_info()))
1507                 {
1508                     // Both segments arrive at the second intersection point
1509                     handle_as_equal = true;
1510                 }
1511                 else
1512                 {
1513                     handler::apply(range_p, range_q, tp, inters.i_info(),
1514                                    inters.d_info(), inters.sides());
1515                     *out++ = tp;
1516                 }
1517             }
1518             else
1519             {
1520                 collinear_opposite
1521                     <
1522                         TurnInfo,
1523                         AssignPolicy
1524                     >::apply(range_p, range_q, tp, out, inters, inters.sides());
1525                 // Zero, or two, turn points are assigned to *out++
1526             }
1527         }
1528
1529         if (handle_as_equal)
1530         {
1531             if ( ! inters.d_info().opposite )
1532             {
1533                 // Both equal
1534                 // or collinear-and-ending at intersection point
1535                 using handler = equal<TurnInfo, verify_policy_aa>;
1536                 handler::apply(range_p, range_q, tp,
1537                         inters.i_info(), inters.d_info(), inters.sides(),
1538                         umbrella_strategy);
1539                 if (handle_as_collinear)
1540                 {
1541                     // Keep info as collinear,
1542                     // so override already assigned method
1543                     tp.method = method_collinear;
1544                 }
1545                 *out++ = tp;
1546             }
1547             else
1548             {
1549                 equal_opposite
1550                     <
1551                         TurnInfo,
1552                         AssignPolicy
1553                     >::apply(range_p, range_q, tp, out, inters);
1554                 // Zero, or two, turn points are assigned to *out++
1555             }
1556         }
1557
1558         if ((handle_as_degenerate
1559              && BOOST_GEOMETRY_CONDITION(AssignPolicy::include_degenerate))
1560             || (do_only_convert
1561                 && BOOST_GEOMETRY_CONDITION(AssignPolicy::include_no_turn)))
1562         {
1563             if (inters.i_info().count > 0)
1564             {
1565                 only_convert::apply(tp, inters.i_info());
1566                 *out++ = tp;
1567             }
1568         }
1569
1570         return out;
1571     }
1572 };
1573
1574
1575 }} // namespace detail::overlay
1576 #endif //DOXYGEN_NO_DETAIL
1577
1578
1579 }} // namespace boost::geometry
1580
1581
1582 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HPP