detail/overlay/get_turn_info_helpers.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
0004
0005 // This file was modified by Oracle on 2013-2024.
0006 // Modifications copyright (c) 2013-2024 Oracle and/or its affiliates.
0007 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
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_HELPERS_HPP
0015 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HELPERS_HPP
0016
0017 #include <boost/geometry/algorithms/detail/direction_code.hpp>
0018 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
0019 #include <boost/geometry/core/assert.hpp>
0020 #include <boost/geometry/policies/relate/intersection_policy.hpp>
0021 #include <boost/geometry/strategies/intersection_result.hpp>
0022
0023 namespace boost { namespace geometry {
0024
0025 #ifndef DOXYGEN_NO_DETAIL
0026 namespace detail { namespace overlay {
0027
0028 enum turn_position { position_middle, position_front, position_back };
0029
0030 template <typename Point, typename SegmentRatio>
0031 struct turn_operation_linear
0032     : public turn_operation<Point, SegmentRatio>
0033 {
0034     turn_operation_linear()
0035         : position(position_middle)
0036         , is_collinear(false)
0037     {}
0038
0039     turn_position position;
0040     bool is_collinear; // valid only for Linear geometry
0041 };
0042
0043 template
0044 <
0045     typename UniqueSubRange1,
0046     typename UniqueSubRange2,
0047     typename Strategy
0048 >
0049 struct side_calculator
0050 {
0051     using side_strategy_type = decltype(std::declval<Strategy>().side());
0052
0053     inline side_calculator(UniqueSubRange1 const& range_p,
0054                            UniqueSubRange2 const& range_q,
0055                            Strategy const& strategy)
0056         : m_side_strategy(strategy.side())
0057         , m_range_p(range_p)
0058         , m_range_q(range_q)
0059     {}
0060
0061     inline int pi_wrt_q1() const { return m_side_strategy.apply(get_qi(), get_qj(), get_pi()); }
0062
0063     inline int pj_wrt_q1() const { return m_side_strategy.apply(get_qi(), get_qj(), get_pj()); }
0064     inline int pj_wrt_q2() const { return m_side_strategy.apply(get_qj(), get_qk(), get_pj()); }
0065     inline int qj_wrt_p1() const { return m_side_strategy.apply(get_pi(), get_pj(), get_qj()); }
0066     inline int qj_wrt_p2() const { return m_side_strategy.apply(get_pj(), get_pk(), get_qj()); }
0067
0068     inline int pk_wrt_p1() const { return m_side_strategy.apply(get_pi(), get_pj(), get_pk()); }
0069     inline int pk_wrt_q1() const { return m_side_strategy.apply(get_qi(), get_qj(), get_pk()); }
0070     inline int qk_wrt_p1() const { return m_side_strategy.apply(get_pi(), get_pj(), get_qk()); }
0071     inline int qk_wrt_q1() const { return m_side_strategy.apply(get_qi(), get_qj(), get_qk()); }
0072
0073     inline int pk_wrt_q2() const { return m_side_strategy.apply(get_qj(), get_qk(), get_pk()); }
0074     inline int qk_wrt_p2() const { return m_side_strategy.apply(get_pj(), get_pk(), get_qk()); }
0075
0076     inline auto const& get_pi() const { return m_range_p.at(0); }
0077     inline auto const& get_pj() const { return m_range_p.at(1); }
0078     inline auto const& get_pk() const { return m_range_p.at(2); }
0079
0080     inline auto const& get_qi() const { return m_range_q.at(0); }
0081     inline auto const& get_qj() const { return m_range_q.at(1); }
0082     inline auto const& get_qk() const { return m_range_q.at(2); }
0083
0084     // Used side-strategy, owned by the calculator
0085     side_strategy_type m_side_strategy;
0086
0087     // Used ranges - owned by get_turns or (for points) by intersection_info_base
0088     UniqueSubRange1 const& m_range_p;
0089     UniqueSubRange2 const& m_range_q;
0090 };
0091
0092 template
0093 <
0094     typename UniqueSubRange1, typename UniqueSubRange2,
0095     typename TurnPoint, typename UmbrellaStrategy
0096 >
0097 class intersection_info_base
0098 {
0099 public:
0100
0101     using intersection_point_type = segment_intersection_points<TurnPoint>;
0102     using intersection_policy_type = policies::relate::segments_intersection_policy
0103         <
0104             intersection_point_type
0105         >;
0106
0107     using result_type = typename intersection_policy_type::return_type;
0108
0109     using side_calculator_type = side_calculator
0110         <
0111             UniqueSubRange1, UniqueSubRange2, UmbrellaStrategy
0112         >;
0113
0114     using swapped_side_calculator_type = side_calculator
0115         <
0116             UniqueSubRange2, UniqueSubRange1, UmbrellaStrategy
0117         >;
0118
0119     intersection_info_base(UniqueSubRange1 const& range_p,
0120                            UniqueSubRange2 const& range_q,
0121                            UmbrellaStrategy const& umbrella_strategy)
0122         : m_range_p(range_p)
0123         , m_range_q(range_q)
0124         , m_side_calc(range_p, range_q, umbrella_strategy)
0125         , m_swapped_side_calc(range_q, range_p, umbrella_strategy)
0126         , m_result(umbrella_strategy.relate()
0127                         .apply(range_p, range_q, intersection_policy_type()))
0128     {}
0129
0130     inline bool p_is_last_segment() const { return m_range_p.is_last_segment(); }
0131     inline bool q_is_last_segment() const { return m_range_q.is_last_segment(); }
0132
0133     inline auto const& rpi() const { return m_side_calc.get_pi(); }
0134     inline auto const& rpj() const { return m_side_calc.get_pj(); }
0135     inline auto const& rpk() const { return m_side_calc.get_pk(); }
0136
0137     inline auto const& rqi() const { return m_side_calc.get_qi(); }
0138     inline auto const& rqj() const { return m_side_calc.get_qj(); }
0139     inline auto const& rqk() const { return m_side_calc.get_qk(); }
0140
0141     inline side_calculator_type const& sides() const { return m_side_calc; }
0142     inline swapped_side_calculator_type const& swapped_sides() const
0143     {
0144         return m_swapped_side_calc;
0145     }
0146
0147 private :
0148     // Owned by get_turns
0149     UniqueSubRange1 const& m_range_p;
0150     UniqueSubRange2 const& m_range_q;
0151
0152     // Owned by this class
0153     side_calculator_type m_side_calc;
0154     swapped_side_calculator_type m_swapped_side_calc;
0155
0156 protected :
0157     result_type m_result;
0158 };
0159
0160
0161 template
0162 <
0163     typename UniqueSubRange1, typename UniqueSubRange2,
0164     typename TurnPoint,
0165     typename UmbrellaStrategy
0166 >
0167 class intersection_info
0168     : public intersection_info_base<UniqueSubRange1, UniqueSubRange2,
0169         TurnPoint, UmbrellaStrategy>
0170 {
0171     using base = intersection_info_base<UniqueSubRange1, UniqueSubRange2,
0172         TurnPoint, UmbrellaStrategy>;
0173
0174 public:
0175
0176     using cs_tag = typename UmbrellaStrategy::cs_tag;
0177
0178     using side_calculator_type = typename base::side_calculator_type;
0179     using result_type = typename base::result_type;
0180
0181     using i_info_type = typename result_type::intersection_points_type;
0182     using d_info_type = typename result_type::direction_type;
0183
0184     intersection_info(UniqueSubRange1 const& range_p,
0185                       UniqueSubRange2 const& range_q,
0186                       UmbrellaStrategy const& umbrella_strategy)
0187         : base(range_p, range_q, umbrella_strategy)
0188         , m_umbrella_strategy(umbrella_strategy)
0189     {}
0190
0191     inline result_type const& result() const { return base::m_result; }
0192     inline i_info_type const& i_info() const { return base::m_result.intersection_points; }
0193     inline d_info_type const& d_info() const { return base::m_result.direction; }
0194
0195     // TODO: it's more like is_spike_ip_p
0196     inline bool is_spike_p() const
0197     {
0198         if (base::p_is_last_segment())
0199         {
0200             return false;
0201         }
0202         if (base::sides().pk_wrt_p1() == 0)
0203         {
0204             // p:  pi--------pj--------pk
0205             // or: pi----pk==pj
0206
0207             if (! is_ip_j<0>())
0208             {
0209                 return false;
0210             }
0211
0212             // TODO: why is q used to determine spike property in p?
0213             bool const has_qk = ! base::q_is_last_segment();
0214             int const qk_p1 = has_qk ? base::sides().qk_wrt_p1() : 0;
0215             int const qk_p2 = has_qk ? base::sides().qk_wrt_p2() : 0;
0216
0217             if (qk_p1 == -qk_p2)
0218             {
0219                 if (qk_p1 == 0)
0220                 {
0221                     // qk is collinear with both p1 and p2,
0222                     // verify if pk goes backwards w.r.t. pi/pj
0223                     return direction_code<cs_tag>(base::rpi(), base::rpj(), base::rpk()) == -1;
0224                 }
0225
0226                 // qk is at opposite side of p1/p2, therefore
0227                 // p1/p2 (collinear) are opposite and form a spike
0228                 return true;
0229             }
0230         }
0231
0232         return false;
0233     }
0234
0235     inline bool is_spike_q() const
0236     {
0237         if (base::q_is_last_segment())
0238         {
0239             return false;
0240         }
0241
0242         // See comments at is_spike_p
0243         if (base::sides().qk_wrt_q1() == 0)
0244         {
0245             if (! is_ip_j<1>())
0246             {
0247                 return false;
0248             }
0249
0250             // TODO: why is p used to determine spike property in q?
0251             bool const has_pk = ! base::p_is_last_segment();
0252             int const pk_q1 = has_pk ? base::sides().pk_wrt_q1() : 0;
0253             int const pk_q2 = has_pk ? base::sides().pk_wrt_q2() : 0;
0254
0255             if (pk_q1 == -pk_q2)
0256             {
0257                 if (pk_q1 == 0)
0258                 {
0259                     return direction_code<cs_tag>(base::rqi(), base::rqj(), base::rqk()) == -1;
0260                 }
0261
0262                 return true;
0263             }
0264         }
0265
0266         return false;
0267     }
0268
0269     UmbrellaStrategy const& strategy() const
0270     {
0271         return m_umbrella_strategy;
0272     }
0273
0274 private:
0275     template <std::size_t OpId>
0276     bool is_ip_j() const
0277     {
0278         int arrival = d_info().arrival[OpId];
0279         bool same_dirs = d_info().dir_a == 0 && d_info().dir_b == 0;
0280
0281         if (same_dirs)
0282         {
0283             if (i_info().count == 2)
0284             {
0285                 return arrival != -1;
0286             }
0287             else
0288             {
0289                 return arrival == 0;
0290             }
0291         }
0292         else
0293         {
0294             return arrival == 1;
0295         }
0296     }
0297
0298     UmbrellaStrategy const& m_umbrella_strategy;
0299 };
0300
0301 }} // namespace detail::overlay
0302 #endif // DOXYGEN_NO_DETAIL
0303
0304 }} // namespace boost::geometry
0305
0306 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HELPERS_HPP