]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | // Unit Test | |
3 | ||
4 | // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. | |
5 | // Copyright (c) 2008-2012 Bruno Lalande, Paris, France. | |
6 | // Copyright (c) 2009-2012 Mateusz Loskot, London, UK. | |
7 | ||
b32b8144 FG |
8 | // Copyright (c) 2017, Oracle and/or its affiliates. |
9 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
10 | ||
7c673cae FG |
11 | // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library |
12 | // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. | |
13 | ||
14 | // Use, modification and distribution is subject to the Boost Software License, | |
15 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
16 | // http://www.boost.org/LICENSE_1_0.txt) | |
17 | ||
18 | #define BOOST_GEOMETRY_DEFINE_STREAM_OPERATOR_SEGMENT_RATIO | |
19 | ||
20 | #include <geometry_test_common.hpp> | |
21 | ||
22 | #include <boost/geometry/algorithms/assign.hpp> | |
23 | ||
b32b8144 | 24 | #include <boost/geometry/strategies/cartesian/intersection.hpp> |
7c673cae FG |
25 | #include <boost/geometry/strategies/intersection_result.hpp> |
26 | ||
27 | #include <boost/geometry/policies/relate/intersection_points.hpp> | |
28 | #include <boost/geometry/policies/relate/direction.hpp> | |
29 | #include <boost/geometry/policies/relate/tupled.hpp> | |
30 | ||
31 | #include <boost/geometry/algorithms/intersection.hpp> | |
92f5a8d4 | 32 | #include <boost/geometry/algorithms/detail/overlay/segment_as_subrange.hpp> |
7c673cae FG |
33 | |
34 | #include <boost/geometry/geometries/point.hpp> | |
35 | #include <boost/geometry/geometries/segment.hpp> | |
36 | ||
37 | ||
38 | template <typename IntersectionPoints> | |
39 | static int check(IntersectionPoints const& is, | |
40 | std::size_t index, double expected_x, double expected_y) | |
41 | { | |
42 | if (expected_x != -99 && expected_y != -99 && is.count > index) | |
43 | { | |
44 | double x = bg::get<0>(is.intersections[index]); | |
45 | double y = bg::get<1>(is.intersections[index]); | |
46 | ||
47 | BOOST_CHECK_CLOSE(x, expected_x, 0.001); | |
48 | BOOST_CHECK_CLOSE(y, expected_y, 0.001); | |
49 | return 1; | |
50 | } | |
51 | return 0; | |
52 | } | |
53 | ||
54 | ||
55 | template <typename P> | |
56 | static void test_segment_intersection(std::string const& case_id, | |
57 | int x1, int y1, int x2, int y2, | |
58 | int x3, int y3, int x4, int y4, | |
59 | char expected_how, bool expected_opposite, | |
60 | int expected_arrival1, int expected_arrival2, | |
61 | int expected_x1, int expected_y1, | |
62 | int expected_x2 = -99, int expected_y2 = -99) | |
63 | ||
64 | { | |
92f5a8d4 | 65 | boost::ignore_unused(case_id); |
7c673cae FG |
66 | |
67 | typedef bg::model::referring_segment<const P> segment_type; | |
68 | ||
69 | P p1, p2, p3, p4; | |
70 | bg::assign_values(p1, x1, y1); | |
71 | bg::assign_values(p2, x2, y2); | |
72 | bg::assign_values(p3, x3, y3); | |
73 | bg::assign_values(p4, x4, y4); | |
74 | ||
92f5a8d4 TL |
75 | segment_type s12(p1, p2); |
76 | segment_type s34(p3, p4); | |
7c673cae | 77 | |
92f5a8d4 TL |
78 | bg::detail::segment_as_subrange<segment_type> sr12(s12); |
79 | bg::detail::segment_as_subrange<segment_type> sr34(s34); | |
7c673cae | 80 | |
92f5a8d4 | 81 | typedef bg::segment_intersection_points<P> result_type; |
7c673cae | 82 | |
b32b8144 FG |
83 | typedef bg::policies::relate::segments_intersection_points |
84 | < | |
85 | result_type | |
86 | > points_policy_type; | |
87 | ||
7c673cae FG |
88 | // Get the intersection point (or two points) |
89 | result_type is | |
b32b8144 | 90 | = bg::strategy::intersection::cartesian_segments<> |
92f5a8d4 | 91 | ::apply(sr12, sr34, points_policy_type()); |
7c673cae FG |
92 | |
93 | // Get just a character for Left/Right/intersects/etc, purpose is more for debugging | |
94 | bg::policies::relate::direction_type dir | |
b32b8144 | 95 | = bg::strategy::intersection::cartesian_segments<> |
92f5a8d4 | 96 | ::apply(sr12, sr34, bg::policies::relate::segments_direction()); |
7c673cae FG |
97 | |
98 | std::size_t expected_count = | |
99 | check(is, 0, expected_x1, expected_y1) | |
100 | + check(is, 1, expected_x2, expected_y2); | |
101 | ||
102 | BOOST_CHECK_EQUAL(is.count, expected_count); | |
103 | BOOST_CHECK_EQUAL(dir.how, expected_how); | |
104 | BOOST_CHECK_EQUAL(dir.opposite, expected_opposite); | |
105 | BOOST_CHECK_EQUAL(dir.arrival[0], expected_arrival1); | |
106 | BOOST_CHECK_EQUAL(dir.arrival[1], expected_arrival2); | |
107 | } | |
108 | ||
109 | template <typename P, typename Pair> | |
110 | static void test_segment_ratio(std::string const& case_id, | |
111 | int x1, int y1, int x2, int y2, | |
112 | int x3, int y3, int x4, int y4, | |
113 | Pair expected_pair_a1, Pair expected_pair_a2, | |
114 | Pair expected_pair_b1, Pair expected_pair_b2, | |
115 | int exp_ax1, int exp_ay1, int exp_ax2, int exp_ay2, | |
116 | std::size_t expected_count = 2) | |
117 | ||
118 | { | |
92f5a8d4 | 119 | boost::ignore_unused(case_id); |
7c673cae FG |
120 | |
121 | typedef bg::model::referring_segment<const P> segment_type; | |
122 | ||
123 | P p1, p2, p3, p4; | |
124 | bg::assign_values(p1, x1, y1); | |
125 | bg::assign_values(p2, x2, y2); | |
126 | bg::assign_values(p3, x3, y3); | |
127 | bg::assign_values(p4, x4, y4); | |
128 | ||
129 | segment_type s12(p1, p2); | |
130 | segment_type s34(p3, p4); | |
131 | ||
92f5a8d4 TL |
132 | bg::detail::segment_as_subrange<segment_type> sr12(s12); |
133 | bg::detail::segment_as_subrange<segment_type> sr34(s34); | |
7c673cae | 134 | |
92f5a8d4 | 135 | typedef bg::segment_intersection_points<P> result_type; |
7c673cae | 136 | |
b32b8144 FG |
137 | typedef bg::policies::relate::segments_intersection_points |
138 | < | |
139 | result_type | |
140 | > points_policy_type; | |
141 | ||
7c673cae FG |
142 | // Get the intersection point (or two points) |
143 | result_type is | |
b32b8144 | 144 | = bg::strategy::intersection::cartesian_segments<> |
92f5a8d4 TL |
145 | ::apply(sr12, sr34, points_policy_type()); |
146 | ||
147 | typedef bg::segment_ratio<typename bg::coordinate_type<P>::type> ratio_type; | |
7c673cae FG |
148 | |
149 | ratio_type expected_a1(expected_pair_a1.first, expected_pair_a1.second); | |
150 | ratio_type expected_a2(expected_pair_a2.first, expected_pair_a2.second); | |
151 | ratio_type expected_b1(expected_pair_b1.first, expected_pair_b1.second); | |
152 | ratio_type expected_b2(expected_pair_b2.first, expected_pair_b2.second); | |
153 | ||
154 | BOOST_CHECK_EQUAL(is.count, expected_count); | |
155 | ||
156 | BOOST_CHECK_EQUAL(is.fractions[0].robust_ra, expected_a1); | |
157 | BOOST_CHECK_EQUAL(is.fractions[0].robust_rb, expected_b1); | |
158 | BOOST_CHECK_EQUAL(bg::get<0>(is.intersections[0]), exp_ax1); | |
159 | BOOST_CHECK_EQUAL(bg::get<1>(is.intersections[0]), exp_ay1); | |
160 | ||
161 | if (expected_count == 2) | |
162 | { | |
163 | BOOST_CHECK_EQUAL(bg::get<0>(is.intersections[1]), exp_ax2); | |
164 | BOOST_CHECK_EQUAL(bg::get<1>(is.intersections[1]), exp_ay2); | |
165 | BOOST_CHECK_EQUAL(is.fractions[1].robust_ra, expected_a2); | |
166 | BOOST_CHECK_EQUAL(is.fractions[1].robust_rb, expected_b2); | |
167 | } | |
168 | } | |
169 | ||
170 | ||
171 | template <typename P> | |
172 | void test_all() | |
173 | { | |
174 | // Collinear - non opposite | |
175 | ||
176 | // a1---------->a2 | |
177 | // b1--->b2 | |
178 | test_segment_intersection<P>("n1", | |
179 | 2, 0, 6, 0, | |
180 | 0, 0, 2, 0, | |
181 | 'a', false, -1, 0, | |
182 | 2, 0); | |
183 | ||
184 | // a1---------->a2 | |
185 | // b1--->b2 | |
186 | test_segment_intersection<P>("n2", | |
187 | 2, 0, 6, 0, | |
188 | 1, 0, 3, 0, | |
189 | 'c', false, -1, 1, | |
190 | 2, 0, 3, 0); | |
191 | ||
192 | // a1---------->a2 | |
193 | // b1--->b2 | |
194 | test_segment_intersection<P>("n3", | |
195 | 2, 0, 6, 0, | |
196 | 2, 0, 4, 0, | |
197 | 'c', false, -1, 1, | |
198 | 2, 0, 4, 0); | |
199 | ||
200 | // a1---------->a2 | |
201 | // b1--->b2 | |
202 | test_segment_intersection<P>("n4", | |
203 | 2, 0, 6, 0, | |
204 | 3, 0, 5, 0, | |
205 | 'c', false, -1, 1, | |
206 | 3, 0, 5, 0); | |
207 | ||
208 | // a1---------->a2 | |
209 | // b1--->b2 | |
210 | test_segment_intersection<P>("n5", | |
211 | 2, 0, 6, 0, | |
212 | 4, 0, 6, 0, | |
213 | 'c', false, 0, 0, | |
214 | 4, 0, 6, 0); | |
215 | ||
216 | // a1---------->a2 | |
217 | // b1--->b2 | |
218 | test_segment_intersection<P>("n6", | |
219 | 2, 0, 6, 0, | |
220 | 5, 0, 7, 0, | |
221 | 'c', false, 1, -1, | |
222 | 5, 0, 6, 0); | |
223 | ||
224 | // a1---------->a2 | |
225 | // b1--->b2 | |
226 | test_segment_intersection<P>("n7", | |
227 | 2, 0, 6, 0, | |
228 | 6, 0, 8, 0, | |
229 | 'a', false, 0, -1, | |
230 | 6, 0); | |
231 | ||
232 | // Collinear - opposite | |
233 | // a1---------->a2 | |
234 | // b2<---b1 | |
235 | test_segment_intersection<P>("o1", | |
236 | 2, 0, 6, 0, | |
237 | 2, 0, 0, 0, | |
238 | 'f', true, -1, -1, | |
239 | 2, 0); | |
240 | ||
241 | // a1---------->a2 | |
242 | // b2<---b1 | |
243 | test_segment_intersection<P>("o2", | |
244 | 2, 0, 6, 0, | |
245 | 3, 0, 1, 0, | |
246 | 'c', true, -1, -1, | |
247 | 2, 0, 3, 0); | |
248 | ||
249 | // a1---------->a2 | |
250 | // b2<---b1 | |
251 | test_segment_intersection<P>("o3", | |
252 | 2, 0, 6, 0, | |
253 | 4, 0, 2, 0, | |
254 | 'c', true, -1, 0, | |
255 | 2, 0, 4, 0); | |
256 | ||
257 | // a1---------->a2 | |
258 | // b2<---b1 | |
259 | test_segment_intersection<P>("o4", | |
260 | 2, 0, 6, 0, | |
261 | 5, 0, 3, 0, | |
262 | 'c', true, -1, 1, | |
263 | 3, 0, 5, 0); | |
264 | ||
265 | // a1---------->a2 | |
266 | // b2<---b1 | |
267 | test_segment_intersection<P>("o5", | |
268 | 2, 0, 6, 0, | |
269 | 6, 0, 4, 0, | |
270 | 'c', true, 0, 1, | |
271 | 4, 0, 6, 0); | |
272 | ||
273 | // a1---------->a2 | |
274 | // b2<---b1 | |
275 | test_segment_intersection<P>("o6", | |
276 | 2, 0, 6, 0, | |
277 | 7, 0, 5, 0, | |
278 | 'c', true, 1, 1, | |
279 | 5, 0, 6, 0); | |
280 | ||
281 | // a1---------->a2 | |
282 | // b2<---b1 | |
283 | test_segment_intersection<P>("o7", | |
284 | 2, 0, 6, 0, | |
285 | 8, 0, 6, 0, | |
286 | 't', true, 0, 0, | |
287 | 6, 0); | |
288 | ||
289 | // a1---------->a2 | |
290 | // b1---------->b2 | |
291 | test_segment_intersection<P>("e1", | |
292 | 2, 0, 6, 0, | |
293 | 2, 0, 6, 0, | |
294 | 'e', false, 0, 0, | |
295 | 2, 0, 6, 0); | |
296 | ||
297 | // a1---------->a2 | |
298 | // b2<----------b1 | |
299 | test_segment_intersection<P>("e1", | |
300 | 2, 0, 6, 0, | |
301 | 6, 0, 2, 0, | |
302 | 'e', true, 0, 0, | |
303 | 2, 0, 6, 0); | |
304 | ||
305 | // Disjoint (in vertical direction, picture still horizontal) | |
306 | // a2<---a1 | |
307 | // b2<---b1 | |
308 | test_segment_intersection<P>("case_recursive_boxes_1", | |
309 | 10, 7, 10, 6, | |
310 | 10, 10, 10, 9, | |
311 | 'd', false, 0, 0, | |
312 | -1, -1, -1, -1); | |
313 | ||
314 | } | |
315 | ||
316 | ||
317 | template <typename P> | |
318 | void test_ratios() | |
319 | { | |
320 | // B inside A | |
321 | // a1------------>a2 | |
322 | // b1--->b2 | |
323 | test_segment_ratio<P>("n4", | |
324 | 2, 0, 7, 0, | |
325 | 3, 0, 5, 0, | |
326 | std::make_pair(1, 5), std::make_pair(3, 5), // IP located on 1/5, 3/5 w.r.t A | |
327 | std::make_pair(0, 1), std::make_pair(1, 1), // IP located on 0, 1 w.r.t. B | |
328 | // IP's are ordered as in A (currently) | |
329 | 3, 0, 5, 0); | |
330 | ||
331 | // a1------------>a2 | |
332 | // b2<---b1 | |
333 | test_segment_ratio<P>("o4", | |
334 | 2, 0, 7, 0, | |
335 | 5, 0, 3, 0, | |
336 | std::make_pair(1, 5), std::make_pair(3, 5), | |
337 | std::make_pair(1, 1), std::make_pair(0, 1), | |
338 | 3, 0, 5, 0); | |
339 | ||
340 | // a2<------------a1 | |
341 | // b2<---b1 | |
342 | test_segment_ratio<P>("o4b", | |
343 | 7, 0, 2, 0, | |
344 | 5, 0, 3, 0, | |
345 | std::make_pair(2, 5), std::make_pair(4, 5), | |
346 | std::make_pair(0, 1), std::make_pair(1, 1), | |
347 | 5, 0, 3, 0); | |
348 | ||
349 | // a2<------------a1 | |
350 | // b1--->b2 | |
351 | test_segment_ratio<P>("o4c", | |
352 | 7, 0, 2, 0, | |
353 | 3, 0, 5, 0, | |
354 | std::make_pair(2, 5), std::make_pair(4, 5), | |
355 | std::make_pair(1, 1), std::make_pair(0, 1), | |
356 | 5, 0, 3, 0); | |
357 | ||
358 | // Touch-interior | |
359 | // a1---------->a2 | |
360 | // b1--->b2 | |
361 | test_segment_ratio<P>("n3", | |
362 | 2, 0, 7, 0, | |
363 | 2, 0, 4, 0, | |
364 | std::make_pair(0, 1), std::make_pair(2, 5), | |
365 | std::make_pair(0, 1), std::make_pair(1, 1), | |
366 | 2, 0, 4, 0); | |
367 | ||
368 | // a2<-------------a1 | |
369 | // b2<----b1 | |
370 | test_segment_ratio<P>("n3b", | |
371 | 7, 0, 2, 0, | |
372 | 7, 0, 5, 0, | |
373 | std::make_pair(0, 1), std::make_pair(2, 5), | |
374 | std::make_pair(0, 1), std::make_pair(1, 1), | |
375 | 7, 0, 5, 0); | |
376 | ||
377 | ||
378 | // A inside B | |
379 | // a1--->a2 | |
380 | // b1------------>b2 | |
381 | test_segment_ratio<P>("rn4", | |
382 | 3, 0, 5, 0, | |
383 | 2, 0, 7, 0, | |
384 | std::make_pair(0, 1), std::make_pair(1, 1), | |
385 | std::make_pair(1, 5), std::make_pair(3, 5), | |
386 | 3, 0, 5, 0); | |
387 | ||
388 | // a2<---a1 | |
389 | // b1------------>b2 | |
390 | test_segment_ratio<P>("ro4", | |
391 | 5, 0, 3, 0, | |
392 | 2, 0, 7, 0, | |
393 | std::make_pair(0, 1), std::make_pair(1, 1), | |
394 | std::make_pair(3, 5), std::make_pair(1, 5), | |
395 | 5, 0, 3, 0); | |
396 | ||
397 | // a2<---a1 | |
398 | // b2<------------b1 | |
399 | test_segment_ratio<P>("ro4b", | |
400 | 5, 0, 3, 0, | |
401 | 7, 0, 2, 0, | |
402 | std::make_pair(0, 1), std::make_pair(1, 1), | |
403 | std::make_pair(2, 5), std::make_pair(4, 5), | |
404 | 5, 0, 3, 0); | |
405 | ||
406 | // a1--->a2 | |
407 | // b2<------------b1 | |
408 | test_segment_ratio<P>("ro4c", | |
409 | 3, 0, 5, 0, | |
410 | 7, 0, 2, 0, | |
411 | std::make_pair(0, 1), std::make_pair(1, 1), | |
412 | std::make_pair(4, 5), std::make_pair(2, 5), | |
413 | 3, 0, 5, 0); | |
414 | ||
415 | // B inside A, boundaries intersect | |
416 | // We change the coordinates a bit (w.r.t. n3 above) to have it asymmetrical | |
417 | // a1---------->a2 | |
418 | // b1--->b2 | |
419 | test_segment_ratio<P>("n3", | |
420 | 2, 0, 7, 0, | |
421 | 2, 0, 4, 0, | |
422 | std::make_pair(0, 1), std::make_pair(2, 5), | |
423 | std::make_pair(0, 1), std::make_pair(1, 1), | |
424 | 2, 0, 4, 0); | |
425 | ||
426 | // a1---------->a2 | |
427 | // b2<---b1 | |
428 | test_segment_ratio<P>("o3", | |
429 | 2, 0, 7, 0, | |
430 | 4, 0, 2, 0, | |
431 | std::make_pair(0, 1), std::make_pair(2, 5), | |
432 | std::make_pair(1, 1), std::make_pair(0, 1), | |
433 | 2, 0, 4, 0); | |
434 | ||
435 | // a1---------->a2 | |
436 | // b1--->b2 | |
437 | test_segment_ratio<P>("n5", | |
438 | 2, 0, 7, 0, | |
439 | 5, 0, 7, 0, | |
440 | std::make_pair(3, 5), std::make_pair(1, 1), | |
441 | std::make_pair(0, 1), std::make_pair(1, 1), | |
442 | 5, 0, 7, 0); | |
443 | ||
444 | // a1---------->a2 | |
445 | // b2<---b1 | |
446 | test_segment_ratio<P>("o5", | |
447 | 2, 0, 7, 0, | |
448 | 7, 0, 5, 0, | |
449 | std::make_pair(3, 5), std::make_pair(1, 1), | |
450 | std::make_pair(1, 1), std::make_pair(0, 1), | |
451 | 5, 0, 7, 0); | |
452 | ||
453 | // Generic (overlaps) | |
454 | // a1---------->a2 | |
455 | // b1----->b2 | |
456 | test_segment_ratio<P>("n2", | |
457 | 2, 0, 7, 0, | |
458 | 1, 0, 4, 0, | |
459 | std::make_pair(0, 1), std::make_pair(2, 5), | |
460 | std::make_pair(1, 3), std::make_pair(1, 1), | |
461 | 2, 0, 4, 0); | |
462 | ||
463 | // Same, b reversed | |
464 | test_segment_ratio<P>("n2_b", | |
465 | 2, 0, 7, 0, | |
466 | 4, 0, 1, 0, | |
467 | std::make_pair(0, 1), std::make_pair(2, 5), | |
468 | std::make_pair(2, 3), std::make_pair(0, 1), | |
469 | 2, 0, 4, 0); | |
470 | ||
471 | // Same, both reversed | |
472 | test_segment_ratio<P>("n2_c", | |
473 | 7, 0, 2, 0, | |
474 | 4, 0, 1, 0, | |
475 | std::make_pair(3, 5), std::make_pair(1, 1), | |
476 | std::make_pair(0, 1), std::make_pair(2, 3), | |
477 | 4, 0, 2, 0); | |
478 | ||
479 | // a1---------->a2 | |
480 | // b1----->b2 | |
481 | test_segment_ratio<P>("n6", | |
482 | 2, 0, 6, 0, | |
483 | 5, 0, 8, 0, | |
484 | std::make_pair(3, 4), std::make_pair(1, 1), | |
485 | std::make_pair(0, 1), std::make_pair(1, 3), | |
486 | 5, 0, 6, 0); | |
487 | ||
488 | // Degenerated one | |
489 | // a1---------->a2 | |
490 | // b1/b2 | |
491 | const int ignored = 99; | |
492 | test_segment_ratio<P>("degenerated1", | |
493 | 2, 0, 6, 0, | |
494 | 5, 0, 5, 0, | |
495 | std::make_pair(3, 4), // IP located on 3/4 w.r.t A | |
496 | std::make_pair(ignored, 1), // not checked | |
497 | std::make_pair(0, 1), // IP located at any place w.r.t B, so 0 | |
498 | std::make_pair(ignored, 1), // not checked | |
499 | 5, 0, | |
500 | ignored, ignored, | |
501 | 1); | |
502 | ||
503 | test_segment_ratio<P>("degenerated2", | |
504 | 5, 0, 5, 0, | |
505 | 2, 0, 6, 0, | |
506 | std::make_pair(0, 1), std::make_pair(ignored, 1), | |
507 | std::make_pair(3, 4), std::make_pair(ignored, 1), | |
508 | 5, 0, | |
509 | ignored, ignored, | |
510 | 1); | |
511 | ||
512 | // Vertical one like in box_poly5 but in integer | |
513 | test_segment_ratio<P>("box_poly5", | |
514 | 45, 25, 45, 15, | |
515 | 45, 22, 45, 19, | |
516 | std::make_pair(3, 10), std::make_pair(6, 10), | |
517 | std::make_pair(0, 1), std::make_pair(1, 1), | |
518 | 45, 22, 45, 19); | |
519 | } | |
520 | ||
521 | int test_main(int, char* []) | |
522 | { | |
523 | // We don't rescale but use integer points as, by nature, robust points | |
524 | test_all<bg::model::point<int, 2, bg::cs::cartesian> >(); | |
525 | test_ratios<bg::model::point<int, 2, bg::cs::cartesian> >(); | |
526 | return 0; | |
527 | } |