ceph/src/boost/boost/geometry/strategies/agnostic/hull_graham_andrew.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   4
   5 // This file was modified by Oracle on 2014-2020.
   6 // Modifications copyright (c) 2014-2020 Oracle and/or its affiliates.
   7
   8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   9
  10 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
  11 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
  12
  13 // Use, modification and distribution is subject to the Boost Software License,
  14 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  15 // http://www.boost.org/LICENSE_1_0.txt)
  16
  17 #ifndef BOOST_GEOMETRY_STRATEGIES_AGNOSTIC_CONVEX_GRAHAM_ANDREW_HPP
  18 #define BOOST_GEOMETRY_STRATEGIES_AGNOSTIC_CONVEX_GRAHAM_ANDREW_HPP
  19
  20
  21 #include <cstddef>
  22 #include <algorithm>
  23 #include <vector>
  24
  25 #include <boost/range/begin.hpp>
  26 #include <boost/range/empty.hpp>
  27 #include <boost/range/end.hpp>
  28 #include <boost/range/size.hpp>
  29
  30 #include <boost/geometry/algorithms/detail/for_each_range.hpp>
  31 #include <boost/geometry/core/assert.hpp>
  32 #include <boost/geometry/core/cs.hpp>
  33 #include <boost/geometry/core/point_type.hpp>
  34 #include <boost/geometry/policies/compare.hpp>
  35 #include <boost/geometry/strategies/convex_hull.hpp>
  36 #include <boost/geometry/strategies/side.hpp>
  37 #include <boost/geometry/views/detail/range_type.hpp>
  38
  39
  40 namespace boost { namespace geometry
  41 {
  42
  43 namespace strategy { namespace convex_hull
  44 {
  45
  46 #ifndef DOXYGEN_NO_DETAIL
  47 namespace detail
  48 {
  49
  50
  51 template <typename Geometry, typename Point, typename Less>
  52 inline void get_extremes(Geometry const& geometry,
  53                          Point& left, Point& right,
  54                          Less const& less)
  55 {
  56     bool first = true;
  57     geometry::detail::for_each_range(geometry, [&](auto const& range)
  58     {
  59         if (boost::empty(range))
  60         {
  61             return;
  62         }
  63
  64         // First iterate through this range
  65         // (this two-stage approach avoids many point copies,
  66         //  because iterators are kept in memory. Because iterators are
  67         //  not persistent (in MSVC) this approach is not applicable
  68         //  for more ranges together)
  69
  70         auto left_it = boost::begin(range);
  71         auto right_it = boost::begin(range);
  72
  73         for (auto it = ++boost::begin(range); it != boost::end(range); ++it)
  74         {
  75             if (less(*it, *left_it))
  76             {
  77                 left_it = it;
  78             }
  79
  80             if (less(*right_it, *it))
  81             {
  82                 right_it = it;
  83             }
  84         }
  85
  86         // Then compare with earlier
  87         if (first)
  88         {
  89             // First time, assign left/right
  90             left = *left_it;
  91             right = *right_it;
  92             first = false;
  93         }
  94         else
  95         {
  96             // Next time, check if this range was left/right from
  97             // the extremes already collected
  98             if (less(*left_it, left))
  99             {
 100                 left = *left_it;
 101             }
 102
 103             if (less(right, *right_it))
 104             {
 105                 right = *right_it;
 106             }
 107         }
 108     });
 109 }
 110
 111
 112 template
 113 <
 114     typename Geometry,
 115     typename Point,
 116     typename Container,
 117     typename SideStrategy
 118 >
 119 inline void assign_ranges(Geometry const& geometry,
 120                           Point const& most_left, Point const& most_right,
 121                           Container& lower_points, Container& upper_points,
 122                           SideStrategy const& side)
 123 {
 124     geometry::detail::for_each_range(geometry, [&](auto const& range)
 125     {
 126         // Put points in one of the two output sequences
 127         for (auto it = boost::begin(range); it != boost::end(range); ++it)
 128         {
 129             // check if it is lying most_left or most_right from the line
 130
 131             int dir = side.apply(most_left, most_right, *it);
 132             switch(dir)
 133             {
 134                 case 1 : // left side
 135                     upper_points.push_back(*it);
 136                     break;
 137                 case -1 : // right side
 138                     lower_points.push_back(*it);
 139                     break;
 140
 141                 // 0: on line most_left-most_right,
 142                 //    or most_left, or most_right,
 143                 //    -> all never part of hull
 144             }
 145         }
 146     });
 147 }
 148
 149
 150 template <typename Range, typename Less>
 151 inline void sort(Range& range, Less const& less)
 152 {
 153     std::sort(boost::begin(range), boost::end(range), less);
 154 }
 155
 156 } // namespace detail
 157 #endif // DOXYGEN_NO_DETAIL
 158
 159
 160 /*!
 161 \brief Graham scan strategy to calculate convex hull
 162 \ingroup strategies
 163  */
 164 template <typename InputGeometry, typename OutputPoint>
 165 class graham_andrew
 166 {
 167 public :
 168     typedef OutputPoint point_type;
 169     typedef InputGeometry geometry_type;
 170
 171 private:
 172
 173     typedef typename cs_tag<point_type>::type cs_tag;
 174
 175     typedef typename std::vector<point_type> container_type;
 176     typedef typename std::vector<point_type>::const_iterator iterator;
 177     typedef typename std::vector<point_type>::const_reverse_iterator rev_iterator;
 178
 179
 180     class partitions
 181     {
 182         friend class graham_andrew;
 183
 184         container_type m_lower_hull;
 185         container_type m_upper_hull;
 186         container_type m_copied_input;
 187     };
 188
 189
 190 public:
 191     typedef partitions state_type;
 192
 193
 194     inline void apply(InputGeometry const& geometry, partitions& state) const
 195     {
 196         // First pass.
 197         // Get min/max (in most cases left / right) points
 198         // This makes use of the geometry::less/greater predicates
 199
 200         // For the left boundary it is important that multiple points
 201         // are sorted from bottom to top. Therefore the less predicate
 202         // does not take the x-only template parameter (this fixes ticket #6019.
 203         // For the right boundary it is not necessary (though also not harmful),
 204         // because points are sorted from bottom to top in a later stage.
 205         // For symmetry and to get often more balanced lower/upper halves
 206         // we keep it.
 207
 208         typedef typename geometry::point_type<InputGeometry>::type point_type;
 209
 210         point_type most_left, most_right;
 211
 212         // TODO: User-defined CS-specific less-compare
 213         geometry::less<point_type> less;
 214
 215         detail::get_extremes(geometry, most_left, most_right, less);
 216
 217         container_type lower_points, upper_points;
 218
 219         // TODO: User-defiend CS-specific side strategy
 220         typename strategy::side::services::default_strategy<cs_tag>::type side;
 221
 222         // Bounding left/right points
 223         // Second pass, now that extremes are found, assign all points
 224         // in either lower, either upper
 225         detail::assign_ranges(geometry, most_left, most_right,
 226                               lower_points, upper_points,
 227                               side);
 228
 229         // Sort both collections, first on x(, then on y)
 230         detail::sort(lower_points, less);
 231         detail::sort(upper_points, less);
 232
 233         // And decide which point should be in the final hull
 234         build_half_hull<-1>(lower_points, state.m_lower_hull,
 235                             most_left, most_right,
 236                             side);
 237         build_half_hull<1>(upper_points, state.m_upper_hull,
 238                            most_left, most_right,
 239                            side);
 240     }
 241
 242
 243     template <typename OutputIterator>
 244     inline void result(partitions const& state,
 245                        OutputIterator out,
 246                        bool clockwise,
 247                        bool closed) const
 248     {
 249         if (clockwise)
 250         {
 251             output_ranges(state.m_upper_hull, state.m_lower_hull, out, closed);
 252         }
 253         else
 254         {
 255             output_ranges(state.m_lower_hull, state.m_upper_hull, out, closed);
 256         }
 257     }
 258
 259
 260 private:
 261
 262     template <int Factor, typename SideStrategy>
 263     static inline void build_half_hull(container_type const& input,
 264             container_type& output,
 265             point_type const& left, point_type const& right,
 266             SideStrategy const& side)
 267     {
 268         output.push_back(left);
 269         for(iterator it = input.begin(); it != input.end(); ++it)
 270         {
 271             add_to_hull<Factor>(*it, output, side);
 272         }
 273         add_to_hull<Factor>(right, output, side);
 274     }
 275
 276
 277     template <int Factor, typename SideStrategy>
 278     static inline void add_to_hull(point_type const& p, container_type& output,
 279                                    SideStrategy const& side)
 280     {
 281         output.push_back(p);
 282         std::size_t output_size = output.size();
 283         while (output_size >= 3)
 284         {
 285             rev_iterator rit = output.rbegin();
 286             point_type const last = *rit++;
 287             point_type const& last2 = *rit++;
 288
 289             if (Factor * side.apply(*rit, last, last2) <= 0)
 290             {
 291                 // Remove last two points from stack, and add last again
 292                 // This is much faster then erasing the one but last.
 293                 output.pop_back();
 294                 output.pop_back();
 295                 output.push_back(last);
 296                 output_size--;
 297             }
 298             else
 299             {
 300                 return;
 301             }
 302         }
 303     }
 304
 305
 306     template <typename OutputIterator>
 307     static inline void output_ranges(container_type const& first, container_type const& second,
 308                                      OutputIterator out, bool closed)
 309     {
 310         std::copy(boost::begin(first), boost::end(first), out);
 311
 312         BOOST_GEOMETRY_ASSERT(closed ? !boost::empty(second) : boost::size(second) > 1);
 313         std::copy(++boost::rbegin(second), // skip the first Point
 314                   closed ? boost::rend(second) : --boost::rend(second), // skip the last Point if open
 315                   out);
 316
 317         typedef typename boost::range_size<container_type>::type size_type;
 318         size_type const count = boost::size(first) + boost::size(second) - 1;
 319         // count describes a closed case but comparison with min size of closed
 320         // gives the result compatible also with open
 321         // here core_detail::closure::minimum_ring_size<closed> could be used
 322         if (count < 4)
 323         {
 324             // there should be only one missing
 325             *out++ = *boost::begin(first);
 326         }
 327     }
 328 };
 329
 330 }} // namespace strategy::convex_hull
 331
 332
 333 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
 334 template <typename InputGeometry, typename OutputPoint>
 335 struct strategy_convex_hull<InputGeometry, OutputPoint, cartesian_tag>
 336 {
 337     typedef strategy::convex_hull::graham_andrew<InputGeometry, OutputPoint> type;
 338 };
 339 #endif
 340
 341 }} // namespace boost::geometry
 342
 343
 344 #endif // BOOST_GEOMETRY_STRATEGIES_AGNOSTIC_CONVEX_GRAHAM_ANDREW_HPP