]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | // Unit Test | |
3 | ||
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. | |
7 | ||
1e59de90 TL |
8 | // This file was modified by Oracle on 2021-2022. |
9 | // Modifications copyright (c) 2021-2022 Oracle and/or its affiliates. | |
10 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
11 | ||
7c673cae FG |
12 | // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library |
13 | // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. | |
14 | ||
15 | // Use, modification and distribution is subject to the Boost Software License, | |
16 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
17 | // http://www.boost.org/LICENSE_1_0.txt) | |
18 | ||
19 | #include <iterator> | |
20 | ||
21 | ||
22 | #include <algorithms/test_simplify.hpp> | |
23 | #include <boost/geometry/geometries/geometries.hpp> | |
24 | #include <boost/geometry/geometries/point_xy.hpp> | |
25 | ||
26 | #include <test_geometries/wrapped_boost_array.hpp> | |
27 | #include <test_common/test_point.hpp> | |
28 | ||
29 | // #define TEST_PULL89 | |
30 | #ifdef TEST_PULL89 | |
31 | #include <boost/geometry/strategies/cartesian/distance_projected_point_ax.hpp> | |
32 | #endif | |
33 | ||
34 | ||
35 | #ifdef TEST_PULL89 | |
36 | template <typename Geometry, typename T> | |
37 | void test_with_ax(std::string const& wkt, | |
38 | std::string const& expected, | |
39 | T const& adt, | |
40 | T const& xdt) | |
41 | { | |
42 | typedef typename bg::point_type<Geometry>::type point_type; | |
43 | typedef bg::strategy::distance::detail::projected_point_ax<> ax_type; | |
44 | typedef typename bg::strategy::distance::services::return_type | |
45 | < | |
46 | bg::strategy::distance::detail::projected_point_ax<>, | |
47 | point_type, | |
48 | point_type | |
49 | >::type return_type; | |
50 | ||
51 | typedef bg::strategy::distance::detail::projected_point_ax_less | |
52 | < | |
53 | return_type | |
54 | > comparator_type; | |
55 | ||
56 | typedef bg::strategy::simplify::detail::douglas_peucker | |
57 | < | |
58 | point_type, | |
59 | bg::strategy::distance::detail::projected_point_ax<>, | |
60 | comparator_type | |
61 | > dp_ax; | |
62 | ||
63 | return_type max_distance(adt, xdt); | |
64 | comparator_type comparator(max_distance); | |
65 | dp_ax strategy(comparator); | |
66 | ||
67 | test_geometry<Geometry>(wkt, expected, max_distance, strategy); | |
68 | } | |
69 | #endif | |
70 | ||
71 | ||
72 | template <typename P> | |
73 | void test_all() | |
74 | { | |
75 | test_geometry<bg::model::linestring<P> >( | |
76 | "LINESTRING(0 0,5 5,10 10)", | |
77 | "LINESTRING(0 0,10 10)", 1.0); | |
78 | ||
79 | test_geometry<bg::model::linestring<P> >( | |
80 | "LINESTRING(0 0, 5 5, 6 5, 10 10)", | |
81 | "LINESTRING(0 0,10 10)", 1.0); | |
82 | ||
83 | test_geometry<bg::model::linestring<P> >( | |
84 | "LINESTRING(0 0,5 5,7 5,10 10)", | |
85 | "LINESTRING(0 0,5 5,7 5,10 10)", 1.0); | |
86 | ||
87 | // Lightning-form which fails for Douglas-Peucker | |
88 | test_geometry<bg::model::linestring<P> >( | |
89 | "LINESTRING(0 0,120 6,80 10,200 0)", | |
90 | "LINESTRING(0 0,120 6,80 10,200 0)", 7); | |
11fdf7f2 | 91 | |
7c673cae FG |
92 | // Same which reordered coordinates |
93 | test_geometry<bg::model::linestring<P> >( | |
94 | "LINESTRING(0 0,80 10,120 6,200 0)", | |
95 | "LINESTRING(0 0,80 10,200 0)", 7); | |
96 | ||
11fdf7f2 TL |
97 | // Duplicate point is removed |
98 | test_geometry<bg::model::linestring<P> >( | |
99 | "LINESTRING(0 0,0 0)", | |
100 | "LINESTRING(0 0)", 1.0); | |
101 | ||
7c673cae FG |
102 | // Mail 2013-10-07, real-life test, piece of River Leine |
103 | // PostGIS returns exactly the same result | |
104 | test_geometry<bg::model::linestring<P> >( | |
105 | "LINESTRING(4293586 3290439,4293568 3290340,4293566 3290332,4293570 3290244,4293576 3290192" | |
106 | ",4293785 3289660,4293832 3289597,4293879 3289564,4293937 3289545,4294130 3289558" | |
107 | ",4294204 3289553,4294240 3289539,4294301 3289479,4294317 3289420,4294311 3289353" | |
108 | ",4294276 3289302,4293870 3289045,4293795 3288978,4293713 3288879,4293669 3288767" | |
109 | ",4293654 3288652,4293657 3288563,4293690 3288452,4293761 3288360,4293914 3288215" | |
110 | ",4293953 3288142,4293960 3288044,4293951 3287961,4293913 3287875,4293708 3287628" | |
111 | ",4293658 3287542,4293633 3287459,4293630 3287383,4293651 3287323,4293697 3287271" | |
112 | ",4293880 3287128,4293930 3287045,4293938 3286977,4293931 3286901,4293785 3286525" | |
113 | ",4293775 3286426,4293786 3286358,4293821 3286294,4294072 3286076,4294134 3285986)", | |
114 | "LINESTRING(4293586 3290439,4293785 3289660,4294317 3289420,4293654 3288652,4293960 3288044" | |
115 | ",4293633 3287459,4293786 3286358,4294134 3285986)", 250); | |
116 | ||
117 | /* TODO fix this | |
118 | test_geometry<test::wrapped_boost_array<P, 10> >( | |
119 | "LINESTRING(0 0,5 5,7 5,10 10)", | |
120 | "LINESTRING(0 0,5 5,7 5,10 10)", 1.0); | |
121 | */ | |
122 | ||
11fdf7f2 TL |
123 | /* |
124 | ||
125 | Above can be checked in PostGIS by: | |
126 | ||
127 | select astext(ST_Simplify(geomfromtext('LINESTRING(0 0, 5 5, 10 10)'),1.0)) as simplified | |
128 | union all select astext(ST_Simplify(geomfromtext('LINESTRING(0 0, 5 5, 6 5, 10 10)'),1.0)) | |
129 | etc | |
130 | */ | |
131 | ||
7c673cae FG |
132 | |
133 | test_geometry<bg::model::polygon<P> >( | |
134 | "POLYGON((4 0,8 2,8 7,4 9,0 7,0 2,2 1,4 0))", | |
135 | "POLYGON((4 0,8 2,8 7,4 9,0 7,0 2,4 0))", 1.0); | |
136 | ||
137 | test_geometry<bg::model::polygon<P> >( | |
138 | "POLYGON((4 0,8 2,8 7,4 9,0 7,0 2,2 1,4 0),(7 3,7 6,1 6,1 3,4 3,7 3))", | |
139 | "POLYGON((4 0,8 2,8 7,4 9,0 7,0 2,4 0),(7 3,7 6,1 6,1 3,7 3))", 1.0); | |
140 | ||
11fdf7f2 TL |
141 | // Closing point should be simplified away |
142 | test_geometry<bg::model::polygon<P> >( | |
143 | "POLYGON((1 0,0 0,0 4,4 4,4 0,1 0))", | |
144 | "POLYGON((0 0,0 4,4 4,4 0,0 0))", 0.1); | |
145 | ||
146 | // Section around closing point should be simplified away | |
147 | test_geometry<bg::model::polygon<P> >( | |
148 | "POLYGON((5 0,4 0,3 0,2 0,1 0,0 0,0 5,5 5,5 0))", | |
149 | "POLYGON((5 0,0 0,0 5,5 5,5 0))", 0.1); | |
150 | ||
151 | // Manually rotate this WKT over all the 5 redundant points at closing area | |
152 | test_geometry<bg::model::polygon<P> >( | |
153 | "POLYGON((4 0,3 0,2 0,1 0,0 0,0 5,5 5,5 0,4 0))", | |
154 | "POLYGON((0 0,0 5,5 5,5 0,0 0))", 0.1); | |
155 | test_geometry<bg::model::polygon<P> >( | |
156 | "POLYGON((3 0,2 0,1 0,0 0,0 5,5 5,5 0,4 0,3 0))", | |
157 | "POLYGON((0 0,0 5,5 5,5 0,0 0))", 0.1); | |
158 | test_geometry<bg::model::polygon<P> >( | |
159 | "POLYGON((2 0,1 0,0 0,0 5,5 5,5 0,4 0,3 0,2 0))", | |
160 | "POLYGON((0 0,0 5,5 5,5 0,0 0))", 0.1); | |
161 | test_geometry<bg::model::polygon<P> >( | |
162 | "POLYGON((1 0,0 0,0 5,5 5,5 0,4 0,3 0,2 0,1 0))", | |
163 | "POLYGON((0 0,0 5,5 5,5 0,0 0))", 0.1); | |
164 | test_geometry<bg::model::polygon<P> >( | |
165 | "POLYGON((0 0,0 5,5 5,5 0,4 0,3 0,2 0,1 0,0 0))", | |
166 | "POLYGON((0 0,0 5,5 5,5 0,0 0))", 0.1); | |
167 | ||
168 | // Test wither all collinear points in between are simplified away | |
169 | // First approach did select one of them because it was the end of the | |
170 | // "closing area". Now the opposite is taken, which is farthest and never | |
171 | // collinear | |
172 | test_geometry<bg::model::polygon<P> >( | |
173 | "POLYGON((2 0,1 0,0 0,0 1,0 2,0 3,0 4,1 4,2 4,3 4,4 4,4 3,4 2,4 1,4 0,3 0,2 0))", | |
174 | "POLYGON((0 0,0 4,4 4,4 0,0 0))", 1.0); | |
175 | ||
176 | // Test simplifying away one of the sides (collinear), then closing point | |
177 | // and finally the whole polygon | |
178 | std::string const near_triangle = "POLYGON((0.55 0.55,1 0,0.5 0,0 0,0 1,0.55 0.55))"; | |
179 | test_geometry<bg::model::polygon<P> >(near_triangle, | |
180 | "POLYGON((0.55 0.55,1 0,0 0,0 1,0.55 0.55))", 0.01); | |
181 | test_geometry<bg::model::polygon<P> >(near_triangle, | |
182 | "POLYGON((1 0,0 0,0 1,1 0))", 0.1); | |
183 | // 0.9 should still result in a simplified polygon | |
184 | test_geometry<bg::model::polygon<P> >(near_triangle, | |
185 | "POLYGON((1 0,0 0,0 1,1 0))", 0.9); | |
186 | test_geometry<bg::model::polygon<P> >(near_triangle, | |
187 | "POLYGON(())", 1.1); | |
188 | ||
189 | // Test simplifying away the closing point, and closing it explicitly | |
190 | std::string const salamina = "POLYGON((2616131.59828 4579307.29099,2616687.86177 4579151.05325,2618172.52982 4578718.79836,2618728.79332 4578522.73574,2620336.91468 4577424.54293,2620522.48427 4576992.50129,2621264.76264 4569815.3917,2621140.75272 4569502.07546,2620491.53745 4568208.96982,2620151.34509 4567855.90928,2612606.55528 4562800.36094,2611833.3301 4562291.50023,2611369.5731 4562174.16117,2610225.54269 4562408.69959,2605896.21638 4564367.29512,2605494.13038 4564641.6634,2605277.94792 4566288.44857,2606019.89233 4569423.46562,2609050.12019 4577424.54293,2614337.90732 4579347.12775,2615296.7021 4579543.34723,2616131.59828 4579307.29099))"; | |
191 | test_geometry<bg::model::polygon<P> >(salamina, 196318951.5097456, 100); | |
192 | test_geometry<bg::model::polygon<P> >(salamina, 194471472.35804176, 200); | |
193 | test_geometry<bg::model::polygon<P> >(salamina, 191735337.33374023, 500); | |
194 | test_geometry<bg::model::polygon<P> >(salamina, 186593693.18401337, 1000); | |
195 | test_geometry<bg::model::polygon<P> >(salamina, 181448561.04094696, 2000); | |
196 | test_geometry<bg::model::polygon<P> >(salamina, 141965392.92240524, 5000); | |
197 | ||
198 | // Interior ring (sized ~ 1) should be simplified away (distance 5) | |
199 | test_geometry<bg::model::polygon<P> >( | |
200 | "POLYGON((0 0,0 10,10 10,10 0,0 0),(5 5,6 6,5 6,5 5))", | |
201 | "POLYGON((0 0,0 10,10 10,10 0,0 0))", 5.0); | |
7c673cae | 202 | |
1e59de90 TL |
203 | // Non-closed version |
204 | test_geometry<bg::model::polygon<P, true, false> >( | |
205 | "POLYGON((1 0,0 0,0 4,4 4,4 0))", | |
206 | "POLYGON((0 0,0 4,4 4,4 0))", 0.1); | |
207 | test_geometry<bg::model::polygon<P, true, false> >( | |
208 | "POLYGON((0 0,0 1,1 1,1 0))", | |
209 | "POLYGON((0 0,0 1,1 1,1 0))", 0.1); | |
210 | ||
211 | // Non-closed, ccw version | |
212 | // https://github.com/boostorg/geometry/issues/956 | |
213 | test_geometry<bg::model::polygon<P, false, false> >( | |
214 | "POLYGON((0 0,0.4 0,0.4 0.4))", | |
215 | "POLYGON((0 0,0.4 0,0.4 0.4))", 0); | |
7c673cae | 216 | |
7c673cae FG |
217 | |
218 | { | |
219 | // Test with explicit strategy | |
220 | ||
221 | typedef bg::strategy::simplify::douglas_peucker | |
222 | < | |
223 | P, | |
224 | bg::strategy::distance::projected_point<double> | |
225 | > dp; | |
226 | ||
227 | test_geometry<bg::model::linestring<P> >( | |
228 | "LINESTRING(0 0,5 5,10 10)", | |
229 | "LINESTRING(0 0,10 10)", 1.0, dp()); | |
230 | } | |
231 | ||
232 | ||
233 | // POINT: check compilation | |
234 | test_geometry<P>( | |
235 | "POINT(0 0)", | |
236 | "POINT(0 0)", 1.0); | |
237 | ||
1e59de90 TL |
238 | test_geometry<bg::model::segment<P> >( |
239 | "SEGMENT(0 0, 1 1)", | |
240 | "SEGMENT(0 0, 1 1)", 1.0); | |
241 | ||
242 | test_geometry<bg::model::box<P> >( | |
243 | "BOX(0 0, 1 1)", | |
244 | "BOX(0 0, 1 1)", 1.0); | |
245 | ||
246 | test_geometry<bg::model::multi_point<P> >( | |
247 | "MULTIPOINT(0 0, 1 1, 2 2)", | |
248 | "MULTIPOINT(0 0, 1 1, 2 2)", 1.0); | |
249 | ||
7c673cae FG |
250 | |
251 | // RING: check compilation and behaviour | |
252 | test_geometry<bg::model::ring<P> >( | |
253 | "POLYGON((4 0,8 2,8 7,4 9,0 7,0 2,2 1,4 0))", | |
254 | "POLYGON((4 0,8 2,8 7,4 9,0 7,0 2,4 0))", 1.0); | |
255 | ||
256 | ||
257 | #ifdef TEST_PULL89 | |
258 | test_with_ax<bg::model::linestring<P> >( | |
259 | "LINESTRING(0 0,120 6,80 10,200 0)", | |
260 | "LINESTRING(0 0,80 10,200 0)", 10, 7); | |
261 | #endif | |
262 | } | |
263 | ||
264 | template <typename P> | |
265 | void test_zigzag() | |
266 | { | |
267 | static const std::string zigzag = "LINESTRING(0 10,1 7,1 9,2 6,2 7,3 4,3 5,5 3,4 5,6 2,6 3,9 1,7 3,10 1,9 2,12 1,10 2,13 1,11 2,14 1,12 2,16 1,14 2,17 3,15 3,18 4,16 4,19 5,17 5,20 6,18 6,21 8,19 7,21 9,19 8,21 10,19 9,21 11,19 10,20 13,19 11)"; | |
268 | ||
269 | static const std::string expected100 = "LINESTRING(0 10,3 4,5 3,4 5,6 2,9 1,7 3,10 1,9 2,16 1,14 2,17 3,15 3,18 4,16 4,19 5,17 5,21 8,19 7,21 9,19 8,21 10,19 9,21 11,19 10,20 13,19 11)"; | |
270 | static const std::string expected150 = "LINESTRING(0 10,6 2,16 1,14 2,21 8,19 7,21 9,19 8,21 10,19 9,20 13,19 11)"; | |
271 | static const std::string expected200 = "LINESTRING(0 10,6 2,16 1,14 2,21 8,19 7,20 13,19 11)"; | |
272 | static const std::string expected225 = "LINESTRING(0 10,6 2,16 1,21 8,19 11)"; | |
273 | test_geometry<bg::model::linestring<P> >(zigzag, expected100, 1.0001); | |
274 | test_geometry<bg::model::linestring<P> >(zigzag, expected150, 1.5001); | |
275 | test_geometry<bg::model::linestring<P> >(zigzag, expected200, 2.0001); | |
276 | test_geometry<bg::model::linestring<P> >(zigzag, expected225, 2.25); // should be larger than sqrt(5)=2.236 | |
277 | ||
278 | #ifdef TEST_PULL89 | |
279 | // This should work (results might vary but should have LESS points then expected above | |
280 | // Small xtd, larger adt, | |
281 | test_with_ax<bg::model::linestring<P> >(zigzag, expected100, 1.0001, 1.0001); | |
282 | test_with_ax<bg::model::linestring<P> >(zigzag, expected150, 1.5001, 1.0001); | |
283 | test_with_ax<bg::model::linestring<P> >(zigzag, expected200, 2.0001, 1.0001); | |
284 | test_with_ax<bg::model::linestring<P> >(zigzag, expected225, 2.25, 1.0001); | |
285 | #endif | |
286 | ||
287 | } | |
288 | ||
289 | ||
290 | template <typename P> | |
291 | void test_3d() | |
292 | { | |
293 | test_geometry<bg::model::linestring<P> >( | |
294 | "LINESTRING(0 0 0,1 1 1,2 2 0)", | |
295 | "LINESTRING(0 0 0,2 2 0)", 1.0001); | |
296 | test_geometry<bg::model::linestring<P> >( | |
297 | "LINESTRING(0 0 0,1 1 1,2 2 0)", | |
298 | "LINESTRING(0 0 0,1 1 1,2 2 0)", 0.9999); | |
299 | } | |
300 | ||
301 | ||
302 | template <typename P> | |
303 | void test_spherical() | |
304 | { | |
305 | test_geometry<bg::model::linestring<P> >( | |
306 | "LINESTRING(4.1 52.1,4.2 52.2,4.3 52.3)", | |
307 | "LINESTRING(4.1 52.1,4.3 52.3)", 0.01); | |
308 | } | |
309 | ||
310 | ||
311 | int test_main(int, char* []) | |
312 | { | |
313 | // Integer compiles, but simplify-process fails (due to distances) | |
314 | //test_all<bg::model::d2::point_xy<int> >(); | |
315 | ||
7c673cae FG |
316 | test_all<bg::model::d2::point_xy<double> >(); |
317 | ||
11fdf7f2 TL |
318 | #if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE) |
319 | ||
320 | test_all<bg::model::d2::point_xy<float> >(); | |
321 | ||
7c673cae FG |
322 | test_3d<bg::model::point<double, 3, bg::cs::cartesian> >(); |
323 | ||
324 | test_spherical<bg::model::point<double, 2, bg::cs::spherical_equatorial<bg::degree> > >(); | |
325 | ||
326 | test_zigzag<bg::model::d2::point_xy<double> >(); | |
327 | ||
11fdf7f2 | 328 | #endif |
7c673cae FG |
329 | |
330 | ||
331 | return 0; | |
332 | } |