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