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