1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 // Unit Test
3
4 // Copyright (c) 2015, Oracle and/or its affiliates.
5
6 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
7
8 // Licensed under the Boost Software License version 1.0.
9 // http://www.boost.org/users/license.html
10
11 #ifndef BOOST_TEST_MODULE
12 #define BOOST_TEST_MODULE test_douglas_peucker
13 #endif
14
15 #ifdef BOOST_GEOMETRY_TEST_DEBUG
16 #ifndef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
17 #define BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
18 #endif
19 #endif
20
21 #include <iostream>
22 #include <iterator>
23 #include <sstream>
24 #include <string>
25
26 #include <boost/test/included/unit_test.hpp>
27
28 #include <boost/geometry/core/point_type.hpp>
29 #include <boost/geometry/core/tags.hpp>
30
31 #include <boost/geometry/strategies/distance.hpp>
32 #include <boost/geometry/strategies/strategies.hpp>
33
34 #include <boost/geometry/geometries/geometries.hpp>
35 #include <boost/geometry/geometries/adapted/boost_tuple.hpp>
36 #include <boost/geometry/geometries/register/multi_point.hpp>
37
38 #include <boost/geometry/algorithms/comparable_distance.hpp>
39 #include <boost/geometry/algorithms/equals.hpp>
40
41 #include <boost/geometry/io/wkt/wkt.hpp>
42 #include <boost/geometry/io/dsv/write.hpp>
43
44 #include <boost/assign/list_of.hpp>
45 #include <boost/core/ignore_unused.hpp>
46 #include <boost/type_traits/is_same.hpp>
47 #include <boost/tuple/tuple.hpp>
48
49
50 namespace bg = ::boost::geometry;
51 namespace ba = ::boost::assign;
52 namespace services = bg::strategy::distance::services;
53
54 typedef boost::tuple<double, double> tuple_point_type;
55 typedef std::vector<tuple_point_type> tuple_multi_point_type;
56
57 BOOST_GEOMETRY_REGISTER_BOOST_TUPLE_CS(cs::cartesian)
58 BOOST_GEOMETRY_REGISTER_MULTI_POINT(tuple_multi_point_type)
59 BOOST_GEOMETRY_REGISTER_MULTI_POINT_TEMPLATED(std::vector)
60
61 typedef bg::strategy::distance::projected_point<> distance_strategy_type;
62 typedef bg::strategy::distance::projected_point
63 <
64 void, bg::strategy::distance::comparable::pythagoras<>
65 > comparable_distance_strategy_type;
66
67
68 template <typename CoordinateType>
69 struct default_simplify_strategy
70 {
71 typedef bg::model::point<CoordinateType, 2, bg::cs::cartesian> point_type;
72 typedef typename bg::strategy::distance::services::default_strategy
73 <
74 bg::point_tag, bg::segment_tag, point_type
75 >::type default_distance_strategy_type;
76
77 typedef bg::strategy::simplify::douglas_peucker
78 <
79 point_type, default_distance_strategy_type
80 > type;
81 };
82
83
84 template <typename CoordinateType>
85 struct simplify_regular_distance_strategy
86 {
87 typedef bg::model::point<CoordinateType, 2, bg::cs::cartesian> point_type;
88 typedef bg::strategy::simplify::douglas_peucker
89 <
90 point_type, distance_strategy_type
91 > type;
92 };
93
94 template <typename CoordinateType>
95 struct simplify_comparable_distance_strategy
96 {
97 typedef bg::model::point<CoordinateType, 2, bg::cs::cartesian> point_type;
98 typedef bg::strategy::simplify::douglas_peucker
99 <
100 point_type, comparable_distance_strategy_type
101 > type;
102 };
103
104
105
106 template <typename Geometry>
from_wkt(std::string const & wkt)107 inline Geometry from_wkt(std::string const& wkt)
108 {
109 Geometry geometry;
110 boost::geometry::read_wkt(wkt, geometry);
111 return geometry;
112 }
113
114 template <typename Iterator>
print_point_range(std::ostream & os,Iterator first,Iterator beyond,std::string const & header)115 inline std::ostream& print_point_range(std::ostream& os,
116 Iterator first,
117 Iterator beyond,
118 std::string const& header)
119 {
120 os << header << "(";
121 for (Iterator it = first; it != beyond; ++it)
122 {
123 os << " " << bg::dsv(*it);
124 }
125 os << " )";
126 return os;
127 }
128
129
130 struct equals
131 {
132 template <typename Iterator1, typename Iterator2>
applyequals133 static inline bool apply(Iterator1 begin1, Iterator1 end1,
134 Iterator2 begin2, Iterator2 end2)
135 {
136 std::size_t num_points1 = std::distance(begin1, end1);
137 std::size_t num_points2 = std::distance(begin2, end2);
138
139 if ( num_points1 != num_points2 )
140 {
141 return false;
142 }
143
144 Iterator1 it1 = begin1;
145 Iterator2 it2 = begin2;
146 for (; it1 != end1; ++it1, ++it2)
147 {
148 if ( !bg::equals(*it1, *it2) )
149 {
150 return false;
151 }
152 }
153 return true;
154 }
155
156 template <typename Range1, typename Range2>
applyequals157 static inline bool apply(Range1 const& range1, Range2 const& range2)
158 {
159 return apply(boost::begin(range1), boost::end(range1),
160 boost::begin(range2), boost::end(range2));
161 }
162 };
163
164
165
166
167 template <typename Geometry>
168 struct test_one_case
169 {
170 template <typename Strategy, typename Range>
applytest_one_case171 static inline void apply(std::string const& case_id,
172 std::string const& wkt,
173 double max_distance,
174 Strategy const& strategy,
175 Range const& expected_result)
176 {
177 typedef typename bg::point_type<Geometry>::type point_type;
178 std::vector<point_type> result;
179
180 Geometry geometry = from_wkt<Geometry>(wkt);
181
182 std::string typeid_name
183 = typeid(typename bg::coordinate_type<point_type>::type).name();
184
185 #ifdef BOOST_GEOMETRY_TEST_DEBUG
186 std::cout << case_id << " - " << typeid_name
187 << std::endl;
188 std::cout << wkt << std::endl;
189 #endif
190
191 strategy.apply(geometry, std::back_inserter(result), max_distance);
192
193 boost::ignore_unused(strategy);
194
195 #ifdef BOOST_GEOMETRY_TEST_DEBUG
196 print_point_range(std::cout, boost::begin(result), boost::end(result),
197 "output: ");
198 std::cout << std::endl << std::endl;
199 #endif
200 std::stringstream stream_expected;
201 print_point_range(stream_expected, boost::begin(expected_result),
202 boost::end(expected_result),
203 "");
204 std::stringstream stream_detected;
205 print_point_range(stream_detected, boost::begin(result),
206 boost::end(result),
207 "");
208
209 BOOST_CHECK_MESSAGE(equals::apply(result, expected_result),
210 "case id: " << case_id << " - " << typeid_name
211 << ", geometry: " << wkt
212 << ", Expected: " << stream_expected.str()
213 << " - Detected: " << stream_detected.str());
214
215 #ifdef BOOST_GEOMETRY_TEST_DEBUG
216 std::cout << "---------------" << std::endl;
217 std::cout << "---------------" << std::endl;
218 std::cout << std::endl << std::endl;
219 #endif
220 }
221 };
222
223
224 template <typename CoordinateType, typename Strategy>
test_with_strategy(std::string label)225 inline void test_with_strategy(std::string label)
226 {
227 std::cout.precision(20);
228 Strategy strategy;
229
230 typedef bg::model::point<CoordinateType, 2, bg::cs::cartesian> point_type;
231 typedef bg::model::linestring<point_type> linestring_type;
232 typedef bg::model::segment<point_type> segment_type;
233 typedef test_one_case<linestring_type> tester;
234
235 label = " (" + label + ")";
236
237 {
238 point_type const p1(-6,-13), p2(0,-15);
239 segment_type const s(point_type(12,-3), point_type(-12,5));
240
241 if (bg::comparable_distance(p1, s) >= bg::comparable_distance(p2, s))
242 {
243 tester::apply("l01c1" + label,
244 "LINESTRING(12 -3, 4 8,-6 -13,-9 4,0 -15,-12 5)",
245 10,
246 strategy,
247 ba::tuple_list_of(12,-3)(4,8)(-6,-13)(-12,5)
248 );
249 }
250 else
251 {
252 tester::apply("l01c2" + label,
253 "LINESTRING(12 -3, 4 8,-6 -13,-9 4,0 -15,-12 5)",
254 10,
255 strategy,
256 ba::tuple_list_of(12,-3)(4,8)(-6,-13)(-9,4)(0,-15)(-12,5)
257 );
258 }
259 }
260
261 tester::apply("l02" + label,
262 "LINESTRING(-6 -13,-9 4,0 -15,-12 5)",
263 10,
264 strategy,
265 ba::tuple_list_of(-6,-13)(-12,5)
266 );
267
268 tester::apply("l03" + label,
269 "LINESTRING(12 -3, 4 8,-6 -13,-9 4,0 -14,-12 5)",
270 10,
271 strategy,
272 ba::tuple_list_of(12,-3)(4,8)(-6,-13)(-12,5)
273 );
274
275 tester::apply("l04" + label,
276 "LINESTRING(12 -3, 4 8,-6 -13,-9 4,0 -14,-12 5)",
277 14,
278 strategy,
279 ba::tuple_list_of(12,-3)(-6,-13)(-12,5)
280 );
281
282 {
283 segment_type const s(point_type(0,-1), point_type(5,-4));
284 point_type const p1(5,-1), p2(0,-4);
285
286 #ifdef BOOST_GEOMETRY_TEST_DEBUG
287 bool d_larger_first = (bg::distance(p1, s) > bg::distance(p2, s));
288 bool d_larger_second = (bg::distance(p1, s) < bg::distance(p2, s));
289 bool cd_larger_first
290 = (bg::comparable_distance(p1, s) > bg::comparable_distance(p2, s));
291 bool cd_larger_second
292 = (bg::comparable_distance(p1, s) < bg::comparable_distance(p2, s));
293
294 std::cout << "segment: " << bg::dsv(s) << std::endl;
295 std::cout << "distance from " << bg::dsv(p1) << ": "
296 << bg::distance(p1, s) << std::endl;
297 std::cout << "comp. distance from " << bg::dsv(p1) << ": "
298 << bg::comparable_distance(p1, s) << std::endl;
299 std::cout << "distance from " << bg::dsv(p2) << ": "
300 << bg::distance(p2, s) << std::endl;
301 std::cout << "comp. distance from " << bg::dsv(p2) << ": "
302 << bg::comparable_distance(p2, s) << std::endl;
303 std::cout << "larger distance from "
304 << (d_larger_first ? "first" : (d_larger_second ? "second" : "equal"))
305 << std::endl;
306 std::cout << "larger comp. distance from "
307 << (cd_larger_first ? "first" : (cd_larger_second ? "second" : "equal"))
308 << std::endl;
309 std::cout << "difference of distances: "
310 << (bg::distance(p1, s) - bg::distance(p2, s))
311 << std::endl;
312 std::cout << "difference of comp. distances: "
313 << (bg::comparable_distance(p1, s) - bg::comparable_distance(p2, s))
314 << std::endl;
315 #endif
316
317 std::string wkt =
318 "LINESTRING(0 0,5 0,0 -1,5 -1,0 -2,5 -2,0 -3,5 -3,0 -4,5 -4,0 0)";
319
320 if (bg::comparable_distance(p1, s) >= bg::comparable_distance(p2, s))
321 {
322 tester::apply("l05c1" + label,
323 wkt,
324 1,
325 strategy,
326 ba::tuple_list_of(0,0)(5,0)(0,-1)(5,-1)(0,-2)(5,-2)(0,-3)(5,-4)(0,0)
327 );
328 tester::apply("l05c1a" + label,
329 wkt,
330 2,
331 strategy,
332 ba::tuple_list_of(0,0)(5,0)(0,-1)(5,-1)(0,-2)(5,-4)(0,0)
333 );
334 }
335 else
336 {
337 tester::apply("l05c2" + label,
338 wkt,
339 1,
340 strategy,
341 ba::tuple_list_of(0,0)(5,0)(0,-1)(5,-1)(0,-2)(5,-2)(0,-4)(5,-4)(0,0)
342 );
343 tester::apply("l05c2a" + label,
344 wkt,
345 2,
346 strategy,
347 ba::tuple_list_of(0,0)(5,0)(0,-1)(5,-1)(0,-4)(5,-4)(0,0)
348 );
349 }
350 }
351
352 #ifdef BOOST_GEOMETRY_TEST_DEBUG
353 std::cout << std::endl;
354 std::cout << std::endl;
355 std::cout << "*************************************************";
356 std::cout << std::endl;
357 std::cout << std::endl;
358 #endif
359 }
360
361
BOOST_AUTO_TEST_CASE(test_default_strategy)362 BOOST_AUTO_TEST_CASE( test_default_strategy )
363 {
364 test_with_strategy<int, default_simplify_strategy<int>::type>("i");
365 test_with_strategy<float, default_simplify_strategy<float>::type>("f");
366 test_with_strategy<double, default_simplify_strategy<double>::type>("d");
367 test_with_strategy
368 <
369 long double,
370 default_simplify_strategy<long double>::type
371 >("ld");
372 }
373
BOOST_AUTO_TEST_CASE(test_with_regular_distance_strategy)374 BOOST_AUTO_TEST_CASE( test_with_regular_distance_strategy )
375 {
376 test_with_strategy
377 <
378 int,
379 simplify_regular_distance_strategy<int>::type
380 >("i");
381
382 test_with_strategy
383 <
384 float,
385 simplify_regular_distance_strategy<float>::type
386 >("f");
387
388 test_with_strategy
389 <
390 double,
391 simplify_regular_distance_strategy<double>::type
392 >("d");
393 test_with_strategy
394 <
395 long double,
396 simplify_regular_distance_strategy<long double>::type
397 >("ld");
398 }
399
BOOST_AUTO_TEST_CASE(test_with_comparable_distance_strategy)400 BOOST_AUTO_TEST_CASE( test_with_comparable_distance_strategy )
401 {
402 test_with_strategy
403 <
404 int,
405 simplify_comparable_distance_strategy<int>::type
406 >("i");
407 test_with_strategy
408 <
409 float,
410 simplify_comparable_distance_strategy<float>::type
411 >("f");
412 test_with_strategy
413 <
414 double,
415 simplify_comparable_distance_strategy<double>::type
416 >("d");
417 test_with_strategy
418 <
419 long double,
420 simplify_comparable_distance_strategy<long double>::type
421 >("ld");
422 }
423