ceph/src/boost/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   4
   5 // This file was modified by Oracle on 2013, 2014, 2015, 2017.
   6 // Modifications copyright (c) 2013-2017 Oracle and/or its affiliates.
   7
   8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   9
  10 // Use, modification and distribution is subject to the Boost Software License,
  11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  12 // http://www.boost.org/LICENSE_1_0.txt)
  13
  14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HELPERS_HPP
  15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HELPERS_HPP
  16
  17 #include <boost/geometry/policies/robustness/no_rescale_policy.hpp>
  18
  19 namespace boost { namespace geometry {
  20
  21 #ifndef DOXYGEN_NO_DETAIL
  22 namespace detail { namespace overlay {
  23
  24 enum turn_position { position_middle, position_front, position_back };
  25
  26 template <typename Point, typename SegmentRatio>
  27 struct turn_operation_linear
  28     : public turn_operation<Point, SegmentRatio>
  29 {
  30     turn_operation_linear()
  31         : position(position_middle)
  32         , is_collinear(false)
  33     {}
  34
  35     turn_position position;
  36     bool is_collinear; // valid only for Linear geometry
  37 };
  38
  39 template <typename TurnPointCSTag, typename PointP, typename PointQ,
  40           typename SideStrategy,
  41           typename Pi = PointP, typename Pj = PointP, typename Pk = PointP,
  42           typename Qi = PointQ, typename Qj = PointQ, typename Qk = PointQ
  43 >
  44 struct side_calculator
  45 {
  46     inline side_calculator(Pi const& pi, Pj const& pj, Pk const& pk,
  47                            Qi const& qi, Qj const& qj, Qk const& qk,
  48                            SideStrategy const& side_strategy)
  49         : m_pi(pi), m_pj(pj), m_pk(pk)
  50         , m_qi(qi), m_qj(qj), m_qk(qk)
  51         , m_side_strategy(side_strategy)
  52     {}
  53
  54     inline int pk_wrt_p1() const { return m_side_strategy.apply(m_pi, m_pj, m_pk); }
  55     inline int pk_wrt_q1() const { return m_side_strategy.apply(m_qi, m_qj, m_pk); }
  56     inline int qk_wrt_p1() const { return m_side_strategy.apply(m_pi, m_pj, m_qk); }
  57     inline int qk_wrt_q1() const { return m_side_strategy.apply(m_qi, m_qj, m_qk); }
  58
  59     inline int pk_wrt_q2() const { return m_side_strategy.apply(m_qj, m_qk, m_pk); }
  60     inline int qk_wrt_p2() const { return m_side_strategy.apply(m_pj, m_pk, m_qk); }
  61
  62     Pi const& m_pi;
  63     Pj const& m_pj;
  64     Pk const& m_pk;
  65     Qi const& m_qi;
  66     Qj const& m_qj;
  67     Qk const& m_qk;
  68
  69     SideStrategy m_side_strategy;
  70 };
  71
  72 template <typename Point1, typename Point2, typename RobustPolicy>
  73 struct robust_points
  74 {
  75     typedef typename geometry::robust_point_type
  76         <
  77             Point1, RobustPolicy
  78         >::type robust_point1_type;
  79
  80     // TODO: define robust_point2_type using Point2?
  81     typedef robust_point1_type robust_point2_type;
  82
  83     inline robust_points(Point1 const& pi, Point1 const& pj, Point1 const& pk,
  84                          Point2 const& qi, Point2 const& qj, Point2 const& qk,
  85                          RobustPolicy const& robust_policy)
  86     {
  87         geometry::recalculate(m_rpi, pi, robust_policy);
  88         geometry::recalculate(m_rpj, pj, robust_policy);
  89         geometry::recalculate(m_rpk, pk, robust_policy);
  90         geometry::recalculate(m_rqi, qi, robust_policy);
  91         geometry::recalculate(m_rqj, qj, robust_policy);
  92         geometry::recalculate(m_rqk, qk, robust_policy);
  93     }
  94
  95     robust_point1_type m_rpi, m_rpj, m_rpk;
  96     robust_point2_type m_rqi, m_rqj, m_rqk;
  97 };
  98
  99 template <typename Point1, typename Point2, typename TurnPoint, typename IntersectionStrategy, typename RobustPolicy>
 100 class intersection_info_base
 101     : private robust_points<Point1, Point2, RobustPolicy>
 102 {
 103     typedef robust_points<Point1, Point2, RobustPolicy> base;
 104
 105 public:
 106     typedef Point1 point1_type;
 107     typedef Point2 point2_type;
 108
 109     typedef typename base::robust_point1_type robust_point1_type;
 110     typedef typename base::robust_point2_type robust_point2_type;
 111
 112     typedef typename cs_tag<TurnPoint>::type cs_tag;
 113
 114     typedef typename IntersectionStrategy::side_strategy_type side_strategy_type;
 115     typedef side_calculator<cs_tag, robust_point1_type, robust_point2_type, side_strategy_type> side_calculator_type;
 116
 117     intersection_info_base(Point1 const& pi, Point1 const& pj, Point1 const& pk,
 118                            Point2 const& qi, Point2 const& qj, Point2 const& qk,
 119                            IntersectionStrategy const& intersection_strategy,
 120                            RobustPolicy const& robust_policy)
 121         : base(pi, pj, pk, qi, qj, qk, robust_policy)
 122         , m_side_calc(base::m_rpi, base::m_rpj, base::m_rpk,
 123                       base::m_rqi, base::m_rqj, base::m_rqk,
 124                       intersection_strategy.get_side_strategy())
 125         , m_pi(pi), m_pj(pj), m_pk(pk)
 126         , m_qi(qi), m_qj(qj), m_qk(qk)
 127     {}
 128
 129     inline Point1 const& pi() const { return m_pi; }
 130     inline Point1 const& pj() const { return m_pj; }
 131     inline Point1 const& pk() const { return m_pk; }
 132
 133     inline Point2 const& qi() const { return m_qi; }
 134     inline Point2 const& qj() const { return m_qj; }
 135     inline Point2 const& qk() const { return m_qk; }
 136
 137     inline robust_point1_type const& rpi() const { return base::m_rpi; }
 138     inline robust_point1_type const& rpj() const { return base::m_rpj; }
 139     inline robust_point1_type const& rpk() const { return base::m_rpk; }
 140
 141     inline robust_point2_type const& rqi() const { return base::m_rqi; }
 142     inline robust_point2_type const& rqj() const { return base::m_rqj; }
 143     inline robust_point2_type const& rqk() const { return base::m_rqk; }
 144
 145     inline side_calculator_type const& sides() const { return m_side_calc; }
 146
 147 private:
 148     side_calculator_type m_side_calc;
 149
 150     point1_type const& m_pi;
 151     point1_type const& m_pj;
 152     point1_type const& m_pk;
 153     point2_type const& m_qi;
 154     point2_type const& m_qj;
 155     point2_type const& m_qk;
 156 };
 157
 158 template <typename Point1, typename Point2, typename TurnPoint, typename IntersectionStrategy>
 159 class intersection_info_base<Point1, Point2, TurnPoint, IntersectionStrategy, detail::no_rescale_policy>
 160 {
 161 public:
 162     typedef Point1 point1_type;
 163     typedef Point2 point2_type;
 164
 165     typedef Point1 robust_point1_type;
 166     typedef Point2 robust_point2_type;
 167
 168     typedef typename cs_tag<TurnPoint>::type cs_tag;
 169
 170     typedef typename IntersectionStrategy::side_strategy_type side_strategy_type;
 171     typedef side_calculator<cs_tag, Point1, Point2, side_strategy_type> side_calculator_type;
 172
 173     intersection_info_base(Point1 const& pi, Point1 const& pj, Point1 const& pk,
 174                            Point2 const& qi, Point2 const& qj, Point2 const& qk,
 175                            IntersectionStrategy const& intersection_strategy,
 176                            no_rescale_policy const& /*robust_policy*/)
 177         : m_side_calc(pi, pj, pk, qi, qj, qk,
 178                       intersection_strategy.get_side_strategy())
 179     {}
 180
 181     inline Point1 const& pi() const { return m_side_calc.m_pi; }
 182     inline Point1 const& pj() const { return m_side_calc.m_pj; }
 183     inline Point1 const& pk() const { return m_side_calc.m_pk; }
 184
 185     inline Point2 const& qi() const { return m_side_calc.m_qi; }
 186     inline Point2 const& qj() const { return m_side_calc.m_qj; }
 187     inline Point2 const& qk() const { return m_side_calc.m_qk; }
 188
 189     inline Point1 const& rpi() const { return pi(); }
 190     inline Point1 const& rpj() const { return pj(); }
 191     inline Point1 const& rpk() const { return pk(); }
 192
 193     inline Point2 const& rqi() const { return qi(); }
 194     inline Point2 const& rqj() const { return qj(); }
 195     inline Point2 const& rqk() const { return qk(); }
 196
 197     inline side_calculator_type const& sides() const { return m_side_calc; }
 198
 199 private:
 200     side_calculator_type m_side_calc;
 201 };
 202
 203
 204 template
 205 <
 206     typename Point1,
 207     typename Point2,
 208     typename TurnPoint,
 209     typename IntersectionStrategy,
 210     typename RobustPolicy
 211 >
 212 class intersection_info
 213     : public intersection_info_base<Point1, Point2, TurnPoint, IntersectionStrategy, RobustPolicy>
 214 {
 215     typedef intersection_info_base<Point1, Point2, TurnPoint, IntersectionStrategy, RobustPolicy> base;
 216
 217 public:
 218     typedef segment_intersection_points
 219     <
 220         TurnPoint,
 221         typename geometry::segment_ratio_type
 222             <
 223                 TurnPoint, RobustPolicy
 224             >::type
 225     > intersection_point_type;
 226
 227     // NOTE: formerly defined in intersection_strategies
 228     typedef policies::relate::segments_tupled
 229         <
 230             policies::relate::segments_intersection_points
 231                 <
 232                     intersection_point_type
 233                 >,
 234             policies::relate::segments_direction
 235         > intersection_policy_type;
 236
 237     typedef IntersectionStrategy intersection_strategy_type;
 238     typedef typename IntersectionStrategy::side_strategy_type side_strategy_type;
 239
 240     typedef model::referring_segment<Point1 const> segment_type1;
 241     typedef model::referring_segment<Point2 const> segment_type2;
 242     typedef typename base::side_calculator_type side_calculator_type;
 243
 244     typedef typename intersection_policy_type::return_type result_type;
 245     typedef typename boost::tuples::element<0, result_type>::type i_info_type; // intersection_info
 246     typedef typename boost::tuples::element<1, result_type>::type d_info_type; // dir_info
 247
 248     intersection_info(Point1 const& pi, Point1 const& pj, Point1 const& pk,
 249                       Point2 const& qi, Point2 const& qj, Point2 const& qk,
 250                       IntersectionStrategy const& intersection_strategy,
 251                       RobustPolicy const& robust_policy)
 252         : base(pi, pj, pk, qi, qj, qk, intersection_strategy, robust_policy)
 253         , m_result(intersection_strategy.apply(
 254                         segment_type1(pi, pj),
 255                         segment_type2(qi, qj),
 256                         intersection_policy_type(),
 257                         robust_policy,
 258                         base::rpi(), base::rpj(),
 259                         base::rqi(), base::rqj()))
 260         , m_intersection_strategy(intersection_strategy)
 261         , m_robust_policy(robust_policy)
 262     {}
 263
 264     inline result_type const& result() const { return m_result; }
 265     inline i_info_type const& i_info() const { return m_result.template get<0>(); }
 266     inline d_info_type const& d_info() const { return m_result.template get<1>(); }
 267
 268     inline intersection_strategy_type const& get_intersection_strategy() const
 269     {
 270         return m_intersection_strategy;
 271     }
 272
 273     inline side_strategy_type get_side_strategy() const
 274     {
 275         return m_intersection_strategy.get_side_strategy();
 276     }
 277
 278     // TODO: it's more like is_spike_ip_p
 279     inline bool is_spike_p() const
 280     {
 281         if (base::sides().pk_wrt_p1() == 0)
 282         {
 283             if (! is_ip_j<0>())
 284             {
 285                 return false;
 286             }
 287
 288             int const qk_p1 = base::sides().qk_wrt_p1();
 289             int const qk_p2 = base::sides().qk_wrt_p2();
 290
 291             if (qk_p1 == -qk_p2)
 292             {
 293                 if (qk_p1 == 0)
 294                 {
 295                     return is_spike_of_collinear(base::pi(), base::pj(),
 296                                                  base::pk());
 297                 }
 298
 299                 return true;
 300             }
 301         }
 302
 303         return false;
 304     }
 305
 306     // TODO: it's more like is_spike_ip_q
 307     inline bool is_spike_q() const
 308     {
 309         if (base::sides().qk_wrt_q1() == 0)
 310         {
 311             if (! is_ip_j<1>())
 312             {
 313                 return false;
 314             }
 315
 316             int const pk_q1 = base::sides().pk_wrt_q1();
 317             int const pk_q2 = base::sides().pk_wrt_q2();
 318
 319             if (pk_q1 == -pk_q2)
 320             {
 321                 if (pk_q1 == 0)
 322                 {
 323                     return is_spike_of_collinear(base::qi(), base::qj(),
 324                                                  base::qk());
 325                 }
 326
 327                 return true;
 328             }
 329         }
 330
 331         return false;
 332     }
 333
 334 private:
 335     template <typename Point>
 336     inline bool is_spike_of_collinear(Point const& i, Point const& j,
 337                                       Point const& k) const
 338     {
 339         typedef model::referring_segment<Point const> seg;
 340
 341         // no need to calcualte direction info
 342         typedef policies::relate::segments_intersection_points
 343                 <
 344                     intersection_point_type
 345                 > policy_type;
 346
 347         typename policy_type::return_type const result
 348             = m_intersection_strategy.apply(seg(i, j), seg(j, k),
 349                                             policy_type(),
 350                                             m_robust_policy);
 351
 352         return result.count == 2;
 353     }
 354
 355     template <std::size_t OpId>
 356     bool is_ip_j() const
 357     {
 358         int arrival = d_info().arrival[OpId];
 359         bool same_dirs = d_info().dir_a == 0 && d_info().dir_b == 0;
 360
 361         if (same_dirs)
 362         {
 363             if (i_info().count == 2)
 364             {
 365                 return arrival != -1;
 366             }
 367             else
 368             {
 369                 return arrival == 0;
 370             }
 371         }
 372         else
 373         {
 374             return arrival == 1;
 375         }
 376     }
 377
 378     result_type m_result;
 379     IntersectionStrategy const& m_intersection_strategy;
 380     RobustPolicy const& m_robust_policy;
 381 };
 382
 383 }} // namespace detail::overlay
 384 #endif // DOXYGEN_NO_DETAIL
 385
 386 }} // namespace boost::geometry
 387
 388 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HELPERS_HPP