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-2020.
   6 // Modifications copyright (c) 2013-2020 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/algorithms/detail/direction_code.hpp>
  18 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
  19 #include <boost/geometry/algorithms/detail/recalculate.hpp>
  20 #include <boost/geometry/core/assert.hpp>
  21 #include <boost/geometry/policies/relate/intersection_policy.hpp>
  22 #include <boost/geometry/policies/robustness/rescale_policy_tags.hpp>
  23 #include <boost/geometry/strategies/intersection_result.hpp>
  24
  25 namespace boost { namespace geometry {
  26
  27 #ifndef DOXYGEN_NO_DETAIL
  28 namespace detail { namespace overlay {
  29
  30 enum turn_position { position_middle, position_front, position_back };
  31
  32 template <typename Point, typename SegmentRatio>
  33 struct turn_operation_linear
  34     : public turn_operation<Point, SegmentRatio>
  35 {
  36     turn_operation_linear()
  37         : position(position_middle)
  38         , is_collinear(false)
  39     {}
  40
  41     turn_position position;
  42     bool is_collinear; // valid only for Linear geometry
  43 };
  44
  45 template
  46 <
  47     typename UniqueSubRange1,
  48     typename UniqueSubRange2,
  49     typename Strategy
  50 >
  51 struct side_calculator
  52 {
  53     typedef typename UniqueSubRange1::point_type point1_type;
  54     typedef typename UniqueSubRange2::point_type point2_type;
  55     typedef decltype(std::declval<Strategy>().side()) side_strategy_type;
  56
  57     inline side_calculator(UniqueSubRange1 const& range_p,
  58                            UniqueSubRange2 const& range_q,
  59                            Strategy const& strategy)
  60         : m_side_strategy(strategy.side())
  61         , m_range_p(range_p)
  62         , m_range_q(range_q)
  63     {}
  64
  65     inline int pk_wrt_p1() const { return m_side_strategy.apply(get_pi(), get_pj(), get_pk()); }
  66     inline int pk_wrt_q1() const { return m_side_strategy.apply(get_qi(), get_qj(), get_pk()); }
  67     inline int qk_wrt_p1() const { return m_side_strategy.apply(get_pi(), get_pj(), get_qk()); }
  68     inline int qk_wrt_q1() const { return m_side_strategy.apply(get_qi(), get_qj(), get_qk()); }
  69
  70     inline int pk_wrt_q2() const { return m_side_strategy.apply(get_qj(), get_qk(), get_pk()); }
  71     inline int qk_wrt_p2() const { return m_side_strategy.apply(get_pj(), get_pk(), get_qk()); }
  72
  73     // Necessary when rescaling turns off:
  74     inline int qj_wrt_p1() const { return m_side_strategy.apply(get_pi(), get_pj(), get_qj()); }
  75     inline int qj_wrt_p2() const { return m_side_strategy.apply(get_pj(), get_pk(), get_qj()); }
  76     inline int pj_wrt_q1() const { return m_side_strategy.apply(get_qi(), get_qj(), get_pj()); }
  77     inline int pj_wrt_q2() const { return m_side_strategy.apply(get_qj(), get_qk(), get_pj()); }
  78
  79     inline point1_type const& get_pi() const { return m_range_p.at(0); }
  80     inline point1_type const& get_pj() const { return m_range_p.at(1); }
  81     inline point1_type const& get_pk() const { return m_range_p.at(2); }
  82
  83     inline point2_type const& get_qi() const { return m_range_q.at(0); }
  84     inline point2_type const& get_qj() const { return m_range_q.at(1); }
  85     inline point2_type const& get_qk() const { return m_range_q.at(2); }
  86
  87     // Used side-strategy, owned by the calculator
  88     side_strategy_type m_side_strategy;
  89
  90     // Used ranges - owned by get_turns or (for robust points) by intersection_info_base
  91     UniqueSubRange1 const& m_range_p;
  92     UniqueSubRange2 const& m_range_q;
  93 };
  94
  95 template<typename Point, typename UniqueSubRange, typename RobustPolicy>
  96 struct robust_subrange_adapter
  97 {
  98     typedef Point point_type;
  99
 100     robust_subrange_adapter(UniqueSubRange const& unique_sub_range,
 101                      Point const& robust_point_i, Point const& robust_point_j,
 102                      RobustPolicy const& robust_policy)
 103
 104         : m_unique_sub_range(unique_sub_range)
 105         , m_robust_policy(robust_policy)
 106         , m_robust_point_i(robust_point_i)
 107         , m_robust_point_j(robust_point_j)
 108         , m_k_retrieved(false)
 109     {}
 110
 111     std::size_t size() const { return m_unique_sub_range.size(); }
 112
 113     //! Get precalculated point
 114     Point const& at(std::size_t index) const
 115     {
 116         BOOST_GEOMETRY_ASSERT(index < size());
 117         switch (index)
 118         {
 119             case 0 : return m_robust_point_i;
 120             case 1 : return m_robust_point_j;
 121             case 2 : return get_point_k();
 122             default : return m_robust_point_i;
 123         }
 124     }
 125
 126 private :
 127     Point const& get_point_k() const
 128     {
 129         if (! m_k_retrieved)
 130         {
 131             geometry::recalculate(m_robust_point_k, m_unique_sub_range.at(2), m_robust_policy);
 132             m_k_retrieved = true;
 133         }
 134         return m_robust_point_k;
 135     }
 136
 137     UniqueSubRange const& m_unique_sub_range;
 138     RobustPolicy const& m_robust_policy;
 139
 140     Point const& m_robust_point_i;
 141     Point const& m_robust_point_j;
 142     mutable Point m_robust_point_k;
 143
 144     mutable bool m_k_retrieved;
 145 };
 146
 147 template
 148 <
 149     typename UniqueSubRange1, typename UniqueSubRange2,
 150     typename RobustPolicy
 151 >
 152 struct robust_point_calculator
 153 {
 154     typedef typename geometry::robust_point_type
 155         <
 156             typename UniqueSubRange1::point_type, RobustPolicy
 157         >::type robust_point1_type;
 158     typedef typename geometry::robust_point_type
 159         <
 160             typename UniqueSubRange2::point_type, RobustPolicy
 161         >::type robust_point2_type;
 162
 163     inline robust_point_calculator(UniqueSubRange1 const& range_p,
 164                                    UniqueSubRange2 const& range_q,
 165                                    RobustPolicy const& robust_policy)
 166         : m_robust_policy(robust_policy)
 167         , m_range_p(range_p)
 168         , m_range_q(range_q)
 169         , m_pk_retrieved(false)
 170         , m_qk_retrieved(false)
 171     {
 172         // Calculate pi,pj and qi,qj which are almost always necessary
 173         // But don't calculate pk/qk yet, which is retrieved (taking
 174         // more time) and not always necessary.
 175         geometry::recalculate(m_rpi, range_p.at(0), robust_policy);
 176         geometry::recalculate(m_rpj, range_p.at(1), robust_policy);
 177         geometry::recalculate(m_rqi, range_q.at(0), robust_policy);
 178         geometry::recalculate(m_rqj, range_q.at(1), robust_policy);
 179     }
 180
 181     inline robust_point1_type const& get_rpk() const
 182     {
 183         if (! m_pk_retrieved)
 184         {
 185             geometry::recalculate(m_rpk, m_range_p.at(2), m_robust_policy);
 186             m_pk_retrieved = true;
 187         }
 188         return m_rpk;
 189     }
 190     inline robust_point2_type const& get_rqk() const
 191     {
 192         if (! m_qk_retrieved)
 193         {
 194             geometry::recalculate(m_rqk, m_range_q.at(2), m_robust_policy);
 195             m_qk_retrieved = true;
 196         }
 197         return m_rqk;
 198     }
 199
 200     robust_point1_type m_rpi, m_rpj;
 201     robust_point2_type m_rqi, m_rqj;
 202
 203 private :
 204     RobustPolicy const& m_robust_policy;
 205     UniqueSubRange1 const& m_range_p;
 206     UniqueSubRange2 const& m_range_q;
 207
 208     // On retrieval
 209     mutable robust_point1_type m_rpk;
 210     mutable robust_point2_type m_rqk;
 211     mutable bool m_pk_retrieved;
 212     mutable bool m_qk_retrieved;
 213 };
 214
 215 // Default version (empty - specialized below)
 216 template
 217 <
 218     typename UniqueSubRange1, typename UniqueSubRange2,
 219     typename TurnPoint, typename UmbrellaStrategy,
 220     typename RobustPolicy,
 221     typename Tag = typename rescale_policy_type<RobustPolicy>::type
 222 >
 223 class intersection_info_base {};
 224
 225 // Version with rescaling, having robust points
 226 template
 227 <
 228     typename UniqueSubRange1, typename UniqueSubRange2,
 229     typename TurnPoint, typename UmbrellaStrategy,
 230     typename RobustPolicy
 231 >
 232 class intersection_info_base<UniqueSubRange1, UniqueSubRange2,
 233         TurnPoint, UmbrellaStrategy, RobustPolicy, rescale_policy_tag>
 234 {
 235     typedef robust_point_calculator
 236     <
 237         UniqueSubRange1, UniqueSubRange2,
 238         RobustPolicy
 239     >
 240     robust_calc_type;
 241
 242 public:
 243     typedef segment_intersection_points
 244     <
 245         TurnPoint,
 246         geometry::segment_ratio<boost::long_long_type>
 247     > intersection_point_type;
 248     typedef policies::relate::segments_intersection_policy
 249         <
 250             intersection_point_type
 251         > intersection_policy_type;
 252
 253     typedef typename intersection_policy_type::return_type result_type;
 254
 255     typedef typename robust_calc_type::robust_point1_type robust_point1_type;
 256     typedef typename robust_calc_type::robust_point2_type robust_point2_type;
 257
 258     typedef robust_subrange_adapter<robust_point1_type, UniqueSubRange1, RobustPolicy> robust_subrange1;
 259     typedef robust_subrange_adapter<robust_point2_type, UniqueSubRange2, RobustPolicy> robust_subrange2;
 260
 261     typedef side_calculator
 262         <
 263             robust_subrange1, robust_subrange2, UmbrellaStrategy
 264         > side_calculator_type;
 265
 266     typedef side_calculator
 267         <
 268             robust_subrange2, robust_subrange1, UmbrellaStrategy
 269         > robust_swapped_side_calculator_type;
 270
 271     intersection_info_base(UniqueSubRange1 const& range_p,
 272                            UniqueSubRange2 const& range_q,
 273                            UmbrellaStrategy const& umbrella_strategy,
 274                            RobustPolicy const& robust_policy)
 275         : m_range_p(range_p)
 276         , m_range_q(range_q)
 277         , m_robust_calc(range_p, range_q, robust_policy)
 278         , m_robust_range_p(range_p, m_robust_calc.m_rpi, m_robust_calc.m_rpj, robust_policy)
 279         , m_robust_range_q(range_q, m_robust_calc.m_rqi, m_robust_calc.m_rqj, robust_policy)
 280         , m_side_calc(m_robust_range_p, m_robust_range_q, umbrella_strategy)
 281         , m_swapped_side_calc(m_robust_range_q, m_robust_range_p, umbrella_strategy)
 282         , m_result(umbrella_strategy.relate().apply(range_p, range_q,
 283                        intersection_policy_type(),
 284                        m_robust_range_p, m_robust_range_q))
 285     {}
 286
 287     inline bool p_is_last_segment() const { return m_range_p.is_last_segment(); }
 288     inline bool q_is_last_segment() const { return m_range_q.is_last_segment(); }
 289
 290     inline robust_point1_type const& rpi() const { return m_robust_calc.m_rpi; }
 291     inline robust_point1_type const& rpj() const { return m_robust_calc.m_rpj; }
 292     inline robust_point1_type const& rpk() const { return m_robust_calc.get_rpk(); }
 293
 294     inline robust_point2_type const& rqi() const { return m_robust_calc.m_rqi; }
 295     inline robust_point2_type const& rqj() const { return m_robust_calc.m_rqj; }
 296     inline robust_point2_type const& rqk() const { return m_robust_calc.get_rqk(); }
 297
 298     inline side_calculator_type const& sides() const { return m_side_calc; }
 299     inline robust_swapped_side_calculator_type const& swapped_sides() const
 300     {
 301         return m_swapped_side_calc;
 302     }
 303
 304 private :
 305
 306     // Owned by get_turns
 307     UniqueSubRange1 const& m_range_p;
 308     UniqueSubRange2 const& m_range_q;
 309
 310     // Owned by this class
 311     robust_calc_type m_robust_calc;
 312     robust_subrange1 m_robust_range_p;
 313     robust_subrange2 m_robust_range_q;
 314     side_calculator_type m_side_calc;
 315     robust_swapped_side_calculator_type m_swapped_side_calc;
 316
 317 protected :
 318     result_type m_result;
 319 };
 320
 321 // Version without rescaling
 322 template
 323 <
 324     typename UniqueSubRange1, typename UniqueSubRange2,
 325     typename TurnPoint, typename UmbrellaStrategy,
 326     typename RobustPolicy
 327 >
 328 class intersection_info_base<UniqueSubRange1, UniqueSubRange2,
 329         TurnPoint, UmbrellaStrategy, RobustPolicy, no_rescale_policy_tag>
 330 {
 331 public:
 332
 333     typedef segment_intersection_points<TurnPoint> intersection_point_type;
 334     typedef policies::relate::segments_intersection_policy
 335         <
 336             intersection_point_type
 337         > intersection_policy_type;
 338
 339     typedef typename intersection_policy_type::return_type result_type;
 340
 341     typedef typename UniqueSubRange1::point_type point1_type;
 342     typedef typename UniqueSubRange2::point_type point2_type;
 343
 344     typedef side_calculator
 345         <
 346             UniqueSubRange1, UniqueSubRange2, UmbrellaStrategy
 347         > side_calculator_type;
 348
 349     typedef side_calculator
 350         <
 351             UniqueSubRange2, UniqueSubRange1, UmbrellaStrategy
 352         > swapped_side_calculator_type;
 353
 354     intersection_info_base(UniqueSubRange1 const& range_p,
 355                            UniqueSubRange2 const& range_q,
 356                            UmbrellaStrategy const& umbrella_strategy,
 357                            no_rescale_policy const& )
 358         : m_range_p(range_p)
 359         , m_range_q(range_q)
 360         , m_side_calc(range_p, range_q, umbrella_strategy)
 361         , m_swapped_side_calc(range_q, range_p, umbrella_strategy)
 362         , m_result(umbrella_strategy.relate()
 363                         .apply(range_p, range_q, intersection_policy_type()))
 364     {}
 365
 366     inline bool p_is_last_segment() const { return m_range_p.is_last_segment(); }
 367     inline bool q_is_last_segment() const { return m_range_q.is_last_segment(); }
 368
 369     inline point1_type const& rpi() const { return m_side_calc.get_pi(); }
 370     inline point1_type const& rpj() const { return m_side_calc.get_pj(); }
 371     inline point1_type const& rpk() const { return m_side_calc.get_pk(); }
 372
 373     inline point2_type const& rqi() const { return m_side_calc.get_qi(); }
 374     inline point2_type const& rqj() const { return m_side_calc.get_qj(); }
 375     inline point2_type const& rqk() const { return m_side_calc.get_qk(); }
 376
 377     inline side_calculator_type const& sides() const { return m_side_calc; }
 378     inline swapped_side_calculator_type const& swapped_sides() const
 379     {
 380         return m_swapped_side_calc;
 381     }
 382
 383 private :
 384     // Owned by get_turns
 385     UniqueSubRange1 const& m_range_p;
 386     UniqueSubRange2 const& m_range_q;
 387
 388     // Owned by this class
 389     side_calculator_type m_side_calc;
 390     swapped_side_calculator_type m_swapped_side_calc;
 391
 392 protected :
 393     result_type m_result;
 394 };
 395
 396
 397 template
 398 <
 399     typename UniqueSubRange1, typename UniqueSubRange2,
 400     typename TurnPoint,
 401     typename UmbrellaStrategy,
 402     typename RobustPolicy
 403 >
 404 class intersection_info
 405     : public intersection_info_base<UniqueSubRange1, UniqueSubRange2,
 406         TurnPoint, UmbrellaStrategy, RobustPolicy>
 407 {
 408     typedef intersection_info_base<UniqueSubRange1, UniqueSubRange2,
 409         TurnPoint, UmbrellaStrategy, RobustPolicy> base;
 410
 411 public:
 412
 413     typedef typename UniqueSubRange1::point_type point1_type;
 414     typedef typename UniqueSubRange2::point_type point2_type;
 415
 416     typedef typename UmbrellaStrategy::cs_tag cs_tag;
 417
 418     typedef typename base::side_calculator_type side_calculator_type;
 419     typedef typename base::result_type result_type;
 420
 421     typedef typename result_type::intersection_points_type i_info_type;
 422     typedef typename result_type::direction_type d_info_type;
 423
 424     intersection_info(UniqueSubRange1 const& range_p,
 425                       UniqueSubRange2 const& range_q,
 426                       UmbrellaStrategy const& umbrella_strategy,
 427                       RobustPolicy const& robust_policy)
 428         : base(range_p, range_q, umbrella_strategy, robust_policy)
 429         , m_umbrella_strategy(umbrella_strategy)
 430         , m_robust_policy(robust_policy)
 431     {}
 432
 433     inline result_type const& result() const { return base::m_result; }
 434     inline i_info_type const& i_info() const { return base::m_result.intersection_points; }
 435     inline d_info_type const& d_info() const { return base::m_result.direction; }
 436
 437     // TODO: it's more like is_spike_ip_p
 438     inline bool is_spike_p() const
 439     {
 440         if (base::p_is_last_segment())
 441         {
 442             return false;
 443         }
 444         if (base::sides().pk_wrt_p1() == 0)
 445         {
 446             // p:  pi--------pj--------pk
 447             // or: pi----pk==pj
 448
 449             if (! is_ip_j<0>())
 450             {
 451                 return false;
 452             }
 453
 454             // TODO: why is q used to determine spike property in p?
 455             bool const has_qk = ! base::q_is_last_segment();
 456             int const qk_p1 = has_qk ? base::sides().qk_wrt_p1() : 0;
 457             int const qk_p2 = has_qk ? base::sides().qk_wrt_p2() : 0;
 458
 459             if (qk_p1 == -qk_p2)
 460             {
 461                 if (qk_p1 == 0)
 462                 {
 463                     // qk is collinear with both p1 and p2,
 464                     // verify if pk goes backwards w.r.t. pi/pj
 465                     return direction_code<cs_tag>(base::rpi(), base::rpj(), base::rpk()) == -1;
 466                 }
 467
 468                 // qk is at opposite side of p1/p2, therefore
 469                 // p1/p2 (collinear) are opposite and form a spike
 470                 return true;
 471             }
 472         }
 473
 474         return false;
 475     }
 476
 477     inline bool is_spike_q() const
 478     {
 479         if (base::q_is_last_segment())
 480         {
 481             return false;
 482         }
 483
 484         // See comments at is_spike_p
 485         if (base::sides().qk_wrt_q1() == 0)
 486         {
 487             if (! is_ip_j<1>())
 488             {
 489                 return false;
 490             }
 491
 492             // TODO: why is p used to determine spike property in q?
 493             bool const has_pk = ! base::p_is_last_segment();
 494             int const pk_q1 = has_pk ? base::sides().pk_wrt_q1() : 0;
 495             int const pk_q2 = has_pk ? base::sides().pk_wrt_q2() : 0;
 496
 497             if (pk_q1 == -pk_q2)
 498             {
 499                 if (pk_q1 == 0)
 500                 {
 501                     return direction_code<cs_tag>(base::rqi(), base::rqj(), base::rqk()) == -1;
 502                 }
 503
 504                 return true;
 505             }
 506         }
 507
 508         return false;
 509     }
 510
 511     UmbrellaStrategy const& strategy() const
 512     {
 513         return m_umbrella_strategy;
 514     }
 515
 516 private:
 517     template <std::size_t OpId>
 518     bool is_ip_j() const
 519     {
 520         int arrival = d_info().arrival[OpId];
 521         bool same_dirs = d_info().dir_a == 0 && d_info().dir_b == 0;
 522
 523         if (same_dirs)
 524         {
 525             if (i_info().count == 2)
 526             {
 527                 return arrival != -1;
 528             }
 529             else
 530             {
 531                 return arrival == 0;
 532             }
 533         }
 534         else
 535         {
 536             return arrival == 1;
 537         }
 538     }
 539
 540     UmbrellaStrategy const& m_umbrella_strategy;
 541     RobustPolicy const& m_robust_policy;
 542 };
 543
 544 }} // namespace detail::overlay
 545 #endif // DOXYGEN_NO_DETAIL
 546
 547 }} // namespace boost::geometry
 548
 549 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HELPERS_HPP