]>
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 | ||
5 | // Use, modification and distribution is subject to the Boost Software License, | |
6 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
7 | // http://www.boost.org/LICENSE_1_0.txt) | |
8 | ||
9 | #ifndef BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_DIRECTION_HPP | |
10 | #define BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_DIRECTION_HPP | |
11 | ||
12 | ||
13 | #include <cstddef> | |
14 | #include <string> | |
15 | ||
16 | #include <boost/concept_check.hpp> | |
17 | ||
18 | #include <boost/geometry/arithmetic/determinant.hpp> | |
19 | #include <boost/geometry/strategies/side_info.hpp> | |
20 | ||
21 | #include <boost/geometry/util/math.hpp> | |
22 | #include <boost/geometry/util/select_calculation_type.hpp> | |
23 | #include <boost/geometry/util/select_most_precise.hpp> | |
24 | ||
25 | ||
26 | namespace boost { namespace geometry | |
27 | { | |
28 | ||
29 | ||
30 | namespace policies { namespace relate | |
31 | { | |
32 | ||
33 | struct direction_type | |
34 | { | |
35 | // NOTE: "char" will be replaced by enum in future version | |
36 | ||
37 | inline direction_type(side_info const& s, char h, | |
38 | int ha, int hb, | |
39 | int da = 0, int db = 0, | |
40 | bool op = false) | |
41 | : how(h) | |
42 | , opposite(op) | |
43 | , how_a(ha) | |
44 | , how_b(hb) | |
45 | , dir_a(da) | |
46 | , dir_b(db) | |
47 | , sides(s) | |
48 | { | |
49 | arrival[0] = ha; | |
50 | arrival[1] = hb; | |
51 | } | |
52 | ||
53 | inline direction_type(char h, bool op, int ha = 0, int hb = 0) | |
54 | : how(h) | |
55 | , opposite(op) | |
56 | , how_a(ha) | |
57 | , how_b(hb) | |
58 | , dir_a(0) | |
59 | , dir_b(0) | |
60 | { | |
61 | arrival[0] = ha; | |
62 | arrival[1] = hb; | |
63 | } | |
64 | ||
65 | ||
66 | // TODO: replace this | |
67 | // NOTE: "char" will be replaced by enum in future version | |
68 | // "How" is the intersection formed? | |
69 | char how; | |
70 | ||
71 | // Is it opposite (for collinear/equal cases) | |
72 | bool opposite; | |
73 | ||
74 | // Information on how A arrives at intersection, how B arrives at intersection | |
75 | // 1: arrives at intersection | |
76 | // -1: starts from intersection | |
77 | int how_a; | |
78 | int how_b; | |
79 | ||
80 | // Direction: how is A positioned from B | |
81 | // 1: points left, seen from IP | |
82 | // -1: points right, seen from IP | |
83 | // In case of intersection: B's TO direction | |
84 | // In case that B's TO direction is at A: B's from direction | |
85 | // In collinear cases: it is 0 | |
86 | int dir_a; // Direction of A-s TO from IP | |
87 | int dir_b; // Direction of B-s TO from IP | |
88 | ||
89 | // New information | |
90 | side_info sides; | |
91 | // THIS IS EQUAL TO arrival_a, arrival_b - they probably can go now we have robust fractions | |
92 | int arrival[2]; // 1=arrival, -1=departure, 0=neutral; == how_a//how_b | |
93 | ||
94 | ||
95 | // About arrival[0] (== arrival of a2 w.r.t. b) for COLLINEAR cases | |
96 | // Arrival 1: a1--------->a2 (a arrives within b) | |
97 | // b1----->b2 | |
98 | ||
99 | // Arrival 1: (a in b) | |
100 | // | |
101 | ||
102 | ||
103 | // Arrival -1: a1--------->a2 (a does not arrive within b) | |
104 | // b1----->b2 | |
105 | ||
106 | // Arrival -1: (b in a) a_1-------------a_2 | |
107 | // b_1---b_2 | |
108 | ||
109 | // Arrival 0: a1------->a2 (a arrives at TO-border of b) | |
110 | // b1--->b2 | |
111 | ||
112 | }; | |
113 | ||
114 | struct segments_direction | |
115 | { | |
116 | typedef direction_type return_type; | |
117 | ||
118 | template | |
119 | < | |
120 | typename Segment1, | |
121 | typename Segment2, | |
122 | typename SegmentIntersectionInfo | |
123 | > | |
124 | static inline return_type segments_crosses(side_info const& sides, | |
125 | SegmentIntersectionInfo const& , | |
126 | Segment1 const& , Segment2 const& ) | |
127 | { | |
128 | bool const ra0 = sides.get<0,0>() == 0; | |
129 | bool const ra1 = sides.get<0,1>() == 0; | |
130 | bool const rb0 = sides.get<1,0>() == 0; | |
131 | bool const rb1 = sides.get<1,1>() == 0; | |
132 | ||
133 | return | |
134 | // opposite and same starting point (FROM) | |
135 | ra0 && rb0 ? calculate_side<1>(sides, 'f', -1, -1) | |
136 | ||
137 | // opposite and point to each other (TO) | |
138 | : ra1 && rb1 ? calculate_side<0>(sides, 't', 1, 1) | |
139 | ||
140 | // not opposite, forming an angle, first a then b, | |
141 | // directed either both left, or both right | |
142 | // Check side of B2 from A. This is not calculated before | |
143 | : ra1 && rb0 ? angle<1>(sides, 'a', 1, -1) | |
144 | ||
145 | // not opposite, forming a angle, first b then a, | |
146 | // directed either both left, or both right | |
147 | : ra0 && rb1 ? angle<0>(sides, 'a', -1, 1) | |
148 | ||
149 | // b starts from interior of a | |
150 | : rb0 ? starts_from_middle(sides, 'B', 0, -1) | |
151 | ||
152 | // a starts from interior of b (#39) | |
153 | : ra0 ? starts_from_middle(sides, 'A', -1, 0) | |
154 | ||
155 | // b ends at interior of a, calculate direction of A from IP | |
156 | : rb1 ? b_ends_at_middle(sides) | |
157 | ||
158 | // a ends at interior of b | |
159 | : ra1 ? a_ends_at_middle(sides) | |
160 | ||
161 | // normal intersection | |
162 | : calculate_side<1>(sides, 'i', -1, -1) | |
163 | ; | |
164 | } | |
165 | ||
166 | template <typename Ratio> | |
167 | static inline int arrival_value(Ratio const& r_from, Ratio const& r_to) | |
168 | { | |
169 | // a1--------->a2 | |
170 | // b1----->b2 | |
171 | // a departs: -1 | |
172 | ||
173 | // a1--------->a2 | |
174 | // b1----->b2 | |
175 | // a arrives: 1 | |
176 | ||
177 | // a1--------->a2 | |
178 | // b1----->b2 | |
179 | // both arrive there -> r-to = 1/1, or 0/1 (on_segment) | |
180 | ||
181 | // First check the TO (for arrival), then FROM (for departure) | |
182 | return r_to.in_segment() ? 1 | |
183 | : r_to.on_segment() ? 0 | |
184 | : r_from.on_segment() ? -1 | |
185 | : -1 | |
186 | ; | |
187 | } | |
188 | ||
189 | template <typename Ratio> | |
190 | static inline void analyze(Ratio const& r, | |
191 | int& in_segment_count, | |
192 | int& on_end_count, | |
193 | int& outside_segment_count) | |
194 | { | |
195 | if (r.on_end()) | |
196 | { | |
197 | on_end_count++; | |
198 | } | |
199 | else if (r.in_segment()) | |
200 | { | |
201 | in_segment_count++; | |
202 | } | |
203 | else | |
204 | { | |
205 | outside_segment_count++; | |
206 | } | |
207 | } | |
208 | ||
209 | static inline int arrival_from_position_value(int /*v_from*/, int v_to) | |
210 | { | |
211 | return v_to == 2 ? 1 | |
212 | : v_to == 1 || v_to == 3 ? 0 | |
213 | //: v_from >= 1 && v_from <= 3 ? -1 | |
214 | : -1; | |
215 | ||
216 | // NOTE: this should be an equivalent of the above for the other order | |
217 | /* (v_from < 3 && v_to > 3) || (v_from > 3 && v_to < 3) ? 1 | |
218 | : v_from == 3 || v_to == 3 ? 0 | |
219 | : -1;*/ | |
220 | } | |
221 | ||
222 | static inline void analyse_position_value(int pos_val, | |
223 | int & in_segment_count, | |
224 | int & on_end_count, | |
225 | int & outside_segment_count) | |
226 | { | |
227 | if ( pos_val == 1 || pos_val == 3 ) | |
228 | { | |
229 | on_end_count++; | |
230 | } | |
231 | else if ( pos_val == 2 ) | |
232 | { | |
233 | in_segment_count++; | |
234 | } | |
235 | else | |
236 | { | |
237 | outside_segment_count++; | |
238 | } | |
239 | } | |
240 | ||
241 | template <typename Segment1, typename Segment2, typename Ratio> | |
242 | static inline return_type segments_collinear( | |
243 | Segment1 const& , Segment2 const& , bool opposite, | |
244 | int a1_wrt_b, int a2_wrt_b, int b1_wrt_a, int b2_wrt_a, | |
245 | Ratio const& /*ra_from_wrt_b*/, Ratio const& /*ra_to_wrt_b*/, | |
246 | Ratio const& /*rb_from_wrt_a*/, Ratio const& /*rb_to_wrt_a*/) | |
247 | { | |
248 | return_type r('c', opposite); | |
249 | ||
250 | // IMPORTANT: the order of conditions is different as in intersection_points.hpp | |
251 | // We assign A in 0 and B in 1 | |
252 | r.arrival[0] = arrival_from_position_value(a1_wrt_b, a2_wrt_b); | |
253 | r.arrival[1] = arrival_from_position_value(b1_wrt_a, b2_wrt_a); | |
254 | ||
255 | // Analyse them | |
256 | int a_in_segment_count = 0; | |
257 | int a_on_end_count = 0; | |
258 | int a_outside_segment_count = 0; | |
259 | int b_in_segment_count = 0; | |
260 | int b_on_end_count = 0; | |
261 | int b_outside_segment_count = 0; | |
262 | analyse_position_value(a1_wrt_b, | |
263 | a_in_segment_count, a_on_end_count, a_outside_segment_count); | |
264 | analyse_position_value(a2_wrt_b, | |
265 | a_in_segment_count, a_on_end_count, a_outside_segment_count); | |
266 | analyse_position_value(b1_wrt_a, | |
267 | b_in_segment_count, b_on_end_count, b_outside_segment_count); | |
268 | analyse_position_value(b2_wrt_a, | |
269 | b_in_segment_count, b_on_end_count, b_outside_segment_count); | |
270 | ||
271 | if (a_on_end_count == 1 | |
272 | && b_on_end_count == 1 | |
273 | && a_outside_segment_count == 1 | |
274 | && b_outside_segment_count == 1) | |
275 | { | |
276 | // This is a collinear touch | |
277 | // --------> A (or B) | |
278 | // <---------- B (or A) | |
279 | // We adapt the "how" | |
280 | // TODO: how was to be refactored anyway, | |
281 | if (! opposite) | |
282 | { | |
283 | r.how = 'a'; | |
284 | } | |
285 | else | |
286 | { | |
287 | r.how = r.arrival[0] == 0 ? 't' : 'f'; | |
288 | } | |
289 | } | |
290 | else if (a_on_end_count == 2 | |
291 | && b_on_end_count == 2) | |
292 | { | |
293 | r.how = 'e'; | |
294 | } | |
295 | ||
296 | return r; | |
297 | } | |
298 | ||
299 | template <typename Segment> | |
300 | static inline return_type degenerate(Segment const& , bool) | |
301 | { | |
302 | return return_type('0', false); | |
303 | } | |
304 | ||
305 | template <typename Segment, typename Ratio> | |
306 | static inline return_type one_degenerate(Segment const& , | |
307 | Ratio const& , | |
308 | bool) | |
309 | { | |
310 | // To be decided | |
311 | return return_type('0', false); | |
312 | } | |
313 | ||
314 | static inline return_type disjoint() | |
315 | { | |
316 | return return_type('d', false); | |
317 | } | |
318 | ||
319 | static inline return_type error(std::string const&) | |
320 | { | |
321 | // Return "E" to denote error | |
322 | // This will throw an error in get_turn_info | |
323 | // TODO: change to enum or similar | |
324 | return return_type('E', false); | |
325 | } | |
326 | ||
327 | private : | |
328 | ||
329 | template <std::size_t I> | |
330 | static inline return_type calculate_side(side_info const& sides, | |
331 | char how, int how_a, int how_b) | |
332 | { | |
333 | int const dir = sides.get<1, I>() == 1 ? 1 : -1; | |
334 | return return_type(sides, how, how_a, how_b, -dir, dir); | |
335 | } | |
336 | ||
337 | template <std::size_t I> | |
338 | static inline return_type angle(side_info const& sides, | |
339 | char how, int how_a, int how_b) | |
340 | { | |
341 | int const dir = sides.get<1, I>() == 1 ? 1 : -1; | |
342 | return return_type(sides, how, how_a, how_b, dir, dir); | |
343 | } | |
344 | ||
345 | ||
346 | static inline return_type starts_from_middle(side_info const& sides, | |
347 | char which, | |
348 | int how_a, int how_b) | |
349 | { | |
350 | // Calculate ARROW of b segment w.r.t. s1 | |
351 | int dir = sides.get<1, 1>() == 1 ? 1 : -1; | |
352 | ||
353 | // From other perspective, then reverse | |
354 | bool const is_a = which == 'A'; | |
355 | if (is_a) | |
356 | { | |
357 | dir = -dir; | |
358 | } | |
359 | ||
360 | return return_type(sides, 's', | |
361 | how_a, | |
362 | how_b, | |
363 | is_a ? dir : -dir, | |
364 | ! is_a ? dir : -dir); | |
365 | } | |
366 | ||
367 | ||
368 | ||
369 | // To be harmonized | |
370 | static inline return_type a_ends_at_middle(side_info const& sides) | |
371 | { | |
372 | // Ending at the middle, one ARRIVES, the other one is NEUTRAL | |
373 | // (because it both "arrives" and "departs" there) | |
374 | int const dir = sides.get<1, 1>() == 1 ? 1 : -1; | |
375 | return return_type(sides, 'm', 1, 0, dir, dir); | |
376 | } | |
377 | ||
378 | ||
379 | static inline return_type b_ends_at_middle(side_info const& sides) | |
380 | { | |
381 | int const dir = sides.get<0, 1>() == 1 ? 1 : -1; | |
382 | return return_type(sides, 'm', 0, 1, dir, dir); | |
383 | } | |
384 | ||
385 | }; | |
386 | ||
387 | }} // namespace policies::relate | |
388 | ||
389 | }} // namespace boost::geometry | |
390 | ||
391 | #endif // BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_DIRECTION_HPP |