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