1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2
3 // Copyright (c) 2020, Oracle and/or its affiliates.
4
5 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
6
7 // Licensed under the Boost Software License version 1.0.
8 // http://www.boost.org/users/license.html
9
10 #include <geometry_test_common.hpp>
11
12 #include <boost/geometry/algorithms/correct.hpp>
13 #include <boost/geometry/algorithms/equals.hpp>
14 #include <boost/geometry/algorithms/union.hpp>
15 #include <boost/geometry/geometries/geometries.hpp>
16 #include <boost/geometry/io/wkt/wkt.hpp>
17 #include <boost/geometry/strategies/cartesian/area.hpp>
18 #include <boost/geometry/strategies/cartesian/intersection.hpp>
19 #include <boost/geometry/strategies/cartesian/point_in_poly_winding.hpp>
20 #include <boost/geometry/strategies/cartesian/point_in_point.hpp>
21
22 #include <boost/tuple/tuple.hpp>
23
24 typedef bg::model::point<double, 2, bg::cs::cartesian> Pt;
25 typedef bg::model::linestring<Pt> Ls;
26 typedef bg::model::polygon<Pt> Po;
27 typedef bg::model::ring<Pt> R;
28 typedef bg::model::multi_point<Pt> MPt;
29 typedef bg::model::multi_linestring<Ls> MLs;
30 typedef bg::model::multi_polygon<Po> MPo;
31
32 #ifdef BOOST_GEOMETRY_CXX11_TUPLE
33
34 #include <tuple>
35
36 #endif
37
38 template <typename G>
check(std::string const & wkt1,std::string const & wkt2,G const & g,std::string const & expected)39 inline void check(std::string const& wkt1,
40 std::string const& wkt2,
41 G const& g,
42 std::string const& expected)
43 {
44 G expect;
45 bg::read_wkt(expected, expect);
46 bg::correct(expect);
47 if (! boost::empty(g) || ! boost::empty(expect))
48 {
49 BOOST_CHECK_MESSAGE(
50 // Commented out becasue the output in reversed case may be slightly different
51 // e.g. different number of duplicated points in MultiPoint
52 //boost::size(g) == boost::size(expect) &&
53 bg::equals(g, expect),
54 wkt1 << " + " << wkt2 << " -> " << bg::wkt(g)
55 << " different than expected: " << expected
56 );
57 }
58 }
59
check(std::string const & wkt1,std::string const & wkt2,boost::tuple<MPt,MLs,MPo> const & tup,std::string const & out_p_str,std::string const & out_l_str,std::string const & out_a_str)60 inline void check(std::string const& wkt1,
61 std::string const& wkt2,
62 boost::tuple<MPt, MLs, MPo> const& tup,
63 std::string const& out_p_str,
64 std::string const& out_l_str,
65 std::string const& out_a_str)
66 {
67 check(wkt1, wkt2, boost::get<0>(tup), out_p_str);
68 check(wkt1, wkt2, boost::get<1>(tup), out_l_str);
69 check(wkt1, wkt2, boost::get<2>(tup), out_a_str);
70 }
71
check(std::string const & wkt1,std::string const & wkt2,std::pair<MPt,MLs> const & pair,std::string const & out_p_str,std::string const & out_l_str,std::string const &)72 inline void check(std::string const& wkt1,
73 std::string const& wkt2,
74 std::pair<MPt, MLs> const& pair,
75 std::string const& out_p_str,
76 std::string const& out_l_str,
77 std::string const& )
78 {
79 check(wkt1, wkt2, pair.first, out_p_str);
80 check(wkt1, wkt2, pair.second, out_l_str);
81 }
82
83 #ifdef BOOST_GEOMETRY_CXX11_TUPLE
84
check(std::string const & wkt1,std::string const & wkt2,std::tuple<MPt,MLs,MPo> const & tup,std::string const & out_p_str,std::string const & out_l_str,std::string const & out_a_str)85 inline void check(std::string const& wkt1,
86 std::string const& wkt2,
87 std::tuple<MPt, MLs, MPo> const& tup,
88 std::string const& out_p_str,
89 std::string const& out_l_str,
90 std::string const& out_a_str)
91 {
92 check(wkt1, wkt2, std::get<0>(tup), out_p_str);
93 check(wkt1, wkt2, std::get<1>(tup), out_l_str);
94 check(wkt1, wkt2, std::get<2>(tup), out_a_str);
95 }
96
97 #endif
98
99 template <typename In1, typename In2, typename Tup>
test_one(std::string const & in1_str,std::string const & in2_str,std::string const & out_p_str="MULTIPOINT()",std::string const & out_l_str="MULTILINESTRING()",std::string const & out_a_str="MULTIPOLYGON()")100 inline void test_one(std::string const& in1_str,
101 std::string const& in2_str,
102 std::string const& out_p_str = "MULTIPOINT()",
103 std::string const& out_l_str = "MULTILINESTRING()",
104 std::string const& out_a_str = "MULTIPOLYGON()")
105 {
106 In1 in1;
107 bg::read_wkt(in1_str, in1);
108 bg::correct(in1);
109
110 In2 in2;
111 bg::read_wkt(in2_str, in2);
112 bg::correct(in2);
113
114 {
115 Tup result;
116 bg::union_(in1, in2, result);
117 check(in1_str, in2_str, result, out_p_str, out_l_str, out_a_str);
118 }
119 {
120 Tup result;
121 bg::union_(in2, in1, result);
122 check(in1_str, in2_str, result, out_p_str, out_l_str, out_a_str);
123 }
124 }
125
126 template <typename Tup>
test_pp()127 inline void test_pp()
128 {
129 test_one<Pt, Pt, Tup>(
130 "POINT(0 0)",
131 "POINT(0 0)",
132 "MULTIPOINT(0 0)");
133
134 test_one<Pt, MPt, Tup>(
135 "POINT(0 0)",
136 "MULTIPOINT(0 0, 1 1)",
137 "MULTIPOINT(0 0, 1 1)");
138
139 test_one<MPt, MPt, Tup>(
140 "MULTIPOINT(0 0, 1 1, 2 2)",
141 "MULTIPOINT(1 1, 2 2, 3 3)",
142 "MULTIPOINT(0 0, 1 1, 2 2, 3 3)");
143 }
144
145 template <typename Tup>
test_pl()146 inline void test_pl()
147 {
148 test_one<Pt, Ls, Tup>(
149 "POINT(0 0)",
150 "LINESTRING(0 0, 1 1)",
151 "MULTIPOINT()",
152 "MULTILINESTRING((0 0, 1 1))");
153
154 test_one<Pt, Ls, Tup>(
155 "POINT(2 2)",
156 "LINESTRING(0 0, 1 1)",
157 "MULTIPOINT(2 2)",
158 "MULTILINESTRING((0 0, 1 1))");
159
160 test_one<Pt, MLs, Tup>(
161 "POINT(1 1)",
162 "MULTILINESTRING((0 0, 1 1),(1 1, 2 2),(4 4, 5 5))",
163 "MULTIPOINT()",
164 "MULTILINESTRING((0 0, 1 1),(1 1, 2 2),(4 4, 5 5))");
165
166 test_one<MPt, Ls, Tup>(
167 "MULTIPOINT(0 0, 1 1, 2 2, 3 3)",
168 "LINESTRING(0 0, 1 1)",
169 "MULTIPOINT(2 2, 3 3)",
170 "MULTILINESTRING((0 0, 1 1))");
171
172 test_one<MPt, MLs, Tup>(
173 "MULTIPOINT(0 0, 1 1, 2 2, 3 3)",
174 "MULTILINESTRING((0 0, 1 1),(1 1, 2 2),(4 4, 5 5))",
175 "MULTIPOINT(3 3)",
176 "MULTILINESTRING((0 0, 1 1),(1 1, 2 2),(4 4, 5 5))");
177 }
178
179 template <typename Tup>
test_pa()180 inline void test_pa()
181 {
182 test_one<Pt, R, Tup>(
183 "POINT(0 0)",
184 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0))",
185 "MULTIPOINT()",
186 "MULTILINESTRING()",
187 "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0)))");
188
189 test_one<Pt, Po, Tup>(
190 "POINT(2 2)",
191 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0))",
192 "MULTIPOINT(2 2)",
193 "MULTILINESTRING()",
194 "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0)))");
195
196 test_one<Pt, MPo, Tup>(
197 "POINT(2 2)",
198 "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0)),((0 0, 1 2, 2 2, 2 1, 0 0)))",
199 "MULTIPOINT()",
200 "MULTILINESTRING()",
201 "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0)),((0 0, 1 2, 2 2, 2 1, 0 0)))");
202
203 test_one<MPt, R, Tup>(
204 "MULTIPOINT(0 0, 1 1, 2 2, 3 3, 4 4, 5 5, 6 6)",
205 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0))",
206 "MULTIPOINT(6 6)",
207 "MULTILINESTRING()",
208 "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0)))");
209
210 test_one<MPt, Po, Tup>(
211 "MULTIPOINT(0 0, 1 1, 2 2, 3 3, 4 4, 5 5, 6 6)",
212 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0))",
213 "MULTIPOINT(1 1, 2 2, 3 3, 6 6)",
214 "MULTILINESTRING()",
215 "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0)))");
216
217 test_one<MPt, MPo, Tup>(
218 "MULTIPOINT(0 0, 0 0, 1 1, 2 2, 3 3, 4 4, 5 5, 6 6)",
219 "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0)),((0 0, 1 2, 2 2, 2 1, 0 0)))",
220 "MULTIPOINT(3 3, 6 6)",
221 "MULTILINESTRING()",
222 "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0)),((0 0, 1 2, 2 2, 2 1, 0 0)))");
223 }
224
225 template <typename Tup>
test_ll()226 inline void test_ll()
227 {
228 test_one<Ls, Ls, Tup>(
229 "LINESTRING(0 0, 1 0, 2 1, 3 0)",
230 "LINESTRING(0 0, 1 0, 3 0, 4 0)",
231 "MULTIPOINT()",
232 "MULTILINESTRING((0 0,1 0,2 1,3 0),(1 0,3 0,4 0))");
233
234 test_one<Ls, MLs, Tup>(
235 "LINESTRING(0 0, 1 0, 2 1, 3 0)",
236 "MULTILINESTRING((0 0, 1 0, 3 0),(2 1, 2 2))",
237 "MULTIPOINT()",
238 "MULTILINESTRING((0 0,1 0,2 1,3 0),(1 0,3 0),(2 1,2 2))");
239
240 test_one<MLs, MLs, Tup>(
241 "MULTILINESTRING((0 0, 1 0, 2 1),(2 1, 3 0))",
242 "MULTILINESTRING((0 0, 1 0, 3 0),(2 1, 2 2))",
243 "MULTIPOINT()",
244 "MULTILINESTRING((0 0,1 0,3 0),(2 1,2 2),(1 0,2 1),(2 1,3 0))");
245
246 test_one<Ls, Ls, Tup>(
247 "LINESTRING(0 0, 0 5, 5 5, 5 0, 0 0)",
248 "LINESTRING(0 0, 0 1, 6 1, 5 2, 5 5, 5 6, 4 5, 4 7, 7 7, 7 0, 0 0)",
249 "MULTIPOINT()",
250 "MULTILINESTRING((0 0,0 5,5 5,5 0,0 0),(0 1,6 1,5 2),"
251 "(5 5,5 6,4 5,4 7,7 7,7 0,5 0))");
252
253 test_one<MLs, MLs, Tup>(
254 "MULTILINESTRING((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0))",
255 "MULTILINESTRING((0 0, 1 4, 5 4, 5 1, 4 1, 0 0),(0 0, 2 1, 2 2, 1 2, 0 0))",
256 "MULTIPOINT()",
257 "MULTILINESTRING((0 0,1 4,5 4,5 1,4 1,0 0),(0 0,2 1,2 2,1 2,0 0),"
258 "(0 0,0 5,5 5,5 4),(5 1,5 0,0 0),(4 1,4 4))");
259 }
260
261 template <typename Tup>
test_la()262 inline void test_la()
263 {
264 test_one<Ls, R, Tup>(
265 "LINESTRING(0 2, -4 1, 0 0, 5 0, 9 1, 5 2, 9 3, 5 5, 4 9, 4 5, 3 3, 2 5, 2 9, 0 5)",
266 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0))",
267 "MULTIPOINT()",
268 "MULTILINESTRING((0 2, -4 1, 0 0),(5 0, 9 1, 5 2, 9 3, 5 5, 4 9, 4 5),(2 5, 2 9, 0 5))",
269 "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0)))");
270
271 test_one<Ls, Po, Tup>(
272 "LINESTRING(1 4, -4 1, 0 0, 5 0, 9 1, 5 2, 9 3, 5 5, 4 9, 4 5, 3 3, 2 5, 2 9, 0 5)",
273 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0))",
274 "MULTIPOINT()",
275 "MULTILINESTRING((0 3.4, -4 1, 0 0),(5 0, 9 1, 5 2, 9 3, 5 5, 4 9, 4 5),(3.5 4, 3 3, 2.5 4),(2 5, 2 9, 0 5))",
276 "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0)))");
277
278 test_one<MLs, R, Tup>(
279 "MULTILINESTRING((0 2, -4 1, 0 0, 5 0, 9 1, 5 2, 9 3, 5 5, 4 9), (4 9, 4 5, 3 3, 2 5, 2 9, 0 5))",
280 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0))",
281 "MULTIPOINT()",
282 "MULTILINESTRING((0 2, -4 1, 0 0),(5 0, 9 1, 5 2, 9 3, 5 5, 4 9),(4 9, 4 5),(2 5, 2 9, 0 5))",
283 "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0)))");
284
285 test_one<MLs, Po, Tup>(
286 "MULTILINESTRING((1 4, -4 1, 0 0, 5 0, 9 1, 5 2, 9 3, 5 5, 4 9), (4 9, 4 5, 3 3, 2 5, 2 9, 0 5))",
287 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0))",
288 "MULTIPOINT()",
289 "MULTILINESTRING((0 3.4, -4 1, 0 0),(5 0, 9 1, 5 2, 9 3, 5 5, 4 9),(4 9, 4 5),(3.5 4, 3 3, 2.5 4),(2 5, 2 9, 0 5))",
290 "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0)))");
291
292 test_one<MLs, MPo, Tup>(
293 "MULTILINESTRING((1 4, -4 1, 0 0, 5 0, 9 1, 5 2, 9 3, 5 5, 4 9), (4 9, 4 5, 4 4, 2 2, 2 5, 1 9, 0 5))",
294 "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0)),((0 0, 1 2, 2 2, 2 1, 0 0)))",
295 "MULTIPOINT()",
296 "MULTILINESTRING((0 3.4, -4 1, 0 0),(5 0, 9 1, 5 2, 9 3, 5 5, 4 9),(4 9, 4 5),(4 4, 2 2, 2 4),(2 5, 1 9, 0 5))",
297 "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0)),((0 0, 1 2, 2 2, 2 1, 0 0)))");
298
299 test_one<Ls, R, Tup>(
300 "LINESTRING(0 0, 0 5, 5 5, 5 0, 0 0)",
301 "POLYGON((0 0, 0 1, 6 1, 5 2, 5 5, 5 6, 4 5, 4 7, 7 7, 7 0, 0 0))",
302 "MULTIPOINT()",
303 "MULTILINESTRING((0 1, 0 5, 5 5),(5 2, 5 1))",
304 "MULTIPOLYGON(((0 0, 0 1, 6 1, 5 2, 5 5, 5 6, 4 5, 4 7, 7 7, 7 0, 0 0)))");
305
306 test_one<MLs, Po, Tup>(
307 "MULTILINESTRING((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0))",
308 "POLYGON((0 0, 1 4, 5 4, 5 1, 4 1, 0 0),(0 0, 2 1, 2 2, 1 2, 0 0))",
309 "MULTIPOINT()",
310 "MULTILINESTRING((0 0, 0 5, 5 5, 5 4),(5 1, 5 0, 0 0))",
311 "MULTIPOLYGON(((0 0, 1 4, 5 4, 5 1, 4 1, 0 0),(0 0, 2 1, 2 2, 1 2, 0 0)))");
312 }
313
314 template <typename Tup>
test_aa()315 inline void test_aa()
316 {
317 test_one<R, R, Tup>(
318 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0))",
319 "POLYGON((0 0, 0 1, 6 1, 5 2, 5 5, 5 6, 4 5, 4 7, 7 7, 7 0, 0 0))",
320 "MULTIPOINT()",
321 "MULTILINESTRING()",
322 "MULTIPOLYGON(((0 5,4 5,4 7,7 7,7 0,0 0,0 5),(5 1,6 1,5 2,5 1),(5 5,5 6,4 5,5 5)))");
323
324 test_one<R, MPo, Tup>(
325 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0))",
326 "MULTIPOLYGON(((0 0, 0 1, 6 1, 6 0, 0 0)),"
327 "((6 1, 5 2, 5 5, 5 6, 4 5, 4 7, 7 7, 7 1, 6 1)))",
328 "MULTIPOINT()",
329 "MULTILINESTRING()",
330 "MULTIPOLYGON(((0 5,4 5,4 7,7 7,7 1,6 1,6 0,0 0,0 5),(5 1,6 1,5 2,5 1),(5 5,5 6,4 5,5 5)))");
331
332 test_one<Po, Po, Tup>(
333 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0))",
334 "POLYGON((0 0, 1 4, 5 4, 5 1, 4 1, 0 0),(0 0, 2 1, 2 2, 1 2, 0 0))",
335 "MULTIPOINT()",
336 "MULTILINESTRING()",
337 "MULTIPOLYGON(((5 0,0 0,0 5,5 5,5 0),(0 0,2 1,2 2,1 2,0 0)))");
338
339 test_one<Po, MPo, Tup>(
340 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0))",
341 "MULTIPOLYGON(((0 0, 1 4, 5 4, 5 1, 4 1, 0 0),(0 0, 2 1, 2 2, 1 2, 0 0)),"
342 "((5 0, 5 1, 6 1, 6 4, 5 4, 3 6, 2 5, 2 7, 7 7, 7 0 5 0)))",
343 "MULTIPOINT()",
344 "MULTILINESTRING()",
345 "MULTIPOLYGON(((2 5,2 7,7 7,7 0,0 0,0 5,2 5),(4 5,3 6,2 5,4 5),"
346 "(5 4,5 1,6 1,6 4,5 4),(0 0,2 1,2 2,1 2,0 0)))");
347
348 test_one<MPo, MPo, Tup>(
349 "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0)),"
350 "((2 6, 2 8, 8 8, 8 5, 7 5, 7 6, 2 6)))",
351 "MULTIPOLYGON(((0 0, 1 4, 5 4, 5 1, 4 1, 0 0),(0 0, 2 1, 2 2, 1 2, 0 0)),"
352 "((5 0, 5 1, 6 1, 6 4, 5 4, 3 6, 2 5, 2 7, 7 7, 7 0 5 0)))",
353 "MULTIPOINT()",
354 "MULTILINESTRING()",
355 "MULTIPOLYGON(((0 0,0 5,2 5,2 7,2 8,8 8,8 5,7 5,7 0,0 0),"
356 "(5 4,5 1,6 1,6 4,5 4),(0 0,2 1,2 2,1 2,0 0),(4 5,3 6,2 5,4 5)))");
357 }
358
359 template <typename Tup>
test_pair()360 inline void test_pair()
361 {
362 test_pp<Tup>();
363 test_pl<Tup>();
364 test_ll<Tup>();
365 }
366
367 template <typename Tup>
test_tuple()368 inline void test_tuple()
369 {
370 test_pp<Tup>();
371 test_pl<Tup>();
372 test_pa<Tup>();
373 test_ll<Tup>();
374 test_la<Tup>();
375 test_aa<Tup>();
376 }
377
test_main(int,char * [])378 int test_main(int, char* [])
379 {
380 test_pair<std::pair<MPt, MLs> >();
381 test_tuple<boost::tuple<MPt, MLs, MPo> >();
382
383 #ifdef BOOST_GEOMETRY_CXX11_TUPLE
384 test_tuple<std::tuple<MPt, MLs, MPo> >();
385 #endif
386
387 return 0;
388 }
389