ceph/src/boost/libs/geometry/include/boost/geometry/strategies/agnostic/simplify_douglas_peucker.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 1995, 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 1995 Maarten Hilferink, Amsterdam, the Netherlands
   5
   6 // This file was modified by Oracle on 2015.
   7 // Modifications copyright (c) 2015, Oracle and/or its affiliates.
   8
   9 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
  10
  11 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
  12 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
  13
  14 // Use, modification and distribution is subject to the Boost Software License,
  15 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  16 // http://www.boost.org/LICENSE_1_0.txt)
  17
  18 #ifndef BOOST_GEOMETRY_STRATEGY_AGNOSTIC_SIMPLIFY_DOUGLAS_PEUCKER_HPP
  19 #define BOOST_GEOMETRY_STRATEGY_AGNOSTIC_SIMPLIFY_DOUGLAS_PEUCKER_HPP
  20
  21
  22 #include <cstddef>
  23 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
  24 #include <iostream>
  25 #endif
  26 #include <vector>
  27
  28 #include <boost/range.hpp>
  29
  30 #include <boost/geometry/core/cs.hpp>
  31 #include <boost/geometry/strategies/distance.hpp>
  32
  33
  34 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
  35 #include <boost/geometry/io/dsv/write.hpp>
  36 #endif
  37
  38
  39 namespace boost { namespace geometry
  40 {
  41
  42 namespace strategy { namespace simplify
  43 {
  44
  45
  46 #ifndef DOXYGEN_NO_DETAIL
  47 namespace detail
  48 {
  49
  50     /*!
  51         \brief Small wrapper around a point, with an extra member "included"
  52         \details
  53             It has a const-reference to the original point (so no copy here)
  54         \tparam the enclosed point type
  55     */
  56     template<typename Point>
  57     struct douglas_peucker_point
  58     {
  59         Point const& p;
  60         bool included;
  61
  62         inline douglas_peucker_point(Point const& ap)
  63             : p(ap)
  64             , included(false)
  65         {}
  66
  67         // Necessary for proper compilation
  68         inline douglas_peucker_point<Point> operator=(douglas_peucker_point<Point> const& )
  69         {
  70             return douglas_peucker_point<Point>(*this);
  71         }
  72     };
  73
  74     template
  75     <
  76         typename Point,
  77         typename PointDistanceStrategy,
  78         typename LessCompare
  79             = std::less
  80                 <
  81                     typename strategy::distance::services::return_type
  82                         <
  83                             PointDistanceStrategy,
  84                             Point, Point
  85                         >::type
  86                 >
  87     >
  88     class douglas_peucker
  89         : LessCompare // for empty base optimization
  90     {
  91     public :
  92
  93         // See also ticket 5954 https://svn.boost.org/trac/boost/ticket/5954
  94         // Comparable is currently not possible here because it has to be compared to the squared of max_distance, and more.
  95         // For now we have to take the real distance.
  96         typedef PointDistanceStrategy distance_strategy_type;
  97         // typedef typename strategy::distance::services::comparable_type<PointDistanceStrategy>::type distance_strategy_type;
  98
  99         typedef typename strategy::distance::services::return_type
 100                          <
 101                              distance_strategy_type,
 102                              Point, Point
 103                          >::type distance_type;
 104
 105         douglas_peucker()
 106         {}
 107
 108         douglas_peucker(LessCompare const& less_compare)
 109             : LessCompare(less_compare)
 110         {}
 111
 112     private :
 113         typedef detail::douglas_peucker_point<Point> dp_point_type;
 114         typedef typename std::vector<dp_point_type>::iterator iterator_type;
 115
 116
 117         LessCompare const& less() const
 118         {
 119             return *this;
 120         }
 121
 122         inline void consider(iterator_type begin,
 123                              iterator_type end,
 124                              distance_type const& max_dist,
 125                              int& n,
 126                              distance_strategy_type const& ps_distance_strategy) const
 127         {
 128             std::size_t size = end - begin;
 129
 130             // size must be at least 3
 131             // because we want to consider a candidate point in between
 132             if (size <= 2)
 133             {
 134 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
 135                 if (begin != end)
 136                 {
 137                     std::cout << "ignore between " << dsv(begin->p)
 138                         << " and " << dsv((end - 1)->p)
 139                         << " size=" << size << std::endl;
 140                 }
 141                 std::cout << "return because size=" << size << std::endl;
 142 #endif
 143                 return;
 144             }
 145
 146             iterator_type last = end - 1;
 147
 148 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
 149             std::cout << "find between " << dsv(begin->p)
 150                 << " and " << dsv(last->p)
 151                 << " size=" << size << std::endl;
 152 #endif
 153
 154
 155             // Find most far point, compare to the current segment
 156             //geometry::segment<Point const> s(begin->p, last->p);
 157             distance_type md(-1.0); // any value < 0
 158             iterator_type candidate;
 159             for(iterator_type it = begin + 1; it != last; ++it)
 160             {
 161                 distance_type dist = ps_distance_strategy.apply(it->p, begin->p, last->p);
 162
 163 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
 164                 std::cout << "consider " << dsv(it->p)
 165                     << " at " << double(dist)
 166                     << ((dist > max_dist) ? " maybe" : " no")
 167                     << std::endl;
 168
 169 #endif
 170                 if ( less()(md, dist) )
 171                 {
 172                     md = dist;
 173                     candidate = it;
 174                 }
 175             }
 176
 177             // If a point is found, set the include flag
 178             // and handle segments in between recursively
 179             if ( less()(max_dist, md) )
 180             {
 181 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
 182                 std::cout << "use " << dsv(candidate->p) << std::endl;
 183 #endif
 184
 185                 candidate->included = true;
 186                 n++;
 187
 188                 consider(begin, candidate + 1, max_dist, n, ps_distance_strategy);
 189                 consider(candidate, end, max_dist, n, ps_distance_strategy);
 190             }
 191         }
 192
 193
 194     public :
 195
 196         template <typename Range, typename OutputIterator>
 197         inline OutputIterator apply(Range const& range,
 198                                     OutputIterator out,
 199                                     distance_type max_distance) const
 200         {
 201 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
 202                 std::cout << "max distance: " << max_distance
 203                           << std::endl << std::endl;
 204 #endif
 205             distance_strategy_type strategy;
 206
 207             // Copy coordinates, a vector of references to all points
 208             std::vector<dp_point_type> ref_candidates(boost::begin(range),
 209                             boost::end(range));
 210
 211             // Include first and last point of line,
 212             // they are always part of the line
 213             int n = 2;
 214             ref_candidates.front().included = true;
 215             ref_candidates.back().included = true;
 216
 217             // Get points, recursively, including them if they are further away
 218             // than the specified distance
 219             consider(boost::begin(ref_candidates), boost::end(ref_candidates), max_distance, n, strategy);
 220
 221             // Copy included elements to the output
 222             for(typename std::vector<dp_point_type>::const_iterator it
 223                             = boost::begin(ref_candidates);
 224                 it != boost::end(ref_candidates);
 225                 ++it)
 226             {
 227                 if (it->included)
 228                 {
 229                     // copy-coordinates does not work because OutputIterator
 230                     // does not model Point (??)
 231                     //geometry::convert(it->p, *out);
 232                     *out = it->p;
 233                     out++;
 234                 }
 235             }
 236             return out;
 237         }
 238
 239     };
 240 }
 241 #endif // DOXYGEN_NO_DETAIL
 242
 243
 244 /*!
 245 \brief Implements the simplify algorithm.
 246 \ingroup strategies
 247 \details The douglas_peucker strategy simplifies a linestring, ring or
 248     vector of points using the well-known Douglas-Peucker algorithm.
 249 \tparam Point the point type
 250 \tparam PointDistanceStrategy point-segment distance strategy to be used
 251 \note This strategy uses itself a point-segment-distance strategy which
 252     can be specified
 253 \author Barend and Maarten, 1995/1996
 254 \author Barend, revised for Generic Geometry Library, 2008
 255 */
 256
 257 /*
 258 For the algorithm, see for example:
 259  - http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm
 260  - http://www2.dcs.hull.ac.uk/CISRG/projects/Royal-Inst/demos/dp.html
 261 */
 262 template
 263 <
 264     typename Point,
 265     typename PointDistanceStrategy
 266 >
 267 class douglas_peucker
 268 {
 269 public :
 270
 271     typedef PointDistanceStrategy distance_strategy_type;
 272
 273     typedef typename detail::douglas_peucker
 274         <
 275             Point,
 276             PointDistanceStrategy
 277         >::distance_type distance_type;
 278
 279     template <typename Range, typename OutputIterator>
 280     static inline OutputIterator apply(Range const& range,
 281                                        OutputIterator out,
 282                                        distance_type const& max_distance)
 283     {
 284         namespace services = strategy::distance::services;
 285
 286         typedef typename services::comparable_type
 287             <
 288                 PointDistanceStrategy
 289             >::type comparable_distance_strategy_type;
 290
 291         return detail::douglas_peucker
 292             <
 293                 Point, comparable_distance_strategy_type
 294             >().apply(range, out,
 295                       services::result_from_distance
 296                           <
 297                               comparable_distance_strategy_type, Point, Point
 298                           >::apply(comparable_distance_strategy_type(),
 299                                    max_distance)
 300                       );
 301     }
 302
 303 };
 304
 305 }} // namespace strategy::simplify
 306
 307
 308 namespace traits {
 309
 310 template <typename P>
 311 struct point_type<geometry::strategy::simplify::detail::douglas_peucker_point<P> >
 312 {
 313     typedef P type;
 314 };
 315
 316 } // namespace traits
 317
 318
 319 }} // namespace boost::geometry
 320
 321 #endif // BOOST_GEOMETRY_STRATEGY_AGNOSTIC_SIMPLIFY_DOUGLAS_PEUCKER_HPP