]>
Commit | Line | Data |
---|---|---|
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) | |
2 | ||
3 | // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | // Copyright (c) 2008-2015 Bruno Lalande, Paris, France. | |
5 | // Copyright (c) 2009-2015 Mateusz Loskot, London, UK. | |
6 | ||
7 | // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library | |
8 | // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. | |
9 | ||
10 | // Use, modification and distribution is subject to the Boost Software License, | |
11 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
12 | // http://www.boost.org/LICENSE_1_0.txt) | |
13 | ||
14 | #ifndef BOOST_GEOMETRY_ALGORITHMS_SIMPLIFY_HPP | |
15 | #define BOOST_GEOMETRY_ALGORITHMS_SIMPLIFY_HPP | |
16 | ||
17 | #include <cstddef> | |
18 | ||
19 | #include <boost/core/ignore_unused.hpp> | |
20 | #include <boost/range.hpp> | |
21 | ||
22 | #include <boost/variant/apply_visitor.hpp> | |
23 | #include <boost/variant/static_visitor.hpp> | |
24 | #include <boost/variant/variant_fwd.hpp> | |
25 | ||
26 | #include <boost/geometry/core/cs.hpp> | |
27 | #include <boost/geometry/core/closure.hpp> | |
28 | #include <boost/geometry/core/exterior_ring.hpp> | |
29 | #include <boost/geometry/core/interior_rings.hpp> | |
30 | #include <boost/geometry/core/mutable_range.hpp> | |
31 | #include <boost/geometry/core/tags.hpp> | |
32 | ||
33 | #include <boost/geometry/geometries/concepts/check.hpp> | |
34 | #include <boost/geometry/strategies/agnostic/simplify_douglas_peucker.hpp> | |
35 | #include <boost/geometry/strategies/concepts/simplify_concept.hpp> | |
36 | #include <boost/geometry/strategies/default_strategy.hpp> | |
37 | #include <boost/geometry/strategies/distance.hpp> | |
38 | ||
39 | #include <boost/geometry/algorithms/clear.hpp> | |
40 | #include <boost/geometry/algorithms/convert.hpp> | |
41 | #include <boost/geometry/algorithms/not_implemented.hpp> | |
42 | ||
43 | #include <boost/geometry/algorithms/detail/distance/default_strategies.hpp> | |
44 | ||
45 | namespace boost { namespace geometry | |
46 | { | |
47 | ||
48 | #ifndef DOXYGEN_NO_DETAIL | |
49 | namespace detail { namespace simplify | |
50 | { | |
51 | ||
52 | struct simplify_range_insert | |
53 | { | |
54 | template<typename Range, typename Strategy, typename OutputIterator, typename Distance> | |
55 | static inline void apply(Range const& range, OutputIterator out, | |
56 | Distance const& max_distance, Strategy const& strategy) | |
57 | { | |
58 | boost::ignore_unused(strategy); | |
59 | ||
60 | if (boost::size(range) <= 2 || max_distance < 0) | |
61 | { | |
62 | std::copy(boost::begin(range), boost::end(range), out); | |
63 | } | |
64 | else | |
65 | { | |
66 | strategy.apply(range, out, max_distance); | |
67 | } | |
68 | } | |
69 | }; | |
70 | ||
71 | ||
72 | struct simplify_copy | |
73 | { | |
74 | template <typename Range, typename Strategy, typename Distance> | |
75 | static inline void apply(Range const& range, Range& out, | |
76 | Distance const& , Strategy const& ) | |
77 | { | |
78 | std::copy | |
79 | ( | |
80 | boost::begin(range), boost::end(range), geometry::range::back_inserter(out) | |
81 | ); | |
82 | } | |
83 | }; | |
84 | ||
85 | ||
86 | template<std::size_t Minimum> | |
87 | struct simplify_range | |
88 | { | |
89 | template <typename Range, typename Strategy, typename Distance> | |
90 | static inline void apply(Range const& range, Range& out, | |
91 | Distance const& max_distance, Strategy const& strategy) | |
92 | { | |
93 | // Call do_container for a linestring / ring | |
94 | ||
95 | /* For a RING: | |
96 | The first/last point (the closing point of the ring) should maybe | |
97 | be excluded because it lies on a line with second/one but last. | |
98 | Here it is never excluded. | |
99 | ||
100 | Note also that, especially if max_distance is too large, | |
101 | the output ring might be self intersecting while the input ring is | |
102 | not, although chances are low in normal polygons | |
103 | ||
104 | Finally the inputring might have 3 (open) or 4 (closed) points (=correct), | |
105 | the output < 3 or 4(=wrong) | |
106 | */ | |
107 | ||
108 | if (boost::size(range) <= int(Minimum) || max_distance < 0.0) | |
109 | { | |
110 | simplify_copy::apply(range, out, max_distance, strategy); | |
111 | } | |
112 | else | |
113 | { | |
114 | simplify_range_insert::apply | |
115 | ( | |
116 | range, geometry::range::back_inserter(out), max_distance, strategy | |
117 | ); | |
118 | } | |
119 | } | |
120 | }; | |
121 | ||
122 | struct simplify_polygon | |
123 | { | |
124 | private: | |
125 | ||
126 | template | |
127 | < | |
128 | std::size_t Minimum, | |
129 | typename IteratorIn, | |
130 | typename IteratorOut, | |
131 | typename Distance, | |
132 | typename Strategy | |
133 | > | |
134 | static inline void iterate(IteratorIn begin, IteratorIn end, | |
135 | IteratorOut it_out, | |
136 | Distance const& max_distance, Strategy const& strategy) | |
137 | { | |
138 | for (IteratorIn it_in = begin; it_in != end; ++it_in, ++it_out) | |
139 | { | |
140 | simplify_range<Minimum>::apply(*it_in, *it_out, max_distance, strategy); | |
141 | } | |
142 | } | |
143 | ||
144 | template | |
145 | < | |
146 | std::size_t Minimum, | |
147 | typename InteriorRingsIn, | |
148 | typename InteriorRingsOut, | |
149 | typename Distance, | |
150 | typename Strategy | |
151 | > | |
152 | static inline void apply_interior_rings( | |
153 | InteriorRingsIn const& interior_rings_in, | |
154 | InteriorRingsOut& interior_rings_out, | |
155 | Distance const& max_distance, Strategy const& strategy) | |
156 | { | |
157 | traits::resize<InteriorRingsOut>::apply(interior_rings_out, | |
158 | boost::size(interior_rings_in)); | |
159 | ||
160 | iterate<Minimum>( | |
161 | boost::begin(interior_rings_in), boost::end(interior_rings_in), | |
162 | boost::begin(interior_rings_out), | |
163 | max_distance, strategy); | |
164 | } | |
165 | ||
166 | public: | |
167 | template <typename Polygon, typename Strategy, typename Distance> | |
168 | static inline void apply(Polygon const& poly_in, Polygon& poly_out, | |
169 | Distance const& max_distance, Strategy const& strategy) | |
170 | { | |
171 | std::size_t const minimum = core_detail::closure::minimum_ring_size | |
172 | < | |
173 | geometry::closure<Polygon>::value | |
174 | >::value; | |
175 | ||
176 | // Note that if there are inner rings, and distance is too large, | |
177 | // they might intersect with the outer ring in the output, | |
178 | // while it didn't in the input. | |
179 | simplify_range<minimum>::apply(exterior_ring(poly_in), | |
180 | exterior_ring(poly_out), | |
181 | max_distance, strategy); | |
182 | ||
183 | apply_interior_rings<minimum>(interior_rings(poly_in), | |
184 | interior_rings(poly_out), | |
185 | max_distance, strategy); | |
186 | } | |
187 | }; | |
188 | ||
189 | ||
190 | template<typename Policy> | |
191 | struct simplify_multi | |
192 | { | |
193 | template <typename MultiGeometry, typename Strategy, typename Distance> | |
194 | static inline void apply(MultiGeometry const& multi, MultiGeometry& out, | |
195 | Distance const& max_distance, Strategy const& strategy) | |
196 | { | |
197 | traits::resize<MultiGeometry>::apply(out, boost::size(multi)); | |
198 | ||
199 | typename boost::range_iterator<MultiGeometry>::type it_out | |
200 | = boost::begin(out); | |
201 | for (typename boost::range_iterator<MultiGeometry const>::type | |
202 | it_in = boost::begin(multi); | |
203 | it_in != boost::end(multi); | |
204 | ++it_in, ++it_out) | |
205 | { | |
206 | Policy::apply(*it_in, *it_out, max_distance, strategy); | |
207 | } | |
208 | } | |
209 | }; | |
210 | ||
211 | ||
212 | }} // namespace detail::simplify | |
213 | #endif // DOXYGEN_NO_DETAIL | |
214 | ||
215 | ||
216 | #ifndef DOXYGEN_NO_DISPATCH | |
217 | namespace dispatch | |
218 | { | |
219 | ||
220 | template | |
221 | < | |
222 | typename Geometry, | |
223 | typename Tag = typename tag<Geometry>::type | |
224 | > | |
225 | struct simplify: not_implemented<Tag> | |
226 | {}; | |
227 | ||
228 | template <typename Point> | |
229 | struct simplify<Point, point_tag> | |
230 | { | |
231 | template <typename Distance, typename Strategy> | |
232 | static inline void apply(Point const& point, Point& out, | |
233 | Distance const& , Strategy const& ) | |
234 | { | |
235 | geometry::convert(point, out); | |
236 | } | |
237 | }; | |
238 | ||
239 | ||
240 | template <typename Linestring> | |
241 | struct simplify<Linestring, linestring_tag> | |
242 | : detail::simplify::simplify_range<2> | |
243 | {}; | |
244 | ||
245 | template <typename Ring> | |
246 | struct simplify<Ring, ring_tag> | |
247 | : detail::simplify::simplify_range | |
248 | < | |
249 | core_detail::closure::minimum_ring_size | |
250 | < | |
251 | geometry::closure<Ring>::value | |
252 | >::value | |
253 | > | |
254 | {}; | |
255 | ||
256 | template <typename Polygon> | |
257 | struct simplify<Polygon, polygon_tag> | |
258 | : detail::simplify::simplify_polygon | |
259 | {}; | |
260 | ||
261 | ||
262 | template | |
263 | < | |
264 | typename Geometry, | |
265 | typename Tag = typename tag<Geometry>::type | |
266 | > | |
267 | struct simplify_insert: not_implemented<Tag> | |
268 | {}; | |
269 | ||
270 | ||
271 | template <typename Linestring> | |
272 | struct simplify_insert<Linestring, linestring_tag> | |
273 | : detail::simplify::simplify_range_insert | |
274 | {}; | |
275 | ||
276 | template <typename Ring> | |
277 | struct simplify_insert<Ring, ring_tag> | |
278 | : detail::simplify::simplify_range_insert | |
279 | {}; | |
280 | ||
281 | template <typename MultiPoint> | |
282 | struct simplify<MultiPoint, multi_point_tag> | |
283 | : detail::simplify::simplify_copy | |
284 | {}; | |
285 | ||
286 | ||
287 | template <typename MultiLinestring> | |
288 | struct simplify<MultiLinestring, multi_linestring_tag> | |
289 | : detail::simplify::simplify_multi<detail::simplify::simplify_range<2> > | |
290 | {}; | |
291 | ||
292 | ||
293 | template <typename MultiPolygon> | |
294 | struct simplify<MultiPolygon, multi_polygon_tag> | |
295 | : detail::simplify::simplify_multi<detail::simplify::simplify_polygon> | |
296 | {}; | |
297 | ||
298 | ||
299 | } // namespace dispatch | |
300 | #endif // DOXYGEN_NO_DISPATCH | |
301 | ||
302 | ||
303 | namespace resolve_strategy | |
304 | { | |
305 | ||
306 | struct simplify | |
307 | { | |
308 | template <typename Geometry, typename Distance, typename Strategy> | |
309 | static inline void apply(Geometry const& geometry, | |
310 | Geometry& out, | |
311 | Distance const& max_distance, | |
312 | Strategy const& strategy) | |
313 | { | |
314 | dispatch::simplify<Geometry>::apply(geometry, out, max_distance, strategy); | |
315 | } | |
316 | ||
317 | template <typename Geometry, typename Distance> | |
318 | static inline void apply(Geometry const& geometry, | |
319 | Geometry& out, | |
320 | Distance const& max_distance, | |
321 | default_strategy) | |
322 | { | |
323 | typedef typename point_type<Geometry>::type point_type; | |
324 | ||
325 | typedef typename strategy::distance::services::default_strategy | |
326 | < | |
327 | point_tag, segment_tag, point_type | |
328 | >::type ds_strategy_type; | |
329 | ||
330 | typedef strategy::simplify::douglas_peucker | |
331 | < | |
332 | point_type, ds_strategy_type | |
333 | > strategy_type; | |
334 | ||
335 | BOOST_CONCEPT_ASSERT( | |
336 | (concepts::SimplifyStrategy<strategy_type, point_type>) | |
337 | ); | |
338 | ||
339 | apply(geometry, out, max_distance, strategy_type()); | |
340 | } | |
341 | }; | |
342 | ||
343 | struct simplify_insert | |
344 | { | |
345 | template | |
346 | < | |
347 | typename Geometry, | |
348 | typename OutputIterator, | |
349 | typename Distance, | |
350 | typename Strategy | |
351 | > | |
352 | static inline void apply(Geometry const& geometry, | |
353 | OutputIterator& out, | |
354 | Distance const& max_distance, | |
355 | Strategy const& strategy) | |
356 | { | |
357 | dispatch::simplify_insert<Geometry>::apply(geometry, out, max_distance, strategy); | |
358 | } | |
359 | ||
360 | template <typename Geometry, typename OutputIterator, typename Distance> | |
361 | static inline void apply(Geometry const& geometry, | |
362 | OutputIterator& out, | |
363 | Distance const& max_distance, | |
364 | default_strategy) | |
365 | { | |
366 | typedef typename point_type<Geometry>::type point_type; | |
367 | ||
368 | typedef typename strategy::distance::services::default_strategy | |
369 | < | |
370 | point_tag, segment_tag, point_type | |
371 | >::type ds_strategy_type; | |
372 | ||
373 | typedef strategy::simplify::douglas_peucker | |
374 | < | |
375 | point_type, ds_strategy_type | |
376 | > strategy_type; | |
377 | ||
378 | BOOST_CONCEPT_ASSERT( | |
379 | (concepts::SimplifyStrategy<strategy_type, point_type>) | |
380 | ); | |
381 | ||
382 | apply(geometry, out, max_distance, strategy_type()); | |
383 | } | |
384 | }; | |
385 | ||
386 | } // namespace resolve_strategy | |
387 | ||
388 | ||
389 | namespace resolve_variant { | |
390 | ||
391 | template <typename Geometry> | |
392 | struct simplify | |
393 | { | |
394 | template <typename Distance, typename Strategy> | |
395 | static inline void apply(Geometry const& geometry, | |
396 | Geometry& out, | |
397 | Distance const& max_distance, | |
398 | Strategy const& strategy) | |
399 | { | |
400 | resolve_strategy::simplify::apply(geometry, out, max_distance, strategy); | |
401 | } | |
402 | }; | |
403 | ||
404 | template <BOOST_VARIANT_ENUM_PARAMS(typename T)> | |
405 | struct simplify<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> > | |
406 | { | |
407 | template <typename Distance, typename Strategy> | |
408 | struct visitor: boost::static_visitor<void> | |
409 | { | |
410 | Distance const& m_max_distance; | |
411 | Strategy const& m_strategy; | |
412 | ||
413 | visitor(Distance const& max_distance, Strategy const& strategy) | |
414 | : m_max_distance(max_distance) | |
415 | , m_strategy(strategy) | |
416 | {} | |
417 | ||
418 | template <typename Geometry> | |
419 | void operator()(Geometry const& geometry, Geometry& out) const | |
420 | { | |
421 | simplify<Geometry>::apply(geometry, out, m_max_distance, m_strategy); | |
422 | } | |
423 | }; | |
424 | ||
425 | template <typename Distance, typename Strategy> | |
426 | static inline void | |
427 | apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry, | |
428 | boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>& out, | |
429 | Distance const& max_distance, | |
430 | Strategy const& strategy) | |
431 | { | |
432 | boost::apply_visitor( | |
433 | visitor<Distance, Strategy>(max_distance, strategy), | |
434 | geometry, | |
435 | out | |
436 | ); | |
437 | } | |
438 | }; | |
439 | ||
440 | } // namespace resolve_variant | |
441 | ||
442 | ||
443 | /*! | |
444 | \brief Simplify a geometry using a specified strategy | |
445 | \ingroup simplify | |
446 | \tparam Geometry \tparam_geometry | |
447 | \tparam Distance A numerical distance measure | |
448 | \tparam Strategy A type fulfilling a SimplifyStrategy concept | |
449 | \param strategy A strategy to calculate simplification | |
450 | \param geometry input geometry, to be simplified | |
451 | \param out output geometry, simplified version of the input geometry | |
452 | \param max_distance distance (in units of input coordinates) of a vertex | |
453 | to other segments to be removed | |
454 | \param strategy simplify strategy to be used for simplification, might | |
455 | include point-distance strategy | |
456 | ||
457 | \image html svg_simplify_country.png "The image below presents the simplified country" | |
458 | \qbk{distinguish,with strategy} | |
459 | */ | |
460 | template<typename Geometry, typename Distance, typename Strategy> | |
461 | inline void simplify(Geometry const& geometry, Geometry& out, | |
462 | Distance const& max_distance, Strategy const& strategy) | |
463 | { | |
464 | concepts::check<Geometry>(); | |
465 | ||
466 | geometry::clear(out); | |
467 | ||
468 | resolve_variant::simplify<Geometry>::apply(geometry, out, max_distance, strategy); | |
469 | } | |
470 | ||
471 | ||
472 | ||
473 | ||
474 | /*! | |
475 | \brief Simplify a geometry | |
476 | \ingroup simplify | |
477 | \tparam Geometry \tparam_geometry | |
478 | \tparam Distance \tparam_numeric | |
479 | \note This version of simplify simplifies a geometry using the default | |
480 | strategy (Douglas Peucker), | |
481 | \param geometry input geometry, to be simplified | |
482 | \param out output geometry, simplified version of the input geometry | |
483 | \param max_distance distance (in units of input coordinates) of a vertex | |
484 | to other segments to be removed | |
485 | ||
486 | \qbk{[include reference/algorithms/simplify.qbk]} | |
487 | */ | |
488 | template<typename Geometry, typename Distance> | |
489 | inline void simplify(Geometry const& geometry, Geometry& out, | |
490 | Distance const& max_distance) | |
491 | { | |
492 | concepts::check<Geometry>(); | |
493 | ||
494 | geometry::simplify(geometry, out, max_distance, default_strategy()); | |
495 | } | |
496 | ||
497 | ||
498 | #ifndef DOXYGEN_NO_DETAIL | |
499 | namespace detail { namespace simplify | |
500 | { | |
501 | ||
502 | ||
503 | /*! | |
504 | \brief Simplify a geometry, using an output iterator | |
505 | and a specified strategy | |
506 | \ingroup simplify | |
507 | \tparam Geometry \tparam_geometry | |
508 | \param geometry input geometry, to be simplified | |
509 | \param out output iterator, outputs all simplified points | |
510 | \param max_distance distance (in units of input coordinates) of a vertex | |
511 | to other segments to be removed | |
512 | \param strategy simplify strategy to be used for simplification, | |
513 | might include point-distance strategy | |
514 | ||
515 | \qbk{distinguish,with strategy} | |
516 | \qbk{[include reference/algorithms/simplify.qbk]} | |
517 | */ | |
518 | template<typename Geometry, typename OutputIterator, typename Distance, typename Strategy> | |
519 | inline void simplify_insert(Geometry const& geometry, OutputIterator out, | |
520 | Distance const& max_distance, Strategy const& strategy) | |
521 | { | |
522 | concepts::check<Geometry const>(); | |
523 | ||
524 | resolve_strategy::simplify_insert::apply(geometry, out, max_distance, strategy); | |
525 | } | |
526 | ||
527 | /*! | |
528 | \brief Simplify a geometry, using an output iterator | |
529 | \ingroup simplify | |
530 | \tparam Geometry \tparam_geometry | |
531 | \param geometry input geometry, to be simplified | |
532 | \param out output iterator, outputs all simplified points | |
533 | \param max_distance distance (in units of input coordinates) of a vertex | |
534 | to other segments to be removed | |
535 | ||
536 | \qbk{[include reference/algorithms/simplify_insert.qbk]} | |
537 | */ | |
538 | template<typename Geometry, typename OutputIterator, typename Distance> | |
539 | inline void simplify_insert(Geometry const& geometry, OutputIterator out, | |
540 | Distance const& max_distance) | |
541 | { | |
542 | // Concept: output point type = point type of input geometry | |
543 | concepts::check<Geometry const>(); | |
544 | concepts::check<typename point_type<Geometry>::type>(); | |
545 | ||
546 | simplify_insert(geometry, out, max_distance, default_strategy()); | |
547 | } | |
548 | ||
549 | }} // namespace detail::simplify | |
550 | #endif // DOXYGEN_NO_DETAIL | |
551 | ||
552 | ||
553 | ||
554 | }} // namespace boost::geometry | |
555 | ||
556 | #endif // BOOST_GEOMETRY_ALGORITHMS_SIMPLIFY_HPP |