Chris@16: // Boost.Geometry (aka GGL, Generic Geometry Library)
Chris@16: 
Chris@16: // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
Chris@16: // Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
Chris@16: // Copyright (c) 2009-2012 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: 
Chris@16: #include <cstddef>
Chris@16: 
Chris@16: #include <boost/range.hpp>
Chris@16: #include <boost/typeof/typeof.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/ring_type.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@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@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: #include <boost/geometry/algorithms/num_interior_rings.hpp>
Chris@16: 
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@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@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@16:         typedef typename ring_type<Polygon>::type ring_type;
Chris@16: 
Chris@16:         int 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@16:         simplify_range<Minimum>::apply(exterior_ring(poly_in),
Chris@16:                                        exterior_ring(poly_out),
Chris@16:                                        max_distance, strategy);
Chris@16: 
Chris@16:         traits::resize
Chris@16:             <
Chris@16:                 typename boost::remove_reference
Chris@16:                 <
Chris@16:                     typename traits::interior_mutable_type<Polygon>::type
Chris@16:                 >::type
Chris@16:             >::apply(interior_rings(poly_out), num_interior_rings(poly_in));
Chris@16: 
Chris@16:         typename interior_return_type<Polygon const>::type rings_in
Chris@16:                     = interior_rings(poly_in);
Chris@16:         typename interior_return_type<Polygon>::type rings_out
Chris@16:                     = interior_rings(poly_out);
Chris@16:         BOOST_AUTO_TPL(it_out, boost::begin(rings_out));
Chris@16:         for (BOOST_AUTO_TPL(it_in,  boost::begin(rings_in));
Chris@16:             it_in != boost::end(rings_in);
Chris@16:             ++it_in, ++it_out)
Chris@16:         {
Chris@16:             simplify_range<Minimum>::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@16: 
Chris@16: } // namespace dispatch
Chris@16: #endif // DOXYGEN_NO_DISPATCH
Chris@16: 
Chris@16: 
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:     BOOST_CONCEPT_ASSERT(
Chris@16:         (concept::SimplifyStrategy<Strategy, typename point_type<Geometry>::type>)
Chris@16:     );
Chris@16: 
Chris@16:     geometry::clear(out);
Chris@16: 
Chris@16:     dispatch::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@16:     typedef typename point_type<Geometry>::type point_type;
Chris@16:     typedef typename strategy::distance::services::default_strategy
Chris@16:             <
Chris@16:                 segment_tag, point_type
Chris@16:             >::type ds_strategy_type;
Chris@16: 
Chris@16:     typedef strategy::simplify::douglas_peucker
Chris@16:         <
Chris@16:             point_type, ds_strategy_type
Chris@16:         > strategy_type;
Chris@16: 
Chris@16:     simplify(geometry, out, max_distance, strategy_type());
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@16:                               Distance const& max_distance, Strategy const& strategy)
Chris@16: {
Chris@16:     concept::check<Geometry const>();
Chris@16:     BOOST_CONCEPT_ASSERT(
Chris@16:         (concept::SimplifyStrategy<Strategy, typename point_type<Geometry>::type>)
Chris@16:     );
Chris@16: 
Chris@16:     dispatch::simplify_insert<Geometry>::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@16:                               Distance const& max_distance)
Chris@16: {
Chris@16:     typedef typename point_type<Geometry>::type point_type;
Chris@16: 
Chris@16:     // Concept: output point type = point type of input geometry
Chris@16:     concept::check<Geometry const>();
Chris@16:     concept::check<point_type>();
Chris@16: 
Chris@16:     typedef typename strategy::distance::services::default_strategy
Chris@16:         <
Chris@16:             segment_tag, point_type
Chris@16:         >::type ds_strategy_type;
Chris@16: 
Chris@16:     typedef strategy::simplify::douglas_peucker
Chris@16:         <
Chris@16:             point_type, ds_strategy_type
Chris@16:         > strategy_type;
Chris@16: 
Chris@16:     dispatch::simplify_insert<Geometry>::apply(geometry, out, max_distance, strategy_type());
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