1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2014, 2019, Oracle and/or its affiliates. 4 5 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle 6 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 7 8 // Licensed under the Boost Software License version 1.0. 9 // http://www.boost.org/users/license.html 10 11 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_FEATURE_RANGE_TO_RANGE_HPP 12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_FEATURE_RANGE_TO_RANGE_HPP 13 14 #include <cstddef> 15 16 #include <iterator> 17 #include <utility> 18 19 #include <boost/geometry/core/assert.hpp> 20 #include <boost/geometry/core/point_type.hpp> 21 #include <boost/geometry/strategies/distance.hpp> 22 #include <boost/geometry/algorithms/dispatch/distance.hpp> 23 #include <boost/geometry/index/rtree.hpp> 24 25 26 namespace boost { namespace geometry 27 { 28 29 #ifndef DOXYGEN_NO_DETAIL 30 namespace detail { namespace closest_feature 31 { 32 33 34 // returns a pair of a objects where the first is an object of the 35 // r-tree range and the second an object of the query range that 36 // realizes the closest feature of the two ranges 37 class range_to_range_rtree 38 { 39 private: 40 template 41 < 42 typename RTreeRangeIterator, 43 typename QueryRangeIterator, 44 typename Strategy, 45 typename RTreeValueType, 46 typename Distance 47 > apply(RTreeRangeIterator rtree_first,RTreeRangeIterator rtree_last,QueryRangeIterator queries_first,QueryRangeIterator queries_last,Strategy const & strategy,RTreeValueType & rtree_min,QueryRangeIterator & qit_min,Distance & dist_min)48 static inline void apply(RTreeRangeIterator rtree_first, 49 RTreeRangeIterator rtree_last, 50 QueryRangeIterator queries_first, 51 QueryRangeIterator queries_last, 52 Strategy const& strategy, 53 RTreeValueType& rtree_min, 54 QueryRangeIterator& qit_min, 55 Distance& dist_min) 56 { 57 typedef strategy::index::services::from_strategy 58 < 59 Strategy 60 > index_strategy_from; 61 typedef index::parameters 62 < 63 index::linear<8>, typename index_strategy_from::type 64 > index_parameters_type; 65 typedef index::rtree<RTreeValueType, index_parameters_type> rtree_type; 66 67 BOOST_GEOMETRY_ASSERT( rtree_first != rtree_last ); 68 BOOST_GEOMETRY_ASSERT( queries_first != queries_last ); 69 70 Distance const zero = Distance(0); 71 dist_min = zero; 72 73 // create -- packing algorithm 74 rtree_type rt(rtree_first, rtree_last, 75 index_parameters_type(index::linear<8>(), 76 index_strategy_from::get(strategy))); 77 78 RTreeValueType t_v; 79 bool first = true; 80 81 for (QueryRangeIterator qit = queries_first; 82 qit != queries_last; ++qit, first = false) 83 { 84 std::size_t n = rt.query(index::nearest(*qit, 1), &t_v); 85 86 BOOST_GEOMETRY_ASSERT( n > 0 ); 87 // n above is unused outside BOOST_GEOMETRY_ASSERT, 88 // hence the call to boost::ignore_unused below 89 // 90 // however, t_v (initialized by the call to rt.query(...)) 91 // is used below, which is why we cannot put the call to 92 // rt.query(...) inside BOOST_GEOMETRY_ASSERT 93 boost::ignore_unused(n); 94 95 Distance dist = dispatch::distance 96 < 97 RTreeValueType, 98 typename std::iterator_traits 99 < 100 QueryRangeIterator 101 >::value_type, 102 Strategy 103 >::apply(t_v, *qit, strategy); 104 105 if (first || dist < dist_min) 106 { 107 dist_min = dist; 108 rtree_min = t_v; 109 qit_min = qit; 110 if ( math::equals(dist_min, zero) ) 111 { 112 return; 113 } 114 } 115 } 116 } 117 118 public: 119 template <typename RTreeRangeIterator, typename QueryRangeIterator> 120 struct return_type 121 { 122 typedef std::pair 123 < 124 typename std::iterator_traits<RTreeRangeIterator>::value_type, 125 QueryRangeIterator 126 > type; 127 }; 128 129 130 template 131 < 132 typename RTreeRangeIterator, 133 typename QueryRangeIterator, 134 typename Strategy, 135 typename Distance 136 > 137 static inline typename return_type 138 < 139 RTreeRangeIterator, QueryRangeIterator apply(RTreeRangeIterator rtree_first,RTreeRangeIterator rtree_last,QueryRangeIterator queries_first,QueryRangeIterator queries_last,Strategy const & strategy,Distance & dist_min)140 >::type apply(RTreeRangeIterator rtree_first, 141 RTreeRangeIterator rtree_last, 142 QueryRangeIterator queries_first, 143 QueryRangeIterator queries_last, 144 Strategy const& strategy, 145 Distance& dist_min) 146 { 147 typedef typename std::iterator_traits 148 < 149 RTreeRangeIterator 150 >::value_type rtree_value_type; 151 152 rtree_value_type rtree_min; 153 QueryRangeIterator qit_min; 154 155 apply(rtree_first, rtree_last, queries_first, queries_last, 156 strategy, rtree_min, qit_min, dist_min); 157 158 return std::make_pair(rtree_min, qit_min); 159 } 160 161 162 template 163 < 164 typename RTreeRangeIterator, 165 typename QueryRangeIterator, 166 typename Strategy 167 > 168 static inline typename return_type 169 < 170 RTreeRangeIterator, QueryRangeIterator apply(RTreeRangeIterator rtree_first,RTreeRangeIterator rtree_last,QueryRangeIterator queries_first,QueryRangeIterator queries_last,Strategy const & strategy)171 >::type apply(RTreeRangeIterator rtree_first, 172 RTreeRangeIterator rtree_last, 173 QueryRangeIterator queries_first, 174 QueryRangeIterator queries_last, 175 Strategy const& strategy) 176 { 177 typedef typename std::iterator_traits 178 < 179 RTreeRangeIterator 180 >::value_type rtree_value_type; 181 182 typename strategy::distance::services::return_type 183 < 184 Strategy, 185 typename point_type<rtree_value_type>::type, 186 typename point_type 187 < 188 typename std::iterator_traits 189 < 190 QueryRangeIterator 191 >::value_type 192 >::type 193 >::type dist_min; 194 195 return apply(rtree_first, rtree_last, queries_first, queries_last, 196 strategy, dist_min); 197 } 198 }; 199 200 201 }} // namespace detail::closest_feature 202 #endif // DOXYGEN_NO_DETAIL 203 204 }} // namespace boost::geometry 205 206 207 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_FEATURE_RANGE_TO_RANGE_HPP 208