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> apply(Point const & point,iterator_type first,iterator_type last,Strategy const & strategy,iterator_type & it_min1,iterator_type & it_min2,Distance & dist_min)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> apply(Point const & point,iterator_type first,iterator_type last,Strategy const & strategy,Distance & dist_min)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 apply(Point const & point,iterator_type first,iterator_type last,Strategy const & strategy)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> apply(Point const & point,Range const & range,Strategy const & strategy,Distance & dist_min)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 apply(Point const & point,Range const & range,Strategy const & strategy)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> apply(Point const & point,iterator_type first,iterator_type last,Strategy const & strategy,iterator_type & it_min1,iterator_type & it_min2,Distance & dist_min)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> apply(Point const & point,iterator_type first,iterator_type last,Strategy const & strategy,Distance & dist_min)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 apply(Point const & point,iterator_type first,iterator_type last,Strategy const & strategy)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> apply(Point const & point,Range const & range,Strategy const & strategy,Distance & dist_min)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 apply(Point const & point,Range const & range,Strategy const & strategy)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 254