1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
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.
8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
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)
14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HELPERS_HPP
15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HELPERS_HPP
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>
28 namespace boost { namespace geometry {
30 #ifndef DOXYGEN_NO_DETAIL
31 namespace detail { namespace overlay {
33 enum turn_position { position_middle, position_front, position_back };
35 template <typename Point, typename SegmentRatio>
36 struct turn_operation_linear
37 : public turn_operation<Point, SegmentRatio>
39 turn_operation_linear()
40 : position(position_middle)
44 turn_position position;
45 bool is_collinear; // valid only for Linear geometry
50 typename TurnPointCSTag,
51 typename UniqueSubRange1,
52 typename UniqueSubRange2,
55 struct side_calculator
57 typedef typename UniqueSubRange1::point_type point1_type;
58 typedef typename UniqueSubRange2::point_type point2_type;
60 inline side_calculator(UniqueSubRange1 const& range_p,
61 UniqueSubRange2 const& range_q,
62 SideStrategy const& side_strategy)
63 : m_side_strategy(side_strategy)
68 inline int pk_wrt_p1() const { return m_side_strategy.apply(get_pi(), get_pj(), get_pk()); }
69 inline int pk_wrt_q1() const { return m_side_strategy.apply(get_qi(), get_qj(), get_pk()); }
70 inline int qk_wrt_p1() const { return m_side_strategy.apply(get_pi(), get_pj(), get_qk()); }
71 inline int qk_wrt_q1() const { return m_side_strategy.apply(get_qi(), get_qj(), get_qk()); }
73 inline int pk_wrt_q2() const { return m_side_strategy.apply(get_qj(), get_qk(), get_pk()); }
74 inline int qk_wrt_p2() const { return m_side_strategy.apply(get_pj(), get_pk(), get_qk()); }
76 // Necessary when rescaling turns off:
77 inline int qj_wrt_p1() const { return m_side_strategy.apply(get_pi(), get_pj(), get_qj()); }
78 inline int qj_wrt_p2() const { return m_side_strategy.apply(get_pj(), get_pk(), get_qj()); }
79 inline int pj_wrt_q1() const { return m_side_strategy.apply(get_qi(), get_qj(), get_pj()); }
80 inline int pj_wrt_q2() const { return m_side_strategy.apply(get_qj(), get_qk(), get_pj()); }
82 inline point1_type const& get_pi() const { return m_range_p.at(0); }
83 inline point1_type const& get_pj() const { return m_range_p.at(1); }
84 inline point1_type const& get_pk() const { return m_range_p.at(2); }
86 inline point2_type const& get_qi() const { return m_range_q.at(0); }
87 inline point2_type const& get_qj() const { return m_range_q.at(1); }
88 inline point2_type const& get_qk() const { return m_range_q.at(2); }
90 // Used side-strategy, owned by the calculator,
91 // created from .get_side_strategy()
92 SideStrategy m_side_strategy;
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;
99 template<typename Point, typename UniqueSubRange, typename RobustPolicy>
100 struct robust_subrange_adapter
102 typedef Point point_type;
104 robust_subrange_adapter(UniqueSubRange const& unique_sub_range,
105 Point const& robust_point_i, Point const& robust_point_j,
106 RobustPolicy const& robust_policy)
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)
115 std::size_t size() const { return m_unique_sub_range.size(); }
117 //! Get precalculated point
118 Point const& at(std::size_t index) const
120 BOOST_GEOMETRY_ASSERT(index < size());
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;
131 Point const& get_point_k() const
135 geometry::recalculate(m_robust_point_k, m_unique_sub_range.at(2), m_robust_policy);
136 m_k_retrieved = true;
138 return m_robust_point_k;
141 UniqueSubRange const& m_unique_sub_range;
142 RobustPolicy const& m_robust_policy;
144 Point const& m_robust_point_i;
145 Point const& m_robust_point_j;
146 mutable Point m_robust_point_k;
148 mutable bool m_k_retrieved;
153 typename UniqueSubRange1, typename UniqueSubRange2,
154 typename RobustPolicy
156 struct robust_point_calculator
158 typedef typename geometry::robust_point_type
160 typename UniqueSubRange1::point_type, RobustPolicy
161 >::type robust_point1_type;
162 typedef typename geometry::robust_point_type
164 typename UniqueSubRange2::point_type, RobustPolicy
165 >::type robust_point2_type;
167 inline robust_point_calculator(UniqueSubRange1 const& range_p,
168 UniqueSubRange2 const& range_q,
169 RobustPolicy const& robust_policy)
170 : m_robust_policy(robust_policy)
173 , m_pk_retrieved(false)
174 , m_qk_retrieved(false)
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);
185 inline robust_point1_type const& get_rpk() const
187 if (! m_pk_retrieved)
189 geometry::recalculate(m_rpk, m_range_p.at(2), m_robust_policy);
190 m_pk_retrieved = true;
194 inline robust_point2_type const& get_rqk() const
196 if (! m_qk_retrieved)
198 geometry::recalculate(m_rqk, m_range_q.at(2), m_robust_policy);
199 m_qk_retrieved = true;
204 robust_point1_type m_rpi, m_rpj;
205 robust_point2_type m_rqi, m_rqj;
208 RobustPolicy const& m_robust_policy;
209 UniqueSubRange1 const& m_range_p;
210 UniqueSubRange2 const& m_range_q;
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;
219 // Default version (empty - specialized below)
222 typename UniqueSubRange1, typename UniqueSubRange2,
223 typename TurnPoint, typename UmbrellaStrategy,
224 typename RobustPolicy,
225 typename Tag = typename rescale_policy_type<RobustPolicy>::type
227 class intersection_info_base {};
229 // Version with rescaling, having robust points
232 typename UniqueSubRange1, typename UniqueSubRange2,
233 typename TurnPoint, typename UmbrellaStrategy,
234 typename RobustPolicy
236 class intersection_info_base<UniqueSubRange1, UniqueSubRange2,
237 TurnPoint, UmbrellaStrategy, RobustPolicy, rescale_policy_tag>
239 typedef robust_point_calculator
241 UniqueSubRange1, UniqueSubRange2,
247 typedef segment_intersection_points
250 geometry::segment_ratio<boost::long_long_type>
251 > intersection_point_type;
252 typedef policies::relate::segments_tupled
254 policies::relate::segments_intersection_points
256 intersection_point_type
258 policies::relate::segments_direction
259 > intersection_policy_type;
261 typedef typename intersection_policy_type::return_type result_type;
263 typedef typename robust_calc_type::robust_point1_type robust_point1_type;
264 typedef typename robust_calc_type::robust_point2_type robust_point2_type;
266 typedef robust_subrange_adapter<robust_point1_type, UniqueSubRange1, RobustPolicy> robust_subrange1;
267 typedef robust_subrange_adapter<robust_point2_type, UniqueSubRange2, RobustPolicy> robust_subrange2;
269 typedef typename cs_tag<TurnPoint>::type cs_tag;
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;
275 typedef side_calculator
277 cs_tag, robust_subrange2, robust_subrange1,
279 > robust_swapped_side_calculator_type;
281 intersection_info_base(UniqueSubRange1 const& range_p,
282 UniqueSubRange2 const& range_q,
283 UmbrellaStrategy const& umbrella_strategy,
284 RobustPolicy const& robust_policy)
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))
297 inline bool p_is_last_segment() const { return m_range_p.is_last_segment(); }
298 inline bool q_is_last_segment() const { return m_range_q.is_last_segment(); }
300 inline robust_point1_type const& rpi() const { return m_robust_calc.m_rpi; }
301 inline robust_point1_type const& rpj() const { return m_robust_calc.m_rpj; }
302 inline robust_point1_type const& rpk() const { return m_robust_calc.get_rpk(); }
304 inline robust_point2_type const& rqi() const { return m_robust_calc.m_rqi; }
305 inline robust_point2_type const& rqj() const { return m_robust_calc.m_rqj; }
306 inline robust_point2_type const& rqk() const { return m_robust_calc.get_rqk(); }
308 inline side_calculator_type const& sides() const { return m_side_calc; }
310 robust_swapped_side_calculator_type get_swapped_sides() const
312 robust_swapped_side_calculator_type result(
313 m_robust_range_q, m_robust_range_p,
314 m_side_calc.m_side_strategy);
320 // Owned by get_turns
321 UniqueSubRange1 const& m_range_p;
322 UniqueSubRange2 const& m_range_q;
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;
331 result_type m_result;
334 // Version without rescaling
337 typename UniqueSubRange1, typename UniqueSubRange2,
338 typename TurnPoint, typename UmbrellaStrategy,
339 typename RobustPolicy
341 class intersection_info_base<UniqueSubRange1, UniqueSubRange2,
342 TurnPoint, UmbrellaStrategy, RobustPolicy, no_rescale_policy_tag>
346 typedef segment_intersection_points<TurnPoint> intersection_point_type;
347 typedef policies::relate::segments_tupled
349 policies::relate::segments_intersection_points
351 intersection_point_type
353 policies::relate::segments_direction
354 > intersection_policy_type;
356 typedef typename intersection_policy_type::return_type result_type;
358 typedef typename UniqueSubRange1::point_type point1_type;
359 typedef typename UniqueSubRange2::point_type point2_type;
361 typedef typename UmbrellaStrategy::cs_tag cs_tag;
363 typedef typename UmbrellaStrategy::side_strategy_type side_strategy_type;
364 typedef side_calculator<cs_tag, UniqueSubRange1, UniqueSubRange2, side_strategy_type> side_calculator_type;
366 typedef side_calculator
368 cs_tag, UniqueSubRange2, UniqueSubRange1,
370 > swapped_side_calculator_type;
372 intersection_info_base(UniqueSubRange1 const& range_p,
373 UniqueSubRange2 const& range_q,
374 UmbrellaStrategy const& umbrella_strategy,
375 no_rescale_policy const& )
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()))
383 inline bool p_is_last_segment() const { return m_range_p.is_last_segment(); }
384 inline bool q_is_last_segment() const { return m_range_q.is_last_segment(); }
386 inline point1_type const& rpi() const { return m_side_calc.get_pi(); }
387 inline point1_type const& rpj() const { return m_side_calc.get_pj(); }
388 inline point1_type const& rpk() const { return m_side_calc.get_pk(); }
390 inline point2_type const& rqi() const { return m_side_calc.get_qi(); }
391 inline point2_type const& rqj() const { return m_side_calc.get_qj(); }
392 inline point2_type const& rqk() const { return m_side_calc.get_qk(); }
394 inline side_calculator_type const& sides() const { return m_side_calc; }
396 swapped_side_calculator_type get_swapped_sides() const
398 swapped_side_calculator_type result(
399 m_range_q, m_range_p,
400 m_side_calc.m_side_strategy);
405 // Owned by get_turns
406 UniqueSubRange1 const& m_range_p;
407 UniqueSubRange2 const& m_range_q;
409 // Owned by this class
410 side_calculator_type m_side_calc;
413 result_type m_result;
419 typename UniqueSubRange1, typename UniqueSubRange2,
421 typename UmbrellaStrategy,
422 typename RobustPolicy
424 class intersection_info
425 : public intersection_info_base<UniqueSubRange1, UniqueSubRange2,
426 TurnPoint, UmbrellaStrategy, RobustPolicy>
428 typedef intersection_info_base<UniqueSubRange1, UniqueSubRange2,
429 TurnPoint, UmbrellaStrategy, RobustPolicy> base;
433 typedef typename UniqueSubRange1::point_type point1_type;
434 typedef typename UniqueSubRange2::point_type point2_type;
436 typedef UmbrellaStrategy intersection_strategy_type;
437 typedef typename UmbrellaStrategy::side_strategy_type side_strategy_type;
438 typedef typename UmbrellaStrategy::cs_tag cs_tag;
440 typedef typename base::side_calculator_type side_calculator_type;
441 typedef typename base::result_type result_type;
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
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)
456 inline result_type const& result() const { return base::m_result; }
457 inline i_info_type const& i_info() const { return base::m_result.template get<0>(); }
458 inline d_info_type const& d_info() const { return base::m_result.template get<1>(); }
460 inline side_strategy_type get_side_strategy() const
462 return m_intersection_strategy.get_side_strategy();
465 // TODO: it's more like is_spike_ip_p
466 inline bool is_spike_p() const
468 if (base::p_is_last_segment())
472 if (base::sides().pk_wrt_p1() == 0)
474 // p: pi--------pj--------pk
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;
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;
496 // qk is at opposite side of p1/p2, therefore
497 // p1/p2 (collinear) are opposite and form a spike
505 inline bool is_spike_q() const
507 if (base::q_is_last_segment())
512 // See comments at is_spike_p
513 if (base::sides().qk_wrt_q1() == 0)
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;
529 return direction_code<cs_tag>(base::rqi(), base::rqj(), base::rqk()) == -1;
540 template <std::size_t OpId>
543 int arrival = d_info().arrival[OpId];
544 bool same_dirs = d_info().dir_a == 0 && d_info().dir_b == 0;
548 if (i_info().count == 2)
550 return arrival != -1;
563 UmbrellaStrategy const& m_intersection_strategy;
564 RobustPolicy const& m_robust_policy;
567 }} // namespace detail::overlay
568 #endif // DOXYGEN_NO_DETAIL
570 }} // namespace boost::geometry
572 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HELPERS_HPP