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
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
|
// Boost.Geometry Index
//
// R-tree quadratic split algorithm implementation
//
// Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland.
//
// 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_QUADRATIC_REDISTRIBUTE_ELEMENTS_HPP
#define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUADRATIC_REDISTRIBUTE_ELEMENTS_HPP
#include <algorithm>
#include <boost/geometry/index/detail/algorithms/content.hpp>
#include <boost/geometry/index/detail/algorithms/union_content.hpp>
#include <boost/geometry/index/detail/rtree/node/node.hpp>
#include <boost/geometry/index/detail/rtree/visitors/insert.hpp>
#include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp>
namespace boost { namespace geometry { namespace index {
namespace detail { namespace rtree {
namespace quadratic {
template <typename Elements, typename Parameters, typename Translator, typename Box>
struct pick_seeds
{
typedef typename Elements::value_type element_type;
typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
typedef typename coordinate_type<indexable_type>::type coordinate_type;
typedef Box box_type;
typedef typename index::detail::default_content_result<box_type>::type content_type;
static inline void apply(Elements const& elements,
Parameters const& parameters,
Translator const& tr,
size_t & seed1,
size_t & seed2)
{
const size_t elements_count = parameters.get_max_elements() + 1;
BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "wrong number of elements");
BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements_count, "unexpected number of elements");
content_type greatest_free_content = 0;
seed1 = 0;
seed2 = 1;
for ( size_t i = 0 ; i < elements_count - 1 ; ++i )
{
for ( size_t j = i + 1 ; j < elements_count ; ++j )
{
indexable_type const& ind1 = rtree::element_indexable(elements[i], tr);
indexable_type const& ind2 = rtree::element_indexable(elements[j], tr);
box_type enlarged_box;
//geometry::convert(ind1, enlarged_box);
detail::bounds(ind1, enlarged_box);
geometry::expand(enlarged_box, ind2);
content_type free_content = (index::detail::content(enlarged_box) - index::detail::content(ind1)) - index::detail::content(ind2);
if ( greatest_free_content < free_content )
{
greatest_free_content = free_content;
seed1 = i;
seed2 = j;
}
}
}
::boost::ignore_unused_variable_warning(parameters);
}
};
} // namespace quadratic
template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
struct redistribute_elements<Value, Options, Translator, Box, Allocators, quadratic_tag>
{
typedef typename Options::parameters_type parameters_type;
typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node;
typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
typedef typename index::detail::default_content_result<Box>::type content_type;
template <typename Node>
static inline void apply(Node & n,
Node & second_node,
Box & box1,
Box & box2,
parameters_type const& parameters,
Translator const& translator,
Allocators & allocators)
{
typedef typename rtree::elements_type<Node>::type elements_type;
typedef typename elements_type::value_type element_type;
typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
typedef typename coordinate_type<indexable_type>::type coordinate_type;
elements_type & elements1 = rtree::elements(n);
elements_type & elements2 = rtree::elements(second_node);
BOOST_GEOMETRY_INDEX_ASSERT(elements1.size() == parameters.get_max_elements() + 1, "unexpected elements number");
// copy original elements
elements_type elements_copy(elements1); // MAY THROW, STRONG (alloc, copy)
elements_type elements_backup(elements1); // MAY THROW, STRONG (alloc, copy)
// calculate initial seeds
size_t seed1 = 0;
size_t seed2 = 0;
quadratic::pick_seeds<
elements_type,
parameters_type,
Translator,
Box
>::apply(elements_copy, parameters, translator, seed1, seed2);
// prepare nodes' elements containers
elements1.clear();
BOOST_GEOMETRY_INDEX_ASSERT(elements2.empty(), "second node's elements container should be empty");
BOOST_TRY
{
// add seeds
elements1.push_back(elements_copy[seed1]); // MAY THROW, STRONG (copy)
elements2.push_back(elements_copy[seed2]); // MAY THROW, STRONG (alloc, copy)
// calculate boxes
//geometry::convert(rtree::element_indexable(elements_copy[seed1], translator), box1);
detail::bounds(rtree::element_indexable(elements_copy[seed1], translator), box1);
//geometry::convert(rtree::element_indexable(elements_copy[seed2], translator), box2);
detail::bounds(rtree::element_indexable(elements_copy[seed2], translator), box2);
// remove seeds
if (seed1 < seed2)
{
rtree::move_from_back(elements_copy, elements_copy.begin() + seed2); // MAY THROW, STRONG (copy)
elements_copy.pop_back();
rtree::move_from_back(elements_copy, elements_copy.begin() + seed1); // MAY THROW, STRONG (copy)
elements_copy.pop_back();
}
else
{
rtree::move_from_back(elements_copy, elements_copy.begin() + seed1); // MAY THROW, STRONG (copy)
elements_copy.pop_back();
rtree::move_from_back(elements_copy, elements_copy.begin() + seed2); // MAY THROW, STRONG (copy)
elements_copy.pop_back();
}
// initialize areas
content_type content1 = index::detail::content(box1);
content_type content2 = index::detail::content(box2);
size_t remaining = elements_copy.size();
// redistribute the rest of the elements
while ( !elements_copy.empty() )
{
typename elements_type::reverse_iterator el_it = elements_copy.rbegin();
bool insert_into_group1 = false;
size_t elements1_count = elements1.size();
size_t elements2_count = elements2.size();
// if there is small number of elements left and the number of elements in node is lesser than min_elems
// just insert them to this node
if ( elements1_count + remaining <= parameters.get_min_elements() )
{
insert_into_group1 = true;
}
else if ( elements2_count + remaining <= parameters.get_min_elements() )
{
insert_into_group1 = false;
}
// insert the best element
else
{
// find element with minimum groups areas increses differences
content_type content_increase1 = 0;
content_type content_increase2 = 0;
el_it = pick_next(elements_copy.rbegin(), elements_copy.rend(),
box1, box2, content1, content2, translator,
content_increase1, content_increase2);
if ( content_increase1 < content_increase2 ||
( content_increase1 == content_increase2 && ( content1 < content2 ||
( content1 == content2 && elements1_count <= elements2_count ) )
) )
{
insert_into_group1 = true;
}
else
{
insert_into_group1 = false;
}
}
// move element to the choosen group
element_type const& elem = *el_it;
indexable_type const& indexable = rtree::element_indexable(elem, translator);
if ( insert_into_group1 )
{
elements1.push_back(elem); // MAY THROW, STRONG (copy)
geometry::expand(box1, indexable);
content1 = index::detail::content(box1);
}
else
{
elements2.push_back(elem); // MAY THROW, STRONG (alloc, copy)
geometry::expand(box2, indexable);
content2 = index::detail::content(box2);
}
BOOST_GEOMETRY_INDEX_ASSERT(!elements_copy.empty(), "expected more elements");
typename elements_type::iterator el_it_base = el_it.base();
rtree::move_from_back(elements_copy, --el_it_base); // MAY THROW, STRONG (copy)
elements_copy.pop_back();
BOOST_GEOMETRY_INDEX_ASSERT(0 < remaining, "expected more remaining elements");
--remaining;
}
}
BOOST_CATCH(...)
{
//elements_copy.clear();
elements1.clear();
elements2.clear();
rtree::destroy_elements<Value, Options, Translator, Box, Allocators>::apply(elements_backup, allocators);
//elements_backup.clear();
BOOST_RETHROW // RETHROW, BASIC
}
BOOST_CATCH_END
}
// TODO: awulkiew - change following function to static member of the pick_next class?
template <typename It>
static inline It pick_next(It first, It last,
Box const& box1, Box const& box2,
content_type const& content1, content_type const& content2,
Translator const& translator,
content_type & out_content_increase1, content_type & out_content_increase2)
{
typedef typename boost::iterator_value<It>::type element_type;
typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
content_type greatest_content_incrase_diff = 0;
It out_it = first;
out_content_increase1 = 0;
out_content_increase2 = 0;
// find element with greatest difference between increased group's boxes areas
for ( It el_it = first ; el_it != last ; ++el_it )
{
indexable_type const& indexable = rtree::element_indexable(*el_it, translator);
// calculate enlarged boxes and areas
Box enlarged_box1(box1);
Box enlarged_box2(box2);
geometry::expand(enlarged_box1, indexable);
geometry::expand(enlarged_box2, indexable);
content_type enlarged_content1 = index::detail::content(enlarged_box1);
content_type enlarged_content2 = index::detail::content(enlarged_box2);
content_type content_incrase1 = (enlarged_content1 - content1);
content_type content_incrase2 = (enlarged_content2 - content2);
content_type content_incrase_diff = content_incrase1 < content_incrase2 ?
content_incrase2 - content_incrase1 : content_incrase1 - content_incrase2;
if ( greatest_content_incrase_diff < content_incrase_diff )
{
greatest_content_incrase_diff = content_incrase_diff;
out_it = el_it;
out_content_increase1 = content_incrase1;
out_content_increase2 = content_incrase2;
}
}
return out_it;
}
};
}} // namespace detail::rtree
}}} // namespace boost::geometry::index
#endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUADRATIC_REDISTRIBUTE_ELEMENTS_HPP
|
