1 // Boost.Geometry (aka GGL, Generic Geometry Library)
4 // Copyright (c) 2017 Barend Gehrels, Amsterdam, the Netherlands.
5 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
7 // This file was modified by Oracle on 2017.
8 // Modifications copyright (c) 2017, Oracle and/or its affiliates.
9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
11 // Use, modification and distribution is subject to the Boost Software License,
12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
13 // http://www.boost.org/LICENSE_1_0.txt)
15 #include <geometry_test_common.hpp>
17 #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp>
19 #include <boost/geometry/strategies/strategies.hpp> // for equals/within
20 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
21 #include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
22 #include <boost/geometry/algorithms/correct.hpp>
23 #include <boost/geometry/algorithms/equals.hpp>
24 #include <boost/geometry/io/wkt/wkt.hpp>
25 #include <boost/geometry/geometries/geometries.hpp>
27 #include <boost/assign/list_of.hpp>
28 #include <boost/foreach.hpp>
30 #if defined(TEST_WITH_SVG)
31 #include "debug_sort_by_side_svg.hpp"
39 std::string
as_string(std::vector
<T
> const& v
)
41 std::stringstream out
;
43 BOOST_FOREACH(T
const& value
, v
)
45 out
<< (first
? "[" : " , ") << value
;
48 out
<< (first
? "" : "]");
56 typename Geometry
, typename Point
,
57 typename RobustPolicy
, typename Strategy
59 std::vector
<std::size_t> apply_get_turns(std::string
const& case_id
,
60 Geometry
const& geometry1
, Geometry
const& geometry2
,
61 Point
const& turn_point
, Point
const& origin_point
,
62 RobustPolicy
const& robust_policy
,
63 Strategy
const& strategy
,
64 std::size_t expected_open_count
,
65 std::size_t expected_max_rank
,
66 std::vector
<bg::signed_size_type
> const& expected_right_count
)
68 using namespace boost::geometry
;
70 std::vector
<std::size_t> result
;
72 //todo: maybe should be enriched to count left/right - but can also be counted from ranks
73 typedef typename
bg::point_type
<Geometry
>::type point_type
;
74 typedef bg::detail::overlay::turn_info
77 typename
bg::segment_ratio_type
<point_type
, RobustPolicy
>::type
79 typedef std::deque
<turn_info
> turn_container_type
;
81 turn_container_type turns
;
83 detail::get_turns::no_interrupt_policy policy
;
87 detail::overlay::assign_null_policy
88 >(geometry1
, geometry2
, strategy
, robust_policy
, turns
, policy
);
91 // Define sorter, sorting counter-clockwise such that polygons are on the
93 typedef typename
Strategy::side_strategy_type side_strategy
;
94 typedef bg::detail::overlay::sort_by_side::side_sorter
96 false, false, overlay_union
,
97 point_type
, side_strategy
, std::less
<int>
100 sbs_type
sbs(strategy
.get_side_strategy());
102 std::cout
<< "Case: " << case_id
<< std::endl
;
104 bool has_origin
= false;
105 for (std::size_t turn_index
= 0; turn_index
< turns
.size(); turn_index
++)
107 turn_info
const& turn
= turns
[turn_index
];
109 if (bg::equals(turn
.point
, turn_point
))
111 // std::cout << "Found turn: " << turn_index << std::endl;
112 for (int i
= 0; i
< 2; i
++)
114 Point point1
, point2
, point3
;
115 bg::copy_segment_points
<false, false>(geometry1
, geometry2
,
116 turn
.operations
[i
].seg_id
, point1
, point2
, point3
);
117 bool const is_origin
= ! has_origin
&& bg::equals(point1
, origin_point
);
123 sbs
.add(turn
.operations
[i
], turn_index
, i
,
124 geometry1
, geometry2
, is_origin
);
130 BOOST_CHECK_MESSAGE(has_origin
,
131 " caseid=" << case_id
132 << " origin not found");
136 for (std::size_t turn_index
= 0; turn_index
< turns
.size(); turn_index
++)
138 turn_info
const& turn
= turns
[turn_index
];
139 if (bg::equals(turn
.point
, turn_point
))
141 for (int i
= 0; i
< 2; i
++)
143 Point point1
, point2
, point3
;
144 bg::copy_segment_points
<false, false>(geometry1
, geometry2
,
145 turn
.operations
[i
].seg_id
, point1
, point2
, point3
);
146 // std::cout << "Turn " << turn_index << " op " << i << " point1=" << bg::wkt(point1) << std::endl;
154 sbs
.apply(turn_point
);
157 sbs
.assign_zones(detail::overlay::operation_union
);
159 std::size_t const open_count
= sbs
.open_count(detail::overlay::operation_union
);
160 std::size_t const max_rank
= sbs
.m_ranked_points
.back().rank
;
161 std::vector
<bg::signed_size_type
> right_count(max_rank
+ 1, -1);
163 int previous_rank
= -1;
164 int previous_to_rank
= -1;
165 for (std::size_t i
= 0; i
< sbs
.m_ranked_points
.size(); i
++)
167 typename
sbs_type::rp
const& ranked_point
= sbs
.m_ranked_points
[i
];
169 int const rank
= static_cast<int>(ranked_point
.rank
);
170 bool const set_right
= rank
!= previous_to_rank
;
171 if (rank
!= previous_rank
)
173 BOOST_CHECK_MESSAGE(rank
== previous_rank
+ 1,
174 " caseid=" << case_id
175 << " ranks: conflict in ranks=" << ranked_point
.rank
176 << " vs " << previous_rank
+ 1);
177 previous_rank
= rank
;
180 if (ranked_point
.direction
!= bg::detail::overlay::sort_by_side::dir_to
)
185 previous_to_rank
= rank
;
188 right_count
[rank
] = ranked_point
.count_right
;
192 BOOST_CHECK_MESSAGE(right_count
[rank
] == int(ranked_point
.count_right
),
193 " caseid=" << case_id
194 << " ranks: conflict in right_count=" << ranked_point
.count_right
195 << " vs " << right_count
[rank
]);
199 BOOST_CHECK_MESSAGE(open_count
== expected_open_count
,
200 " caseid=" << case_id
201 << " open_count: expected=" << expected_open_count
202 << " detected=" << open_count
);
204 BOOST_CHECK_MESSAGE(max_rank
== expected_max_rank
,
205 " caseid=" << case_id
206 << " max_rank: expected=" << expected_max_rank
207 << " detected=" << max_rank
);
209 BOOST_CHECK_MESSAGE(right_count
== expected_right_count
,
210 " caseid=" << case_id
211 << " right count: expected=" << as_string(expected_right_count
)
212 << " detected=" << as_string(right_count
));
214 #if defined(TEST_WITH_SVG)
215 debug::sorted_side_map(case_id
, sbs
, turn_point
, geometry1
, geometry2
);
222 template <typename T
>
223 void test_basic(std::string
const& case_id
,
224 std::string
const& wkt1
,
225 std::string
const& wkt2
,
226 std::string
const& wkt_turn_point
,
227 std::string
const& wkt_origin_point
,
228 std::size_t expected_open_count
,
229 std::size_t expected_max_rank
,
230 std::vector
<bg::signed_size_type
> const& expected_right_count
)
232 typedef bg::model::point
<T
, 2, bg::cs::cartesian
> point_type
;
233 typedef bg::model::polygon
<point_type
> polygon
;
234 typedef bg::model::multi_polygon
<polygon
> multi_polygon
;
237 bg::read_wkt(wkt1
, g1
);
240 bg::read_wkt(wkt2
, g2
);
242 point_type turn_point
, origin_point
;
243 bg::read_wkt(wkt_turn_point
, turn_point
);
244 bg::read_wkt(wkt_origin_point
, origin_point
);
246 // Reverse if necessary
250 typedef typename
bg::rescale_overlay_policy_type
254 >::type rescale_policy_type
;
256 rescale_policy_type robust_policy
257 = bg::get_rescale_policy
<rescale_policy_type
>(g1
, g2
);
259 typedef typename
bg::strategy::intersection::services::default_strategy
261 typename
bg::cs_tag
<point_type
>::type
262 >::type strategy_type
;
264 strategy_type strategy
;
266 apply_get_turns(case_id
, g1
, g2
, turn_point
, origin_point
,
267 robust_policy
, strategy
,
268 expected_open_count
, expected_max_rank
, expected_right_count
);
271 using boost::assign::list_of
;
273 template <typename T
>
276 test_basic
<T
>("simplex",
277 "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)))",
278 "MULTIPOLYGON(((1 0,1 1,2 1,2 0,1, 0)))",
279 "POINT(1 1)", "POINT(1 0)",
280 2, 3, list_of(-1)(1)(-1)(1));
282 test_basic
<T
>("dup1",
283 "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)))",
284 "MULTIPOLYGON(((1 0,1 1,2 1,2 0,1, 0)),((0 2,1 2,1 1,0 1,0 2)))",
285 "POINT(1 1)", "POINT(1 0)",
286 2, 3, list_of(-1)(1)(-1)(2));
288 test_basic
<T
>("dup2",
289 "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
290 "MULTIPOLYGON(((1 0,1 1,2 1,2 0,1, 0)))",
291 "POINT(1 1)", "POINT(1 0)",
292 2, 3, list_of(-1)(2)(-1)(1));
294 test_basic
<T
>("dup3",
295 "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
296 "MULTIPOLYGON(((1 0,1 1,2 1,2 0,1, 0)),((0 2,1 2,1 1,0 1,0 2)))",
297 "POINT(1 1)", "POINT(1 0)",
298 2, 3, list_of(-1)(2)(-1)(2));
300 test_basic
<T
>("threequart1",
301 "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
302 "MULTIPOLYGON(((1 2,2 2,2 1,1 1,1 2)))",
303 "POINT(1 1)", "POINT(1 0)",
304 1, 3, list_of(-1)(1)(1)(1));
306 test_basic
<T
>("threequart2",
307 "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
308 "MULTIPOLYGON(((1 2,2 2,2 1,1 1,1 2)),((2 0,1 0,1 1,2 0)))",
309 "POINT(1 1)", "POINT(1 0)",
310 1, 4, list_of(-1)(2)(1)(1)(1));
312 test_basic
<T
>("threequart3",
313 "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
314 "MULTIPOLYGON(((1 2,2 2,2 1,1 1,1 2)),((2 0,1 0,1 1,2 0)),((0 1,0 2,1 1,0 1)))",
315 "POINT(1 1)", "POINT(1 0)",
316 1, 5, list_of(-1)(2)(1)(1)(-1)(2));
318 test_basic
<T
>("full1",
319 "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
320 "MULTIPOLYGON(((1 2,2 2,2 1,1 1,1 2)),((0 0,0 1,1 1,1 0,0 0)))",
321 "POINT(1 1)", "POINT(1 0)",
322 0, 3, list_of(1)(1)(1)(1));
324 test_basic
<T
>("hole1",
325 "MULTIPOLYGON(((0 0,0 3,2 3,2 2,3 2,3 0,0 0),(1 1,2 1,2 2,1 2,1 1)),((4 2,3 2,3 3,4 3,4 2)))",
326 "MULTIPOLYGON(((1 0,1 1,2 1,2 2,1 2,1 4,4 4,4 0,1, 0),(3 2,3 3,2 3,2 2,3 2)))",
327 "POINT(1 2)", "POINT(2 2)",
328 1, 2, list_of(-1)(2)(1));
330 test_basic
<T
>("hole2",
331 "MULTIPOLYGON(((0 0,0 3,2 3,2 2,3 2,3 0,0 0),(1 1,2 1,2 2,1 2,1 1)),((4 2,3 2,3 3,4 3,4 2)))",
332 "MULTIPOLYGON(((1 0,1 1,2 1,2 2,1 2,1 4,4 4,4 0,1, 0),(3 2,3 3,2 3,2 2,3 2)))",
333 "POINT(2 2)", "POINT(2 1)",
334 2, 3, list_of(-1)(2)(-1)(2));
336 test_basic
<T
>("hole3",
337 "MULTIPOLYGON(((0 0,0 3,2 3,2 2,3 2,3 0,0 0),(1 1,2 1,2 2,1 2,1 1)),((4 2,3 2,3 3,4 3,4 2)))",
338 "MULTIPOLYGON(((1 0,1 1,2 1,2 2,1 2,1 4,4 4,4 0,1, 0),(3 2,3 3,2 3,2 2,3 2)))",
339 "POINT(3 2)", "POINT(2 2)",
340 1, 3, list_of(-1)(2)(-1)(2));
344 int test_main(int, char* [])