| // Boost.Geometry (aka GGL, Generic Geometry Library) |
| |
| // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. |
| // Copyright (c) 2008-2015 Bruno Lalande, Paris, France. |
| // Copyright (c) 2009-2015 Mateusz Loskot, London, UK. |
| |
| // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library |
| // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. |
| |
| // Use, modification and distribution is subject to the Boost Software License, |
| // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| |
| #ifndef BOOST_GEOMETRY_ALGORITHMS_SIMPLIFY_HPP |
| #define BOOST_GEOMETRY_ALGORITHMS_SIMPLIFY_HPP |
| |
| #include <cstddef> |
| |
| #include <boost/core/ignore_unused.hpp> |
| #include <boost/range.hpp> |
| |
| #include <boost/variant/apply_visitor.hpp> |
| #include <boost/variant/static_visitor.hpp> |
| #include <boost/variant/variant_fwd.hpp> |
| |
| #include <boost/geometry/core/cs.hpp> |
| #include <boost/geometry/core/closure.hpp> |
| #include <boost/geometry/core/exterior_ring.hpp> |
| #include <boost/geometry/core/interior_rings.hpp> |
| #include <boost/geometry/core/mutable_range.hpp> |
| #include <boost/geometry/core/tags.hpp> |
| |
| #include <boost/geometry/geometries/concepts/check.hpp> |
| #include <boost/geometry/strategies/agnostic/simplify_douglas_peucker.hpp> |
| #include <boost/geometry/strategies/concepts/simplify_concept.hpp> |
| #include <boost/geometry/strategies/default_strategy.hpp> |
| #include <boost/geometry/strategies/distance.hpp> |
| |
| #include <boost/geometry/algorithms/clear.hpp> |
| #include <boost/geometry/algorithms/convert.hpp> |
| #include <boost/geometry/algorithms/not_implemented.hpp> |
| |
| #include <boost/geometry/algorithms/detail/distance/default_strategies.hpp> |
| |
| namespace boost { namespace geometry |
| { |
| |
| #ifndef DOXYGEN_NO_DETAIL |
| namespace detail { namespace simplify |
| { |
| |
| struct simplify_range_insert |
| { |
| template<typename Range, typename Strategy, typename OutputIterator, typename Distance> |
| static inline void apply(Range const& range, OutputIterator out, |
| Distance const& max_distance, Strategy const& strategy) |
| { |
| boost::ignore_unused(strategy); |
| |
| if (boost::size(range) <= 2 || max_distance < 0) |
| { |
| std::copy(boost::begin(range), boost::end(range), out); |
| } |
| else |
| { |
| strategy.apply(range, out, max_distance); |
| } |
| } |
| }; |
| |
| |
| struct simplify_copy |
| { |
| template <typename Range, typename Strategy, typename Distance> |
| static inline void apply(Range const& range, Range& out, |
| Distance const& , Strategy const& ) |
| { |
| std::copy |
| ( |
| boost::begin(range), boost::end(range), std::back_inserter(out) |
| ); |
| } |
| }; |
| |
| |
| template<std::size_t Minimum> |
| struct simplify_range |
| { |
| template <typename Range, typename Strategy, typename Distance> |
| static inline void apply(Range const& range, Range& out, |
| Distance const& max_distance, Strategy const& strategy) |
| { |
| // Call do_container for a linestring / ring |
| |
| /* For a RING: |
| The first/last point (the closing point of the ring) should maybe |
| be excluded because it lies on a line with second/one but last. |
| Here it is never excluded. |
| |
| Note also that, especially if max_distance is too large, |
| the output ring might be self intersecting while the input ring is |
| not, although chances are low in normal polygons |
| |
| Finally the inputring might have 3 (open) or 4 (closed) points (=correct), |
| the output < 3 or 4(=wrong) |
| */ |
| |
| if (boost::size(range) <= int(Minimum) || max_distance < 0.0) |
| { |
| simplify_copy::apply(range, out, max_distance, strategy); |
| } |
| else |
| { |
| simplify_range_insert::apply |
| ( |
| range, std::back_inserter(out), max_distance, strategy |
| ); |
| } |
| } |
| }; |
| |
| struct simplify_polygon |
| { |
| private: |
| |
| template |
| < |
| std::size_t Minimum, |
| typename IteratorIn, |
| typename IteratorOut, |
| typename Distance, |
| typename Strategy |
| > |
| static inline void iterate(IteratorIn begin, IteratorIn end, |
| IteratorOut it_out, |
| Distance const& max_distance, Strategy const& strategy) |
| { |
| for (IteratorIn it_in = begin; it_in != end; ++it_in, ++it_out) |
| { |
| simplify_range<Minimum>::apply(*it_in, *it_out, max_distance, strategy); |
| } |
| } |
| |
| template |
| < |
| std::size_t Minimum, |
| typename InteriorRingsIn, |
| typename InteriorRingsOut, |
| typename Distance, |
| typename Strategy |
| > |
| static inline void apply_interior_rings( |
| InteriorRingsIn const& interior_rings_in, |
| InteriorRingsOut& interior_rings_out, |
| Distance const& max_distance, Strategy const& strategy) |
| { |
| traits::resize<InteriorRingsOut>::apply(interior_rings_out, |
| boost::size(interior_rings_in)); |
| |
| iterate<Minimum>( |
| boost::begin(interior_rings_in), boost::end(interior_rings_in), |
| boost::begin(interior_rings_out), |
| max_distance, strategy); |
| } |
| |
| public: |
| template <typename Polygon, typename Strategy, typename Distance> |
| static inline void apply(Polygon const& poly_in, Polygon& poly_out, |
| Distance const& max_distance, Strategy const& strategy) |
| { |
| std::size_t const minimum = core_detail::closure::minimum_ring_size |
| < |
| geometry::closure<Polygon>::value |
| >::value; |
| |
| // Note that if there are inner rings, and distance is too large, |
| // they might intersect with the outer ring in the output, |
| // while it didn't in the input. |
| simplify_range<minimum>::apply(exterior_ring(poly_in), |
| exterior_ring(poly_out), |
| max_distance, strategy); |
| |
| apply_interior_rings<minimum>(interior_rings(poly_in), |
| interior_rings(poly_out), |
| max_distance, strategy); |
| } |
| }; |
| |
| |
| template<typename Policy> |
| struct simplify_multi |
| { |
| template <typename MultiGeometry, typename Strategy, typename Distance> |
| static inline void apply(MultiGeometry const& multi, MultiGeometry& out, |
| Distance const& max_distance, Strategy const& strategy) |
| { |
| traits::resize<MultiGeometry>::apply(out, boost::size(multi)); |
| |
| typename boost::range_iterator<MultiGeometry>::type it_out |
| = boost::begin(out); |
| for (typename boost::range_iterator<MultiGeometry const>::type |
| it_in = boost::begin(multi); |
| it_in != boost::end(multi); |
| ++it_in, ++it_out) |
| { |
| Policy::apply(*it_in, *it_out, max_distance, strategy); |
| } |
| } |
| }; |
| |
| |
| }} // namespace detail::simplify |
| #endif // DOXYGEN_NO_DETAIL |
| |
| |
| #ifndef DOXYGEN_NO_DISPATCH |
| namespace dispatch |
| { |
| |
| template |
| < |
| typename Geometry, |
| typename Tag = typename tag<Geometry>::type |
| > |
| struct simplify: not_implemented<Tag> |
| {}; |
| |
| template <typename Point> |
| struct simplify<Point, point_tag> |
| { |
| template <typename Distance, typename Strategy> |
| static inline void apply(Point const& point, Point& out, |
| Distance const& , Strategy const& ) |
| { |
| geometry::convert(point, out); |
| } |
| }; |
| |
| |
| template <typename Linestring> |
| struct simplify<Linestring, linestring_tag> |
| : detail::simplify::simplify_range<2> |
| {}; |
| |
| template <typename Ring> |
| struct simplify<Ring, ring_tag> |
| : detail::simplify::simplify_range |
| < |
| core_detail::closure::minimum_ring_size |
| < |
| geometry::closure<Ring>::value |
| >::value |
| > |
| {}; |
| |
| template <typename Polygon> |
| struct simplify<Polygon, polygon_tag> |
| : detail::simplify::simplify_polygon |
| {}; |
| |
| |
| template |
| < |
| typename Geometry, |
| typename Tag = typename tag<Geometry>::type |
| > |
| struct simplify_insert: not_implemented<Tag> |
| {}; |
| |
| |
| template <typename Linestring> |
| struct simplify_insert<Linestring, linestring_tag> |
| : detail::simplify::simplify_range_insert |
| {}; |
| |
| template <typename Ring> |
| struct simplify_insert<Ring, ring_tag> |
| : detail::simplify::simplify_range_insert |
| {}; |
| |
| template <typename MultiPoint> |
| struct simplify<MultiPoint, multi_point_tag> |
| : detail::simplify::simplify_copy |
| {}; |
| |
| |
| template <typename MultiLinestring> |
| struct simplify<MultiLinestring, multi_linestring_tag> |
| : detail::simplify::simplify_multi<detail::simplify::simplify_range<2> > |
| {}; |
| |
| |
| template <typename MultiPolygon> |
| struct simplify<MultiPolygon, multi_polygon_tag> |
| : detail::simplify::simplify_multi<detail::simplify::simplify_polygon> |
| {}; |
| |
| |
| } // namespace dispatch |
| #endif // DOXYGEN_NO_DISPATCH |
| |
| |
| namespace resolve_strategy |
| { |
| |
| struct simplify |
| { |
| template <typename Geometry, typename Distance, typename Strategy> |
| static inline void apply(Geometry const& geometry, |
| Geometry& out, |
| Distance const& max_distance, |
| Strategy const& strategy) |
| { |
| dispatch::simplify<Geometry>::apply(geometry, out, max_distance, strategy); |
| } |
| |
| template <typename Geometry, typename Distance> |
| static inline void apply(Geometry const& geometry, |
| Geometry& out, |
| Distance const& max_distance, |
| default_strategy) |
| { |
| typedef typename point_type<Geometry>::type point_type; |
| |
| typedef typename strategy::distance::services::default_strategy |
| < |
| point_tag, segment_tag, point_type |
| >::type ds_strategy_type; |
| |
| typedef strategy::simplify::douglas_peucker |
| < |
| point_type, ds_strategy_type |
| > strategy_type; |
| |
| BOOST_CONCEPT_ASSERT( |
| (concept::SimplifyStrategy<strategy_type, point_type>) |
| ); |
| |
| apply(geometry, out, max_distance, strategy_type()); |
| } |
| }; |
| |
| struct simplify_insert |
| { |
| template |
| < |
| typename Geometry, |
| typename OutputIterator, |
| typename Distance, |
| typename Strategy |
| > |
| static inline void apply(Geometry const& geometry, |
| OutputIterator& out, |
| Distance const& max_distance, |
| Strategy const& strategy) |
| { |
| dispatch::simplify_insert<Geometry>::apply(geometry, out, max_distance, strategy); |
| } |
| |
| template <typename Geometry, typename OutputIterator, typename Distance> |
| static inline void apply(Geometry const& geometry, |
| OutputIterator& out, |
| Distance const& max_distance, |
| default_strategy) |
| { |
| typedef typename point_type<Geometry>::type point_type; |
| |
| typedef typename strategy::distance::services::default_strategy |
| < |
| point_tag, segment_tag, point_type |
| >::type ds_strategy_type; |
| |
| typedef strategy::simplify::douglas_peucker |
| < |
| point_type, ds_strategy_type |
| > strategy_type; |
| |
| BOOST_CONCEPT_ASSERT( |
| (concept::SimplifyStrategy<strategy_type, point_type>) |
| ); |
| |
| apply(geometry, out, max_distance, strategy_type()); |
| } |
| }; |
| |
| } // namespace resolve_strategy |
| |
| |
| namespace resolve_variant { |
| |
| template <typename Geometry> |
| struct simplify |
| { |
| template <typename Distance, typename Strategy> |
| static inline void apply(Geometry const& geometry, |
| Geometry& out, |
| Distance const& max_distance, |
| Strategy const& strategy) |
| { |
| resolve_strategy::simplify::apply(geometry, out, max_distance, strategy); |
| } |
| }; |
| |
| template <BOOST_VARIANT_ENUM_PARAMS(typename T)> |
| struct simplify<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> > |
| { |
| template <typename Distance, typename Strategy> |
| struct visitor: boost::static_visitor<void> |
| { |
| Distance const& m_max_distance; |
| Strategy const& m_strategy; |
| |
| visitor(Distance const& max_distance, Strategy const& strategy) |
| : m_max_distance(max_distance) |
| , m_strategy(strategy) |
| {} |
| |
| template <typename Geometry> |
| void operator()(Geometry const& geometry, Geometry& out) const |
| { |
| simplify<Geometry>::apply(geometry, out, m_max_distance, m_strategy); |
| } |
| }; |
| |
| template <typename Distance, typename Strategy> |
| static inline void |
| apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry, |
| boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>& out, |
| Distance const& max_distance, |
| Strategy const& strategy) |
| { |
| boost::apply_visitor( |
| visitor<Distance, Strategy>(max_distance, strategy), |
| geometry, |
| out |
| ); |
| } |
| }; |
| |
| } // namespace resolve_variant |
| |
| |
| /*! |
| \brief Simplify a geometry using a specified strategy |
| \ingroup simplify |
| \tparam Geometry \tparam_geometry |
| \tparam Distance A numerical distance measure |
| \tparam Strategy A type fulfilling a SimplifyStrategy concept |
| \param strategy A strategy to calculate simplification |
| \param geometry input geometry, to be simplified |
| \param out output geometry, simplified version of the input geometry |
| \param max_distance distance (in units of input coordinates) of a vertex |
| to other segments to be removed |
| \param strategy simplify strategy to be used for simplification, might |
| include point-distance strategy |
| |
| \image html svg_simplify_country.png "The image below presents the simplified country" |
| \qbk{distinguish,with strategy} |
| */ |
| template<typename Geometry, typename Distance, typename Strategy> |
| inline void simplify(Geometry const& geometry, Geometry& out, |
| Distance const& max_distance, Strategy const& strategy) |
| { |
| concept::check<Geometry>(); |
| |
| geometry::clear(out); |
| |
| resolve_variant::simplify<Geometry>::apply(geometry, out, max_distance, strategy); |
| } |
| |
| |
| |
| |
| /*! |
| \brief Simplify a geometry |
| \ingroup simplify |
| \tparam Geometry \tparam_geometry |
| \tparam Distance \tparam_numeric |
| \note This version of simplify simplifies a geometry using the default |
| strategy (Douglas Peucker), |
| \param geometry input geometry, to be simplified |
| \param out output geometry, simplified version of the input geometry |
| \param max_distance distance (in units of input coordinates) of a vertex |
| to other segments to be removed |
| |
| \qbk{[include reference/algorithms/simplify.qbk]} |
| */ |
| template<typename Geometry, typename Distance> |
| inline void simplify(Geometry const& geometry, Geometry& out, |
| Distance const& max_distance) |
| { |
| concept::check<Geometry>(); |
| |
| simplify(geometry, out, max_distance, default_strategy()); |
| } |
| |
| |
| #ifndef DOXYGEN_NO_DETAIL |
| namespace detail { namespace simplify |
| { |
| |
| |
| /*! |
| \brief Simplify a geometry, using an output iterator |
| and a specified strategy |
| \ingroup simplify |
| \tparam Geometry \tparam_geometry |
| \param geometry input geometry, to be simplified |
| \param out output iterator, outputs all simplified points |
| \param max_distance distance (in units of input coordinates) of a vertex |
| to other segments to be removed |
| \param strategy simplify strategy to be used for simplification, |
| might include point-distance strategy |
| |
| \qbk{distinguish,with strategy} |
| \qbk{[include reference/algorithms/simplify.qbk]} |
| */ |
| template<typename Geometry, typename OutputIterator, typename Distance, typename Strategy> |
| inline void simplify_insert(Geometry const& geometry, OutputIterator out, |
| Distance const& max_distance, Strategy const& strategy) |
| { |
| concept::check<Geometry const>(); |
| |
| resolve_strategy::simplify_insert::apply(geometry, out, max_distance, strategy); |
| } |
| |
| /*! |
| \brief Simplify a geometry, using an output iterator |
| \ingroup simplify |
| \tparam Geometry \tparam_geometry |
| \param geometry input geometry, to be simplified |
| \param out output iterator, outputs all simplified points |
| \param max_distance distance (in units of input coordinates) of a vertex |
| to other segments to be removed |
| |
| \qbk{[include reference/algorithms/simplify_insert.qbk]} |
| */ |
| template<typename Geometry, typename OutputIterator, typename Distance> |
| inline void simplify_insert(Geometry const& geometry, OutputIterator out, |
| Distance const& max_distance) |
| { |
| // Concept: output point type = point type of input geometry |
| concept::check<Geometry const>(); |
| concept::check<typename point_type<Geometry>::type>(); |
| |
| simplify_insert(geometry, out, max_distance, default_strategy()); |
| } |
| |
| }} // namespace detail::simplify |
| #endif // DOXYGEN_NO_DETAIL |
| |
| |
| |
| }} // namespace boost::geometry |
| |
| #endif // BOOST_GEOMETRY_ALGORITHMS_SIMPLIFY_HPP |