1
// Generic Geometry Library
3
// Copyright Barend Gehrels 1995-2009, Geodan Holding B.V. Amsterdam, the Netherlands.
4
// Copyright Bruno Lalande 2008, 2009
5
// Use, modification and distribution is subject to the Boost Software License,
6
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
7
// http://www.boost.org/LICENSE_1_0.txt)
9
#ifndef GGL_ALGORITHMS_SIMPLIFY_HPP
10
#define GGL_ALGORITHMS_SIMPLIFY_HPP
12
#include <boost/range/functions.hpp>
13
#include <boost/range/metafunctions.hpp>
15
#include <ggl/algorithms/distance.hpp>
16
#include <ggl/core/cs.hpp>
17
#include <ggl/core/ring_type.hpp>
18
#include <ggl/core/exterior_ring.hpp>
19
#include <ggl/core/interior_rings.hpp>
20
#include <ggl/strategies/agnostic/agn_simplify.hpp>
24
\defgroup simplify simplification (generalization)
25
\par Source description:
26
- Wikipedia: given a 'curve' composed of line segments to find a curve not too dissimilar but that has fewer points
28
\see http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm
31
Performance is measured on simplification of a collection of rings, such that 10% of the points is kept.
32
- 2776 counties of US are simplified in 0.8 seconds (2.5 seconds or 11.5 seconds in 2 other libraries)
33
- 3918 zipcode areas of the Netherlands are simplified in 0.03 seconds (0.1 seconds or 0.45 seconds in 2 other libraries)
38
\image html simplify_linestring.png
39
- POLYGON: simplifying a valid simple polygon (which never intersects itself) might result in an invalid polygon,
40
where the simplified rings intersect themselves or one of the other outer or inner rings.
41
Efficient simplification of a ring/polygon is still an "Open Problem"
42
(http://maven.smith.edu/~orourke/TOPP/P24.html#Problem.24)
49
#ifndef DOXYGEN_NO_DETAIL
50
namespace detail { namespace simplify {
52
template<typename R, typename OutputIterator, typename S>
53
inline void simplify_range_strategy(R const& range, OutputIterator out, double max_distance, S const& strategy)
55
if (boost::begin(range) == boost::end(range) || max_distance < 0)
57
std::copy(boost::begin(range), boost::end(range), out);
61
typename boost::range_const_iterator<R>::type it = boost::begin(range) + 1;
62
if (it == boost::end(range) || it + 1 == boost::end(range))
64
std::copy(boost::begin(range), boost::end(range), out);
68
strategy.simplify(range, out, max_distance);
73
template<typename R, typename OutputIterator>
74
inline void simplify_range(R const& range, OutputIterator out, double max_distance)
76
// Define default strategy
77
typedef typename point_type<R>::type point_type;
78
typedef typename cs_tag<point_type>::type cs_tag;
79
typedef typename strategy_distance_segment
84
segment<const point_type>
85
>::type strategy_type;
87
strategy::simplify::douglas_peucker<R, OutputIterator, strategy_type> douglas;
89
simplify_range_strategy(range, out, max_distance, douglas);
92
template<typename R, typename OutputIterator, typename S>
93
inline void simplify_ring(R const& r_in, OutputIterator out, double max_distance, S const& strategy)
95
// Call do_container for a ring
97
// The first/last point (the closing point of the ring) should maybe be excluded because it
98
// lies on a line with second/one but last. Here it is never excluded.
100
// Note also that, especially if max_distance is too large, the output ring might be self intersecting
101
// while the input ring is not, although chances are low in normal polygons
103
// Finally the inputring might have 4 points (=correct), the output < 4(=wrong)
104
if (boost::size(r_in) <= 4 || max_distance < 0)
106
std::copy(boost::begin(r_in), boost::end(r_in), out);
110
simplify_range_strategy(r_in, out, max_distance, strategy);
114
template<typename Y, typename S>
115
inline void simplify_polygon(Y const& poly_in, Y& poly_out, double max_distance, S const& strategy)
117
typedef typename boost::range_iterator
118
<typename interior_type<Y>::type>::type iterator_type;
119
typedef typename boost::range_const_iterator
120
<typename interior_type<Y>::type>::type const_iterator_type;
124
// Note that if there are inner rings, and distance is too large, they might intersect with the
125
// outer ring in the output, while it didn't in the input.
126
simplify_ring(exterior_ring(poly_in), std::back_inserter(exterior_ring(poly_out)),
127
max_distance, strategy);
129
interior_rings(poly_out).resize(boost::size(interior_rings(poly_in)));
131
const_iterator_type it_in = boost::begin(interior_rings(poly_in));
132
iterator_type it_out = boost::begin(interior_rings(poly_out));
134
for (; it_in != boost::end(interior_rings(poly_in)); it_in++, it_out++)
136
simplify_ring(*it_in, std::back_inserter(*it_out), max_distance, strategy);
141
inline void simplify_polygon(Y const& poly_in, Y& poly_out, double max_distance)
143
// Define default strategy
144
typedef typename ring_type<Y>::type ring_type;
145
typedef std::back_insert_iterator<ring_type> iterator_type;
147
typedef typename point_type<Y>::type point_type;
148
typedef typename cs_tag<point_type>::type cs_tag;
149
typedef typename strategy_distance_segment
154
segment<const point_type>
155
>::type strategy_type;
157
strategy::simplify::douglas_peucker<ring_type, iterator_type, strategy_type> douglas;
159
simplify_polygon(poly_in, poly_out, max_distance, douglas);
162
}} // namespace detail::simplify
163
#endif // DOXYGEN_NO_DETAIL
166
#ifndef DOXYGEN_NO_DISPATCH
170
template <typename Tag, typename G>
175
// Partial specializations
176
template <typename R>
177
struct simplify<linestring_tag, R>
179
template<typename OutputIterator, typename S>
180
static inline void apply(R const& range, OutputIterator out, double max_distance, S const& strategy)
182
strategy.simplify(range, out, max_distance);
185
template<typename OutputIterator>
186
static inline void apply(R const& range, OutputIterator out, double max_distance)
188
// Define default strategy
189
typedef typename point_type<R>::type point_type;
190
typedef typename cs_tag<point_type>::type cs_tag;
191
typedef typename strategy_distance_segment
196
segment<const point_type>
197
>::type strategy_type;
199
strategy::simplify::douglas_peucker<R, OutputIterator, strategy_type> douglas;
201
detail::simplify::simplify_range_strategy(range, out, max_distance, douglas);
205
template <typename R>
206
struct simplify<ring_tag, R>
208
/// Simplify a ring, using a strategy
210
static inline void apply(R const& ring_in, R& ring_out, double max_distance, S const& strategy)
212
using detail::simplify::simplify_ring;
213
simplify_ring(ring_in, std::back_inserter(ring_out), max_distance, strategy);
217
static inline void apply(R const& ring_in, R& ring_out, double max_distance)
219
// Define default strategy
220
typedef typename point_type<R>::type point_type;
221
typedef typename cs_tag<point_type>::type cs_tag;
222
typedef typename strategy_distance_segment
227
segment<const point_type>
228
>::type strategy_type;
229
typedef std::back_insert_iterator<R> iterator_type;
231
strategy::simplify::douglas_peucker<R, iterator_type, strategy_type> douglas;
233
detail::simplify::simplify_ring(ring_in, std::back_inserter(ring_out), max_distance, douglas);
237
template <typename P>
238
struct simplify<polygon_tag, P>
240
/// Simplify a polygon, using a strategy
242
static inline void apply(P const& poly_in, P& poly_out, double max_distance, S const& strategy)
244
detail::simplify::simplify_polygon(poly_in, poly_out, max_distance, strategy);
247
/// Simplify a polygon
248
static inline void apply(P const& poly_in, P& poly_out, double max_distance)
250
detail::simplify::simplify_polygon(poly_in, poly_out, max_distance);
254
} // namespace dispatch
255
#endif // DOXYGEN_NO_DISPATCH
258
// Model 1, using output iterator
261
\brief Simplify a geometry
263
\details The simplify algorithm removes points, keeping the shape as much as possible.
264
This version of simplify uses an output iterator
265
\param geometry the geometry to be simplified, being a ggl::linestring, vector, iterator pair, or any other boost compatible range
266
\param out output iterator, outputs all simplified points
267
\param max_distance distance (in units of input coordinates) of a vertex to other segments to be removed
269
The simplify algorithm can be used as following:
270
\dontinclude doxygen_examples.cpp
271
\skip example_simplify_linestring1
275
template<typename G, typename O>
276
inline void simplify(const G& geometry, O out, double max_distance)
278
typedef dispatch::simplify<typename tag<G>::type, G> simplify_type;
279
simplify_type::apply(geometry, out, max_distance);
283
\brief Simplify a geometry
285
\details The simplify algorithm removes points, keeping the shape as much as possible.
286
This version of simplify uses an output iterator and a simplify strategy
287
\param geometry the geometry to be simplified, being a ggl::linestring, vector, iterator pair, or any other boost compatible range
288
\param out output iterator, outputs all simplified points
289
\param max_distance distance (in units of input coordinates) of a vertex to other segments to be removed
290
\param strategy simplify strategy to be used for simplification, might include point-distance strategy
292
The simplify algorithm with strategy can be used as following:
293
\dontinclude doxygen_examples.cpp
294
\skip example_simplify_linestring2
298
template<typename G, typename O, typename S>
299
inline void simplify(const G& geometry, O out, double max_distance, S const& strategy)
301
typedef dispatch::simplify<typename tag<G>::type, G> simplify_type;
302
simplify_type::apply(geometry, out, max_distance, strategy);
305
// Model 2, where output is same type as input
308
\brief Simplify a geometry
310
\details This version of simplify simplifies a geometry using the default strategy (Douglas Peucker),
311
where the output is of the same geometry type as the input.
312
\param geometry input geometry, to be simplified
313
\param out output geometry, simplified version of the input geometry
314
\param max_distance distance (in units of input coordinates) of a vertex to other segments to be removed
317
inline void simplify(const G& geometry, G& out, double max_distance)
319
typedef dispatch::simplify<typename tag<G>::type, G> simplify_type;
320
simplify_type::apply(geometry, out, max_distance);
324
\brief Simplify a geometry
326
\details This version of simplify simplifies a geometry using a specified strategy
327
where the output is of the same geometry type as the input.
328
\param geometry input geometry, to be simplified
329
\param out output geometry, simplified version of the input geometry
330
\param max_distance distance (in units of input coordinates) of a vertex to other segments to be removed
331
\param strategy simplify strategy to be used for simplification, might include point-distance strategy
333
template<typename G, typename S>
334
inline void simplify(const G& geometry, G& out, double max_distance, S const& strategy)
336
typedef dispatch::simplify<typename tag<G>::type, G> simplify_type;
337
simplify_type::apply(geometry, out, max_distance, strategy);
342
#endif // GGL_ALGORITHMS_SIMPLIFY_HPP
added
removed
include/ggl/algorithms/simplify.hpp
