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