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/intersection.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 << " x " << 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::intersection(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::intersection(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)");
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(1 1, 2 2)");
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(0 0)");
152
153 test_one<Pt, MLs, Tup>(
154 "POINT(1 1)",
155 "MULTILINESTRING((0 0, 1 1),(1 1, 2 2),(4 4, 5 5))",
156 "MULTIPOINT(1 1)");
157
158 test_one<MPt, Ls, Tup>(
159 "MULTIPOINT(0 0, 1 1, 2 2, 3 3)",
160 "LINESTRING(0 0, 1 1)",
161 "MULTIPOINT(0 0, 1 1)");
162
163 test_one<MPt, MLs, Tup>(
164 "MULTIPOINT(0 0, 1 1, 2 2, 3 3)",
165 "MULTILINESTRING((0 0, 1 1),(1 1, 2 2),(4 4, 5 5))",
166 "MULTIPOINT(0 0, 1 1, 2 2)");
167 }
168
169 template <typename Tup>
test_pa()170 inline void test_pa()
171 {
172 test_one<Pt, R, Tup>(
173 "POINT(0 0)",
174 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0))",
175 "MULTIPOINT(0 0)");
176
177 test_one<Pt, Po, Tup>(
178 "POINT(0 0)",
179 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0))",
180 "MULTIPOINT(0 0)");
181
182 test_one<Pt, MPo, Tup>(
183 "POINT(0 0)",
184 "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)))",
185 "MULTIPOINT(0 0)");
186
187 test_one<MPt, R, Tup>(
188 "MULTIPOINT(0 0, 1 1, 2 2, 3 3, 4 4, 5 5, 6 6)",
189 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0))",
190 "MULTIPOINT(0 0, 1 1, 2 2, 3 3, 4 4, 5 5)");
191
192 test_one<MPt, Po, Tup>(
193 "MULTIPOINT(0 0, 1 1, 2 2, 3 3, 4 4, 5 5, 6 6)",
194 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0))",
195 "MULTIPOINT(0 0, 4 4, 5 5)");
196
197 test_one<MPt, MPo, Tup>(
198 "MULTIPOINT(0 0, 0 0, 1 1, 2 2, 3 3, 4 4, 5 5, 6 6)",
199 "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)))",
200 "MULTIPOINT(0 0, 0 0, 1 1, 2 2, 4 4, 5 5)"); // one (0 0) could be filtered out
201 }
202
203 template <typename Tup>
test_ll()204 inline void test_ll()
205 {
206 test_one<Ls, Ls, Tup>(
207 "LINESTRING(0 0, 1 0, 2 1, 3 0)",
208 "LINESTRING(0 0, 1 0, 3 0, 4 0)",
209 "MULTIPOINT(3 0)",
210 "MULTILINESTRING((0 0, 1 0))");
211
212 test_one<Ls, MLs, Tup>(
213 "LINESTRING(0 0, 1 0, 2 1, 3 0)",
214 "MULTILINESTRING((0 0, 1 0, 3 0),(2 1, 2 2))",
215 "MULTIPOINT(3 0, 2 1)",
216 "MULTILINESTRING((0 0, 1 0))");
217
218 test_one<MLs, MLs, Tup>(
219 "MULTILINESTRING((0 0, 1 0, 2 1),(2 1, 3 0))",
220 "MULTILINESTRING((0 0, 1 0, 3 0),(2 1, 2 2))",
221 "MULTIPOINT(3 0, 2 1, 2 1)", // (2 1) could be filtered out
222 "MULTILINESTRING((0 0, 1 0))");
223
224
225 test_one<Ls, Ls, Tup>(
226 "LINESTRING(0 0, 0 5, 5 5, 5 0, 0 0)",
227 "LINESTRING(0 0, 0 1, 6 1, 5 2, 5 5, 5 6, 4 5, 4 7, 7 7, 7 0, 0 0)",
228 "MULTIPOINT(4 5, 5 1, 0 0)", // (0 0) could be filtered out
229 "MULTILINESTRING((0 0, 0 1), (5 5, 5 2), (5 0, 0 0))");
230
231 test_one<MLs, MLs, Tup>(
232 "MULTILINESTRING((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0))",
233 "MULTILINESTRING((0 0, 1 4, 5 4, 5 1, 4 1, 0 0),(0 0, 2 1, 2 2, 1 2, 0 0))",
234 // all (0 0) could be filtered out
235 "MULTIPOINT(0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0)",
236 "MULTILINESTRING((5 4,5 1),(0 0,4 1),(4 4,1 4,0 0))");
237 }
238
239 template <typename Tup>
test_la()240 inline void test_la()
241 {
242 test_one<Ls, R, Tup>(
243 "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)",
244 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0))",
245 "MULTIPOINT(0 2, 5 2, 5 5, 0 5)",
246 "MULTILINESTRING((0 0, 5 0),(4 5, 3 3, 2 5))");
247
248 test_one<Ls, Po, Tup>(
249 "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)",
250 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0))",
251 "MULTIPOINT(5 2, 5 5, 0 5)",
252 "MULTILINESTRING((1 4, 0 3.4)(0 0, 5 0),(4 5, 3.5 4),(2.5 4, 2 5))");
253
254 test_one<MLs, R, Tup>(
255 "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))",
256 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0))",
257 "MULTIPOINT(0 2, 5 2, 5 5, 0 5)",
258 "MULTILINESTRING((0 0, 5 0),(4 5, 3 3, 2 5))");
259
260 test_one<MLs, Po, Tup>(
261 "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))",
262 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0))",
263 "MULTIPOINT(5 2, 5 5, 0 5)",
264 "MULTILINESTRING((1 4, 0 3.4)(0 0, 5 0),(4 5, 3.5 4),(2.5 4, 2 5))");
265
266 test_one<MLs, MPo, Tup>(
267 "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))",
268 "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)))",
269 "MULTIPOINT(5 2, 5 5, 2 2, 0 5)",
270 "MULTILINESTRING((1 4, 0 3.4)(0 0, 5 0),(4 5, 4 4),(2 4, 2 5))");
271
272
273 test_one<Ls, R, Tup>(
274 "LINESTRING(0 0, 0 5, 5 5, 5 0, 0 0)",
275 "POLYGON((0 0, 0 1, 6 1, 5 2, 5 5, 5 6, 4 5, 4 7, 7 7, 7 0, 0 0))",
276 "MULTIPOINT(4 5)",
277 "MULTILINESTRING((0 0, 0 1), (5 5, 5 2), (5 1, 5 0, 0 0))");
278
279 test_one<MLs, Po, Tup>(
280 "MULTILINESTRING((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0))",
281 "POLYGON((0 0, 1 4, 5 4, 5 1, 4 1, 0 0),(0 0, 2 1, 2 2, 1 2, 0 0))",
282 "MULTIPOINT(0 0)", // (0 0) could be filtered out
283 "MULTILINESTRING((5 4, 5 1),(0 0, 4 1, 4 4, 1 4, 0 0))");
284 }
285
286 template <typename Tup>
test_aa()287 inline void test_aa()
288 {
289 test_one<R, R, Tup>(
290 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0))",
291 "POLYGON((0 0, 0 1, 6 1, 5 2, 5 5, 5 6, 4 5, 4 7, 7 7, 7 0, 0 0))",
292 "MULTIPOINT(4 5)",
293 "MULTILINESTRING((5 2, 5 5))",
294 "MULTIPOLYGON(((0 0, 0 1, 5 1, 5 0, 0 0)))");
295
296 test_one<R, MPo, Tup>(
297 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0))",
298 "MULTIPOLYGON(((0 0, 0 1, 6 1, 6 0, 0 0)),"
299 "((6 1, 5 2, 5 5, 5 6, 4 5, 4 7, 7 7, 7 1, 6 1)))",
300 "MULTIPOINT(4 5)",
301 "MULTILINESTRING((5 2, 5 5))",
302 "MULTIPOLYGON(((0 0, 0 1, 5 1, 5 0, 0 0)))");
303
304 test_one<Po, Po, Tup>(
305 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0))",
306 "POLYGON((0 0, 1 4, 5 4, 5 1, 4 1, 0 0),(0 0, 2 1, 2 2, 1 2, 0 0))",
307 // all (0 0) could be filtered out
308 "MULTIPOINT(0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0)",
309 "MULTILINESTRING((0 0, 1 4, 4 4),(0 0, 4 1))",
310 "MULTIPOLYGON(((4 1, 4 4, 5 4, 5 1, 4 1)))");
311
312 test_one<Po, MPo, Tup>(
313 "POLYGON((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0))",
314 "MULTIPOLYGON(((0 0, 1 4, 5 4, 5 1, 4 1, 0 0),(0 0, 2 1, 2 2, 1 2, 0 0)),"
315 "((5 0, 5 1, 6 1, 6 4, 5 4, 3 6, 2 5, 2 7, 7 7, 7 0 5 0)))",
316 // all (0 0) and (5 0) could be filtered out
317 "MULTIPOINT(2 5, 5 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0)",
318 "MULTILINESTRING((0 0, 1 4, 4 4),(0 0, 4 1),(5 1, 5 0))",
319 "MULTIPOLYGON(((4 1, 4 4, 5 4, 5 1, 4 1)),((5 4, 4 5, 5 5, 5 4)))");
320
321 test_one<MPo, MPo, Tup>(
322 "MULTIPOLYGON(((0 0, 0 5, 5 5, 5 0, 0 0),(0 0, 4 1, 4 4, 1 4, 0 0)),"
323 "((2 6, 2 8, 8 8, 8 5, 7 5, 7 6, 2 6)))",
324 "MULTIPOLYGON(((0 0, 1 4, 5 4, 5 1, 4 1, 0 0),(0 0, 2 1, 2 2, 1 2, 0 0)),"
325 "((5 0, 5 1, 6 1, 6 4, 5 4, 3 6, 2 5, 2 7, 7 7, 7 0 5 0)))",
326 // all (0 0) and (5 0) could be filtered out
327 "MULTIPOINT(2 5, 5 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0, 0 0)",
328 "MULTILINESTRING((0 0, 1 4, 4 4),(0 0, 4 1),(5 1, 5 0),(7 5, 7 6))",
329 "MULTIPOLYGON(((4 1, 4 4, 5 4, 5 1, 4 1)),"
330 "((5 4, 4 5, 5 5, 5 4)),"
331 "((2 6, 2 7, 7 7, 7 6, 2 6)))");
332 }
333
334 template <typename Tup>
test_pair()335 inline void test_pair()
336 {
337 test_pp<Tup>();
338 test_pl<Tup>();
339 test_pa<Tup>();
340 test_ll<Tup>();
341 test_la<Tup>();
342 }
343
344 template <typename Tup>
test_tuple()345 inline void test_tuple()
346 {
347 test_pp<Tup>();
348 test_pl<Tup>();
349 test_pa<Tup>();
350 test_ll<Tup>();
351 test_la<Tup>();
352 test_aa<Tup>();
353 }
354
test_main(int,char * [])355 int test_main(int, char* [])
356 {
357 test_pair<std::pair<MPt, MLs> >();
358 test_tuple<boost::tuple<MPt, MLs, MPo> >();
359
360 #ifdef BOOST_GEOMETRY_CXX11_TUPLE
361 test_tuple<std::tuple<MPt, MLs, MPo> >();
362 #endif
363
364 return 0;
365 }
366