1 // Boost.Geometry (aka GGL, Generic Geometry Library)
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.
7 // This file was modified by Oracle on 2018-2020.
8 // Modifications copyright (c) 2018-2020 Oracle and/or its affiliates.
9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
11 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
12 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
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)
18 #ifndef BOOST_GEOMETRY_ALGORITHMS_SIMPLIFY_HPP
19 #define BOOST_GEOMETRY_ALGORITHMS_SIMPLIFY_HPP
24 #include <boost/core/ignore_unused.hpp>
25 #include <boost/range/begin.hpp>
26 #include <boost/range/end.hpp>
27 #include <boost/range/size.hpp>
28 #include <boost/range/value_type.hpp>
29 #include <boost/variant/apply_visitor.hpp>
30 #include <boost/variant/static_visitor.hpp>
31 #include <boost/variant/variant_fwd.hpp>
33 #include <boost/geometry/core/cs.hpp>
34 #include <boost/geometry/core/closure.hpp>
35 #include <boost/geometry/core/exterior_ring.hpp>
36 #include <boost/geometry/core/interior_rings.hpp>
37 #include <boost/geometry/core/mutable_range.hpp>
38 #include <boost/geometry/core/tags.hpp>
40 #include <boost/geometry/geometries/concepts/check.hpp>
41 #include <boost/geometry/strategies/agnostic/simplify_douglas_peucker.hpp>
42 #include <boost/geometry/strategies/concepts/simplify_concept.hpp>
43 #include <boost/geometry/strategies/default_strategy.hpp>
44 #include <boost/geometry/strategies/distance.hpp>
46 #include <boost/geometry/algorithms/area.hpp>
47 #include <boost/geometry/algorithms/clear.hpp>
48 #include <boost/geometry/algorithms/convert.hpp>
49 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
50 #include <boost/geometry/algorithms/not_implemented.hpp>
51 #include <boost/geometry/algorithms/is_empty.hpp>
52 #include <boost/geometry/algorithms/perimeter.hpp>
54 #include <boost/geometry/algorithms/detail/distance/default_strategies.hpp>
56 namespace boost { namespace geometry
59 #ifndef DOXYGEN_NO_DETAIL
60 namespace detail { namespace simplify
63 template <typename Range, typename EqualsStrategy>
64 inline bool is_degenerate(Range const& range, EqualsStrategy const& strategy)
66 return boost::size(range) == 2
67 && detail::equals::equals_point_point(geometry::range::front(range),
68 geometry::range::back(range),
72 struct simplify_range_insert
74 template<typename Range, typename Strategy, typename OutputIterator, typename Distance>
75 static inline void apply(Range const& range, OutputIterator out,
76 Distance const& max_distance, Strategy const& strategy)
78 typedef typename Strategy::distance_strategy_type::equals_point_point_strategy_type
81 boost::ignore_unused(strategy);
83 if (is_degenerate(range, equals_strategy_type()))
85 std::copy(boost::begin(range), boost::begin(range) + 1, out);
87 else if (boost::size(range) <= 2 || max_distance < 0)
89 std::copy(boost::begin(range), boost::end(range), out);
93 strategy.apply(range, out, max_distance);
101 template <typename RangeIn, typename RangeOut, typename Strategy, typename Distance>
102 static inline void apply(RangeIn const& range, RangeOut& out,
103 Distance const& , Strategy const& )
107 boost::begin(range), boost::end(range),
108 geometry::range::back_inserter(out)
114 template <std::size_t MinimumToUseStrategy>
115 struct simplify_range
117 template <typename RangeIn, typename RangeOut, typename Strategy, typename Distance>
118 static inline void apply(RangeIn const& range, RangeOut& out,
119 Distance const& max_distance, Strategy const& strategy)
121 typedef typename Strategy::distance_strategy_type::equals_point_point_strategy_type
122 equals_strategy_type;
125 // Note that, especially if max_distance is too large,
126 // the output ring might be self intersecting while the input ring is
127 // not, although chances are low in normal polygons
129 if (boost::size(range) <= MinimumToUseStrategy || max_distance < 0)
131 simplify_copy::apply(range, out, max_distance, strategy);
135 simplify_range_insert::apply
137 range, geometry::range::back_inserter(out), max_distance, strategy
141 // Verify the two remaining points are equal. If so, remove one of them.
142 // This can cause the output being under the minimum size
143 if (is_degenerate(out, equals_strategy_type()))
145 range::resize(out, 1);
153 template <typename Area>
154 static inline int area_sign(Area const& area)
156 return area > 0 ? 1 : area < 0 ? -1 : 0;
159 template <typename Strategy, typename Ring>
160 static std::size_t get_opposite(std::size_t index, Ring const& ring)
162 typename Strategy::distance_strategy_type distance_strategy;
164 // Verify if it is NOT the case that all points are less than the
165 // simplifying distance. If so, output is empty.
166 typename Strategy::distance_type max_distance(-1);
168 typename geometry::point_type<Ring>::type point = range::at(ring, index);
170 for (typename boost::range_iterator<Ring const>::type
171 it = boost::begin(ring); it != boost::end(ring); ++it, ++i)
173 // This actually is point-segment distance but will result
174 // in point-point distance
175 typename Strategy::distance_type dist = distance_strategy.apply(*it, point, point);
176 if (dist > max_distance)
186 template <typename Ring, typename Strategy, typename Distance>
187 static inline void apply(Ring const& ring, Ring& out,
188 Distance const& max_distance, Strategy const& strategy)
190 std::size_t const size = boost::size(ring);
196 int const input_sign = area_sign(geometry::area(ring));
198 std::set<std::size_t> visited_indexes;
200 // Rotate it into a copied vector
201 // (vector, because source type might not support rotation)
202 // (duplicate end point will be simplified away)
203 typedef typename geometry::point_type<Ring>::type point_type;
205 std::vector<point_type> rotated(size);
207 // Closing point (but it will not start here)
208 std::size_t index = 0;
210 // Iterate (usually one iteration is enough)
211 for (std::size_t iteration = 0; iteration < 4u; iteration++)
213 // Always take the opposite. Opposite guarantees that no point
214 // "halfway" is chosen, creating an artefact (very narrow triangle)
215 // Iteration 0: opposite to closing point (1/2, = on convex hull)
216 // (this will start simplification with that point
217 // and its opposite ~0)
218 // Iteration 1: move a quarter on that ring, then opposite to 1/4
219 // (with its opposite 3/4)
220 // Iteration 2: move an eight on that ring, then opposite (1/8)
221 // Iteration 3: again move a quarter, then opposite (7/8)
222 // So finally 8 "sides" of the ring have been examined (if it were
223 // a semi-circle). Most probably, there are only 0 or 1 iterations.
226 case 1 : index = (index + size / 4) % size; break;
227 case 2 : index = (index + size / 8) % size; break;
228 case 3 : index = (index + size / 4) % size; break;
230 index = get_opposite<Strategy>(index, ring);
232 if (visited_indexes.count(index) > 0)
234 // Avoid trying the same starting point more than once
238 std::rotate_copy(boost::begin(ring), range::pos(ring, index),
239 boost::end(ring), rotated.begin());
241 // Close the rotated copy
242 rotated.push_back(range::at(ring, index));
244 simplify_range<0>::apply(rotated, out, max_distance, strategy);
246 // Verify that what was positive, stays positive (or goes to 0)
247 // and what was negative stays negative (or goes to 0)
248 int const output_sign = area_sign(geometry::area(out));
249 if (output_sign == input_sign)
251 // Result is considered as satisfactory (usually this is the
252 // first iteration - only for small rings, having a scale
253 // similar to simplify_distance, next iterations are tried
257 // Original is simplified away. Possibly there is a solution
258 // when another starting point is used
259 geometry::clear(out);
262 && geometry::perimeter(ring) < 3 * max_distance)
264 // Check if it is useful to iterate. A minimal triangle has a
265 // perimeter of a bit more than 3 times the simplify distance
270 visited_indexes.insert(index);
271 rotated.resize(size);
277 struct simplify_polygon
284 typename InteriorRingsOut,
288 static inline void iterate(IteratorIn begin, IteratorIn end,
289 InteriorRingsOut& interior_rings_out,
290 Distance const& max_distance, Strategy const& strategy)
292 typedef typename boost::range_value<InteriorRingsOut>::type single_type;
293 for (IteratorIn it = begin; it != end; ++it)
296 simplify_ring::apply(*it, out, max_distance, strategy);
297 if (! geometry::is_empty(out))
299 range::push_back(interior_rings_out, out);
306 typename InteriorRingsIn,
307 typename InteriorRingsOut,
311 static inline void apply_interior_rings(
312 InteriorRingsIn const& interior_rings_in,
313 InteriorRingsOut& interior_rings_out,
314 Distance const& max_distance, Strategy const& strategy)
316 range::clear(interior_rings_out);
319 boost::begin(interior_rings_in), boost::end(interior_rings_in),
321 max_distance, strategy);
325 template <typename Polygon, typename Strategy, typename Distance>
326 static inline void apply(Polygon const& poly_in, Polygon& poly_out,
327 Distance const& max_distance, Strategy const& strategy)
329 // Note that if there are inner rings, and distance is too large,
330 // they might intersect with the outer ring in the output,
331 // while it didn't in the input.
332 simplify_ring::apply(exterior_ring(poly_in), exterior_ring(poly_out),
333 max_distance, strategy);
335 apply_interior_rings(interior_rings(poly_in),
336 interior_rings(poly_out), max_distance, strategy);
341 template<typename Policy>
342 struct simplify_multi
344 template <typename MultiGeometry, typename Strategy, typename Distance>
345 static inline void apply(MultiGeometry const& multi, MultiGeometry& out,
346 Distance const& max_distance, Strategy const& strategy)
350 typedef typename boost::range_value<MultiGeometry>::type single_type;
352 for (typename boost::range_iterator<MultiGeometry const>::type
353 it = boost::begin(multi); it != boost::end(multi); ++it)
355 single_type single_out;
356 Policy::apply(*it, single_out, max_distance, strategy);
357 if (! geometry::is_empty(single_out))
359 range::push_back(out, single_out);
366 }} // namespace detail::simplify
367 #endif // DOXYGEN_NO_DETAIL
370 #ifndef DOXYGEN_NO_DISPATCH
377 typename Tag = typename tag<Geometry>::type
379 struct simplify: not_implemented<Tag>
382 template <typename Point>
383 struct simplify<Point, point_tag>
385 template <typename Distance, typename Strategy>
386 static inline void apply(Point const& point, Point& out,
387 Distance const& , Strategy const& )
389 geometry::convert(point, out);
393 // Linestring, keep 2 points (unless those points are the same)
394 template <typename Linestring>
395 struct simplify<Linestring, linestring_tag>
396 : detail::simplify::simplify_range<2>
399 template <typename Ring>
400 struct simplify<Ring, ring_tag>
401 : detail::simplify::simplify_ring
404 template <typename Polygon>
405 struct simplify<Polygon, polygon_tag>
406 : detail::simplify::simplify_polygon
413 typename Tag = typename tag<Geometry>::type
415 struct simplify_insert: not_implemented<Tag>
419 template <typename Linestring>
420 struct simplify_insert<Linestring, linestring_tag>
421 : detail::simplify::simplify_range_insert
424 template <typename Ring>
425 struct simplify_insert<Ring, ring_tag>
426 : detail::simplify::simplify_range_insert
429 template <typename MultiPoint>
430 struct simplify<MultiPoint, multi_point_tag>
431 : detail::simplify::simplify_copy
435 template <typename MultiLinestring>
436 struct simplify<MultiLinestring, multi_linestring_tag>
437 : detail::simplify::simplify_multi<detail::simplify::simplify_range<2> >
441 template <typename MultiPolygon>
442 struct simplify<MultiPolygon, multi_polygon_tag>
443 : detail::simplify::simplify_multi<detail::simplify::simplify_polygon>
447 } // namespace dispatch
448 #endif // DOXYGEN_NO_DISPATCH
451 namespace resolve_strategy
456 template <typename Geometry, typename Distance, typename Strategy>
457 static inline void apply(Geometry const& geometry,
459 Distance const& max_distance,
460 Strategy const& strategy)
462 dispatch::simplify<Geometry>::apply(geometry, out, max_distance, strategy);
465 template <typename Geometry, typename Distance>
466 static inline void apply(Geometry const& geometry,
468 Distance const& max_distance,
471 typedef typename point_type<Geometry>::type point_type;
473 typedef typename strategy::distance::services::default_strategy
475 point_tag, segment_tag, point_type
476 >::type ds_strategy_type;
478 typedef strategy::simplify::douglas_peucker
480 point_type, ds_strategy_type
483 BOOST_CONCEPT_ASSERT(
484 (concepts::SimplifyStrategy<strategy_type, point_type>)
487 apply(geometry, out, max_distance, strategy_type());
491 struct simplify_insert
496 typename OutputIterator,
500 static inline void apply(Geometry const& geometry,
502 Distance const& max_distance,
503 Strategy const& strategy)
505 dispatch::simplify_insert<Geometry>::apply(geometry, out, max_distance, strategy);
508 template <typename Geometry, typename OutputIterator, typename Distance>
509 static inline void apply(Geometry const& geometry,
511 Distance const& max_distance,
514 typedef typename point_type<Geometry>::type point_type;
516 typedef typename strategy::distance::services::default_strategy
518 point_tag, segment_tag, point_type
519 >::type ds_strategy_type;
521 typedef strategy::simplify::douglas_peucker
523 point_type, ds_strategy_type
526 BOOST_CONCEPT_ASSERT(
527 (concepts::SimplifyStrategy<strategy_type, point_type>)
530 apply(geometry, out, max_distance, strategy_type());
534 } // namespace resolve_strategy
537 namespace resolve_variant {
539 template <typename Geometry>
542 template <typename Distance, typename Strategy>
543 static inline void apply(Geometry const& geometry,
545 Distance const& max_distance,
546 Strategy const& strategy)
548 resolve_strategy::simplify::apply(geometry, out, max_distance, strategy);
552 template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
553 struct simplify<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
555 template <typename Distance, typename Strategy>
556 struct visitor: boost::static_visitor<void>
558 Distance const& m_max_distance;
559 Strategy const& m_strategy;
561 visitor(Distance const& max_distance, Strategy const& strategy)
562 : m_max_distance(max_distance)
563 , m_strategy(strategy)
566 template <typename Geometry>
567 void operator()(Geometry const& geometry, Geometry& out) const
569 simplify<Geometry>::apply(geometry, out, m_max_distance, m_strategy);
573 template <typename Distance, typename Strategy>
575 apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry,
576 boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>& out,
577 Distance const& max_distance,
578 Strategy const& strategy)
580 boost::apply_visitor(
581 visitor<Distance, Strategy>(max_distance, strategy),
588 } // namespace resolve_variant
592 \brief Simplify a geometry using a specified strategy
594 \tparam Geometry \tparam_geometry
595 \tparam Distance A numerical distance measure
596 \tparam Strategy A type fulfilling a SimplifyStrategy concept
597 \param strategy A strategy to calculate simplification
598 \param geometry input geometry, to be simplified
599 \param out output geometry, simplified version of the input geometry
600 \param max_distance distance (in units of input coordinates) of a vertex
601 to other segments to be removed
602 \param strategy simplify strategy to be used for simplification, might
603 include point-distance strategy
605 \image html svg_simplify_country.png "The image below presents the simplified country"
606 \qbk{distinguish,with strategy}
608 template<typename Geometry, typename Distance, typename Strategy>
609 inline void simplify(Geometry const& geometry, Geometry& out,
610 Distance const& max_distance, Strategy const& strategy)
612 concepts::check<Geometry>();
614 geometry::clear(out);
616 resolve_variant::simplify<Geometry>::apply(geometry, out, max_distance, strategy);
623 \brief Simplify a geometry
625 \tparam Geometry \tparam_geometry
626 \tparam Distance \tparam_numeric
627 \note This version of simplify simplifies a geometry using the default
628 strategy (Douglas Peucker),
629 \param geometry input geometry, to be simplified
630 \param out output geometry, simplified version of the input geometry
631 \param max_distance distance (in units of input coordinates) of a vertex
632 to other segments to be removed
634 \qbk{[include reference/algorithms/simplify.qbk]}
636 template<typename Geometry, typename Distance>
637 inline void simplify(Geometry const& geometry, Geometry& out,
638 Distance const& max_distance)
640 concepts::check<Geometry>();
642 geometry::simplify(geometry, out, max_distance, default_strategy());
646 #ifndef DOXYGEN_NO_DETAIL
647 namespace detail { namespace simplify
652 \brief Simplify a geometry, using an output iterator
653 and a specified strategy
655 \tparam Geometry \tparam_geometry
656 \param geometry input geometry, to be simplified
657 \param out output iterator, outputs all simplified points
658 \param max_distance distance (in units of input coordinates) of a vertex
659 to other segments to be removed
660 \param strategy simplify strategy to be used for simplification,
661 might include point-distance strategy
663 \qbk{distinguish,with strategy}
664 \qbk{[include reference/algorithms/simplify.qbk]}
666 template<typename Geometry, typename OutputIterator, typename Distance, typename Strategy>
667 inline void simplify_insert(Geometry const& geometry, OutputIterator out,
668 Distance const& max_distance, Strategy const& strategy)
670 concepts::check<Geometry const>();
672 resolve_strategy::simplify_insert::apply(geometry, out, max_distance, strategy);
676 \brief Simplify a geometry, using an output iterator
678 \tparam Geometry \tparam_geometry
679 \param geometry input geometry, to be simplified
680 \param out output iterator, outputs all simplified points
681 \param max_distance distance (in units of input coordinates) of a vertex
682 to other segments to be removed
684 \qbk{[include reference/algorithms/simplify_insert.qbk]}
686 template<typename Geometry, typename OutputIterator, typename Distance>
687 inline void simplify_insert(Geometry const& geometry, OutputIterator out,
688 Distance const& max_distance)
690 // Concept: output point type = point type of input geometry
691 concepts::check<Geometry const>();
692 concepts::check<typename point_type<Geometry>::type>();
694 simplify_insert(geometry, out, max_distance, default_strategy());
697 }} // namespace detail::simplify
698 #endif // DOXYGEN_NO_DETAIL
702 }} // namespace boost::geometry
704 #endif // BOOST_GEOMETRY_ALGORITHMS_SIMPLIFY_HPP