1 // Boost.Geometry Index
3 // R-tree R*-tree split algorithm implementation
5 // Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland.
7 // Use, modification and distribution is subject to the Boost Software License,
8 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
9 // http://www.boost.org/LICENSE_1_0.txt)
11 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_REDISTRIBUTE_ELEMENTS_HPP
12 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_REDISTRIBUTE_ELEMENTS_HPP
14 #include <boost/geometry/index/detail/algorithms/intersection_content.hpp>
15 #include <boost/geometry/index/detail/algorithms/union_content.hpp>
16 #include <boost/geometry/index/detail/algorithms/margin.hpp>
18 #include <boost/geometry/index/detail/bounded_view.hpp>
20 #include <boost/geometry/index/detail/rtree/node/node.hpp>
21 #include <boost/geometry/index/detail/rtree/visitors/insert.hpp>
22 #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp>
24 namespace boost { namespace geometry { namespace index {
26 namespace detail { namespace rtree {
30 template <typename Element, typename Translator, typename Tag, size_t Corner, size_t AxisIndex>
31 class element_axis_corner_less
33 typedef typename rtree::element_indexable_type<Element, Translator>::type indexable_type;
34 typedef typename geometry::point_type<indexable_type>::type point_type;
35 typedef geometry::model::box<point_type> bounds_type;
36 typedef index::detail::bounded_view<indexable_type, bounds_type> bounded_view_type;
39 element_axis_corner_less(Translator const& tr)
43 bool operator()(Element const& e1, Element const& e2) const
45 bounded_view_type bounded_ind1(rtree::element_indexable(e1, m_tr));
46 bounded_view_type bounded_ind2(rtree::element_indexable(e2, m_tr));
48 return geometry::get<Corner, AxisIndex>(bounded_ind1)
49 < geometry::get<Corner, AxisIndex>(bounded_ind2);
53 Translator const& m_tr;
56 template <typename Element, typename Translator, size_t Corner, size_t AxisIndex>
57 class element_axis_corner_less<Element, Translator, box_tag, Corner, AxisIndex>
60 element_axis_corner_less(Translator const& tr)
64 bool operator()(Element const& e1, Element const& e2) const
66 return geometry::get<Corner, AxisIndex>(rtree::element_indexable(e1, m_tr))
67 < geometry::get<Corner, AxisIndex>(rtree::element_indexable(e2, m_tr));
71 Translator const& m_tr;
74 template <typename Element, typename Translator, size_t Corner, size_t AxisIndex>
75 class element_axis_corner_less<Element, Translator, point_tag, Corner, AxisIndex>
78 element_axis_corner_less(Translator const& tr)
82 bool operator()(Element const& e1, Element const& e2) const
84 return geometry::get<AxisIndex>(rtree::element_indexable(e1, m_tr))
85 < geometry::get<AxisIndex>(rtree::element_indexable(e2, m_tr));
89 Translator const& m_tr;
92 template <typename Box, size_t Corner, size_t AxisIndex>
93 struct choose_split_axis_and_index_for_corner
95 typedef typename index::detail::default_margin_result<Box>::type margin_type;
96 typedef typename index::detail::default_content_result<Box>::type content_type;
98 template <typename Elements, typename Parameters, typename Translator>
99 static inline void apply(Elements const& elements,
100 size_t & choosen_index,
101 margin_type & sum_of_margins,
102 content_type & smallest_overlap,
103 content_type & smallest_content,
104 Parameters const& parameters,
105 Translator const& translator)
107 typedef typename Elements::value_type element_type;
108 typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
109 typedef typename tag<indexable_type>::type indexable_tag;
111 BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == parameters.get_max_elements() + 1, "wrong number of elements");
114 Elements elements_copy(elements); // MAY THROW, STRONG (alloc, copy)
116 size_t const index_first = parameters.get_min_elements();
117 size_t const index_last = parameters.get_max_elements() - parameters.get_min_elements() + 2;
120 element_axis_corner_less<element_type, Translator, indexable_tag, Corner, AxisIndex> elements_less(translator);
121 std::sort(elements_copy.begin(), elements_copy.end(), elements_less); // MAY THROW, BASIC (copy)
123 // typename Elements::iterator f = elements_copy.begin() + index_first;
124 // typename Elements::iterator l = elements_copy.begin() + index_last;
125 // std::nth_element(elements_copy.begin(), f, elements_copy.end(), elements_less); // MAY THROW, BASIC (copy)
126 // std::nth_element(f, l, elements_copy.end(), elements_less); // MAY THROW, BASIC (copy)
127 // std::sort(f, l, elements_less); // MAY THROW, BASIC (copy)
131 choosen_index = index_first;
133 smallest_overlap = (std::numeric_limits<content_type>::max)();
134 smallest_content = (std::numeric_limits<content_type>::max)();
136 // calculate sum of margins for all distributions
137 for ( size_t i = index_first ; i < index_last ; ++i )
139 // TODO - awulkiew: may be optimized - box of group 1 may be initialized with
140 // box of min_elems number of elements and expanded for each iteration by another element
142 Box box1 = rtree::elements_box<Box>(elements_copy.begin(), elements_copy.begin() + i, translator);
143 Box box2 = rtree::elements_box<Box>(elements_copy.begin() + i, elements_copy.end(), translator);
145 sum_of_margins += index::detail::comparable_margin(box1) + index::detail::comparable_margin(box2);
147 content_type ovl = index::detail::intersection_content(box1, box2);
148 content_type con = index::detail::content(box1) + index::detail::content(box2);
150 // TODO - shouldn't here be < instead of <= ?
151 if ( ovl < smallest_overlap || (ovl == smallest_overlap && con <= smallest_content) )
154 smallest_overlap = ovl;
155 smallest_content = con;
159 ::boost::ignore_unused_variable_warning(parameters);
163 //template <typename Box, size_t AxisIndex, typename ElementIndexableTag>
164 //struct choose_split_axis_and_index_for_axis
166 // BOOST_MPL_ASSERT_MSG(false, NOT_IMPLEMENTED_FOR_THIS_TAG, (ElementIndexableTag));
169 template <typename Box, size_t AxisIndex, typename ElementIndexableTag>
170 struct choose_split_axis_and_index_for_axis
172 typedef typename index::detail::default_margin_result<Box>::type margin_type;
173 typedef typename index::detail::default_content_result<Box>::type content_type;
175 template <typename Elements, typename Parameters, typename Translator>
176 static inline void apply(Elements const& elements,
177 size_t & choosen_corner,
178 size_t & choosen_index,
179 margin_type & sum_of_margins,
180 content_type & smallest_overlap,
181 content_type & smallest_content,
182 Parameters const& parameters,
183 Translator const& translator)
186 margin_type som1 = 0;
187 content_type ovl1 = (std::numeric_limits<content_type>::max)();
188 content_type con1 = (std::numeric_limits<content_type>::max)();
190 choose_split_axis_and_index_for_corner<Box, min_corner, AxisIndex>
191 ::apply(elements, index1,
193 parameters, translator); // MAY THROW, STRONG
196 margin_type som2 = 0;
197 content_type ovl2 = (std::numeric_limits<content_type>::max)();
198 content_type con2 = (std::numeric_limits<content_type>::max)();
200 choose_split_axis_and_index_for_corner<Box, max_corner, AxisIndex>
201 ::apply(elements, index2,
203 parameters, translator); // MAY THROW, STRONG
205 sum_of_margins = som1 + som2;
207 if ( ovl1 < ovl2 || (ovl1 == ovl2 && con1 <= con2) )
209 choosen_corner = min_corner;
210 choosen_index = index1;
211 smallest_overlap = ovl1;
212 smallest_content = con1;
216 choosen_corner = max_corner;
217 choosen_index = index2;
218 smallest_overlap = ovl2;
219 smallest_content = con2;
224 template <typename Box, size_t AxisIndex>
225 struct choose_split_axis_and_index_for_axis<Box, AxisIndex, point_tag>
227 typedef typename index::detail::default_margin_result<Box>::type margin_type;
228 typedef typename index::detail::default_content_result<Box>::type content_type;
230 template <typename Elements, typename Parameters, typename Translator>
231 static inline void apply(Elements const& elements,
232 size_t & choosen_corner,
233 size_t & choosen_index,
234 margin_type & sum_of_margins,
235 content_type & smallest_overlap,
236 content_type & smallest_content,
237 Parameters const& parameters,
238 Translator const& translator)
240 choose_split_axis_and_index_for_corner<Box, min_corner, AxisIndex>
241 ::apply(elements, choosen_index,
242 sum_of_margins, smallest_overlap, smallest_content,
243 parameters, translator); // MAY THROW, STRONG
245 choosen_corner = min_corner;
249 template <typename Box, size_t Dimension>
250 struct choose_split_axis_and_index
252 BOOST_STATIC_ASSERT(0 < Dimension);
254 typedef typename index::detail::default_margin_result<Box>::type margin_type;
255 typedef typename index::detail::default_content_result<Box>::type content_type;
257 template <typename Elements, typename Parameters, typename Translator>
258 static inline void apply(Elements const& elements,
259 size_t & choosen_axis,
260 size_t & choosen_corner,
261 size_t & choosen_index,
262 margin_type & smallest_sum_of_margins,
263 content_type & smallest_overlap,
264 content_type & smallest_content,
265 Parameters const& parameters,
266 Translator const& translator)
268 typedef typename rtree::element_indexable_type<typename Elements::value_type, Translator>::type element_indexable_type;
270 choose_split_axis_and_index<Box, Dimension - 1>
271 ::apply(elements, choosen_axis, choosen_corner, choosen_index,
272 smallest_sum_of_margins, smallest_overlap, smallest_content,
273 parameters, translator); // MAY THROW, STRONG
275 margin_type sum_of_margins = 0;
277 size_t corner = min_corner;
280 content_type overlap_val = (std::numeric_limits<content_type>::max)();
281 content_type content_val = (std::numeric_limits<content_type>::max)();
283 choose_split_axis_and_index_for_axis<
286 typename tag<element_indexable_type>::type
287 >::apply(elements, corner, index, sum_of_margins, overlap_val, content_val, parameters, translator); // MAY THROW, STRONG
289 if ( sum_of_margins < smallest_sum_of_margins )
291 choosen_axis = Dimension - 1;
292 choosen_corner = corner;
293 choosen_index = index;
294 smallest_sum_of_margins = sum_of_margins;
295 smallest_overlap = overlap_val;
296 smallest_content = content_val;
301 template <typename Box>
302 struct choose_split_axis_and_index<Box, 1>
304 typedef typename index::detail::default_margin_result<Box>::type margin_type;
305 typedef typename index::detail::default_content_result<Box>::type content_type;
307 template <typename Elements, typename Parameters, typename Translator>
308 static inline void apply(Elements const& elements,
309 size_t & choosen_axis,
310 size_t & choosen_corner,
311 size_t & choosen_index,
312 margin_type & smallest_sum_of_margins,
313 content_type & smallest_overlap,
314 content_type & smallest_content,
315 Parameters const& parameters,
316 Translator const& translator)
318 typedef typename rtree::element_indexable_type<typename Elements::value_type, Translator>::type element_indexable_type;
322 choose_split_axis_and_index_for_axis<
325 typename tag<element_indexable_type>::type
326 >::apply(elements, choosen_corner, choosen_index, smallest_sum_of_margins, smallest_overlap, smallest_content, parameters, translator); // MAY THROW
330 template <size_t Corner, size_t Dimension, size_t I = 0>
333 BOOST_STATIC_ASSERT(0 < Dimension);
334 BOOST_STATIC_ASSERT(I < Dimension);
336 template <typename Elements, typename Translator>
337 static inline void apply(Elements & elements, const size_t axis, const size_t index, Translator const& tr)
339 //BOOST_GEOMETRY_INDEX_ASSERT(axis < Dimension, "unexpected axis value");
343 nth_element<Corner, Dimension, I + 1>::apply(elements, axis, index, tr); // MAY THROW, BASIC (copy)
347 typedef typename Elements::value_type element_type;
348 typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
349 typedef typename tag<indexable_type>::type indexable_tag;
351 element_axis_corner_less<element_type, Translator, indexable_tag, Corner, I> less(tr);
352 std::nth_element(elements.begin(), elements.begin() + index, elements.end(), less); // MAY THROW, BASIC (copy)
357 template <size_t Corner, size_t Dimension>
358 struct nth_element<Corner, Dimension, Dimension>
360 template <typename Elements, typename Translator>
361 static inline void apply(Elements & /*elements*/, const size_t /*axis*/, const size_t /*index*/, Translator const& /*tr*/)
367 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
368 struct redistribute_elements<Value, Options, Translator, Box, Allocators, rstar_tag>
370 typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node;
371 typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
372 typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
374 typedef typename Options::parameters_type parameters_type;
376 static const size_t dimension = geometry::dimension<Box>::value;
378 typedef typename index::detail::default_margin_result<Box>::type margin_type;
379 typedef typename index::detail::default_content_result<Box>::type content_type;
381 template <typename Node>
382 static inline void apply(
387 parameters_type const& parameters,
388 Translator const& translator,
389 Allocators & allocators)
391 typedef typename rtree::elements_type<Node>::type elements_type;
392 typedef typename elements_type::value_type element_type;
394 elements_type & elements1 = rtree::elements(n);
395 elements_type & elements2 = rtree::elements(second_node);
397 // copy original elements - use in-memory storage (std::allocator)
398 // TODO: move if noexcept
399 typedef typename rtree::container_from_elements_type<elements_type, element_type>::type
401 container_type elements_copy(elements1.begin(), elements1.end()); // MAY THROW, STRONG
402 container_type elements_backup(elements1.begin(), elements1.end()); // MAY THROW, STRONG
404 size_t split_axis = 0;
405 size_t split_corner = 0;
406 size_t split_index = parameters.get_min_elements();
407 margin_type smallest_sum_of_margins = (std::numeric_limits<margin_type>::max)();
408 content_type smallest_overlap = (std::numeric_limits<content_type>::max)();
409 content_type smallest_content = (std::numeric_limits<content_type>::max)();
411 // NOTE: this function internally copies passed elements
412 // why not pass mutable elements and use the same container for all axes/corners
413 // and again, the same below calling partial_sort/nth_element
414 // It would be even possible to not re-sort/find nth_element if the axis/corner
415 // was found for the last sorting - last combination of axis/corner
416 rstar::choose_split_axis_and_index<Box, dimension>
417 ::apply(elements_copy,
418 split_axis, split_corner, split_index,
419 smallest_sum_of_margins, smallest_overlap, smallest_content,
420 parameters, translator); // MAY THROW, STRONG
422 // TODO: awulkiew - get rid of following static_casts?
423 BOOST_GEOMETRY_INDEX_ASSERT(split_axis < dimension, "unexpected value");
424 BOOST_GEOMETRY_INDEX_ASSERT(split_corner == static_cast<size_t>(min_corner) || split_corner == static_cast<size_t>(max_corner), "unexpected value");
425 BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= split_index && split_index <= parameters.get_max_elements() - parameters.get_min_elements() + 1, "unexpected value");
427 // TODO: consider using nth_element
428 if ( split_corner == static_cast<size_t>(min_corner) )
430 rstar::nth_element<min_corner, dimension>
431 ::apply(elements_copy, split_axis, split_index, translator); // MAY THROW, BASIC (copy)
435 rstar::nth_element<max_corner, dimension>
436 ::apply(elements_copy, split_axis, split_index, translator); // MAY THROW, BASIC (copy)
441 // copy elements to nodes
442 elements1.assign(elements_copy.begin(), elements_copy.begin() + split_index); // MAY THROW, BASIC
443 elements2.assign(elements_copy.begin() + split_index, elements_copy.end()); // MAY THROW, BASIC
446 box1 = rtree::elements_box<Box>(elements1.begin(), elements1.end(), translator);
447 box2 = rtree::elements_box<Box>(elements2.begin(), elements2.end(), translator);
451 //elements_copy.clear();
455 rtree::destroy_elements<Value, Options, Translator, Box, Allocators>::apply(elements_backup, allocators);
456 //elements_backup.clear();
458 BOOST_RETHROW // RETHROW, BASIC
464 }} // namespace detail::rtree
466 }}} // namespace boost::geometry::index
468 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_REDISTRIBUTE_ELEMENTS_HPP