]>
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 | ||
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 | ||
62 | inline douglas_peucker_point(Point const& ap) | |
63 | : p(ap) | |
64 | , included(false) | |
65 | {} | |
66 | ||
67 | // Necessary for proper compilation | |
68 | 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 | ||
105 | douglas_peucker() | |
106 | {} | |
107 | ||
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 | ||
117 | LessCompare const& less() const | |
118 | { | |
119 | return *this; | |
120 | } | |
121 | ||
122 | 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> | |
197 | 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> | |
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 |