detail/closest_feature/range_to_range.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2014, 2019, Oracle and/or its affiliates.
0004
0005 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0006 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0007
0008 // Licensed under the Boost Software License version 1.0.
0009 // http://www.boost.org/users/license.html
0010
0011 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_FEATURE_RANGE_TO_RANGE_HPP
0012 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_FEATURE_RANGE_TO_RANGE_HPP
0013
0014 #include <cstddef>
0015
0016 #include <iterator>
0017 #include <utility>
0018
0019 #include <boost/geometry/core/assert.hpp>
0020 #include <boost/geometry/core/point_type.hpp>
0021 #include <boost/geometry/strategies/distance.hpp>
0022 #include <boost/geometry/algorithms/dispatch/distance.hpp>
0023 #include <boost/geometry/index/rtree.hpp>
0024
0025
0026 namespace boost { namespace geometry
0027 {
0028
0029 #ifndef DOXYGEN_NO_DETAIL
0030 namespace detail { namespace closest_feature
0031 {
0032
0033
0034 // returns a pair of a objects where the first is an object of the
0035 // r-tree range and the second an object of the query range that
0036 // realizes the closest feature of the two ranges
0037 class range_to_range_rtree
0038 {
0039 private:
0040     template
0041     <
0042         typename RTreeRangeIterator,
0043         typename QueryRangeIterator,
0044         typename Strategies,
0045         typename RTreeValueType,
0046         typename Distance
0047     >
0048     static inline void apply(RTreeRangeIterator rtree_first,
0049                              RTreeRangeIterator rtree_last,
0050                              QueryRangeIterator queries_first,
0051                              QueryRangeIterator queries_last,
0052                              Strategies const& strategies,
0053                              RTreeValueType& rtree_min,
0054                              QueryRangeIterator& qit_min,
0055                              Distance& dist_min)
0056     {
0057         typedef index::parameters
0058             <
0059                 index::linear<8>, Strategies
0060             > index_parameters_type;
0061         typedef index::rtree<RTreeValueType, index_parameters_type> rtree_type;
0062
0063         BOOST_GEOMETRY_ASSERT( rtree_first != rtree_last );
0064         BOOST_GEOMETRY_ASSERT( queries_first != queries_last );
0065
0066         Distance const zero = Distance(0);
0067         dist_min = zero;
0068
0069         // create -- packing algorithm
0070         rtree_type rt(rtree_first, rtree_last,
0071                       index_parameters_type(index::linear<8>(), strategies));
0072
0073         RTreeValueType t_v;
0074         bool first = true;
0075
0076         for (QueryRangeIterator qit = queries_first;
0077              qit != queries_last; ++qit, first = false)
0078         {
0079             std::size_t n = rt.query(index::nearest(*qit, 1), &t_v);
0080
0081             BOOST_GEOMETRY_ASSERT( n > 0 );
0082             // n above is unused outside BOOST_GEOMETRY_ASSERT,
0083             // hence the call to boost::ignore_unused below
0084             //
0085             // however, t_v (initialized by the call to rt.query(...))
0086             // is used below, which is why we cannot put the call to
0087             // rt.query(...) inside BOOST_GEOMETRY_ASSERT
0088             boost::ignore_unused(n);
0089
0090             Distance dist = dispatch::distance
0091                 <
0092                     RTreeValueType,
0093                     typename std::iterator_traits
0094                         <
0095                             QueryRangeIterator
0096                         >::value_type,
0097                     Strategies
0098                 >::apply(t_v, *qit, strategies);
0099
0100             if (first || dist < dist_min)
0101             {
0102                 dist_min = dist;
0103                 rtree_min = t_v;
0104                 qit_min = qit;
0105                 if ( math::equals(dist_min, zero) )
0106                 {
0107                     return;
0108                 }
0109             }
0110         }
0111     }
0112
0113 public:
0114     template <typename RTreeRangeIterator, typename QueryRangeIterator>
0115     struct return_type
0116     {
0117         typedef std::pair
0118             <
0119                 typename std::iterator_traits<RTreeRangeIterator>::value_type,
0120                 QueryRangeIterator
0121             > type;
0122     };
0123
0124
0125     template
0126     <
0127         typename RTreeRangeIterator,
0128         typename QueryRangeIterator,
0129         typename Strategy,
0130         typename Distance
0131     >
0132     static inline typename return_type
0133         <
0134             RTreeRangeIterator, QueryRangeIterator
0135         >::type apply(RTreeRangeIterator rtree_first,
0136                       RTreeRangeIterator rtree_last,
0137                       QueryRangeIterator queries_first,
0138                       QueryRangeIterator queries_last,
0139                       Strategy const& strategy,
0140                       Distance& dist_min)
0141     {
0142         typedef typename std::iterator_traits
0143             <
0144                 RTreeRangeIterator
0145             >::value_type rtree_value_type;
0146
0147         rtree_value_type rtree_min;
0148         QueryRangeIterator qit_min;
0149
0150         apply(rtree_first, rtree_last, queries_first, queries_last,
0151               strategy, rtree_min, qit_min, dist_min);
0152
0153         return std::make_pair(rtree_min, qit_min);
0154     }
0155
0156
0157     template
0158     <
0159         typename RTreeRangeIterator,
0160         typename QueryRangeIterator,
0161         typename Strategy
0162     >
0163     static inline typename return_type
0164         <
0165             RTreeRangeIterator, QueryRangeIterator
0166         >::type apply(RTreeRangeIterator rtree_first,
0167                       RTreeRangeIterator rtree_last,
0168                       QueryRangeIterator queries_first,
0169                       QueryRangeIterator queries_last,
0170                       Strategy const& strategy)
0171     {
0172         typedef typename std::iterator_traits
0173             <
0174                 RTreeRangeIterator
0175             >::value_type rtree_value_type;
0176
0177         typename strategy::distance::services::return_type
0178             <
0179                 Strategy,
0180                 typename point_type<rtree_value_type>::type,
0181                 typename point_type
0182                     <
0183                         typename std::iterator_traits
0184                             <
0185                                 QueryRangeIterator
0186                             >::value_type
0187                     >::type
0188             >::type dist_min;
0189
0190         return apply(rtree_first, rtree_last, queries_first, queries_last,
0191                      strategy, dist_min);
0192     }
0193 };
0194
0195
0196 }} // namespace detail::closest_feature
0197 #endif // DOXYGEN_NO_DETAIL
0198
0199 }} // namespace boost::geometry
0200
0201
0202 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_FEATURE_RANGE_TO_RANGE_HPP