123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253 |
- // Boost.Geometry (aka GGL, Generic Geometry Library)
- // Copyright (c) 2014, Oracle and/or its affiliates.
- // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
- // Licensed under the Boost Software License version 1.0.
- // http://www.boost.org/users/license.html
- #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_FEATURE_POINT_TO_RANGE_HPP
- #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_FEATURE_POINT_TO_RANGE_HPP
- #include <utility>
- #include <boost/range.hpp>
- #include <boost/geometry/core/assert.hpp>
- #include <boost/geometry/core/closure.hpp>
- #include <boost/geometry/strategies/distance.hpp>
- #include <boost/geometry/util/math.hpp>
- namespace boost { namespace geometry
- {
- #ifndef DOXYGEN_NO_DETAIL
- namespace detail { namespace closest_feature
- {
- // returns the segment (pair of iterators) that realizes the closest
- // distance of the point to the range
- template
- <
- typename Point,
- typename Range,
- closure_selector Closure,
- typename Strategy
- >
- class point_to_point_range
- {
- protected:
- typedef typename boost::range_iterator<Range const>::type iterator_type;
- template <typename Distance>
- static inline void apply(Point const& point,
- iterator_type first,
- iterator_type last,
- Strategy const& strategy,
- iterator_type& it_min1,
- iterator_type& it_min2,
- Distance& dist_min)
- {
- BOOST_GEOMETRY_ASSERT( first != last );
- Distance const zero = Distance(0);
- iterator_type it = first;
- iterator_type prev = it++;
- if (it == last)
- {
- it_min1 = it_min2 = first;
- dist_min = strategy.apply(point, *first, *first);
- return;
- }
- // start with first segment distance
- dist_min = strategy.apply(point, *prev, *it);
- iterator_type prev_min_dist = prev;
- // check if other segments are closer
- for (++prev, ++it; it != last; ++prev, ++it)
- {
- Distance const dist = strategy.apply(point, *prev, *it);
- // Stop only if we find exactly zero distance
- // otherwise it may stop at some very small value and miss the min
- if (dist == zero)
- {
- dist_min = zero;
- it_min1 = prev;
- it_min2 = it;
- return;
- }
- else if (dist < dist_min)
- {
- dist_min = dist;
- prev_min_dist = prev;
- }
- }
- it_min1 = it_min2 = prev_min_dist;
- ++it_min2;
- }
- public:
- typedef typename std::pair<iterator_type, iterator_type> return_type;
- template <typename Distance>
- static inline return_type apply(Point const& point,
- iterator_type first,
- iterator_type last,
- Strategy const& strategy,
- Distance& dist_min)
- {
- iterator_type it_min1, it_min2;
- apply(point, first, last, strategy, it_min1, it_min2, dist_min);
- return std::make_pair(it_min1, it_min2);
- }
- static inline return_type apply(Point const& point,
- iterator_type first,
- iterator_type last,
- Strategy const& strategy)
- {
- typename strategy::distance::services::return_type
- <
- Strategy,
- Point,
- typename boost::range_value<Range>::type
- >::type dist_min;
- return apply(point, first, last, strategy, dist_min);
- }
- template <typename Distance>
- static inline return_type apply(Point const& point,
- Range const& range,
- Strategy const& strategy,
- Distance& dist_min)
- {
- return apply(point,
- boost::begin(range),
- boost::end(range),
- strategy,
- dist_min);
- }
- static inline return_type apply(Point const& point,
- Range const& range,
- Strategy const& strategy)
- {
- return apply(point, boost::begin(range), boost::end(range), strategy);
- }
- };
- // specialization for open ranges
- template <typename Point, typename Range, typename Strategy>
- class point_to_point_range<Point, Range, open, Strategy>
- : point_to_point_range<Point, Range, closed, Strategy>
- {
- private:
- typedef point_to_point_range<Point, Range, closed, Strategy> base_type;
- typedef typename base_type::iterator_type iterator_type;
- template <typename Distance>
- static inline void apply(Point const& point,
- iterator_type first,
- iterator_type last,
- Strategy const& strategy,
- iterator_type& it_min1,
- iterator_type& it_min2,
- Distance& dist_min)
- {
- BOOST_GEOMETRY_ASSERT( first != last );
- base_type::apply(point, first, last, strategy,
- it_min1, it_min2, dist_min);
- iterator_type it_back = --last;
- Distance const zero = Distance(0);
- Distance dist = strategy.apply(point, *it_back, *first);
- if (geometry::math::equals(dist, zero))
- {
- dist_min = zero;
- it_min1 = it_back;
- it_min2 = first;
- }
- else if (dist < dist_min)
- {
- dist_min = dist;
- it_min1 = it_back;
- it_min2 = first;
- }
- }
- public:
- typedef typename std::pair<iterator_type, iterator_type> return_type;
- template <typename Distance>
- static inline return_type apply(Point const& point,
- iterator_type first,
- iterator_type last,
- Strategy const& strategy,
- Distance& dist_min)
- {
- iterator_type it_min1, it_min2;
- apply(point, first, last, strategy, it_min1, it_min2, dist_min);
- return std::make_pair(it_min1, it_min2);
- }
- static inline return_type apply(Point const& point,
- iterator_type first,
- iterator_type last,
- Strategy const& strategy)
- {
- typedef typename strategy::distance::services::return_type
- <
- Strategy,
- Point,
- typename boost::range_value<Range>::type
- >::type distance_return_type;
- distance_return_type dist_min;
- return apply(point, first, last, strategy, dist_min);
- }
- template <typename Distance>
- static inline return_type apply(Point const& point,
- Range const& range,
- Strategy const& strategy,
- Distance& dist_min)
- {
- return apply(point,
- boost::begin(range),
- boost::end(range),
- strategy,
- dist_min);
- }
- static inline return_type apply(Point const& point,
- Range const& range,
- Strategy const& strategy)
- {
- return apply(point, boost::begin(range), boost::end(range), strategy);
- }
- };
- }} // namespace detail::closest_feature
- #endif // DOXYGEN_NO_DETAIL
- }} // namespace boost::geometry
- #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_FEATURE_POINT_TO_RANGE_HPP
|