detail/closest_feature/point_to_range.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2014-2021, Oracle and/or its affiliates.
0004 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0005 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0006
0007 // Licensed under the Boost Software License version 1.0.
0008 // http://www.boost.org/users/license.html
0009
0010 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_FEATURE_POINT_TO_RANGE_HPP
0011 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_FEATURE_POINT_TO_RANGE_HPP
0012
0013 #include <utility>
0014
0015 #include <boost/range/begin.hpp>
0016 #include <boost/range/end.hpp>
0017
0018 #include <boost/geometry/core/assert.hpp>
0019 #include <boost/geometry/core/closure.hpp>
0020 #include <boost/geometry/strategies/distance.hpp>
0021 #include <boost/geometry/util/math.hpp>
0022
0023
0024 namespace boost { namespace geometry
0025 {
0026
0027 #ifndef DOXYGEN_NO_DETAIL
0028 namespace detail { namespace closest_feature
0029 {
0030
0031
0032 // returns the segment (pair of iterators) that realizes the closest
0033 // distance of the point to the range
0034 template
0035 <
0036     typename Point,
0037     typename Range,
0038     closure_selector Closure
0039 >
0040 class point_to_point_range
0041 {
0042 protected:
0043     typedef typename boost::range_iterator<Range const>::type iterator_type;
0044
0045     template <typename Strategy, typename Distance>
0046     static inline void apply(Point const& point,
0047                              iterator_type first,
0048                              iterator_type last,
0049                              Strategy const& strategy,
0050                              iterator_type& it_min1,
0051                              iterator_type& it_min2,
0052                              Distance& dist_min)
0053     {
0054         BOOST_GEOMETRY_ASSERT( first != last );
0055
0056         Distance const zero = Distance(0);
0057
0058         iterator_type it = first;
0059         iterator_type prev = it++;
0060         if (it == last)
0061         {
0062             it_min1 = it_min2 = first;
0063             dist_min = strategy.apply(point, *first, *first);
0064             return;
0065         }
0066
0067         // start with first segment distance
0068         dist_min = strategy.apply(point, *prev, *it);
0069         iterator_type prev_min_dist = prev;
0070
0071         // check if other segments are closer
0072         for (++prev, ++it; it != last; ++prev, ++it)
0073         {
0074             Distance const dist = strategy.apply(point, *prev, *it);
0075
0076             // Stop only if we find exactly zero distance
0077             // otherwise it may stop at some very small value and miss the min
0078             if (dist == zero)
0079             {
0080                 dist_min = zero;
0081                 it_min1 = prev;
0082                 it_min2 = it;
0083                 return;
0084             }
0085             else if (dist < dist_min)
0086             {
0087                 dist_min = dist;
0088                 prev_min_dist = prev;
0089             }
0090         }
0091
0092         it_min1 = it_min2 = prev_min_dist;
0093         ++it_min2;
0094     }
0095
0096 public:
0097     typedef typename std::pair<iterator_type, iterator_type> return_type;
0098
0099     template <typename Strategy, typename Distance>
0100     static inline return_type apply(Point const& point,
0101                                     iterator_type first,
0102                                     iterator_type last,
0103                                     Strategy const& strategy,
0104                                     Distance& dist_min)
0105     {
0106         iterator_type it_min1, it_min2;
0107         apply(point, first, last, strategy, it_min1, it_min2, dist_min);
0108
0109         return std::make_pair(it_min1, it_min2);
0110     }
0111
0112     template <typename Strategy>
0113     static inline return_type apply(Point const& point,
0114                                     iterator_type first,
0115                                     iterator_type last,
0116                                     Strategy const& strategy)
0117     {
0118         typename strategy::distance::services::return_type
0119             <
0120                 Strategy,
0121                 Point,
0122                 typename boost::range_value<Range>::type
0123             >::type dist_min;
0124
0125         return apply(point, first, last, strategy, dist_min);
0126     }
0127
0128     template <typename Strategy, typename Distance>
0129     static inline return_type apply(Point const& point,
0130                                     Range const& range,
0131                                     Strategy const& strategy,
0132                                     Distance& dist_min)
0133     {
0134         return apply(point,
0135                      boost::begin(range),
0136                      boost::end(range),
0137                      strategy,
0138                      dist_min);
0139     }
0140
0141     template <typename Strategy>
0142     static inline return_type apply(Point const& point,
0143                                     Range const& range,
0144                                     Strategy const& strategy)
0145     {
0146         return apply(point, boost::begin(range), boost::end(range), strategy);
0147     }
0148 };
0149
0150
0151
0152 // specialization for open ranges
0153 template <typename Point, typename Range>
0154 class point_to_point_range<Point, Range, open>
0155     : point_to_point_range<Point, Range, closed>
0156 {
0157 private:
0158     typedef point_to_point_range<Point, Range, closed> base_type;
0159     typedef typename base_type::iterator_type iterator_type;
0160
0161     template <typename Strategy, typename Distance>
0162     static inline void apply(Point const& point,
0163                              iterator_type first,
0164                              iterator_type last,
0165                              Strategy const& strategy,
0166                              iterator_type& it_min1,
0167                              iterator_type& it_min2,
0168                              Distance& dist_min)
0169     {
0170         BOOST_GEOMETRY_ASSERT( first != last );
0171
0172         base_type::apply(point, first, last, strategy,
0173                          it_min1, it_min2, dist_min);
0174
0175         iterator_type it_back = --last;
0176         Distance const zero = Distance(0);
0177         Distance dist = strategy.apply(point, *it_back, *first);
0178
0179         if (geometry::math::equals(dist, zero))
0180         {
0181             dist_min = zero;
0182             it_min1 = it_back;
0183             it_min2 = first;
0184         }
0185         else if (dist < dist_min)
0186         {
0187             dist_min = dist;
0188             it_min1 = it_back;
0189             it_min2 = first;
0190         }
0191     }
0192
0193 public:
0194     typedef typename std::pair<iterator_type, iterator_type> return_type;
0195
0196     template <typename Strategy, typename Distance>
0197     static inline return_type apply(Point const& point,
0198                                     iterator_type first,
0199                                     iterator_type last,
0200                                     Strategy const& strategy,
0201                                     Distance& dist_min)
0202     {
0203         iterator_type it_min1, it_min2;
0204
0205         apply(point, first, last, strategy, it_min1, it_min2, dist_min);
0206
0207         return std::make_pair(it_min1, it_min2);
0208     }
0209
0210     template <typename Strategy>
0211     static inline return_type apply(Point const& point,
0212                                     iterator_type first,
0213                                     iterator_type last,
0214                                     Strategy const& strategy)
0215     {
0216         typedef typename strategy::distance::services::return_type
0217             <
0218                 Strategy,
0219                 Point,
0220                 typename boost::range_value<Range>::type
0221             >::type distance_return_type;
0222
0223         distance_return_type dist_min;
0224
0225         return apply(point, first, last, strategy, dist_min);
0226     }
0227
0228     template <typename Strategy, typename Distance>
0229     static inline return_type apply(Point const& point,
0230                                     Range const& range,
0231                                     Strategy const& strategy,
0232                                     Distance& dist_min)
0233     {
0234         return apply(point,
0235                      boost::begin(range),
0236                      boost::end(range),
0237                      strategy,
0238                      dist_min);
0239     }
0240
0241     template <typename Strategy>
0242     static inline return_type apply(Point const& point,
0243                                     Range const& range,
0244                                     Strategy const& strategy)
0245     {
0246         return apply(point, boost::begin(range), boost::end(range), strategy);
0247     }
0248 };
0249
0250
0251 }} // namespace detail::closest_feature
0252 #endif // DOXYGEN_NO_DETAIL
0253
0254 }} // namespace boost::geometry
0255
0256
0257 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_FEATURE_POINT_TO_RANGE_HPP