1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 1995, 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 1995 Maarten Hilferink, Amsterdam, the Netherlands
5 
6 // This file was modified by Oracle on 2015.
7 // Modifications copyright (c) 2015, Oracle and/or its affiliates.
8 
9 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
10 
11 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
12 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
13 
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)
17 
18 #ifndef BOOST_GEOMETRY_STRATEGY_AGNOSTIC_SIMPLIFY_DOUGLAS_PEUCKER_HPP
19 #define BOOST_GEOMETRY_STRATEGY_AGNOSTIC_SIMPLIFY_DOUGLAS_PEUCKER_HPP
20 
21 
22 #include <cstddef>
23 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
24 #include <iostream>
25 #endif
26 #include <vector>
27 
28 #include <boost/range.hpp>
29 
30 #include <boost/geometry/core/cs.hpp>
31 #include <boost/geometry/strategies/distance.hpp>
32 
33 
34 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
35 #include <boost/geometry/io/dsv/write.hpp>
36 #endif
37 
38 
39 namespace boost { namespace geometry
40 {
41 
42 namespace strategy { namespace simplify
43 {
44 
45 
46 #ifndef DOXYGEN_NO_DETAIL
47 namespace detail
48 {
49 
50     /*!
51         \brief Small wrapper around a point, with an extra member "included"
52         \details
53             It has a const-reference to the original point (so no copy here)
54         \tparam the enclosed point type
55     */
56     template<typename Point>
57     struct douglas_peucker_point
58     {
59         Point const& p;
60         bool included;
61 
douglas_peucker_pointboost::geometry::strategy::simplify::detail::douglas_peucker_point62         inline douglas_peucker_point(Point const& ap)
63             : p(ap)
64             , included(false)
65         {}
66 
67         // Necessary for proper compilation
operator =boost::geometry::strategy::simplify::detail::douglas_peucker_point68         inline douglas_peucker_point<Point> operator=(douglas_peucker_point<Point> const& )
69         {
70             return douglas_peucker_point<Point>(*this);
71         }
72     };
73 
74     template
75     <
76         typename Point,
77         typename PointDistanceStrategy,
78         typename LessCompare
79             = std::less
80                 <
81                     typename strategy::distance::services::return_type
82                         <
83                             PointDistanceStrategy,
84                             Point, Point
85                         >::type
86                 >
87     >
88     class douglas_peucker
89         : LessCompare // for empty base optimization
90     {
91     public :
92 
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;
98 
99         typedef typename strategy::distance::services::return_type
100                          <
101                              distance_strategy_type,
102                              Point, Point
103                          >::type distance_type;
104 
douglas_peucker()105         douglas_peucker()
106         {}
107 
douglas_peucker(LessCompare const & less_compare)108         douglas_peucker(LessCompare const& less_compare)
109             : LessCompare(less_compare)
110         {}
111 
112     private :
113         typedef detail::douglas_peucker_point<Point> dp_point_type;
114         typedef typename std::vector<dp_point_type>::iterator iterator_type;
115 
116 
less() const117         LessCompare const& less() const
118         {
119             return *this;
120         }
121 
consider(iterator_type begin,iterator_type end,distance_type const & max_dist,int & n,distance_strategy_type const & ps_distance_strategy) const122         inline void consider(iterator_type begin,
123                              iterator_type end,
124                              distance_type const& max_dist,
125                              int& n,
126                              distance_strategy_type const& ps_distance_strategy) const
127         {
128             std::size_t size = end - begin;
129 
130             // size must be at least 3
131             // because we want to consider a candidate point in between
132             if (size <= 2)
133             {
134 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
135                 if (begin != end)
136                 {
137                     std::cout << "ignore between " << dsv(begin->p)
138                         << " and " << dsv((end - 1)->p)
139                         << " size=" << size << std::endl;
140                 }
141                 std::cout << "return because size=" << size << std::endl;
142 #endif
143                 return;
144             }
145 
146             iterator_type last = end - 1;
147 
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;
152 #endif
153 
154 
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)
160             {
161                 distance_type dist = ps_distance_strategy.apply(it->p, begin->p, last->p);
162 
163 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
164                 std::cout << "consider " << dsv(it->p)
165                     << " at " << double(dist)
166                     << ((dist > max_dist) ? " maybe" : " no")
167                     << std::endl;
168 
169 #endif
170                 if ( less()(md, dist) )
171                 {
172                     md = dist;
173                     candidate = it;
174                 }
175             }
176 
177             // If a point is found, set the include flag
178             // and handle segments in between recursively
179             if ( less()(max_dist, md) )
180             {
181 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
182                 std::cout << "use " << dsv(candidate->p) << std::endl;
183 #endif
184 
185                 candidate->included = true;
186                 n++;
187 
188                 consider(begin, candidate + 1, max_dist, n, ps_distance_strategy);
189                 consider(candidate, end, max_dist, n, ps_distance_strategy);
190             }
191         }
192 
193 
194     public :
195 
196         template <typename Range, typename OutputIterator>
apply(Range const & range,OutputIterator out,distance_type max_distance) const197         inline OutputIterator apply(Range const& range,
198                                     OutputIterator out,
199                                     distance_type max_distance) const
200         {
201 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
202                 std::cout << "max distance: " << max_distance
203                           << std::endl << std::endl;
204 #endif
205             distance_strategy_type strategy;
206 
207             // Copy coordinates, a vector of references to all points
208             std::vector<dp_point_type> ref_candidates(boost::begin(range),
209                             boost::end(range));
210 
211             // Include first and last point of line,
212             // they are always part of the line
213             int n = 2;
214             ref_candidates.front().included = true;
215             ref_candidates.back().included = true;
216 
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);
220 
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);
225                 ++it)
226             {
227                 if (it->included)
228                 {
229                     // copy-coordinates does not work because OutputIterator
230                     // does not model Point (??)
231                     //geometry::convert(it->p, *out);
232                     *out = it->p;
233                     out++;
234                 }
235             }
236             return out;
237         }
238 
239     };
240 }
241 #endif // DOXYGEN_NO_DETAIL
242 
243 
244 /*!
245 \brief Implements the simplify algorithm.
246 \ingroup strategies
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
252     can be specified
253 \author Barend and Maarten, 1995/1996
254 \author Barend, revised for Generic Geometry Library, 2008
255 */
256 
257 /*
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
261 */
262 template
263 <
264     typename Point,
265     typename PointDistanceStrategy
266 >
267 class douglas_peucker
268 {
269 public :
270 
271     typedef PointDistanceStrategy distance_strategy_type;
272 
273     typedef typename detail::douglas_peucker
274         <
275             Point,
276             PointDistanceStrategy
277         >::distance_type distance_type;
278 
279     template <typename Range, typename OutputIterator>
apply(Range const & range,OutputIterator out,distance_type const & max_distance)280     static inline OutputIterator apply(Range const& range,
281                                        OutputIterator out,
282                                        distance_type const& max_distance)
283     {
284         namespace services = strategy::distance::services;
285 
286         typedef typename services::comparable_type
287             <
288                 PointDistanceStrategy
289             >::type comparable_distance_strategy_type;
290 
291         return detail::douglas_peucker
292             <
293                 Point, comparable_distance_strategy_type
294             >().apply(range, out,
295                       services::result_from_distance
296                           <
297                               comparable_distance_strategy_type, Point, Point
298                           >::apply(comparable_distance_strategy_type(),
299                                    max_distance)
300                       );
301     }
302 
303 };
304 
305 }} // namespace strategy::simplify
306 
307 
308 namespace traits {
309 
310 template <typename P>
311 struct point_type<geometry::strategy::simplify::detail::douglas_peucker_point<P> >
312 {
313     typedef P type;
314 };
315 
316 } // namespace traits
317 
318 
319 }} // namespace boost::geometry
320 
321 #endif // BOOST_GEOMETRY_STRATEGY_AGNOSTIC_SIMPLIFY_DOUGLAS_PEUCKER_HPP
322