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 {
turn_operation_linearboost::geometry::detail::overlay::turn_operation_linear30     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 {
side_calculatorboost::geometry::detail::overlay::side_calculator46     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 
pk_wrt_p1boost::geometry::detail::overlay::side_calculator54     inline int pk_wrt_p1() const { return m_side_strategy.apply(m_pi, m_pj, m_pk); }
pk_wrt_q1boost::geometry::detail::overlay::side_calculator55     inline int pk_wrt_q1() const { return m_side_strategy.apply(m_qi, m_qj, m_pk); }
qk_wrt_p1boost::geometry::detail::overlay::side_calculator56     inline int qk_wrt_p1() const { return m_side_strategy.apply(m_pi, m_pj, m_qk); }
qk_wrt_q1boost::geometry::detail::overlay::side_calculator57     inline int qk_wrt_q1() const { return m_side_strategy.apply(m_qi, m_qj, m_qk); }
58 
pk_wrt_q2boost::geometry::detail::overlay::side_calculator59     inline int pk_wrt_q2() const { return m_side_strategy.apply(m_qj, m_qk, m_pk); }
qk_wrt_p2boost::geometry::detail::overlay::side_calculator60     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 
robust_pointsboost::geometry::detail::overlay::robust_points83     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 
intersection_info_base(Point1 const & pi,Point1 const & pj,Point1 const & pk,Point2 const & qi,Point2 const & qj,Point2 const & qk,IntersectionStrategy const & intersection_strategy,RobustPolicy const & robust_policy)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 
pi() const129     inline Point1 const& pi() const { return m_pi; }
pj() const130     inline Point1 const& pj() const { return m_pj; }
pk() const131     inline Point1 const& pk() const { return m_pk; }
132 
qi() const133     inline Point2 const& qi() const { return m_qi; }
qj() const134     inline Point2 const& qj() const { return m_qj; }
qk() const135     inline Point2 const& qk() const { return m_qk; }
136 
rpi() const137     inline robust_point1_type const& rpi() const { return base::m_rpi; }
rpj() const138     inline robust_point1_type const& rpj() const { return base::m_rpj; }
rpk() const139     inline robust_point1_type const& rpk() const { return base::m_rpk; }
140 
rqi() const141     inline robust_point2_type const& rqi() const { return base::m_rqi; }
rqj() const142     inline robust_point2_type const& rqj() const { return base::m_rqj; }
rqk() const143     inline robust_point2_type const& rqk() const { return base::m_rqk; }
144 
sides() const145     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 
intersection_info_base(Point1 const & pi,Point1 const & pj,Point1 const & pk,Point2 const & qi,Point2 const & qj,Point2 const & qk,IntersectionStrategy const & intersection_strategy,no_rescale_policy const &)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 
pi() const181     inline Point1 const& pi() const { return m_side_calc.m_pi; }
pj() const182     inline Point1 const& pj() const { return m_side_calc.m_pj; }
pk() const183     inline Point1 const& pk() const { return m_side_calc.m_pk; }
184 
qi() const185     inline Point2 const& qi() const { return m_side_calc.m_qi; }
qj() const186     inline Point2 const& qj() const { return m_side_calc.m_qj; }
qk() const187     inline Point2 const& qk() const { return m_side_calc.m_qk; }
188 
rpi() const189     inline Point1 const& rpi() const { return pi(); }
rpj() const190     inline Point1 const& rpj() const { return pj(); }
rpk() const191     inline Point1 const& rpk() const { return pk(); }
192 
rqi() const193     inline Point2 const& rqi() const { return qi(); }
rqj() const194     inline Point2 const& rqj() const { return qj(); }
rqk() const195     inline Point2 const& rqk() const { return qk(); }
196 
sides() const197     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 
intersection_info(Point1 const & pi,Point1 const & pj,Point1 const & pk,Point2 const & qi,Point2 const & qj,Point2 const & qk,IntersectionStrategy const & intersection_strategy,RobustPolicy const & robust_policy)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 
result() const264     inline result_type const& result() const { return m_result; }
i_info() const265     inline i_info_type const& i_info() const { return m_result.template get<0>(); }
d_info() const266     inline d_info_type const& d_info() const { return m_result.template get<1>(); }
267 
get_intersection_strategy() const268     inline intersection_strategy_type const& get_intersection_strategy() const
269     {
270         return m_intersection_strategy;
271     }
272 
get_side_strategy() const273     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
is_spike_p() const279     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
is_spike_q() const307     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>
is_spike_of_collinear(Point const & i,Point const & j,Point const & k) const336     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>
is_ip_j() const356     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
389