1 // Boost.Geometry (aka GGL, Generic Geometry Library)
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.
8 // Copyright (c) 2017, Oracle and/or its affiliates.
9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
11 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
12 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
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)
18 #define BOOST_GEOMETRY_DEFINE_STREAM_OPERATOR_SEGMENT_RATIO
20 #include <geometry_test_common.hpp>
22 #include <boost/geometry/algorithms/assign.hpp>
24 #include <boost/geometry/strategies/cartesian/intersection.hpp>
25 #include <boost/geometry/strategies/intersection_result.hpp>
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>
31 #include <boost/geometry/algorithms/intersection.hpp>
32 #include <boost/geometry/algorithms/detail/overlay/segment_as_subrange.hpp>
34 #include <boost/geometry/geometries/point.hpp>
35 #include <boost/geometry/geometries/segment.hpp>
38 template <typename IntersectionPoints
>
39 static int check(IntersectionPoints
const& is
,
40 std::size_t index
, double expected_x
, double expected_y
)
42 if (expected_x
!= -99 && expected_y
!= -99 && is
.count
> index
)
44 double x
= bg::get
<0>(is
.intersections
[index
]);
45 double y
= bg::get
<1>(is
.intersections
[index
]);
47 BOOST_CHECK_CLOSE(x
, expected_x
, 0.001);
48 BOOST_CHECK_CLOSE(y
, expected_y
, 0.001);
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)
65 boost::ignore_unused(case_id
);
67 typedef bg::model::referring_segment
<const P
> segment_type
;
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
);
75 segment_type
s12(p1
, p2
);
76 segment_type
s34(p3
, p4
);
78 bg::detail::segment_as_subrange
<segment_type
> sr12(s12
);
79 bg::detail::segment_as_subrange
<segment_type
> sr34(s34
);
81 typedef bg::segment_intersection_points
<P
> result_type
;
83 typedef bg::policies::relate::segments_intersection_points
88 // Get the intersection point (or two points)
90 = bg::strategy::intersection::cartesian_segments
<>
91 ::apply(sr12
, sr34
, points_policy_type());
93 // Get just a character for Left/Right/intersects/etc, purpose is more for debugging
94 bg::policies::relate::direction_type dir
95 = bg::strategy::intersection::cartesian_segments
<>
96 ::apply(sr12
, sr34
, bg::policies::relate::segments_direction());
98 std::size_t expected_count
=
99 check(is
, 0, expected_x1
, expected_y1
)
100 + check(is
, 1, expected_x2
, expected_y2
);
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
);
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)
119 boost::ignore_unused(case_id
);
121 typedef bg::model::referring_segment
<const P
> segment_type
;
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
);
129 segment_type
s12(p1
, p2
);
130 segment_type
s34(p3
, p4
);
132 bg::detail::segment_as_subrange
<segment_type
> sr12(s12
);
133 bg::detail::segment_as_subrange
<segment_type
> sr34(s34
);
135 typedef bg::segment_intersection_points
<P
> result_type
;
137 typedef bg::policies::relate::segments_intersection_points
140 > points_policy_type
;
142 // Get the intersection point (or two points)
144 = bg::strategy::intersection::cartesian_segments
<>
145 ::apply(sr12
, sr34
, points_policy_type());
147 typedef bg::segment_ratio
<typename
bg::coordinate_type
<P
>::type
> ratio_type
;
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
);
154 BOOST_CHECK_EQUAL(is
.count
, expected_count
);
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
);
161 if (expected_count
== 2)
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
);
171 template <typename P
>
174 // Collinear - non opposite
178 test_segment_intersection
<P
>("n1",
186 test_segment_intersection
<P
>("n2",
194 test_segment_intersection
<P
>("n3",
202 test_segment_intersection
<P
>("n4",
210 test_segment_intersection
<P
>("n5",
218 test_segment_intersection
<P
>("n6",
226 test_segment_intersection
<P
>("n7",
232 // Collinear - opposite
235 test_segment_intersection
<P
>("o1",
243 test_segment_intersection
<P
>("o2",
251 test_segment_intersection
<P
>("o3",
259 test_segment_intersection
<P
>("o4",
267 test_segment_intersection
<P
>("o5",
275 test_segment_intersection
<P
>("o6",
283 test_segment_intersection
<P
>("o7",
291 test_segment_intersection
<P
>("e1",
299 test_segment_intersection
<P
>("e1",
305 // Disjoint (in vertical direction, picture still horizontal)
308 test_segment_intersection
<P
>("case_recursive_boxes_1",
317 template <typename P
>
323 test_segment_ratio
<P
>("n4",
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)
333 test_segment_ratio
<P
>("o4",
336 std::make_pair(1, 5), std::make_pair(3, 5),
337 std::make_pair(1, 1), std::make_pair(0, 1),
342 test_segment_ratio
<P
>("o4b",
345 std::make_pair(2, 5), std::make_pair(4, 5),
346 std::make_pair(0, 1), std::make_pair(1, 1),
351 test_segment_ratio
<P
>("o4c",
354 std::make_pair(2, 5), std::make_pair(4, 5),
355 std::make_pair(1, 1), std::make_pair(0, 1),
361 test_segment_ratio
<P
>("n3",
364 std::make_pair(0, 1), std::make_pair(2, 5),
365 std::make_pair(0, 1), std::make_pair(1, 1),
368 // a2<-------------a1
370 test_segment_ratio
<P
>("n3b",
373 std::make_pair(0, 1), std::make_pair(2, 5),
374 std::make_pair(0, 1), std::make_pair(1, 1),
381 test_segment_ratio
<P
>("rn4",
384 std::make_pair(0, 1), std::make_pair(1, 1),
385 std::make_pair(1, 5), std::make_pair(3, 5),
390 test_segment_ratio
<P
>("ro4",
393 std::make_pair(0, 1), std::make_pair(1, 1),
394 std::make_pair(3, 5), std::make_pair(1, 5),
399 test_segment_ratio
<P
>("ro4b",
402 std::make_pair(0, 1), std::make_pair(1, 1),
403 std::make_pair(2, 5), std::make_pair(4, 5),
408 test_segment_ratio
<P
>("ro4c",
411 std::make_pair(0, 1), std::make_pair(1, 1),
412 std::make_pair(4, 5), std::make_pair(2, 5),
415 // B inside A, boundaries intersect
416 // We change the coordinates a bit (w.r.t. n3 above) to have it asymmetrical
419 test_segment_ratio
<P
>("n3",
422 std::make_pair(0, 1), std::make_pair(2, 5),
423 std::make_pair(0, 1), std::make_pair(1, 1),
428 test_segment_ratio
<P
>("o3",
431 std::make_pair(0, 1), std::make_pair(2, 5),
432 std::make_pair(1, 1), std::make_pair(0, 1),
437 test_segment_ratio
<P
>("n5",
440 std::make_pair(3, 5), std::make_pair(1, 1),
441 std::make_pair(0, 1), std::make_pair(1, 1),
446 test_segment_ratio
<P
>("o5",
449 std::make_pair(3, 5), std::make_pair(1, 1),
450 std::make_pair(1, 1), std::make_pair(0, 1),
453 // Generic (overlaps)
456 test_segment_ratio
<P
>("n2",
459 std::make_pair(0, 1), std::make_pair(2, 5),
460 std::make_pair(1, 3), std::make_pair(1, 1),
464 test_segment_ratio
<P
>("n2_b",
467 std::make_pair(0, 1), std::make_pair(2, 5),
468 std::make_pair(2, 3), std::make_pair(0, 1),
471 // Same, both reversed
472 test_segment_ratio
<P
>("n2_c",
475 std::make_pair(3, 5), std::make_pair(1, 1),
476 std::make_pair(0, 1), std::make_pair(2, 3),
481 test_segment_ratio
<P
>("n6",
484 std::make_pair(3, 4), std::make_pair(1, 1),
485 std::make_pair(0, 1), std::make_pair(1, 3),
491 const int ignored
= 99;
492 test_segment_ratio
<P
>("degenerated1",
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
503 test_segment_ratio
<P
>("degenerated2",
506 std::make_pair(0, 1), std::make_pair(ignored
, 1),
507 std::make_pair(3, 4), std::make_pair(ignored
, 1),
512 // Vertical one like in box_poly5 but in integer
513 test_segment_ratio
<P
>("box_poly5",
516 std::make_pair(3, 10), std::make_pair(6, 10),
517 std::make_pair(0, 1), std::make_pair(1, 1),
521 int test_main(int, char* [])
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
> >();