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.
6 // Modifications Copyright (c) 2013, 2021, Oracle and/or its affiliates.
7 
8 // Use, modification and distribution is subject to the Boost Software License,
9 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
10 // http://www.boost.org/LICENSE_1_0.txt)
11 
12 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
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 PointP, typename PointQ,
40           typename Pi = PointP, typename Pj = PointP, typename Pk = PointP,
41           typename Qi = PointQ, typename Qj = PointQ, typename Qk = PointQ
42 >
43 struct side_calculator
44 {
45     // todo: get from coordinate system
46     typedef boost::geometry::strategy::side::side_by_triangle<> side;
47 
side_calculatorboost::geometry::detail::overlay::side_calculator48     inline side_calculator(Pi const& pi, Pj const& pj, Pk const& pk,
49                            Qi const& qi, Qj const& qj, Qk const& qk)
50         : m_pi(pi), m_pj(pj), m_pk(pk)
51         , m_qi(qi), m_qj(qj), m_qk(qk)
52     {}
53 
pk_wrt_p1boost::geometry::detail::overlay::side_calculator54     inline int pk_wrt_p1() const { return side::apply(m_pi, m_pj, m_pk); }
pk_wrt_q1boost::geometry::detail::overlay::side_calculator55     inline int pk_wrt_q1() const { return side::apply(m_qi, m_qj, m_pk); }
qk_wrt_p1boost::geometry::detail::overlay::side_calculator56     inline int qk_wrt_p1() const { return side::apply(m_pi, m_pj, m_qk); }
qk_wrt_q1boost::geometry::detail::overlay::side_calculator57     inline int qk_wrt_q1() const { return side::apply(m_qi, m_qj, m_qk); }
58 
pk_wrt_q2boost::geometry::detail::overlay::side_calculator59     inline int pk_wrt_q2() const { return side::apply(m_qj, m_qk, m_pk); }
qk_wrt_p2boost::geometry::detail::overlay::side_calculator60     inline int qk_wrt_p2() const { return side::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 
70 template <typename Point1, typename Point2, typename RobustPolicy>
71 struct robust_points
72 {
73     typedef typename geometry::robust_point_type
74         <
75             Point1, RobustPolicy
76         >::type robust_point1_type;
77 
78     // TODO: define robust_point2_type using Point2?
79     typedef robust_point1_type robust_point2_type;
80 
robust_pointsboost::geometry::detail::overlay::robust_points81     inline robust_points(Point1 const& pi, Point1 const& pj, Point1 const& pk,
82                          Point2 const& qi, Point2 const& qj, Point2 const& qk,
83                          RobustPolicy const& robust_policy)
84     {
85         geometry::recalculate(m_rpi, pi, robust_policy);
86         geometry::recalculate(m_rpj, pj, robust_policy);
87         geometry::recalculate(m_rpk, pk, robust_policy);
88         geometry::recalculate(m_rqi, qi, robust_policy);
89         geometry::recalculate(m_rqj, qj, robust_policy);
90         geometry::recalculate(m_rqk, qk, robust_policy);
91     }
92 
93     robust_point1_type m_rpi, m_rpj, m_rpk;
94     robust_point2_type m_rqi, m_rqj, m_rqk;
95 };
96 
97 template <typename Point1, typename Point2, typename RobustPolicy>
98 class intersection_info_base
99     : private robust_points<Point1, Point2, RobustPolicy>
100 {
101     typedef robust_points<Point1, Point2, RobustPolicy> base;
102 
103 public:
104     typedef Point1 point1_type;
105     typedef Point2 point2_type;
106 
107     typedef typename base::robust_point1_type robust_point1_type;
108     typedef typename base::robust_point2_type robust_point2_type;
109 
110     typedef side_calculator<robust_point1_type, robust_point2_type> side_calculator_type;
111 
intersection_info_base(Point1 const & pi,Point1 const & pj,Point1 const & pk,Point2 const & qi,Point2 const & qj,Point2 const & qk,RobustPolicy const & robust_policy)112     intersection_info_base(Point1 const& pi, Point1 const& pj, Point1 const& pk,
113                            Point2 const& qi, Point2 const& qj, Point2 const& qk,
114                            RobustPolicy const& robust_policy)
115         : base(pi, pj, pk, qi, qj, qk, robust_policy)
116         , m_side_calc(base::m_rpi, base::m_rpj, base::m_rpk,
117                       base::m_rqi, base::m_rqj, base::m_rqk)
118         , m_pi(pi), m_pj(pj), m_pk(pk)
119         , m_qi(qi), m_qj(qj), m_qk(qk)
120     {}
121 
pi() const122     inline Point1 const& pi() const { return m_pi; }
pj() const123     inline Point1 const& pj() const { return m_pj; }
pk() const124     inline Point1 const& pk() const { return m_pk; }
125 
qi() const126     inline Point2 const& qi() const { return m_qi; }
qj() const127     inline Point2 const& qj() const { return m_qj; }
qk() const128     inline Point2 const& qk() const { return m_qk; }
129 
rpi() const130     inline robust_point1_type const& rpi() const { return base::m_rpi; }
rpj() const131     inline robust_point1_type const& rpj() const { return base::m_rpj; }
rpk() const132     inline robust_point1_type const& rpk() const { return base::m_rpk; }
133 
rqi() const134     inline robust_point2_type const& rqi() const { return base::m_rqi; }
rqj() const135     inline robust_point2_type const& rqj() const { return base::m_rqj; }
rqk() const136     inline robust_point2_type const& rqk() const { return base::m_rqk; }
137 
sides() const138     inline side_calculator_type const& sides() const { return m_side_calc; }
139 
140 private:
141     side_calculator_type m_side_calc;
142 
143     point1_type const& m_pi;
144     point1_type const& m_pj;
145     point1_type const& m_pk;
146     point2_type const& m_qi;
147     point2_type const& m_qj;
148     point2_type const& m_qk;
149 };
150 
151 template <typename Point1, typename Point2>
152 class intersection_info_base<Point1, Point2, detail::no_rescale_policy>
153 {
154 public:
155     typedef Point1 point1_type;
156     typedef Point2 point2_type;
157 
158     typedef Point1 robust_point1_type;
159     typedef Point2 robust_point2_type;
160 
161     typedef side_calculator<Point1, Point2> side_calculator_type;
162 
intersection_info_base(Point1 const & pi,Point1 const & pj,Point1 const & pk,Point2 const & qi,Point2 const & qj,Point2 const & qk,no_rescale_policy const &)163     intersection_info_base(Point1 const& pi, Point1 const& pj, Point1 const& pk,
164                            Point2 const& qi, Point2 const& qj, Point2 const& qk,
165                            no_rescale_policy const& /*robust_policy*/)
166         : m_side_calc(pi, pj, pk, qi, qj, qk)
167     {}
168 
pi() const169     inline Point1 const& pi() const { return m_side_calc.m_pi; }
pj() const170     inline Point1 const& pj() const { return m_side_calc.m_pj; }
pk() const171     inline Point1 const& pk() const { return m_side_calc.m_pk; }
172 
qi() const173     inline Point2 const& qi() const { return m_side_calc.m_qi; }
qj() const174     inline Point2 const& qj() const { return m_side_calc.m_qj; }
qk() const175     inline Point2 const& qk() const { return m_side_calc.m_qk; }
176 
rpi() const177     inline Point1 const& rpi() const { return pi(); }
rpj() const178     inline Point1 const& rpj() const { return pj(); }
rpk() const179     inline Point1 const& rpk() const { return pk(); }
180 
rqi() const181     inline Point2 const& rqi() const { return qi(); }
rqj() const182     inline Point2 const& rqj() const { return qj(); }
rqk() const183     inline Point2 const& rqk() const { return qk(); }
184 
sides() const185     inline side_calculator_type const& sides() const { return m_side_calc; }
186 
187 private:
188     side_calculator_type m_side_calc;
189 };
190 
191 
192 template
193 <
194     typename Point1,
195     typename Point2,
196     typename TurnPoint,
197     typename RobustPolicy
198 >
199 class intersection_info
200     : public intersection_info_base<Point1, Point2, RobustPolicy>
201 {
202     typedef intersection_info_base<Point1, Point2, RobustPolicy> base;
203 
204     typedef typename strategy_intersection
205         <
206             typename cs_tag<TurnPoint>::type,
207             Point1,
208             Point2,
209             TurnPoint,
210             RobustPolicy
211         >::segment_intersection_strategy_type strategy;
212 
213 public:
214     typedef model::referring_segment<Point1 const> segment_type1;
215     typedef model::referring_segment<Point2 const> segment_type2;
216     typedef typename base::side_calculator_type side_calculator_type;
217 
218     typedef typename strategy::return_type result_type;
219     typedef typename boost::tuples::element<0, result_type>::type i_info_type; // intersection_info
220     typedef typename boost::tuples::element<1, result_type>::type d_info_type; // dir_info
221 
intersection_info(Point1 const & pi,Point1 const & pj,Point1 const & pk,Point2 const & qi,Point2 const & qj,Point2 const & qk,RobustPolicy const & robust_policy)222     intersection_info(Point1 const& pi, Point1 const& pj, Point1 const& pk,
223                       Point2 const& qi, Point2 const& qj, Point2 const& qk,
224                       RobustPolicy const& robust_policy)
225         : base(pi, pj, pk, qi, qj, qk, robust_policy)
226         , m_result(strategy::apply(segment_type1(pi, pj),
227                                    segment_type2(qi, qj),
228                                    robust_policy,
229                                    base::rpi(), base::rpj(),
230                                    base::rqi(), base::rqj()))
231         , m_robust_policy(robust_policy)
232     {}
233 
result() const234     inline result_type const& result() const { return m_result; }
i_info() const235     inline i_info_type const& i_info() const { return m_result.template get<0>(); }
d_info() const236     inline d_info_type const& d_info() const { return m_result.template get<1>(); }
237 
238     // TODO: it's more like is_spike_ip_p
is_spike_p() const239     inline bool is_spike_p() const
240     {
241         if (base::sides().pk_wrt_p1() == 0)
242         {
243             if (! is_ip_j<0>())
244             {
245                 return false;
246             }
247 
248             int const qk_p1 = base::sides().qk_wrt_p1();
249             int const qk_p2 = base::sides().qk_wrt_p2();
250 
251             if (qk_p1 == -qk_p2)
252             {
253                 if (qk_p1 == 0)
254                 {
255                     return is_spike_of_collinear(base::pi(), base::pj(),
256                                                  base::pk());
257                 }
258 
259                 return true;
260             }
261         }
262 
263         return false;
264     }
265 
266     // TODO: it's more like is_spike_ip_q
is_spike_q() const267     inline bool is_spike_q() const
268     {
269         if (base::sides().qk_wrt_q1() == 0)
270         {
271             if (! is_ip_j<1>())
272             {
273                 return false;
274             }
275 
276             int const pk_q1 = base::sides().pk_wrt_q1();
277             int const pk_q2 = base::sides().pk_wrt_q2();
278 
279             if (pk_q1 == -pk_q2)
280             {
281                 if (pk_q1 == 0)
282                 {
283                     return is_spike_of_collinear(base::qi(), base::qj(),
284                                                  base::qk());
285                 }
286 
287                 return true;
288             }
289         }
290 
291         return false;
292     }
293 
294 private:
295     template <typename Point>
is_spike_of_collinear(Point const & i,Point const & j,Point const & k) const296     inline bool is_spike_of_collinear(Point const& i, Point const& j,
297                                       Point const& k) const
298     {
299         typedef model::referring_segment<Point const> seg;
300 
301         typedef strategy_intersection
302             <
303                 typename cs_tag<Point>::type, Point, Point, Point, RobustPolicy
304             > si;
305 
306         typedef typename si::segment_intersection_strategy_type strategy;
307 
308         typename strategy::return_type result
309             = strategy::apply(seg(i, j), seg(j, k), m_robust_policy);
310 
311         return result.template get<0>().count == 2;
312     }
313 
314     template <std::size_t OpId>
is_ip_j() const315     bool is_ip_j() const
316     {
317         int arrival = d_info().arrival[OpId];
318         bool same_dirs = d_info().dir_a == 0 && d_info().dir_b == 0;
319 
320         if (same_dirs)
321         {
322             if (i_info().count == 2)
323             {
324                 return arrival != -1;
325             }
326             else
327             {
328                 return arrival == 0;
329             }
330         }
331         else
332         {
333             return arrival == 1;
334         }
335     }
336 
337     result_type m_result;
338     RobustPolicy const& m_robust_policy;
339 };
340 
341 }} // namespace detail::overlay
342 #endif // DOXYGEN_NO_DETAIL
343 
344 }} // namespace boost::geometry
345 
346 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HELPERS_HPP
347