]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
20effc67 TL |
6 | // This file was modified by Oracle on 2015-2020. |
7 | // Modifications copyright (c) 2015-2020, Oracle and/or its affiliates. | |
7c673cae | 8 | // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle |
20effc67 | 9 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle |
7c673cae FG |
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 | ||
20effc67 TL |
28 | #include <boost/range/begin.hpp> |
29 | #include <boost/range/end.hpp> | |
7c673cae FG |
30 | |
31 | #include <boost/geometry/core/cs.hpp> | |
32 | #include <boost/geometry/strategies/distance.hpp> | |
33 | ||
34 | ||
35 | #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER | |
36 | #include <boost/geometry/io/dsv/write.hpp> | |
37 | #endif | |
38 | ||
39 | ||
40 | namespace boost { namespace geometry | |
41 | { | |
42 | ||
43 | namespace strategy { namespace simplify | |
44 | { | |
45 | ||
46 | ||
47 | #ifndef DOXYGEN_NO_DETAIL | |
48 | namespace detail | |
49 | { | |
50 | ||
51 | /*! | |
52 | \brief Small wrapper around a point, with an extra member "included" | |
53 | \details | |
54 | It has a const-reference to the original point (so no copy here) | |
55 | \tparam the enclosed point type | |
56 | */ | |
57 | template<typename Point> | |
58 | struct douglas_peucker_point | |
59 | { | |
60 | Point const& p; | |
61 | bool included; | |
62 | ||
63 | inline douglas_peucker_point(Point const& ap) | |
64 | : p(ap) | |
65 | , included(false) | |
66 | {} | |
67 | ||
68 | // Necessary for proper compilation | |
69 | inline douglas_peucker_point<Point> operator=(douglas_peucker_point<Point> const& ) | |
70 | { | |
71 | return douglas_peucker_point<Point>(*this); | |
72 | } | |
73 | }; | |
74 | ||
75 | template | |
76 | < | |
77 | typename Point, | |
78 | typename PointDistanceStrategy, | |
79 | typename LessCompare | |
80 | = std::less | |
81 | < | |
82 | typename strategy::distance::services::return_type | |
83 | < | |
84 | PointDistanceStrategy, | |
85 | Point, Point | |
86 | >::type | |
87 | > | |
88 | > | |
89 | class douglas_peucker | |
90 | : LessCompare // for empty base optimization | |
91 | { | |
92 | public : | |
93 | ||
94 | // See also ticket 5954 https://svn.boost.org/trac/boost/ticket/5954 | |
95 | // Comparable is currently not possible here because it has to be compared to the squared of max_distance, and more. | |
96 | // For now we have to take the real distance. | |
97 | typedef PointDistanceStrategy distance_strategy_type; | |
98 | // typedef typename strategy::distance::services::comparable_type<PointDistanceStrategy>::type distance_strategy_type; | |
99 | ||
100 | typedef typename strategy::distance::services::return_type | |
101 | < | |
102 | distance_strategy_type, | |
103 | Point, Point | |
104 | >::type distance_type; | |
105 | ||
106 | douglas_peucker() | |
107 | {} | |
108 | ||
109 | douglas_peucker(LessCompare const& less_compare) | |
110 | : LessCompare(less_compare) | |
111 | {} | |
112 | ||
113 | private : | |
114 | typedef detail::douglas_peucker_point<Point> dp_point_type; | |
115 | typedef typename std::vector<dp_point_type>::iterator iterator_type; | |
116 | ||
117 | ||
118 | LessCompare const& less() const | |
119 | { | |
120 | return *this; | |
121 | } | |
122 | ||
123 | inline void consider(iterator_type begin, | |
124 | iterator_type end, | |
125 | distance_type const& max_dist, | |
126 | int& n, | |
127 | distance_strategy_type const& ps_distance_strategy) const | |
128 | { | |
129 | std::size_t size = end - begin; | |
130 | ||
131 | // size must be at least 3 | |
132 | // because we want to consider a candidate point in between | |
133 | if (size <= 2) | |
134 | { | |
135 | #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER | |
136 | if (begin != end) | |
137 | { | |
138 | std::cout << "ignore between " << dsv(begin->p) | |
139 | << " and " << dsv((end - 1)->p) | |
140 | << " size=" << size << std::endl; | |
141 | } | |
142 | std::cout << "return because size=" << size << std::endl; | |
143 | #endif | |
144 | return; | |
145 | } | |
146 | ||
147 | iterator_type last = end - 1; | |
148 | ||
149 | #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER | |
150 | std::cout << "find between " << dsv(begin->p) | |
151 | << " and " << dsv(last->p) | |
152 | << " size=" << size << std::endl; | |
153 | #endif | |
154 | ||
155 | ||
156 | // Find most far point, compare to the current segment | |
157 | //geometry::segment<Point const> s(begin->p, last->p); | |
158 | distance_type md(-1.0); // any value < 0 | |
159 | iterator_type candidate; | |
160 | for(iterator_type it = begin + 1; it != last; ++it) | |
161 | { | |
162 | distance_type dist = ps_distance_strategy.apply(it->p, begin->p, last->p); | |
163 | ||
164 | #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER | |
165 | std::cout << "consider " << dsv(it->p) | |
166 | << " at " << double(dist) | |
167 | << ((dist > max_dist) ? " maybe" : " no") | |
168 | << std::endl; | |
169 | ||
170 | #endif | |
171 | if ( less()(md, dist) ) | |
172 | { | |
173 | md = dist; | |
174 | candidate = it; | |
175 | } | |
176 | } | |
177 | ||
178 | // If a point is found, set the include flag | |
179 | // and handle segments in between recursively | |
180 | if ( less()(max_dist, md) ) | |
181 | { | |
182 | #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER | |
183 | std::cout << "use " << dsv(candidate->p) << std::endl; | |
184 | #endif | |
185 | ||
186 | candidate->included = true; | |
187 | n++; | |
188 | ||
189 | consider(begin, candidate + 1, max_dist, n, ps_distance_strategy); | |
190 | consider(candidate, end, max_dist, n, ps_distance_strategy); | |
191 | } | |
192 | } | |
193 | ||
194 | ||
195 | public : | |
196 | ||
197 | template <typename Range, typename OutputIterator> | |
198 | inline OutputIterator apply(Range const& range, | |
199 | OutputIterator out, | |
200 | distance_type max_distance) const | |
201 | { | |
202 | #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER | |
203 | std::cout << "max distance: " << max_distance | |
204 | << std::endl << std::endl; | |
205 | #endif | |
206 | distance_strategy_type strategy; | |
207 | ||
208 | // Copy coordinates, a vector of references to all points | |
209 | std::vector<dp_point_type> ref_candidates(boost::begin(range), | |
210 | boost::end(range)); | |
211 | ||
212 | // Include first and last point of line, | |
213 | // they are always part of the line | |
214 | int n = 2; | |
215 | ref_candidates.front().included = true; | |
216 | ref_candidates.back().included = true; | |
217 | ||
218 | // Get points, recursively, including them if they are further away | |
219 | // than the specified distance | |
220 | consider(boost::begin(ref_candidates), boost::end(ref_candidates), max_distance, n, strategy); | |
221 | ||
222 | // Copy included elements to the output | |
223 | for(typename std::vector<dp_point_type>::const_iterator it | |
224 | = boost::begin(ref_candidates); | |
225 | it != boost::end(ref_candidates); | |
226 | ++it) | |
227 | { | |
228 | if (it->included) | |
229 | { | |
230 | // copy-coordinates does not work because OutputIterator | |
231 | // does not model Point (??) | |
232 | //geometry::convert(it->p, *out); | |
233 | *out = it->p; | |
234 | out++; | |
235 | } | |
236 | } | |
237 | return out; | |
238 | } | |
239 | ||
240 | }; | |
241 | } | |
242 | #endif // DOXYGEN_NO_DETAIL | |
243 | ||
244 | ||
245 | /*! | |
246 | \brief Implements the simplify algorithm. | |
247 | \ingroup strategies | |
248 | \details The douglas_peucker strategy simplifies a linestring, ring or | |
249 | vector of points using the well-known Douglas-Peucker algorithm. | |
250 | \tparam Point the point type | |
251 | \tparam PointDistanceStrategy point-segment distance strategy to be used | |
252 | \note This strategy uses itself a point-segment-distance strategy which | |
253 | can be specified | |
254 | \author Barend and Maarten, 1995/1996 | |
255 | \author Barend, revised for Generic Geometry Library, 2008 | |
256 | */ | |
257 | ||
258 | /* | |
259 | For the algorithm, see for example: | |
260 | - http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm | |
261 | - http://www2.dcs.hull.ac.uk/CISRG/projects/Royal-Inst/demos/dp.html | |
262 | */ | |
263 | template | |
264 | < | |
265 | typename Point, | |
266 | typename PointDistanceStrategy | |
267 | > | |
268 | class douglas_peucker | |
269 | { | |
270 | public : | |
271 | ||
272 | typedef PointDistanceStrategy distance_strategy_type; | |
273 | ||
274 | typedef typename detail::douglas_peucker | |
275 | < | |
276 | Point, | |
277 | PointDistanceStrategy | |
278 | >::distance_type distance_type; | |
279 | ||
280 | template <typename Range, typename OutputIterator> | |
281 | static inline OutputIterator apply(Range const& range, | |
282 | OutputIterator out, | |
283 | distance_type const& max_distance) | |
284 | { | |
285 | namespace services = strategy::distance::services; | |
286 | ||
287 | typedef typename services::comparable_type | |
288 | < | |
289 | PointDistanceStrategy | |
290 | >::type comparable_distance_strategy_type; | |
291 | ||
292 | return detail::douglas_peucker | |
293 | < | |
294 | Point, comparable_distance_strategy_type | |
295 | >().apply(range, out, | |
296 | services::result_from_distance | |
297 | < | |
298 | comparable_distance_strategy_type, Point, Point | |
299 | >::apply(comparable_distance_strategy_type(), | |
300 | max_distance) | |
301 | ); | |
302 | } | |
303 | ||
304 | }; | |
305 | ||
306 | }} // namespace strategy::simplify | |
307 | ||
308 | ||
309 | namespace traits { | |
310 | ||
311 | template <typename P> | |
312 | struct point_type<geometry::strategy::simplify::detail::douglas_peucker_point<P> > | |
313 | { | |
314 | typedef P type; | |
315 | }; | |
316 | ||
317 | } // namespace traits | |
318 | ||
319 | ||
320 | }} // namespace boost::geometry | |
321 | ||
322 | #endif // BOOST_GEOMETRY_STRATEGY_AGNOSTIC_SIMPLIFY_DOUGLAS_PEUCKER_HPP |