1 // Boost.Geometry (aka GGL, Generic Geometry Library)
4 // Copyright (c) 2015, Oracle and/or its affiliates.
6 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
8 // Licensed under the Boost Software License version 1.0.
9 // http://www.boost.org/users/license.html
11 #ifndef BOOST_TEST_MODULE
12 #define BOOST_TEST_MODULE test_douglas_peucker
15 #ifdef BOOST_GEOMETRY_TEST_DEBUG
16 #ifndef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
17 #define BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
26 #include <boost/test/included/unit_test.hpp>
28 #include <boost/geometry/core/point_type.hpp>
29 #include <boost/geometry/core/tags.hpp>
31 #include <boost/geometry/strategies/distance.hpp>
32 #include <boost/geometry/strategies/strategies.hpp>
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>
38 #include <boost/geometry/algorithms/comparable_distance.hpp>
39 #include <boost/geometry/algorithms/equals.hpp>
41 #include <boost/geometry/io/wkt/wkt.hpp>
42 #include <boost/geometry/io/dsv/write.hpp>
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>
50 namespace bg
= ::boost::geometry
;
51 namespace ba
= ::boost::assign
;
52 namespace services
= bg::strategy::distance::services
;
54 typedef boost::tuple
<double, double> tuple_point_type
;
55 typedef std::vector
<tuple_point_type
> tuple_multi_point_type
;
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
)
61 typedef bg::strategy::distance::projected_point
<> distance_strategy_type
;
62 typedef bg::strategy::distance::projected_point
64 void, bg::strategy::distance::comparable::pythagoras
<>
65 > comparable_distance_strategy_type
;
68 template <typename CoordinateType
>
69 struct default_simplify_strategy
71 typedef bg::model::point
<CoordinateType
, 2, bg::cs::cartesian
> point_type
;
72 typedef typename
bg::strategy::distance::services::default_strategy
74 bg::point_tag
, bg::segment_tag
, point_type
75 >::type default_distance_strategy_type
;
77 typedef bg::strategy::simplify::douglas_peucker
79 point_type
, default_distance_strategy_type
84 template <typename CoordinateType
>
85 struct simplify_regular_distance_strategy
87 typedef bg::model::point
<CoordinateType
, 2, bg::cs::cartesian
> point_type
;
88 typedef bg::strategy::simplify::douglas_peucker
90 point_type
, distance_strategy_type
94 template <typename CoordinateType
>
95 struct simplify_comparable_distance_strategy
97 typedef bg::model::point
<CoordinateType
, 2, bg::cs::cartesian
> point_type
;
98 typedef bg::strategy::simplify::douglas_peucker
100 point_type
, comparable_distance_strategy_type
106 template <typename Geometry
>
107 inline Geometry
from_wkt(std::string
const& wkt
)
110 boost::geometry::read_wkt(wkt
, geometry
);
114 template <typename Iterator
>
115 inline std::ostream
& print_point_range(std::ostream
& os
,
118 std::string
const& header
)
121 for (Iterator it
= first
; it
!= beyond
; ++it
)
123 os
<< " " << bg::dsv(*it
);
132 template <typename Iterator1
, typename Iterator2
>
133 static inline bool apply(Iterator1 begin1
, Iterator1 end1
,
134 Iterator2 begin2
, Iterator2 end2
)
136 std::size_t num_points1
= std::distance(begin1
, end1
);
137 std::size_t num_points2
= std::distance(begin2
, end2
);
139 if ( num_points1
!= num_points2
)
144 Iterator1 it1
= begin1
;
145 Iterator2 it2
= begin2
;
146 for (; it1
!= end1
; ++it1
, ++it2
)
148 if ( !bg::equals(*it1
, *it2
) )
156 template <typename Range1
, typename Range2
>
157 static inline bool apply(Range1
const& range1
, Range2
const& range2
)
159 return apply(boost::begin(range1
), boost::end(range1
),
160 boost::begin(range2
), boost::end(range2
));
167 template <typename Geometry
>
170 template <typename Strategy
, typename Range
>
171 static inline void apply(std::string
const& case_id
,
172 std::string
const& wkt
,
174 Strategy
const& strategy
,
175 Range
const& expected_result
)
177 typedef typename
bg::point_type
<Geometry
>::type point_type
;
178 std::vector
<point_type
> result
;
180 Geometry geometry
= from_wkt
<Geometry
>(wkt
);
182 std::string typeid_name
183 = typeid(typename
bg::coordinate_type
<point_type
>::type
).name();
185 #ifdef BOOST_GEOMETRY_TEST_DEBUG
186 std::cout
<< case_id
<< " - " << typeid_name
188 std::cout
<< wkt
<< std::endl
;
191 strategy
.apply(geometry
, std::back_inserter(result
), max_distance
);
193 boost::ignore_unused(strategy
);
195 #ifdef BOOST_GEOMETRY_TEST_DEBUG
196 print_point_range(std::cout
, boost::begin(result
), boost::end(result
),
198 std::cout
<< std::endl
<< std::endl
;
200 std::stringstream stream_expected
;
201 print_point_range(stream_expected
, boost::begin(expected_result
),
202 boost::end(expected_result
),
204 std::stringstream stream_detected
;
205 print_point_range(stream_detected
, boost::begin(result
),
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());
215 #ifdef BOOST_GEOMETRY_TEST_DEBUG
216 std::cout
<< "---------------" << std::endl
;
217 std::cout
<< "---------------" << std::endl
;
218 std::cout
<< std::endl
<< std::endl
;
224 template <typename CoordinateType
, typename Strategy
>
225 inline void test_with_strategy(std::string label
)
227 std::cout
.precision(20);
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
;
235 label
= " (" + label
+ ")";
238 point_type
const p1(-6,-13), p2(0,-15);
239 segment_type
const s(point_type(12,-3), point_type(-12,5));
241 if (bg::comparable_distance(p1
, s
) >= bg::comparable_distance(p2
, s
))
243 tester::apply("l01c1" + label
,
244 "LINESTRING(12 -3, 4 8,-6 -13,-9 4,0 -15,-12 5)",
247 ba::tuple_list_of(12,-3)(4,8)(-6,-13)(-12,5)
252 tester::apply("l01c2" + label
,
253 "LINESTRING(12 -3, 4 8,-6 -13,-9 4,0 -15,-12 5)",
256 ba::tuple_list_of(12,-3)(4,8)(-6,-13)(-9,4)(0,-15)(-12,5)
261 tester::apply("l02" + label
,
262 "LINESTRING(-6 -13,-9 4,0 -15,-12 5)",
265 ba::tuple_list_of(-6,-13)(-12,5)
268 tester::apply("l03" + label
,
269 "LINESTRING(12 -3, 4 8,-6 -13,-9 4,0 -14,-12 5)",
272 ba::tuple_list_of(12,-3)(4,8)(-6,-13)(-12,5)
275 tester::apply("l04" + label
,
276 "LINESTRING(12 -3, 4 8,-6 -13,-9 4,0 -14,-12 5)",
279 ba::tuple_list_of(12,-3)(-6,-13)(-12,5)
283 segment_type
const s(point_type(0,-1), point_type(5,-4));
284 point_type
const p1(5,-1), p2(0,-4);
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
));
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
));
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"))
306 std::cout
<< "larger comp. distance from "
307 << (cd_larger_first
? "first" : (cd_larger_second
? "second" : "equal"))
309 std::cout
<< "difference of distances: "
310 << (bg::distance(p1
, s
) - bg::distance(p2
, s
))
312 std::cout
<< "difference of comp. distances: "
313 << (bg::comparable_distance(p1
, s
) - bg::comparable_distance(p2
, s
))
318 "LINESTRING(0 0,5 0,0 -1,5 -1,0 -2,5 -2,0 -3,5 -3,0 -4,5 -4,0 0)";
320 if (bg::comparable_distance(p1
, s
) >= bg::comparable_distance(p2
, s
))
322 tester::apply("l05c1" + label
,
326 ba::tuple_list_of(0,0)(5,0)(0,-1)(5,-1)(0,-2)(5,-2)(0,-3)(5,-4)(0,0)
328 tester::apply("l05c1a" + label
,
332 ba::tuple_list_of(0,0)(5,0)(0,-1)(5,-1)(0,-2)(5,-4)(0,0)
337 tester::apply("l05c2" + label
,
341 ba::tuple_list_of(0,0)(5,0)(0,-1)(5,-1)(0,-2)(5,-2)(0,-4)(5,-4)(0,0)
343 tester::apply("l05c2a" + label
,
347 ba::tuple_list_of(0,0)(5,0)(0,-1)(5,-1)(0,-4)(5,-4)(0,0)
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
;
362 BOOST_AUTO_TEST_CASE( test_default_strategy
)
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");
370 default_simplify_strategy
<long double>::type
374 BOOST_AUTO_TEST_CASE( test_with_regular_distance_strategy
)
379 simplify_regular_distance_strategy
<int>::type
385 simplify_regular_distance_strategy
<float>::type
391 simplify_regular_distance_strategy
<double>::type
396 simplify_regular_distance_strategy
<long double>::type
400 BOOST_AUTO_TEST_CASE( test_with_comparable_distance_strategy
)
405 simplify_comparable_distance_strategy
<int>::type
410 simplify_comparable_distance_strategy
<float>::type
415 simplify_comparable_distance_strategy
<double>::type
420 simplify_comparable_distance_strategy
<long double>::type