-
Notifications
You must be signed in to change notification settings - Fork 214
/
spatial_query.hpp
275 lines (232 loc) · 8.58 KB
/
spatial_query.hpp
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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
// Boost.Geometry Index
//
// R-tree spatial query visitor implementation
//
// Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland.
//
// This file was modified by Oracle on 2019-2023.
// Modifications copyright (c) 2019-2023 Oracle and/or its affiliates.
// Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
//
// Use, modification and distribution is subject to the Boost Software License,
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
#ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_SPATIAL_QUERY_HPP
#define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_SPATIAL_QUERY_HPP
#include <boost/geometry/index/detail/rtree/node/node_elements.hpp>
#include <boost/geometry/index/detail/rtree/node/weak_visitor.hpp>
#include <boost/geometry/index/detail/predicates.hpp>
#include <boost/geometry/index/parameters.hpp>
namespace boost { namespace geometry { namespace index {
namespace detail { namespace rtree { namespace visitors {
template <typename MembersHolder, typename Predicates, typename OutIter>
struct spatial_query
{
typedef typename MembersHolder::parameters_type parameters_type;
typedef typename MembersHolder::translator_type translator_type;
typedef typename MembersHolder::allocators_type allocators_type;
typedef typename index::detail::strategy_type<parameters_type>::type strategy_type;
typedef typename MembersHolder::node node;
typedef typename MembersHolder::internal_node internal_node;
typedef typename MembersHolder::leaf leaf;
typedef typename allocators_type::node_pointer node_pointer;
typedef typename allocators_type::size_type size_type;
spatial_query(MembersHolder const& members, Predicates const& p, OutIter out_it)
: m_tr(members.translator())
, m_strategy(index::detail::get_strategy(members.parameters()))
, m_pred(p)
, m_out_iter(out_it)
, m_found_count(0)
{}
size_type apply(node_pointer ptr, size_type reverse_level)
{
namespace id = index::detail;
if (reverse_level > 0)
{
internal_node& n = rtree::get<internal_node>(*ptr);
// traverse nodes meeting predicates
for (auto const& p : rtree::elements(n))
{
// if node meets predicates (0 is dummy value)
if (id::predicates_check<id::bounds_tag>(m_pred, 0, p.first, m_strategy))
{
apply(p.second, reverse_level - 1);
}
}
}
else
{
leaf& n = rtree::get<leaf>(*ptr);
// get all values meeting predicates
for (auto const& v : rtree::elements(n))
{
// if value meets predicates
if (id::predicates_check<id::value_tag>(m_pred, v, m_tr(v), m_strategy))
{
*m_out_iter = v;
++m_out_iter;
++m_found_count;
}
}
}
return m_found_count;
}
size_type apply(MembersHolder const& members)
{
return apply(members.root, members.leafs_level);
}
private:
translator_type const& m_tr;
strategy_type m_strategy;
Predicates const& m_pred;
OutIter m_out_iter;
size_type m_found_count;
};
template <typename MembersHolder, typename Predicates>
class spatial_query_incremental
{
typedef typename MembersHolder::value_type value_type;
typedef typename MembersHolder::parameters_type parameters_type;
typedef typename MembersHolder::translator_type translator_type;
typedef typename MembersHolder::allocators_type allocators_type;
typedef typename index::detail::strategy_type<parameters_type>::type strategy_type;
typedef typename MembersHolder::node node;
typedef typename MembersHolder::internal_node internal_node;
typedef typename MembersHolder::leaf leaf;
typedef typename allocators_type::size_type size_type;
typedef typename allocators_type::const_reference const_reference;
typedef typename allocators_type::node_pointer node_pointer;
typedef typename rtree::elements_type<internal_node>::type::const_iterator internal_iterator;
typedef typename rtree::elements_type<leaf>::type leaf_elements;
typedef typename rtree::elements_type<leaf>::type::const_iterator leaf_iterator;
struct internal_data
{
internal_data(internal_iterator f, internal_iterator l, size_type rl)
: first(f), last(l), reverse_level(rl)
{}
internal_iterator first;
internal_iterator last;
size_type reverse_level;
};
public:
spatial_query_incremental()
: m_translator(nullptr)
// , m_strategy()
// , m_pred()
, m_values(nullptr)
, m_current()
{}
spatial_query_incremental(Predicates const& p)
: m_translator(nullptr)
// , m_strategy()
, m_pred(p)
, m_values(nullptr)
, m_current()
{}
spatial_query_incremental(MembersHolder const& members, Predicates const& p)
: m_translator(::boost::addressof(members.translator()))
, m_strategy(index::detail::get_strategy(members.parameters()))
, m_pred(p)
, m_values(nullptr)
, m_current()
{}
const_reference dereference() const
{
BOOST_GEOMETRY_INDEX_ASSERT(m_values, "not dereferencable");
return *m_current;
}
void initialize(MembersHolder const& members)
{
apply(members.root, members.leafs_level);
search_value();
}
void increment()
{
++m_current;
search_value();
}
bool is_end() const
{
return 0 == m_values;
}
friend bool operator==(spatial_query_incremental const& l, spatial_query_incremental const& r)
{
return (l.m_values == r.m_values) && (0 == l.m_values || l.m_current == r.m_current);
}
private:
void apply(node_pointer ptr, size_type reverse_level)
{
namespace id = index::detail;
if (reverse_level > 0)
{
internal_node& n = rtree::get<internal_node>(*ptr);
auto const& elements = rtree::elements(n);
m_internal_stack.push_back(internal_data(elements.begin(), elements.end(), reverse_level - 1));
}
else
{
leaf& n = rtree::get<leaf>(*ptr);
m_values = ::boost::addressof(rtree::elements(n));
m_current = rtree::elements(n).begin();
}
}
void search_value()
{
namespace id = index::detail;
for (;;)
{
// if leaf is choosen, move to the next value in leaf
if ( m_values )
{
if ( m_current != m_values->end() )
{
// return if next value is found
value_type const& v = *m_current;
if (id::predicates_check<id::value_tag>(m_pred, v, (*m_translator)(v), m_strategy))
{
return;
}
++m_current;
}
// no more values, clear current leaf
else
{
m_values = 0;
}
}
// if leaf isn't choosen, move to the next leaf
else
{
// return if there is no more nodes to traverse
if (m_internal_stack.empty())
{
return;
}
internal_data& current_data = m_internal_stack.back();
// no more children in current node, remove it from stack
if (current_data.first == current_data.last)
{
m_internal_stack.pop_back();
continue;
}
internal_iterator it = current_data.first;
++current_data.first;
// next node is found, push it to the stack
if (id::predicates_check<id::bounds_tag>(m_pred, 0, it->first, m_strategy))
{
apply(it->second, current_data.reverse_level);
}
}
}
}
const translator_type * m_translator;
strategy_type m_strategy;
Predicates m_pred;
std::vector<internal_data> m_internal_stack;
const leaf_elements * m_values;
leaf_iterator m_current;
};
}}} // namespace detail::rtree::visitors
}}} // namespace boost::geometry::index
#endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_SPATIAL_QUERY_HPP