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