]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | ||
b32b8144 FG |
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 | |
7c673cae FG |
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 | ||
7c673cae FG |
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 | { | |
30 | 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, | |
b32b8144 | 40 | typename SideStrategy, |
7c673cae FG |
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 | { | |
7c673cae | 46 | inline side_calculator(Pi const& pi, Pj const& pj, Pk const& pk, |
b32b8144 FG |
47 | Qi const& qi, Qj const& qj, Qk const& qk, |
48 | SideStrategy const& side_strategy) | |
7c673cae FG |
49 | : m_pi(pi), m_pj(pj), m_pk(pk) |
50 | , m_qi(qi), m_qj(qj), m_qk(qk) | |
b32b8144 | 51 | , m_side_strategy(side_strategy) |
7c673cae FG |
52 | {} |
53 | ||
b32b8144 FG |
54 | inline int pk_wrt_p1() const { return m_side_strategy.apply(m_pi, m_pj, m_pk); } |
55 | inline int pk_wrt_q1() const { return m_side_strategy.apply(m_qi, m_qj, m_pk); } | |
56 | inline int qk_wrt_p1() const { return m_side_strategy.apply(m_pi, m_pj, m_qk); } | |
57 | inline int qk_wrt_q1() const { return m_side_strategy.apply(m_qi, m_qj, m_qk); } | |
7c673cae | 58 | |
b32b8144 FG |
59 | inline int pk_wrt_q2() const { return m_side_strategy.apply(m_qj, m_qk, m_pk); } |
60 | inline int qk_wrt_p2() const { return m_side_strategy.apply(m_pj, m_pk, m_qk); } | |
7c673cae FG |
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; | |
b32b8144 FG |
68 | |
69 | SideStrategy m_side_strategy; | |
7c673cae FG |
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 | ||
83 | 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 | ||
b32b8144 | 99 | template <typename Point1, typename Point2, typename TurnPoint, typename IntersectionStrategy, typename RobustPolicy> |
7c673cae FG |
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 | ||
b32b8144 FG |
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; | |
7c673cae FG |
116 | |
117 | intersection_info_base(Point1 const& pi, Point1 const& pj, Point1 const& pk, | |
118 | Point2 const& qi, Point2 const& qj, Point2 const& qk, | |
b32b8144 | 119 | IntersectionStrategy const& intersection_strategy, |
7c673cae FG |
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, | |
b32b8144 FG |
123 | base::m_rqi, base::m_rqj, base::m_rqk, |
124 | intersection_strategy.get_side_strategy()) | |
7c673cae FG |
125 | , m_pi(pi), m_pj(pj), m_pk(pk) |
126 | , m_qi(qi), m_qj(qj), m_qk(qk) | |
127 | {} | |
128 | ||
129 | inline Point1 const& pi() const { return m_pi; } | |
130 | inline Point1 const& pj() const { return m_pj; } | |
131 | inline Point1 const& pk() const { return m_pk; } | |
132 | ||
133 | inline Point2 const& qi() const { return m_qi; } | |
134 | inline Point2 const& qj() const { return m_qj; } | |
135 | inline Point2 const& qk() const { return m_qk; } | |
136 | ||
137 | inline robust_point1_type const& rpi() const { return base::m_rpi; } | |
138 | inline robust_point1_type const& rpj() const { return base::m_rpj; } | |
139 | inline robust_point1_type const& rpk() const { return base::m_rpk; } | |
140 | ||
141 | inline robust_point2_type const& rqi() const { return base::m_rqi; } | |
142 | inline robust_point2_type const& rqj() const { return base::m_rqj; } | |
143 | inline robust_point2_type const& rqk() const { return base::m_rqk; } | |
144 | ||
145 | 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 | ||
b32b8144 FG |
158 | template <typename Point1, typename Point2, typename TurnPoint, typename IntersectionStrategy> |
159 | class intersection_info_base<Point1, Point2, TurnPoint, IntersectionStrategy, detail::no_rescale_policy> | |
7c673cae FG |
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 | ||
b32b8144 FG |
170 | typedef typename IntersectionStrategy::side_strategy_type side_strategy_type; |
171 | typedef side_calculator<cs_tag, Point1, Point2, side_strategy_type> side_calculator_type; | |
7c673cae FG |
172 | |
173 | intersection_info_base(Point1 const& pi, Point1 const& pj, Point1 const& pk, | |
174 | Point2 const& qi, Point2 const& qj, Point2 const& qk, | |
b32b8144 | 175 | IntersectionStrategy const& intersection_strategy, |
7c673cae | 176 | no_rescale_policy const& /*robust_policy*/) |
b32b8144 FG |
177 | : m_side_calc(pi, pj, pk, qi, qj, qk, |
178 | intersection_strategy.get_side_strategy()) | |
7c673cae FG |
179 | {} |
180 | ||
181 | inline Point1 const& pi() const { return m_side_calc.m_pi; } | |
182 | inline Point1 const& pj() const { return m_side_calc.m_pj; } | |
183 | inline Point1 const& pk() const { return m_side_calc.m_pk; } | |
184 | ||
185 | inline Point2 const& qi() const { return m_side_calc.m_qi; } | |
186 | inline Point2 const& qj() const { return m_side_calc.m_qj; } | |
187 | inline Point2 const& qk() const { return m_side_calc.m_qk; } | |
188 | ||
189 | inline Point1 const& rpi() const { return pi(); } | |
190 | inline Point1 const& rpj() const { return pj(); } | |
191 | inline Point1 const& rpk() const { return pk(); } | |
192 | ||
193 | inline Point2 const& rqi() const { return qi(); } | |
194 | inline Point2 const& rqj() const { return qj(); } | |
195 | inline Point2 const& rqk() const { return qk(); } | |
196 | ||
197 | 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, | |
b32b8144 | 209 | typename IntersectionStrategy, |
7c673cae FG |
210 | typename RobustPolicy |
211 | > | |
212 | class intersection_info | |
b32b8144 | 213 | : public intersection_info_base<Point1, Point2, TurnPoint, IntersectionStrategy, RobustPolicy> |
7c673cae | 214 | { |
b32b8144 FG |
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; | |
7c673cae | 226 | |
b32b8144 FG |
227 | // NOTE: formerly defined in intersection_strategies |
228 | typedef policies::relate::segments_tupled | |
7c673cae | 229 | < |
b32b8144 FG |
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; | |
7c673cae | 239 | |
7c673cae FG |
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 | ||
b32b8144 | 244 | typedef typename intersection_policy_type::return_type result_type; |
7c673cae FG |
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 | ||
248 | intersection_info(Point1 const& pi, Point1 const& pj, Point1 const& pk, | |
249 | Point2 const& qi, Point2 const& qj, Point2 const& qk, | |
b32b8144 | 250 | IntersectionStrategy const& intersection_strategy, |
7c673cae | 251 | RobustPolicy const& robust_policy) |
b32b8144 FG |
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) | |
7c673cae FG |
261 | , m_robust_policy(robust_policy) |
262 | {} | |
263 | ||
264 | inline result_type const& result() const { return m_result; } | |
265 | inline i_info_type const& i_info() const { return m_result.template get<0>(); } | |
266 | inline d_info_type const& d_info() const { return m_result.template get<1>(); } | |
267 | ||
b32b8144 FG |
268 | inline intersection_strategy_type const& get_intersection_strategy() const |
269 | { | |
270 | return m_intersection_strategy; | |
271 | } | |
272 | ||
273 | inline side_strategy_type get_side_strategy() const | |
274 | { | |
275 | return m_intersection_strategy.get_side_strategy(); | |
276 | } | |
277 | ||
7c673cae FG |
278 | // TODO: it's more like is_spike_ip_p |
279 | 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 | |
307 | 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> | |
336 | 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 | ||
b32b8144 FG |
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); | |
7c673cae | 351 | |
b32b8144 | 352 | return result.count == 2; |
7c673cae FG |
353 | } |
354 | ||
355 | template <std::size_t OpId> | |
356 | 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; | |
b32b8144 | 379 | IntersectionStrategy const& m_intersection_strategy; |
7c673cae FG |
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 |