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 const dist = strategy.apply(point, *prev, *it);
  75
  76             // Stop only if we find exactly zero distance
  77             // otherwise it may stop at some very small value and miss the min
  78             if (dist == zero)
  79             {
  80                 dist_min = zero;
  81                 it_min1 = prev;
  82                 it_min2 = it;
  83                 return;
  84             }
  85             else if (dist < dist_min)
  86             {
  87                 dist_min = dist;
  88                 prev_min_dist = prev;
  89             }
  90         }
  91
  92         it_min1 = it_min2 = prev_min_dist;
  93         ++it_min2;
  94     }
  95
  96 public:
  97     typedef typename std::pair<iterator_type, iterator_type> return_type;
  98
  99     template <typename Distance>
 100     static inline return_type apply(Point const& point,
 101                                     iterator_type first,
 102                                     iterator_type last,
 103                                     Strategy const& strategy,
 104                                     Distance& dist_min)
 105     {
 106         iterator_type it_min1, it_min2;
 107         apply(point, first, last, strategy, it_min1, it_min2, dist_min);
 108
 109         return std::make_pair(it_min1, it_min2);
 110     }
 111
 112     static inline return_type apply(Point const& point,
 113                                     iterator_type first,
 114                                     iterator_type last,
 115                                     Strategy const& strategy)
 116     {
 117         typename strategy::distance::services::return_type
 118             <
 119                 Strategy,
 120                 Point,
 121                 typename boost::range_value<Range>::type
 122             >::type dist_min;
 123
 124         return apply(point, first, last, strategy, dist_min);
 125     }
 126
 127     template <typename Distance>
 128     static inline return_type apply(Point const& point,
 129                                     Range const& range,
 130                                     Strategy const& strategy,
 131                                     Distance& dist_min)
 132     {
 133         return apply(point,
 134                      boost::begin(range),
 135                      boost::end(range),
 136                      strategy,
 137                      dist_min);
 138     }
 139
 140     static inline return_type apply(Point const& point,
 141                                     Range const& range,
 142                                     Strategy const& strategy)
 143     {
 144         return apply(point, boost::begin(range), boost::end(range), strategy);
 145     }
 146 };
 147
 148
 149
 150 // specialization for open ranges
 151 template <typename Point, typename Range, typename Strategy>
 152 class point_to_point_range<Point, Range, open, Strategy>
 153     : point_to_point_range<Point, Range, closed, Strategy>
 154 {
 155 private:
 156     typedef point_to_point_range<Point, Range, closed, Strategy> base_type;
 157     typedef typename base_type::iterator_type iterator_type;
 158
 159     template <typename Distance>
 160     static inline void apply(Point const& point,
 161                              iterator_type first,
 162                              iterator_type last,
 163                              Strategy const& strategy,
 164                              iterator_type& it_min1,
 165                              iterator_type& it_min2,
 166                              Distance& dist_min)
 167     {
 168         BOOST_GEOMETRY_ASSERT( first != last );
 169
 170         base_type::apply(point, first, last, strategy,
 171                          it_min1, it_min2, dist_min);
 172
 173         iterator_type it_back = --last;
 174         Distance const zero = Distance(0);
 175         Distance dist = strategy.apply(point, *it_back, *first);
 176
 177         if (geometry::math::equals(dist, zero))
 178         {
 179             dist_min = zero;
 180             it_min1 = it_back;
 181             it_min2 = first;
 182         }
 183         else if (dist < dist_min)
 184         {
 185             dist_min = dist;
 186             it_min1 = it_back;
 187             it_min2 = first;
 188         }
 189     }
 190
 191 public:
 192     typedef typename std::pair<iterator_type, iterator_type> return_type;
 193
 194     template <typename Distance>
 195     static inline return_type apply(Point const& point,
 196                                     iterator_type first,
 197                                     iterator_type last,
 198                                     Strategy const& strategy,
 199                                     Distance& dist_min)
 200     {
 201         iterator_type it_min1, it_min2;
 202
 203         apply(point, first, last, strategy, it_min1, it_min2, dist_min);
 204
 205         return std::make_pair(it_min1, it_min2);
 206     }
 207
 208     static inline return_type apply(Point const& point,
 209                                     iterator_type first,
 210                                     iterator_type last,
 211                                     Strategy const& strategy)
 212     {
 213         typedef typename strategy::distance::services::return_type
 214             <
 215                 Strategy,
 216                 Point,
 217                 typename boost::range_value<Range>::type
 218             >::type distance_return_type;
 219
 220         distance_return_type dist_min;
 221
 222         return apply(point, first, last, strategy, dist_min);
 223     }
 224
 225     template <typename Distance>
 226     static inline return_type apply(Point const& point,
 227                                     Range const& range,
 228                                     Strategy const& strategy,
 229                                     Distance& dist_min)
 230     {
 231         return apply(point,
 232                      boost::begin(range),
 233                      boost::end(range),
 234                      strategy,
 235                      dist_min);
 236     }
 237
 238     static inline return_type apply(Point const& point,
 239                                     Range const& range,
 240                                     Strategy const& strategy)
 241     {
 242         return apply(point, boost::begin(range), boost::end(range), strategy);
 243     }
 244 };
 245
 246
 247 }} // namespace detail::closest_feature
 248 #endif // DOXYGEN_NO_DETAIL
 249
 250 }} // namespace boost::geometry
 251
 252
 253 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_FEATURE_POINT_TO_RANGE_HPP