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-2020.
0006 // Modifications copyright (c) 2013-2020 Oracle and/or its affiliates.
0007
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/algorithms/detail/recalculate.hpp>
0020 #include <boost/geometry/core/assert.hpp>
0021 #include <boost/geometry/policies/relate/intersection_policy.hpp>
0022 #include <boost/geometry/policies/robustness/rescale_policy_tags.hpp>
0023 #include <boost/geometry/strategies/intersection_result.hpp>
0024
0025 namespace boost { namespace geometry {
0026
0027 #ifndef DOXYGEN_NO_DETAIL
0028 namespace detail { namespace overlay {
0029
0030 enum turn_position { position_middle, position_front, position_back };
0031
0032 template <typename Point, typename SegmentRatio>
0033 struct turn_operation_linear
0034     : public turn_operation<Point, SegmentRatio>
0035 {
0036     turn_operation_linear()
0037         : position(position_middle)
0038         , is_collinear(false)
0039     {}
0040
0041     turn_position position;
0042     bool is_collinear; // valid only for Linear geometry
0043 };
0044
0045 template
0046 <
0047     typename UniqueSubRange1,
0048     typename UniqueSubRange2,
0049     typename Strategy
0050 >
0051 struct side_calculator
0052 {
0053     typedef decltype(std::declval<Strategy>().side()) side_strategy_type;
0054
0055     inline side_calculator(UniqueSubRange1 const& range_p,
0056                            UniqueSubRange2 const& range_q,
0057                            Strategy const& strategy)
0058         : m_side_strategy(strategy.side())
0059         , m_range_p(range_p)
0060         , m_range_q(range_q)
0061     {}
0062
0063     inline int pk_wrt_p1() const { return m_side_strategy.apply(get_pi(), get_pj(), get_pk()); }
0064     inline int pk_wrt_q1() const { return m_side_strategy.apply(get_qi(), get_qj(), get_pk()); }
0065     inline int qk_wrt_p1() const { return m_side_strategy.apply(get_pi(), get_pj(), get_qk()); }
0066     inline int qk_wrt_q1() const { return m_side_strategy.apply(get_qi(), get_qj(), get_qk()); }
0067
0068     inline int pk_wrt_q2() const { return m_side_strategy.apply(get_qj(), get_qk(), get_pk()); }
0069     inline int qk_wrt_p2() const { return m_side_strategy.apply(get_pj(), get_pk(), get_qk()); }
0070
0071     // Necessary when rescaling turns off:
0072     inline int qj_wrt_p1() const { return m_side_strategy.apply(get_pi(), get_pj(), get_qj()); }
0073     inline int qj_wrt_p2() const { return m_side_strategy.apply(get_pj(), get_pk(), get_qj()); }
0074     inline int pj_wrt_q1() const { return m_side_strategy.apply(get_qi(), get_qj(), get_pj()); }
0075     inline int pj_wrt_q2() const { return m_side_strategy.apply(get_qj(), get_qk(), get_pj()); }
0076
0077     inline auto const& get_pi() const { return m_range_p.at(0); }
0078     inline auto const& get_pj() const { return m_range_p.at(1); }
0079     inline auto const& get_pk() const { return m_range_p.at(2); }
0080
0081     inline auto const& get_qi() const { return m_range_q.at(0); }
0082     inline auto const& get_qj() const { return m_range_q.at(1); }
0083     inline auto const& get_qk() const { return m_range_q.at(2); }
0084
0085     // Used side-strategy, owned by the calculator
0086     side_strategy_type m_side_strategy;
0087
0088     // Used ranges - owned by get_turns or (for robust points) by intersection_info_base
0089     UniqueSubRange1 const& m_range_p;
0090     UniqueSubRange2 const& m_range_q;
0091 };
0092
0093 template<typename Point, typename UniqueSubRange, typename RobustPolicy>
0094 struct robust_subrange_adapter
0095 {
0096     typedef Point point_type;
0097
0098     robust_subrange_adapter(UniqueSubRange const& unique_sub_range,
0099                      Point const& robust_point_i, Point const& robust_point_j,
0100                      RobustPolicy const& robust_policy)
0101
0102         : m_unique_sub_range(unique_sub_range)
0103         , m_robust_policy(robust_policy)
0104         , m_robust_point_i(robust_point_i)
0105         , m_robust_point_j(robust_point_j)
0106         , m_k_retrieved(false)
0107     {}
0108
0109     std::size_t size() const { return m_unique_sub_range.size(); }
0110
0111     //! Get precalculated point
0112     Point const& at(std::size_t index) const
0113     {
0114         BOOST_GEOMETRY_ASSERT(index < size());
0115         switch (index)
0116         {
0117             case 0 : return m_robust_point_i;
0118             case 1 : return m_robust_point_j;
0119             case 2 : return get_point_k();
0120             default : return m_robust_point_i;
0121         }
0122     }
0123
0124 private :
0125     Point const& get_point_k() const
0126     {
0127         if (! m_k_retrieved)
0128         {
0129             geometry::recalculate(m_robust_point_k, m_unique_sub_range.at(2), m_robust_policy);
0130             m_k_retrieved = true;
0131         }
0132         return m_robust_point_k;
0133     }
0134
0135     UniqueSubRange const& m_unique_sub_range;
0136     RobustPolicy const& m_robust_policy;
0137
0138     Point const& m_robust_point_i;
0139     Point const& m_robust_point_j;
0140     mutable Point m_robust_point_k;
0141
0142     mutable bool m_k_retrieved;
0143 };
0144
0145 template
0146 <
0147     typename UniqueSubRange1, typename UniqueSubRange2,
0148     typename RobustPolicy
0149 >
0150 struct robust_point_calculator
0151 {
0152     typedef typename geometry::robust_point_type
0153         <
0154             typename UniqueSubRange1::point_type, RobustPolicy
0155         >::type robust_point1_type;
0156     typedef typename geometry::robust_point_type
0157         <
0158             typename UniqueSubRange2::point_type, RobustPolicy
0159         >::type robust_point2_type;
0160
0161     inline robust_point_calculator(UniqueSubRange1 const& range_p,
0162                                    UniqueSubRange2 const& range_q,
0163                                    RobustPolicy const& robust_policy)
0164         : m_robust_policy(robust_policy)
0165         , m_range_p(range_p)
0166         , m_range_q(range_q)
0167         , m_pk_retrieved(false)
0168         , m_qk_retrieved(false)
0169     {
0170         // Calculate pi,pj and qi,qj which are almost always necessary
0171         // But don't calculate pk/qk yet, which is retrieved (taking
0172         // more time) and not always necessary.
0173         geometry::recalculate(m_rpi, range_p.at(0), robust_policy);
0174         geometry::recalculate(m_rpj, range_p.at(1), robust_policy);
0175         geometry::recalculate(m_rqi, range_q.at(0), robust_policy);
0176         geometry::recalculate(m_rqj, range_q.at(1), robust_policy);
0177     }
0178
0179     inline robust_point1_type const& get_rpk() const
0180     {
0181         if (! m_pk_retrieved)
0182         {
0183             geometry::recalculate(m_rpk, m_range_p.at(2), m_robust_policy);
0184             m_pk_retrieved = true;
0185         }
0186         return m_rpk;
0187     }
0188     inline robust_point2_type const& get_rqk() const
0189     {
0190         if (! m_qk_retrieved)
0191         {
0192             geometry::recalculate(m_rqk, m_range_q.at(2), m_robust_policy);
0193             m_qk_retrieved = true;
0194         }
0195         return m_rqk;
0196     }
0197
0198     robust_point1_type m_rpi, m_rpj;
0199     robust_point2_type m_rqi, m_rqj;
0200
0201 private :
0202     RobustPolicy const& m_robust_policy;
0203     UniqueSubRange1 const& m_range_p;
0204     UniqueSubRange2 const& m_range_q;
0205
0206     // On retrieval
0207     mutable robust_point1_type m_rpk;
0208     mutable robust_point2_type m_rqk;
0209     mutable bool m_pk_retrieved;
0210     mutable bool m_qk_retrieved;
0211 };
0212
0213 // Default version (empty - specialized below)
0214 template
0215 <
0216     typename UniqueSubRange1, typename UniqueSubRange2,
0217     typename TurnPoint, typename UmbrellaStrategy,
0218     typename RobustPolicy,
0219     typename Tag = typename rescale_policy_type<RobustPolicy>::type
0220 >
0221 class intersection_info_base {};
0222
0223 // Version with rescaling, having robust points
0224 template
0225 <
0226     typename UniqueSubRange1, typename UniqueSubRange2,
0227     typename TurnPoint, typename UmbrellaStrategy,
0228     typename RobustPolicy
0229 >
0230 class intersection_info_base<UniqueSubRange1, UniqueSubRange2,
0231         TurnPoint, UmbrellaStrategy, RobustPolicy, rescale_policy_tag>
0232 {
0233     typedef robust_point_calculator
0234     <
0235         UniqueSubRange1, UniqueSubRange2,
0236         RobustPolicy
0237     >
0238     robust_calc_type;
0239
0240 public:
0241     typedef segment_intersection_points
0242     <
0243         TurnPoint,
0244         geometry::segment_ratio<boost::long_long_type>
0245     > intersection_point_type;
0246     typedef policies::relate::segments_intersection_policy
0247         <
0248             intersection_point_type
0249         > intersection_policy_type;
0250
0251     typedef typename intersection_policy_type::return_type result_type;
0252
0253     typedef typename robust_calc_type::robust_point1_type robust_point1_type;
0254     typedef typename robust_calc_type::robust_point2_type robust_point2_type;
0255
0256     typedef robust_subrange_adapter<robust_point1_type, UniqueSubRange1, RobustPolicy> robust_subrange1;
0257     typedef robust_subrange_adapter<robust_point2_type, UniqueSubRange2, RobustPolicy> robust_subrange2;
0258
0259     typedef side_calculator
0260         <
0261             robust_subrange1, robust_subrange2, UmbrellaStrategy
0262         > side_calculator_type;
0263
0264     typedef side_calculator
0265         <
0266             robust_subrange2, robust_subrange1, UmbrellaStrategy
0267         > robust_swapped_side_calculator_type;
0268
0269     intersection_info_base(UniqueSubRange1 const& range_p,
0270                            UniqueSubRange2 const& range_q,
0271                            UmbrellaStrategy const& umbrella_strategy,
0272                            RobustPolicy const& robust_policy)
0273         : m_range_p(range_p)
0274         , m_range_q(range_q)
0275         , m_robust_calc(range_p, range_q, robust_policy)
0276         , m_robust_range_p(range_p, m_robust_calc.m_rpi, m_robust_calc.m_rpj, robust_policy)
0277         , m_robust_range_q(range_q, m_robust_calc.m_rqi, m_robust_calc.m_rqj, robust_policy)
0278         , m_side_calc(m_robust_range_p, m_robust_range_q, umbrella_strategy)
0279         , m_swapped_side_calc(m_robust_range_q, m_robust_range_p, umbrella_strategy)
0280         , m_result(umbrella_strategy.relate().apply(range_p, range_q,
0281                        intersection_policy_type(),
0282                        m_robust_range_p, m_robust_range_q))
0283     {}
0284
0285     inline bool p_is_last_segment() const { return m_range_p.is_last_segment(); }
0286     inline bool q_is_last_segment() const { return m_range_q.is_last_segment(); }
0287
0288     inline robust_point1_type const& rpi() const { return m_robust_calc.m_rpi; }
0289     inline robust_point1_type const& rpj() const { return m_robust_calc.m_rpj; }
0290     inline robust_point1_type const& rpk() const { return m_robust_calc.get_rpk(); }
0291
0292     inline robust_point2_type const& rqi() const { return m_robust_calc.m_rqi; }
0293     inline robust_point2_type const& rqj() const { return m_robust_calc.m_rqj; }
0294     inline robust_point2_type const& rqk() const { return m_robust_calc.get_rqk(); }
0295
0296     inline side_calculator_type const& sides() const { return m_side_calc; }
0297     inline robust_swapped_side_calculator_type const& swapped_sides() const
0298     {
0299         return m_swapped_side_calc;
0300     }
0301
0302 private :
0303
0304     // Owned by get_turns
0305     UniqueSubRange1 const& m_range_p;
0306     UniqueSubRange2 const& m_range_q;
0307
0308     // Owned by this class
0309     robust_calc_type m_robust_calc;
0310     robust_subrange1 m_robust_range_p;
0311     robust_subrange2 m_robust_range_q;
0312     side_calculator_type m_side_calc;
0313     robust_swapped_side_calculator_type m_swapped_side_calc;
0314
0315 protected :
0316     result_type m_result;
0317 };
0318
0319 // Version without rescaling
0320 template
0321 <
0322     typename UniqueSubRange1, typename UniqueSubRange2,
0323     typename TurnPoint, typename UmbrellaStrategy,
0324     typename RobustPolicy
0325 >
0326 class intersection_info_base<UniqueSubRange1, UniqueSubRange2,
0327         TurnPoint, UmbrellaStrategy, RobustPolicy, no_rescale_policy_tag>
0328 {
0329 public:
0330
0331     typedef segment_intersection_points<TurnPoint> intersection_point_type;
0332     typedef policies::relate::segments_intersection_policy
0333         <
0334             intersection_point_type
0335         > intersection_policy_type;
0336
0337     typedef typename intersection_policy_type::return_type result_type;
0338
0339     typedef side_calculator
0340         <
0341             UniqueSubRange1, UniqueSubRange2, UmbrellaStrategy
0342         > side_calculator_type;
0343
0344     typedef side_calculator
0345         <
0346             UniqueSubRange2, UniqueSubRange1, UmbrellaStrategy
0347         > swapped_side_calculator_type;
0348
0349     intersection_info_base(UniqueSubRange1 const& range_p,
0350                            UniqueSubRange2 const& range_q,
0351                            UmbrellaStrategy const& umbrella_strategy,
0352                            no_rescale_policy const& )
0353         : m_range_p(range_p)
0354         , m_range_q(range_q)
0355         , m_side_calc(range_p, range_q, umbrella_strategy)
0356         , m_swapped_side_calc(range_q, range_p, umbrella_strategy)
0357         , m_result(umbrella_strategy.relate()
0358                         .apply(range_p, range_q, intersection_policy_type()))
0359     {}
0360
0361     inline bool p_is_last_segment() const { return m_range_p.is_last_segment(); }
0362     inline bool q_is_last_segment() const { return m_range_q.is_last_segment(); }
0363
0364     inline auto const& rpi() const { return m_side_calc.get_pi(); }
0365     inline auto const& rpj() const { return m_side_calc.get_pj(); }
0366     inline auto const& rpk() const { return m_side_calc.get_pk(); }
0367
0368     inline auto const& rqi() const { return m_side_calc.get_qi(); }
0369     inline auto const& rqj() const { return m_side_calc.get_qj(); }
0370     inline auto const& rqk() const { return m_side_calc.get_qk(); }
0371
0372     inline side_calculator_type const& sides() const { return m_side_calc; }
0373     inline swapped_side_calculator_type const& swapped_sides() const
0374     {
0375         return m_swapped_side_calc;
0376     }
0377
0378 private :
0379     // Owned by get_turns
0380     UniqueSubRange1 const& m_range_p;
0381     UniqueSubRange2 const& m_range_q;
0382
0383     // Owned by this class
0384     side_calculator_type m_side_calc;
0385     swapped_side_calculator_type m_swapped_side_calc;
0386
0387 protected :
0388     result_type m_result;
0389 };
0390
0391
0392 template
0393 <
0394     typename UniqueSubRange1, typename UniqueSubRange2,
0395     typename TurnPoint,
0396     typename UmbrellaStrategy,
0397     typename RobustPolicy
0398 >
0399 class intersection_info
0400     : public intersection_info_base<UniqueSubRange1, UniqueSubRange2,
0401         TurnPoint, UmbrellaStrategy, RobustPolicy>
0402 {
0403     typedef intersection_info_base<UniqueSubRange1, UniqueSubRange2,
0404         TurnPoint, UmbrellaStrategy, RobustPolicy> base;
0405
0406 public:
0407
0408     typedef typename UmbrellaStrategy::cs_tag cs_tag;
0409
0410     typedef typename base::side_calculator_type side_calculator_type;
0411     typedef typename base::result_type result_type;
0412
0413     typedef typename result_type::intersection_points_type i_info_type;
0414     typedef typename result_type::direction_type d_info_type;
0415
0416     intersection_info(UniqueSubRange1 const& range_p,
0417                       UniqueSubRange2 const& range_q,
0418                       UmbrellaStrategy const& umbrella_strategy,
0419                       RobustPolicy const& robust_policy)
0420         : base(range_p, range_q, umbrella_strategy, robust_policy)
0421         , m_umbrella_strategy(umbrella_strategy)
0422         , m_robust_policy(robust_policy)
0423     {}
0424
0425     inline result_type const& result() const { return base::m_result; }
0426     inline i_info_type const& i_info() const { return base::m_result.intersection_points; }
0427     inline d_info_type const& d_info() const { return base::m_result.direction; }
0428
0429     // TODO: it's more like is_spike_ip_p
0430     inline bool is_spike_p() const
0431     {
0432         if (base::p_is_last_segment())
0433         {
0434             return false;
0435         }
0436         if (base::sides().pk_wrt_p1() == 0)
0437         {
0438             // p:  pi--------pj--------pk
0439             // or: pi----pk==pj
0440
0441             if (! is_ip_j<0>())
0442             {
0443                 return false;
0444             }
0445
0446             // TODO: why is q used to determine spike property in p?
0447             bool const has_qk = ! base::q_is_last_segment();
0448             int const qk_p1 = has_qk ? base::sides().qk_wrt_p1() : 0;
0449             int const qk_p2 = has_qk ? base::sides().qk_wrt_p2() : 0;
0450
0451             if (qk_p1 == -qk_p2)
0452             {
0453                 if (qk_p1 == 0)
0454                 {
0455                     // qk is collinear with both p1 and p2,
0456                     // verify if pk goes backwards w.r.t. pi/pj
0457                     return direction_code<cs_tag>(base::rpi(), base::rpj(), base::rpk()) == -1;
0458                 }
0459
0460                 // qk is at opposite side of p1/p2, therefore
0461                 // p1/p2 (collinear) are opposite and form a spike
0462                 return true;
0463             }
0464         }
0465
0466         return false;
0467     }
0468
0469     inline bool is_spike_q() const
0470     {
0471         if (base::q_is_last_segment())
0472         {
0473             return false;
0474         }
0475
0476         // See comments at is_spike_p
0477         if (base::sides().qk_wrt_q1() == 0)
0478         {
0479             if (! is_ip_j<1>())
0480             {
0481                 return false;
0482             }
0483
0484             // TODO: why is p used to determine spike property in q?
0485             bool const has_pk = ! base::p_is_last_segment();
0486             int const pk_q1 = has_pk ? base::sides().pk_wrt_q1() : 0;
0487             int const pk_q2 = has_pk ? base::sides().pk_wrt_q2() : 0;
0488
0489             if (pk_q1 == -pk_q2)
0490             {
0491                 if (pk_q1 == 0)
0492                 {
0493                     return direction_code<cs_tag>(base::rqi(), base::rqj(), base::rqk()) == -1;
0494                 }
0495
0496                 return true;
0497             }
0498         }
0499
0500         return false;
0501     }
0502
0503     UmbrellaStrategy const& strategy() const
0504     {
0505         return m_umbrella_strategy;
0506     }
0507
0508 private:
0509     template <std::size_t OpId>
0510     bool is_ip_j() const
0511     {
0512         int arrival = d_info().arrival[OpId];
0513         bool same_dirs = d_info().dir_a == 0 && d_info().dir_b == 0;
0514
0515         if (same_dirs)
0516         {
0517             if (i_info().count == 2)
0518             {
0519                 return arrival != -1;
0520             }
0521             else
0522             {
0523                 return arrival == 0;
0524             }
0525         }
0526         else
0527         {
0528             return arrival == 1;
0529         }
0530     }
0531
0532     UmbrellaStrategy const& m_umbrella_strategy;
0533     RobustPolicy const& m_robust_policy;
0534 };
0535
0536 }} // namespace detail::overlay
0537 #endif // DOXYGEN_NO_DETAIL
0538
0539 }} // namespace boost::geometry
0540
0541 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HELPERS_HPP