1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2014, Oracle and/or its affiliates.
5 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
7 // Licensed under the Boost Software License version 1.0.
8 // http://www.boost.org/users/license.html
10 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_FEATURE_RANGE_TO_RANGE_HPP
11 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_FEATURE_RANGE_TO_RANGE_HPP
18 #include <boost/geometry/core/assert.hpp>
19 #include <boost/geometry/core/point_type.hpp>
20 #include <boost/geometry/strategies/distance.hpp>
21 #include <boost/geometry/algorithms/dispatch/distance.hpp>
22 #include <boost/geometry/index/rtree.hpp>
25 namespace boost { namespace geometry
28 #ifndef DOXYGEN_NO_DETAIL
29 namespace detail { namespace closest_feature
33 // returns a pair of a objects where the first is an object of the
34 // r-tree range and the second an object of the query range that
35 // realizes the closest feature of the two ranges
36 class range_to_range_rtree
41 typename RTreeRangeIterator,
42 typename QueryRangeIterator,
44 typename RTreeValueType,
47 static inline void apply(RTreeRangeIterator rtree_first,
48 RTreeRangeIterator rtree_last,
49 QueryRangeIterator queries_first,
50 QueryRangeIterator queries_last,
51 Strategy const& strategy,
52 RTreeValueType& rtree_min,
53 QueryRangeIterator& qit_min,
56 typedef index::rtree<RTreeValueType, index::linear<8> > rtree_type;
58 BOOST_GEOMETRY_ASSERT( rtree_first != rtree_last );
59 BOOST_GEOMETRY_ASSERT( queries_first != queries_last );
61 Distance const zero = Distance(0);
64 // create -- packing algorithm
65 rtree_type rt(rtree_first, rtree_last);
70 for (QueryRangeIterator qit = queries_first;
71 qit != queries_last; ++qit, first = false)
73 std::size_t n = rt.query(index::nearest(*qit, 1), &t_v);
75 BOOST_GEOMETRY_ASSERT( n > 0 );
76 // n above is unused outside BOOST_GEOMETRY_ASSERT,
77 // hence the call to boost::ignore_unused below
79 // however, t_v (initialized by the call to rt.query(...))
80 // is used below, which is why we cannot put the call to
81 // rt.query(...) inside BOOST_GEOMETRY_ASSERT
82 boost::ignore_unused(n);
84 Distance dist = dispatch::distance
87 typename std::iterator_traits
92 >::apply(t_v, *qit, strategy);
94 if (first || dist < dist_min)
99 if ( math::equals(dist_min, zero) )
108 template <typename RTreeRangeIterator, typename QueryRangeIterator>
113 typename std::iterator_traits<RTreeRangeIterator>::value_type,
121 typename RTreeRangeIterator,
122 typename QueryRangeIterator,
126 static inline typename return_type
128 RTreeRangeIterator, QueryRangeIterator
129 >::type apply(RTreeRangeIterator rtree_first,
130 RTreeRangeIterator rtree_last,
131 QueryRangeIterator queries_first,
132 QueryRangeIterator queries_last,
133 Strategy const& strategy,
136 typedef typename std::iterator_traits
139 >::value_type rtree_value_type;
141 rtree_value_type rtree_min;
142 QueryRangeIterator qit_min;
144 apply(rtree_first, rtree_last, queries_first, queries_last,
145 strategy, rtree_min, qit_min, dist_min);
147 return std::make_pair(rtree_min, qit_min);
153 typename RTreeRangeIterator,
154 typename QueryRangeIterator,
157 static inline typename return_type
159 RTreeRangeIterator, QueryRangeIterator
160 >::type apply(RTreeRangeIterator rtree_first,
161 RTreeRangeIterator rtree_last,
162 QueryRangeIterator queries_first,
163 QueryRangeIterator queries_last,
164 Strategy const& strategy)
166 typedef typename std::iterator_traits
169 >::value_type rtree_value_type;
171 typename strategy::distance::services::return_type
174 typename point_type<rtree_value_type>::type,
177 typename std::iterator_traits
184 return apply(rtree_first, rtree_last, queries_first, queries_last,
190 }} // namespace detail::closest_feature
191 #endif // DOXYGEN_NO_DETAIL
193 }} // namespace boost::geometry
196 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_FEATURE_RANGE_TO_RANGE_HPP