ceph/src/boost/boost/geometry/algorithms/detail/closest_feature/point_to_range.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2014, Oracle and/or its affiliates.
   4
   5 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
   6
   7 // Licensed under the Boost Software License version 1.0.
   8 // http://www.boost.org/users/license.html
   9
  10 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_FEATURE_POINT_TO_RANGE_HPP
  11 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_FEATURE_POINT_TO_RANGE_HPP
  12
  13 #include <utility>
  14
  15 #include <boost/range.hpp>
  16
  17 #include <boost/geometry/core/assert.hpp>
  18 #include <boost/geometry/core/closure.hpp>
  19 #include <boost/geometry/strategies/distance.hpp>
  20 #include <boost/geometry/util/math.hpp>
  21
  22
  23 namespace boost { namespace geometry
  24 {
  25
  26 #ifndef DOXYGEN_NO_DETAIL
  27 namespace detail { namespace closest_feature
  28 {
  29
  30
  31 // returns the segment (pair of iterators) that realizes the closest
  32 // distance of the point to the range
  33 template
  34 <
  35     typename Point,
  36     typename Range,
  37     closure_selector Closure,
  38     typename Strategy
  39 >
  40 class point_to_point_range
  41 {
  42 protected:
  43     typedef typename boost::range_iterator<Range const>::type iterator_type;
  44
  45     template <typename Distance>
  46     static inline void apply(Point const& point,
  47                              iterator_type first,
  48                              iterator_type last,
  49                              Strategy const& strategy,
  50                              iterator_type& it_min1,
  51                              iterator_type& it_min2,
  52                              Distance& dist_min)
  53     {
  54         BOOST_GEOMETRY_ASSERT( first != last );
  55
  56         Distance const zero = Distance(0);
  57
  58         iterator_type it = first;
  59         iterator_type prev = it++;
  60         if (it == last)
  61         {
  62             it_min1 = it_min2 = first;
  63             dist_min = strategy.apply(point, *first, *first);
  64             return;
  65         }
  66
  67         // start with first segment distance
  68         dist_min = strategy.apply(point, *prev, *it);
  69         iterator_type prev_min_dist = prev;
  70
  71         // check if other segments are closer
  72         for (++prev, ++it; it != last; ++prev, ++it)
  73         {
  74             Distance dist = strategy.apply(point, *prev, *it);
  75             if (geometry::math::equals(dist, zero))
  76             {
  77                 dist_min = zero;
  78                 it_min1 = prev;
  79                 it_min2 = it;
  80                 return;
  81             }
  82             else if (dist < dist_min)
  83             {
  84                 dist_min = dist;
  85                 prev_min_dist = prev;
  86             }
  87         }
  88
  89         it_min1 = it_min2 = prev_min_dist;
  90         ++it_min2;
  91     }
  92
  93 public:
  94     typedef typename std::pair<iterator_type, iterator_type> return_type;
  95
  96     template <typename Distance>
  97     static inline return_type apply(Point const& point,
  98                                     iterator_type first,
  99                                     iterator_type last,
 100                                     Strategy const& strategy,
 101                                     Distance& dist_min)
 102     {
 103         iterator_type it_min1, it_min2;
 104         apply(point, first, last, strategy, it_min1, it_min2, dist_min);
 105
 106         return std::make_pair(it_min1, it_min2);
 107     }
 108
 109     static inline return_type apply(Point const& point,
 110                                     iterator_type first,
 111                                     iterator_type last,
 112                                     Strategy const& strategy)
 113     {
 114         typename strategy::distance::services::return_type
 115             <
 116                 Strategy,
 117                 Point,
 118                 typename boost::range_value<Range>::type
 119             >::type dist_min;
 120
 121         return apply(point, first, last, strategy, dist_min);
 122     }
 123
 124     template <typename Distance>
 125     static inline return_type apply(Point const& point,
 126                                     Range const& range,
 127                                     Strategy const& strategy,
 128                                     Distance& dist_min)
 129     {
 130         return apply(point,
 131                      boost::begin(range),
 132                      boost::end(range),
 133                      strategy,
 134                      dist_min);
 135     }
 136
 137     static inline return_type apply(Point const& point,
 138                                     Range const& range,
 139                                     Strategy const& strategy)
 140     {
 141         return apply(point, boost::begin(range), boost::end(range), strategy);
 142     }
 143 };
 144
 145
 146
 147 // specialization for open ranges
 148 template <typename Point, typename Range, typename Strategy>
 149 class point_to_point_range<Point, Range, open, Strategy>
 150     : point_to_point_range<Point, Range, closed, Strategy>
 151 {
 152 private:
 153     typedef point_to_point_range<Point, Range, closed, Strategy> base_type;
 154     typedef typename base_type::iterator_type iterator_type;
 155
 156     template <typename Distance>
 157     static inline void apply(Point const& point,
 158                              iterator_type first,
 159                              iterator_type last,
 160                              Strategy const& strategy,
 161                              iterator_type& it_min1,
 162                              iterator_type& it_min2,
 163                              Distance& dist_min)
 164     {
 165         BOOST_GEOMETRY_ASSERT( first != last );
 166
 167         base_type::apply(point, first, last, strategy,
 168                          it_min1, it_min2, dist_min);
 169
 170         iterator_type it_back = --last;
 171         Distance const zero = Distance(0);
 172         Distance dist = strategy.apply(point, *it_back, *first);
 173
 174         if (geometry::math::equals(dist, zero))
 175         {
 176             dist_min = zero;
 177             it_min1 = it_back;
 178             it_min2 = first;
 179         }
 180         else if (dist < dist_min)
 181         {
 182             dist_min = dist;
 183             it_min1 = it_back;
 184             it_min2 = first;
 185         }
 186     }
 187
 188 public:
 189     typedef typename std::pair<iterator_type, iterator_type> return_type;
 190
 191     template <typename Distance>
 192     static inline return_type apply(Point const& point,
 193                                     iterator_type first,
 194                                     iterator_type last,
 195                                     Strategy const& strategy,
 196                                     Distance& dist_min)
 197     {
 198         iterator_type it_min1, it_min2;
 199
 200         apply(point, first, last, strategy, it_min1, it_min2, dist_min);
 201
 202         return std::make_pair(it_min1, it_min2);
 203     }
 204
 205     static inline return_type apply(Point const& point,
 206                                     iterator_type first,
 207                                     iterator_type last,
 208                                     Strategy const& strategy)
 209     {
 210         typedef typename strategy::distance::services::return_type
 211             <
 212                 Strategy,
 213                 Point,
 214                 typename boost::range_value<Range>::type
 215             >::type distance_return_type;
 216
 217         distance_return_type dist_min;
 218
 219         return apply(point, first, last, strategy, dist_min);
 220     }
 221
 222     template <typename Distance>
 223     static inline return_type apply(Point const& point,
 224                                     Range const& range,
 225                                     Strategy const& strategy,
 226                                     Distance& dist_min)
 227     {
 228         return apply(point,
 229                      boost::begin(range),
 230                      boost::end(range),
 231                      strategy,
 232                      dist_min);
 233     }
 234
 235     static inline return_type apply(Point const& point,
 236                                     Range const& range,
 237                                     Strategy const& strategy)
 238     {
 239         return apply(point, boost::begin(range), boost::end(range), strategy);
 240     }
 241 };
 242
 243
 244 }} // namespace detail::closest_feature
 245 #endif // DOXYGEN_NO_DETAIL
 246
 247 }} // namespace boost::geometry
 248
 249
 250 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_FEATURE_POINT_TO_RANGE_HPP