Chris@16: // Boost.Geometry (aka GGL, Generic Geometry Library)
Chris@16: 
Chris@101: // Copyright (c) 1995, 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
Chris@16: // Copyright (c) 1995 Maarten Hilferink, Amsterdam, the Netherlands
Chris@16: 
Chris@101: // This file was modified by Oracle on 2015.
Chris@101: // Modifications copyright (c) 2015, Oracle and/or its affiliates.
Chris@101: 
Chris@101: // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
Chris@101: 
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_STRATEGY_AGNOSTIC_SIMPLIFY_DOUGLAS_PEUCKER_HPP
Chris@16: #define BOOST_GEOMETRY_STRATEGY_AGNOSTIC_SIMPLIFY_DOUGLAS_PEUCKER_HPP
Chris@16: 
Chris@16: 
Chris@16: #include <cstddef>
Chris@101: #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
Chris@101: #include <iostream>
Chris@101: #endif
Chris@16: #include <vector>
Chris@16: 
Chris@16: #include <boost/range.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/core/cs.hpp>
Chris@16: #include <boost/geometry/strategies/distance.hpp>
Chris@16: 
Chris@16: 
Chris@101: #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
Chris@16: #include <boost/geometry/io/dsv/write.hpp>
Chris@16: #endif
Chris@16: 
Chris@16: 
Chris@16: namespace boost { namespace geometry
Chris@16: {
Chris@16: 
Chris@16: namespace strategy { namespace simplify
Chris@16: {
Chris@16: 
Chris@16: 
Chris@16: #ifndef DOXYGEN_NO_DETAIL
Chris@16: namespace detail
Chris@16: {
Chris@16: 
Chris@16:     /*!
Chris@16:         \brief Small wrapper around a point, with an extra member "included"
Chris@16:         \details
Chris@16:             It has a const-reference to the original point (so no copy here)
Chris@16:         \tparam the enclosed point type
Chris@16:     */
Chris@16:     template<typename Point>
Chris@16:     struct douglas_peucker_point
Chris@16:     {
Chris@16:         Point const& p;
Chris@16:         bool included;
Chris@16: 
Chris@16:         inline douglas_peucker_point(Point const& ap)
Chris@16:             : p(ap)
Chris@16:             , included(false)
Chris@16:         {}
Chris@16: 
Chris@16:         // Necessary for proper compilation
Chris@16:         inline douglas_peucker_point<Point> operator=(douglas_peucker_point<Point> const& )
Chris@16:         {
Chris@16:             return douglas_peucker_point<Point>(*this);
Chris@16:         }
Chris@16:     };
Chris@101: 
Chris@101:     template
Chris@101:     <
Chris@101:         typename Point,
Chris@101:         typename PointDistanceStrategy,
Chris@101:         typename LessCompare
Chris@101:             = std::less
Chris@101:                 <
Chris@101:                     typename strategy::distance::services::return_type
Chris@101:                         <
Chris@101:                             PointDistanceStrategy,
Chris@101:                             Point, Point
Chris@101:                         >::type
Chris@101:                 >
Chris@101:     >
Chris@101:     class douglas_peucker
Chris@101:         : LessCompare // for empty base optimization
Chris@101:     {
Chris@101:     public :
Chris@101: 
Chris@101:         // See also ticket 5954 https://svn.boost.org/trac/boost/ticket/5954
Chris@101:         // Comparable is currently not possible here because it has to be compared to the squared of max_distance, and more.
Chris@101:         // For now we have to take the real distance.
Chris@101:         typedef PointDistanceStrategy distance_strategy_type;
Chris@101:         // typedef typename strategy::distance::services::comparable_type<PointDistanceStrategy>::type distance_strategy_type;
Chris@101: 
Chris@101:         typedef typename strategy::distance::services::return_type
Chris@101:                          <
Chris@101:                              distance_strategy_type,
Chris@101:                              Point, Point
Chris@101:                          >::type distance_type;
Chris@101: 
Chris@101:         douglas_peucker()
Chris@101:         {}
Chris@101: 
Chris@101:         douglas_peucker(LessCompare const& less_compare)
Chris@101:             : LessCompare(less_compare)
Chris@101:         {}
Chris@101: 
Chris@101:     private :
Chris@101:         typedef detail::douglas_peucker_point<Point> dp_point_type;
Chris@101:         typedef typename std::vector<dp_point_type>::iterator iterator_type;
Chris@101: 
Chris@101: 
Chris@101:         LessCompare const& less() const
Chris@101:         {
Chris@101:             return *this;
Chris@101:         }
Chris@101: 
Chris@101:         inline void consider(iterator_type begin,
Chris@101:                              iterator_type end,
Chris@101:                              distance_type const& max_dist,
Chris@101:                              int& n,
Chris@101:                              distance_strategy_type const& ps_distance_strategy) const
Chris@101:         {
Chris@101:             std::size_t size = end - begin;
Chris@101: 
Chris@101:             // size must be at least 3
Chris@101:             // because we want to consider a candidate point in between
Chris@101:             if (size <= 2)
Chris@101:             {
Chris@101: #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
Chris@101:                 if (begin != end)
Chris@101:                 {
Chris@101:                     std::cout << "ignore between " << dsv(begin->p)
Chris@101:                         << " and " << dsv((end - 1)->p)
Chris@101:                         << " size=" << size << std::endl;
Chris@101:                 }
Chris@101:                 std::cout << "return because size=" << size << std::endl;
Chris@101: #endif
Chris@101:                 return;
Chris@101:             }
Chris@101: 
Chris@101:             iterator_type last = end - 1;
Chris@101: 
Chris@101: #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
Chris@101:             std::cout << "find between " << dsv(begin->p)
Chris@101:                 << " and " << dsv(last->p)
Chris@101:                 << " size=" << size << std::endl;
Chris@101: #endif
Chris@101: 
Chris@101: 
Chris@101:             // Find most far point, compare to the current segment
Chris@101:             //geometry::segment<Point const> s(begin->p, last->p);
Chris@101:             distance_type md(-1.0); // any value < 0
Chris@101:             iterator_type candidate;
Chris@101:             for(iterator_type it = begin + 1; it != last; ++it)
Chris@101:             {
Chris@101:                 distance_type dist = ps_distance_strategy.apply(it->p, begin->p, last->p);
Chris@101: 
Chris@101: #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
Chris@101:                 std::cout << "consider " << dsv(it->p)
Chris@101:                     << " at " << double(dist)
Chris@101:                     << ((dist > max_dist) ? " maybe" : " no")
Chris@101:                     << std::endl;
Chris@101: 
Chris@101: #endif
Chris@101:                 if ( less()(md, dist) )
Chris@101:                 {
Chris@101:                     md = dist;
Chris@101:                     candidate = it;
Chris@101:                 }
Chris@101:             }
Chris@101: 
Chris@101:             // If a point is found, set the include flag
Chris@101:             // and handle segments in between recursively
Chris@101:             if ( less()(max_dist, md) )
Chris@101:             {
Chris@101: #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
Chris@101:                 std::cout << "use " << dsv(candidate->p) << std::endl;
Chris@101: #endif
Chris@101: 
Chris@101:                 candidate->included = true;
Chris@101:                 n++;
Chris@101: 
Chris@101:                 consider(begin, candidate + 1, max_dist, n, ps_distance_strategy);
Chris@101:                 consider(candidate, end, max_dist, n, ps_distance_strategy);
Chris@101:             }
Chris@101:         }
Chris@101: 
Chris@101: 
Chris@101:     public :
Chris@101: 
Chris@101:         template <typename Range, typename OutputIterator>
Chris@101:         inline OutputIterator apply(Range const& range,
Chris@101:                                     OutputIterator out,
Chris@101:                                     distance_type max_distance) const
Chris@101:         {
Chris@101: #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
Chris@101:                 std::cout << "max distance: " << max_distance
Chris@101:                           << std::endl << std::endl;
Chris@101: #endif
Chris@101:             distance_strategy_type strategy;
Chris@101: 
Chris@101:             // Copy coordinates, a vector of references to all points
Chris@101:             std::vector<dp_point_type> ref_candidates(boost::begin(range),
Chris@101:                             boost::end(range));
Chris@101: 
Chris@101:             // Include first and last point of line,
Chris@101:             // they are always part of the line
Chris@101:             int n = 2;
Chris@101:             ref_candidates.front().included = true;
Chris@101:             ref_candidates.back().included = true;
Chris@101: 
Chris@101:             // Get points, recursively, including them if they are further away
Chris@101:             // than the specified distance
Chris@101:             consider(boost::begin(ref_candidates), boost::end(ref_candidates), max_distance, n, strategy);
Chris@101: 
Chris@101:             // Copy included elements to the output
Chris@101:             for(typename std::vector<dp_point_type>::const_iterator it
Chris@101:                             = boost::begin(ref_candidates);
Chris@101:                 it != boost::end(ref_candidates);
Chris@101:                 ++it)
Chris@101:             {
Chris@101:                 if (it->included)
Chris@101:                 {
Chris@101:                     // copy-coordinates does not work because OutputIterator
Chris@101:                     // does not model Point (??)
Chris@101:                     //geometry::convert(it->p, *out);
Chris@101:                     *out = it->p;
Chris@101:                     out++;
Chris@101:                 }
Chris@101:             }
Chris@101:             return out;
Chris@101:         }
Chris@101: 
Chris@101:     };
Chris@16: }
Chris@16: #endif // DOXYGEN_NO_DETAIL
Chris@16: 
Chris@16: 
Chris@16: /*!
Chris@16: \brief Implements the simplify algorithm.
Chris@16: \ingroup strategies
Chris@16: \details The douglas_peucker strategy simplifies a linestring, ring or
Chris@16:     vector of points using the well-known Douglas-Peucker algorithm.
Chris@16: \tparam Point the point type
Chris@16: \tparam PointDistanceStrategy point-segment distance strategy to be used
Chris@16: \note This strategy uses itself a point-segment-distance strategy which
Chris@16:     can be specified
Chris@16: \author Barend and Maarten, 1995/1996
Chris@16: \author Barend, revised for Generic Geometry Library, 2008
Chris@16: */
Chris@16: 
Chris@16: /*
Chris@16: For the algorithm, see for example:
Chris@16:  - http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm
Chris@16:  - http://www2.dcs.hull.ac.uk/CISRG/projects/Royal-Inst/demos/dp.html
Chris@16: */
Chris@16: template
Chris@16: <
Chris@16:     typename Point,
Chris@16:     typename PointDistanceStrategy
Chris@16: >
Chris@16: class douglas_peucker
Chris@16: {
Chris@16: public :
Chris@16: 
Chris@16:     typedef PointDistanceStrategy distance_strategy_type;
Chris@16: 
Chris@101:     typedef typename detail::douglas_peucker
Chris@101:         <
Chris@101:             Point,
Chris@101:             PointDistanceStrategy
Chris@101:         >::distance_type distance_type;
Chris@16: 
Chris@16:     template <typename Range, typename OutputIterator>
Chris@16:     static inline OutputIterator apply(Range const& range,
Chris@101:                                        OutputIterator out,
Chris@101:                                        distance_type const& max_distance)
Chris@16:     {
Chris@101:         namespace services = strategy::distance::services;
Chris@16: 
Chris@101:         typedef typename services::comparable_type
Chris@101:             <
Chris@101:                 PointDistanceStrategy
Chris@101:             >::type comparable_distance_strategy_type;
Chris@16: 
Chris@101:         return detail::douglas_peucker
Chris@101:             <
Chris@101:                 Point, comparable_distance_strategy_type
Chris@101:             >().apply(range, out,
Chris@101:                       services::result_from_distance
Chris@101:                           <
Chris@101:                               comparable_distance_strategy_type, Point, Point
Chris@101:                           >::apply(comparable_distance_strategy_type(),
Chris@101:                                    max_distance)
Chris@101:                       );
Chris@16:     }
Chris@16: 
Chris@16: };
Chris@16: 
Chris@16: }} // namespace strategy::simplify
Chris@16: 
Chris@16: 
Chris@16: namespace traits {
Chris@16: 
Chris@16: template <typename P>
Chris@16: struct point_type<strategy::simplify::detail::douglas_peucker_point<P> >
Chris@16: {
Chris@16:     typedef P type;
Chris@16: };
Chris@16: 
Chris@16: } // namespace traits
Chris@16: 
Chris@16: 
Chris@16: }} // namespace boost::geometry
Chris@16: 
Chris@16: #endif // BOOST_GEOMETRY_STRATEGY_AGNOSTIC_SIMPLIFY_DOUGLAS_PEUCKER_HPP