123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321 |
- // 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<geometry::strategy::simplify::detail::douglas_peucker_point<P> >
- {
- typedef P type;
- };
- } // namespace traits
- }} // namespace boost::geometry
- #endif // BOOST_GEOMETRY_STRATEGY_AGNOSTIC_SIMPLIFY_DOUGLAS_PEUCKER_HPP
|