1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 // Unit Test
3
4 // Copyright (c) 2017 Barend Gehrels, Amsterdam, the Netherlands.
5 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
6
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
10
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)
14
15 #include <geometry_test_common.hpp>
16
17 #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp>
18
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>
26
27 #include <boost/assign/list_of.hpp>
28 #include <boost/foreach.hpp>
29
30 #if defined(TEST_WITH_SVG)
31 #include "debug_sort_by_side_svg.hpp"
32 #endif
33
34 namespace
35 {
36
37
38 template <typename T>
as_string(std::vector<T> const & v)39 std::string as_string(std::vector<T> const& v)
40 {
41 std::stringstream out;
42 bool first = true;
43 BOOST_FOREACH(T const& value, v)
44 {
45 out << (first ? "[" : " , ") << value;
46 first = false;
47 }
48 out << (first ? "" : "]");
49 return out.str();
50 }
51
52 }
53
54 template
55 <
56 typename Geometry, typename Point,
57 typename RobustPolicy, typename Strategy
58 >
apply_get_turns(std::string const & case_id,Geometry const & geometry1,Geometry const & geometry2,Point const & turn_point,Point const & origin_point,RobustPolicy const & robust_policy,Strategy const & strategy,std::size_t expected_open_count,std::size_t expected_max_rank,std::vector<bg::signed_size_type> const & expected_right_count)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)
67 {
68 using namespace boost::geometry;
69
70 std::vector<std::size_t> result;
71
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
75 <
76 point_type,
77 typename bg::detail::segment_ratio_type<point_type, RobustPolicy>::type
78 > turn_info;
79 typedef std::deque<turn_info> turn_container_type;
80
81 turn_container_type turns;
82
83 detail::get_turns::no_interrupt_policy policy;
84 bg::get_turns
85 <
86 false, false,
87 detail::overlay::assign_null_policy
88 >(geometry1, geometry2, strategy, robust_policy, turns, policy);
89
90
91 // Define sorter, sorting counter-clockwise such that polygons are on the
92 // right side
93 typedef typename Strategy::side_strategy_type side_strategy;
94 typedef bg::detail::overlay::sort_by_side::side_sorter
95 <
96 false, false, overlay_union,
97 point_type, side_strategy, std::less<int>
98 > sbs_type;
99
100 sbs_type sbs(strategy.get_side_strategy());
101
102 std::cout << "Case: " << case_id << std::endl;
103
104 bool has_origin = false;
105 for (std::size_t turn_index = 0; turn_index < turns.size(); turn_index++)
106 {
107 turn_info const& turn = turns[turn_index];
108
109 if (bg::equals(turn.point, turn_point))
110 {
111 // std::cout << "Found turn: " << turn_index << std::endl;
112 for (int i = 0; i < 2; i++)
113 {
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);
118 if (is_origin)
119 {
120 has_origin = true;
121 }
122
123 sbs.add(turn.operations[i], turn_index, i,
124 geometry1, geometry2, is_origin);
125
126 }
127 }
128 }
129
130 BOOST_CHECK_MESSAGE(has_origin,
131 " caseid=" << case_id
132 << " origin not found");
133
134 if (!has_origin)
135 {
136 for (std::size_t turn_index = 0; turn_index < turns.size(); turn_index++)
137 {
138 turn_info const& turn = turns[turn_index];
139 if (bg::equals(turn.point, turn_point))
140 {
141 for (int i = 0; i < 2; i++)
142 {
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;
147 }
148 }
149 }
150 return result;
151 }
152
153
154 sbs.apply(turn_point);
155
156 sbs.find_open();
157 sbs.assign_zones(detail::overlay::operation_union);
158
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);
162
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++)
166 {
167 typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[i];
168
169 int const rank = static_cast<int>(ranked_point.rank);
170 bool const set_right = rank != previous_to_rank;
171 if (rank != previous_rank)
172 {
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;
178 }
179
180 if (ranked_point.direction != bg::detail::overlay::sort_by_side::dir_to)
181 {
182 continue;
183 }
184
185 previous_to_rank = rank;
186 if (set_right)
187 {
188 right_count[rank] = ranked_point.count_right;
189 }
190 else
191 {
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]);
196 }
197
198 }
199 BOOST_CHECK_MESSAGE(open_count == expected_open_count,
200 " caseid=" << case_id
201 << " open_count: expected=" << expected_open_count
202 << " detected=" << open_count);
203
204 BOOST_CHECK_MESSAGE(max_rank == expected_max_rank,
205 " caseid=" << case_id
206 << " max_rank: expected=" << expected_max_rank
207 << " detected=" << max_rank);
208
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));
213
214 #if defined(TEST_WITH_SVG)
215 debug::sorted_side_map(case_id, sbs, turn_point, geometry1, geometry2);
216 #endif
217
218 return result;
219 }
220
221
222 template <typename T>
test_basic(std::string const & case_id,std::string const & wkt1,std::string const & wkt2,std::string const & wkt_turn_point,std::string const & wkt_origin_point,std::size_t expected_open_count,std::size_t expected_max_rank,std::vector<bg::signed_size_type> const & expected_right_count)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)
231 {
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;
235
236 multi_polygon g1;
237 bg::read_wkt(wkt1, g1);
238
239 multi_polygon g2;
240 bg::read_wkt(wkt2, g2);
241
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);
245
246 // Reverse if necessary
247 bg::correct(g1);
248 bg::correct(g2);
249
250 typedef typename bg::rescale_overlay_policy_type
251 <
252 multi_polygon,
253 multi_polygon
254 >::type rescale_policy_type;
255
256 rescale_policy_type robust_policy
257 = bg::get_rescale_policy<rescale_policy_type>(g1, g2);
258
259 typedef typename bg::strategy::intersection::services::default_strategy
260 <
261 typename bg::cs_tag<point_type>::type
262 >::type strategy_type;
263
264 strategy_type strategy;
265
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);
269 }
270
271 using boost::assign::list_of;
272
273 template <typename T>
test_all()274 void test_all()
275 {
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));
281
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));
287
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));
293
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));
299
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));
305
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));
311
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));
317
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));
323
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));
329
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));
335
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));
341 }
342
343
test_main(int,char * [])344 int test_main(int, char* [])
345 {
346 test_all<double>();
347 return 0;
348 }
349