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