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