1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 1995, 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 1995 Maarten Hilferink, Amsterdam, the Netherlands
6 // This file was modified by Oracle on 2015.
7 // Modifications copyright (c) 2015, Oracle and/or its affiliates.
9 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
11 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
12 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
14 // Use, modification and distribution is subject to the Boost Software License,
15 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
16 // http://www.boost.org/LICENSE_1_0.txt)
18 #ifndef BOOST_GEOMETRY_STRATEGY_AGNOSTIC_SIMPLIFY_DOUGLAS_PEUCKER_HPP
19 #define BOOST_GEOMETRY_STRATEGY_AGNOSTIC_SIMPLIFY_DOUGLAS_PEUCKER_HPP
23 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
28 #include <boost/range.hpp>
30 #include <boost/geometry/core/cs.hpp>
31 #include <boost/geometry/strategies/distance.hpp>
34 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
35 #include <boost/geometry/io/dsv/write.hpp>
39 namespace boost { namespace geometry
42 namespace strategy { namespace simplify
46 #ifndef DOXYGEN_NO_DETAIL
51 \brief Small wrapper around a point, with an extra member "included"
53 It has a const-reference to the original point (so no copy here)
54 \tparam the enclosed point type
56 template<typename Point>
57 struct douglas_peucker_point
62 inline douglas_peucker_point(Point const& ap)
67 // Necessary for proper compilation
68 inline douglas_peucker_point<Point> operator=(douglas_peucker_point<Point> const& )
70 return douglas_peucker_point<Point>(*this);
77 typename PointDistanceStrategy,
81 typename strategy::distance::services::return_type
83 PointDistanceStrategy,
89 : LessCompare // for empty base optimization
93 // See also ticket 5954 https://svn.boost.org/trac/boost/ticket/5954
94 // Comparable is currently not possible here because it has to be compared to the squared of max_distance, and more.
95 // For now we have to take the real distance.
96 typedef PointDistanceStrategy distance_strategy_type;
97 // typedef typename strategy::distance::services::comparable_type<PointDistanceStrategy>::type distance_strategy_type;
99 typedef typename strategy::distance::services::return_type
101 distance_strategy_type,
103 >::type distance_type;
108 douglas_peucker(LessCompare const& less_compare)
109 : LessCompare(less_compare)
113 typedef detail::douglas_peucker_point<Point> dp_point_type;
114 typedef typename std::vector<dp_point_type>::iterator iterator_type;
117 LessCompare const& less() const
122 inline void consider(iterator_type begin,
124 distance_type const& max_dist,
126 distance_strategy_type const& ps_distance_strategy) const
128 std::size_t size = end - begin;
130 // size must be at least 3
131 // because we want to consider a candidate point in between
134 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
137 std::cout << "ignore between " << dsv(begin->p)
138 << " and " << dsv((end - 1)->p)
139 << " size=" << size << std::endl;
141 std::cout << "return because size=" << size << std::endl;
146 iterator_type last = end - 1;
148 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
149 std::cout << "find between " << dsv(begin->p)
150 << " and " << dsv(last->p)
151 << " size=" << size << std::endl;
155 // Find most far point, compare to the current segment
156 //geometry::segment<Point const> s(begin->p, last->p);
157 distance_type md(-1.0); // any value < 0
158 iterator_type candidate;
159 for(iterator_type it = begin + 1; it != last; ++it)
161 distance_type dist = ps_distance_strategy.apply(it->p, begin->p, last->p);
163 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
164 std::cout << "consider " << dsv(it->p)
165 << " at " << double(dist)
166 << ((dist > max_dist) ? " maybe" : " no")
170 if ( less()(md, dist) )
177 // If a point is found, set the include flag
178 // and handle segments in between recursively
179 if ( less()(max_dist, md) )
181 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
182 std::cout << "use " << dsv(candidate->p) << std::endl;
185 candidate->included = true;
188 consider(begin, candidate + 1, max_dist, n, ps_distance_strategy);
189 consider(candidate, end, max_dist, n, ps_distance_strategy);
196 template <typename Range, typename OutputIterator>
197 inline OutputIterator apply(Range const& range,
199 distance_type max_distance) const
201 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
202 std::cout << "max distance: " << max_distance
203 << std::endl << std::endl;
205 distance_strategy_type strategy;
207 // Copy coordinates, a vector of references to all points
208 std::vector<dp_point_type> ref_candidates(boost::begin(range),
211 // Include first and last point of line,
212 // they are always part of the line
214 ref_candidates.front().included = true;
215 ref_candidates.back().included = true;
217 // Get points, recursively, including them if they are further away
218 // than the specified distance
219 consider(boost::begin(ref_candidates), boost::end(ref_candidates), max_distance, n, strategy);
221 // Copy included elements to the output
222 for(typename std::vector<dp_point_type>::const_iterator it
223 = boost::begin(ref_candidates);
224 it != boost::end(ref_candidates);
229 // copy-coordinates does not work because OutputIterator
230 // does not model Point (??)
231 //geometry::convert(it->p, *out);
241 #endif // DOXYGEN_NO_DETAIL
245 \brief Implements the simplify algorithm.
247 \details The douglas_peucker strategy simplifies a linestring, ring or
248 vector of points using the well-known Douglas-Peucker algorithm.
249 \tparam Point the point type
250 \tparam PointDistanceStrategy point-segment distance strategy to be used
251 \note This strategy uses itself a point-segment-distance strategy which
253 \author Barend and Maarten, 1995/1996
254 \author Barend, revised for Generic Geometry Library, 2008
258 For the algorithm, see for example:
259 - http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm
260 - http://www2.dcs.hull.ac.uk/CISRG/projects/Royal-Inst/demos/dp.html
265 typename PointDistanceStrategy
267 class douglas_peucker
271 typedef PointDistanceStrategy distance_strategy_type;
273 typedef typename detail::douglas_peucker
276 PointDistanceStrategy
277 >::distance_type distance_type;
279 template <typename Range, typename OutputIterator>
280 static inline OutputIterator apply(Range const& range,
282 distance_type const& max_distance)
284 namespace services = strategy::distance::services;
286 typedef typename services::comparable_type
288 PointDistanceStrategy
289 >::type comparable_distance_strategy_type;
291 return detail::douglas_peucker
293 Point, comparable_distance_strategy_type
294 >().apply(range, out,
295 services::result_from_distance
297 comparable_distance_strategy_type, Point, Point
298 >::apply(comparable_distance_strategy_type(),
305 }} // namespace strategy::simplify
310 template <typename P>
311 struct point_type<geometry::strategy::simplify::detail::douglas_peucker_point<P> >
316 } // namespace traits
319 }} // namespace boost::geometry
321 #endif // BOOST_GEOMETRY_STRATEGY_AGNOSTIC_SIMPLIFY_DOUGLAS_PEUCKER_HPP