1 // Boost.Geometry Index 2 // 3 // R-tree R*-tree split algorithm implementation 4 // 5 // Copyright (c) 2011-2017 Adam Wulkiewicz, Lodz, Poland. 6 // 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) 10 11 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_REDISTRIBUTE_ELEMENTS_HPP 12 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_REDISTRIBUTE_ELEMENTS_HPP 13 14 #include <boost/geometry/index/detail/algorithms/intersection_content.hpp> 15 #include <boost/geometry/index/detail/algorithms/margin.hpp> 16 #include <boost/geometry/index/detail/algorithms/nth_element.hpp> 17 #include <boost/geometry/index/detail/algorithms/union_content.hpp> 18 19 #include <boost/geometry/index/detail/bounded_view.hpp> 20 21 #include <boost/geometry/index/detail/rtree/node/node.hpp> 22 #include <boost/geometry/index/detail/rtree/visitors/insert.hpp> 23 #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp> 24 25 namespace boost { namespace geometry { namespace index { 26 27 namespace detail { namespace rtree { 28 29 namespace rstar { 30 31 template <typename Element, typename Translator, typename Tag, size_t Corner, size_t AxisIndex> 32 class element_axis_corner_less 33 { 34 typedef typename rtree::element_indexable_type<Element, Translator>::type indexable_type; 35 typedef typename geometry::point_type<indexable_type>::type point_type; 36 typedef geometry::model::box<point_type> bounds_type; 37 typedef index::detail::bounded_view<indexable_type, bounds_type> bounded_view_type; 38 39 public: element_axis_corner_less(Translator const & tr)40 element_axis_corner_less(Translator const& tr) 41 : m_tr(tr) 42 {} 43 operator ()(Element const & e1,Element const & e2) const44 bool operator()(Element const& e1, Element const& e2) const 45 { 46 bounded_view_type bounded_ind1(rtree::element_indexable(e1, m_tr)); 47 bounded_view_type bounded_ind2(rtree::element_indexable(e2, m_tr)); 48 49 return geometry::get<Corner, AxisIndex>(bounded_ind1) 50 < geometry::get<Corner, AxisIndex>(bounded_ind2); 51 } 52 53 private: 54 Translator const& m_tr; 55 }; 56 57 template <typename Element, typename Translator, size_t Corner, size_t AxisIndex> 58 class element_axis_corner_less<Element, Translator, box_tag, Corner, AxisIndex> 59 { 60 public: element_axis_corner_less(Translator const & tr)61 element_axis_corner_less(Translator const& tr) 62 : m_tr(tr) 63 {} 64 operator ()(Element const & e1,Element const & e2) const65 bool operator()(Element const& e1, Element const& e2) const 66 { 67 return geometry::get<Corner, AxisIndex>(rtree::element_indexable(e1, m_tr)) 68 < geometry::get<Corner, AxisIndex>(rtree::element_indexable(e2, m_tr)); 69 } 70 71 private: 72 Translator const& m_tr; 73 }; 74 75 template <typename Element, typename Translator, size_t Corner, size_t AxisIndex> 76 class element_axis_corner_less<Element, Translator, point_tag, Corner, AxisIndex> 77 { 78 public: element_axis_corner_less(Translator const & tr)79 element_axis_corner_less(Translator const& tr) 80 : m_tr(tr) 81 {} 82 operator ()(Element const & e1,Element const & e2) const83 bool operator()(Element const& e1, Element const& e2) const 84 { 85 return geometry::get<AxisIndex>(rtree::element_indexable(e1, m_tr)) 86 < geometry::get<AxisIndex>(rtree::element_indexable(e2, m_tr)); 87 } 88 89 private: 90 Translator const& m_tr; 91 }; 92 93 template <typename Box, size_t Corner, size_t AxisIndex> 94 struct choose_split_axis_and_index_for_corner 95 { 96 typedef typename index::detail::default_margin_result<Box>::type margin_type; 97 typedef typename index::detail::default_content_result<Box>::type content_type; 98 99 template <typename Elements, typename Parameters, typename Translator> applyboost::geometry::index::detail::rtree::rstar::choose_split_axis_and_index_for_corner100 static inline void apply(Elements const& elements, 101 size_t & choosen_index, 102 margin_type & sum_of_margins, 103 content_type & smallest_overlap, 104 content_type & smallest_content, 105 Parameters const& parameters, 106 Translator const& translator) 107 { 108 typedef typename Elements::value_type element_type; 109 typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type; 110 typedef typename tag<indexable_type>::type indexable_tag; 111 112 BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == parameters.get_max_elements() + 1, "wrong number of elements"); 113 114 // copy elements 115 Elements elements_copy(elements); // MAY THROW, STRONG (alloc, copy) 116 117 size_t const index_first = parameters.get_min_elements(); 118 size_t const index_last = parameters.get_max_elements() - parameters.get_min_elements() + 2; 119 120 // sort elements 121 element_axis_corner_less<element_type, Translator, indexable_tag, Corner, AxisIndex> elements_less(translator); 122 std::sort(elements_copy.begin(), elements_copy.end(), elements_less); // MAY THROW, BASIC (copy) 123 // { 124 // typename Elements::iterator f = elements_copy.begin() + index_first; 125 // typename Elements::iterator l = elements_copy.begin() + index_last; 126 // // NOTE: for stdlibc++ shipped with gcc 4.8.2 std::nth_element is replaced with std::sort anyway 127 // index::detail::nth_element(elements_copy.begin(), f, elements_copy.end(), elements_less); // MAY THROW, BASIC (copy) 128 // index::detail::nth_element(f, l, elements_copy.end(), elements_less); // MAY THROW, BASIC (copy) 129 // std::sort(f, l, elements_less); // MAY THROW, BASIC (copy) 130 // } 131 132 // init outputs 133 choosen_index = index_first; 134 sum_of_margins = 0; 135 smallest_overlap = (std::numeric_limits<content_type>::max)(); 136 smallest_content = (std::numeric_limits<content_type>::max)(); 137 138 // calculate sum of margins for all distributions 139 for ( size_t i = index_first ; i < index_last ; ++i ) 140 { 141 // TODO - awulkiew: may be optimized - box of group 1 may be initialized with 142 // box of min_elems number of elements and expanded for each iteration by another element 143 144 Box box1 = rtree::elements_box<Box>(elements_copy.begin(), elements_copy.begin() + i, translator); 145 Box box2 = rtree::elements_box<Box>(elements_copy.begin() + i, elements_copy.end(), translator); 146 147 sum_of_margins += index::detail::comparable_margin(box1) + index::detail::comparable_margin(box2); 148 149 content_type ovl = index::detail::intersection_content(box1, box2); 150 content_type con = index::detail::content(box1) + index::detail::content(box2); 151 152 // TODO - shouldn't here be < instead of <= ? 153 if ( ovl < smallest_overlap || (ovl == smallest_overlap && con <= smallest_content) ) 154 { 155 choosen_index = i; 156 smallest_overlap = ovl; 157 smallest_content = con; 158 } 159 } 160 161 ::boost::ignore_unused_variable_warning(parameters); 162 } 163 }; 164 165 //template <typename Box, size_t AxisIndex, typename ElementIndexableTag> 166 //struct choose_split_axis_and_index_for_axis 167 //{ 168 // BOOST_MPL_ASSERT_MSG(false, NOT_IMPLEMENTED_FOR_THIS_TAG, (ElementIndexableTag)); 169 //}; 170 171 template <typename Box, size_t AxisIndex, typename ElementIndexableTag> 172 struct choose_split_axis_and_index_for_axis 173 { 174 typedef typename index::detail::default_margin_result<Box>::type margin_type; 175 typedef typename index::detail::default_content_result<Box>::type content_type; 176 177 template <typename Elements, typename Parameters, typename Translator> applyboost::geometry::index::detail::rtree::rstar::choose_split_axis_and_index_for_axis178 static inline void apply(Elements const& elements, 179 size_t & choosen_corner, 180 size_t & choosen_index, 181 margin_type & sum_of_margins, 182 content_type & smallest_overlap, 183 content_type & smallest_content, 184 Parameters const& parameters, 185 Translator const& translator) 186 { 187 size_t index1 = 0; 188 margin_type som1 = 0; 189 content_type ovl1 = (std::numeric_limits<content_type>::max)(); 190 content_type con1 = (std::numeric_limits<content_type>::max)(); 191 192 choose_split_axis_and_index_for_corner<Box, min_corner, AxisIndex> 193 ::apply(elements, index1, 194 som1, ovl1, con1, 195 parameters, translator); // MAY THROW, STRONG 196 197 size_t index2 = 0; 198 margin_type som2 = 0; 199 content_type ovl2 = (std::numeric_limits<content_type>::max)(); 200 content_type con2 = (std::numeric_limits<content_type>::max)(); 201 202 choose_split_axis_and_index_for_corner<Box, max_corner, AxisIndex> 203 ::apply(elements, index2, 204 som2, ovl2, con2, 205 parameters, translator); // MAY THROW, STRONG 206 207 sum_of_margins = som1 + som2; 208 209 if ( ovl1 < ovl2 || (ovl1 == ovl2 && con1 <= con2) ) 210 { 211 choosen_corner = min_corner; 212 choosen_index = index1; 213 smallest_overlap = ovl1; 214 smallest_content = con1; 215 } 216 else 217 { 218 choosen_corner = max_corner; 219 choosen_index = index2; 220 smallest_overlap = ovl2; 221 smallest_content = con2; 222 } 223 } 224 }; 225 226 template <typename Box, size_t AxisIndex> 227 struct choose_split_axis_and_index_for_axis<Box, AxisIndex, point_tag> 228 { 229 typedef typename index::detail::default_margin_result<Box>::type margin_type; 230 typedef typename index::detail::default_content_result<Box>::type content_type; 231 232 template <typename Elements, typename Parameters, typename Translator> applyboost::geometry::index::detail::rtree::rstar::choose_split_axis_and_index_for_axis233 static inline void apply(Elements const& elements, 234 size_t & choosen_corner, 235 size_t & choosen_index, 236 margin_type & sum_of_margins, 237 content_type & smallest_overlap, 238 content_type & smallest_content, 239 Parameters const& parameters, 240 Translator const& translator) 241 { 242 choose_split_axis_and_index_for_corner<Box, min_corner, AxisIndex> 243 ::apply(elements, choosen_index, 244 sum_of_margins, smallest_overlap, smallest_content, 245 parameters, translator); // MAY THROW, STRONG 246 247 choosen_corner = min_corner; 248 } 249 }; 250 251 template <typename Box, size_t Dimension> 252 struct choose_split_axis_and_index 253 { 254 BOOST_STATIC_ASSERT(0 < Dimension); 255 256 typedef typename index::detail::default_margin_result<Box>::type margin_type; 257 typedef typename index::detail::default_content_result<Box>::type content_type; 258 259 template <typename Elements, typename Parameters, typename Translator> applyboost::geometry::index::detail::rtree::rstar::choose_split_axis_and_index260 static inline void apply(Elements const& elements, 261 size_t & choosen_axis, 262 size_t & choosen_corner, 263 size_t & choosen_index, 264 margin_type & smallest_sum_of_margins, 265 content_type & smallest_overlap, 266 content_type & smallest_content, 267 Parameters const& parameters, 268 Translator const& translator) 269 { 270 typedef typename rtree::element_indexable_type<typename Elements::value_type, Translator>::type element_indexable_type; 271 272 choose_split_axis_and_index<Box, Dimension - 1> 273 ::apply(elements, choosen_axis, choosen_corner, choosen_index, 274 smallest_sum_of_margins, smallest_overlap, smallest_content, 275 parameters, translator); // MAY THROW, STRONG 276 277 margin_type sum_of_margins = 0; 278 279 size_t corner = min_corner; 280 size_t index = 0; 281 282 content_type overlap_val = (std::numeric_limits<content_type>::max)(); 283 content_type content_val = (std::numeric_limits<content_type>::max)(); 284 285 choose_split_axis_and_index_for_axis< 286 Box, 287 Dimension - 1, 288 typename tag<element_indexable_type>::type 289 >::apply(elements, corner, index, sum_of_margins, overlap_val, content_val, parameters, translator); // MAY THROW, STRONG 290 291 if ( sum_of_margins < smallest_sum_of_margins ) 292 { 293 choosen_axis = Dimension - 1; 294 choosen_corner = corner; 295 choosen_index = index; 296 smallest_sum_of_margins = sum_of_margins; 297 smallest_overlap = overlap_val; 298 smallest_content = content_val; 299 } 300 } 301 }; 302 303 template <typename Box> 304 struct choose_split_axis_and_index<Box, 1> 305 { 306 typedef typename index::detail::default_margin_result<Box>::type margin_type; 307 typedef typename index::detail::default_content_result<Box>::type content_type; 308 309 template <typename Elements, typename Parameters, typename Translator> applyboost::geometry::index::detail::rtree::rstar::choose_split_axis_and_index310 static inline void apply(Elements const& elements, 311 size_t & choosen_axis, 312 size_t & choosen_corner, 313 size_t & choosen_index, 314 margin_type & smallest_sum_of_margins, 315 content_type & smallest_overlap, 316 content_type & smallest_content, 317 Parameters const& parameters, 318 Translator const& translator) 319 { 320 typedef typename rtree::element_indexable_type<typename Elements::value_type, Translator>::type element_indexable_type; 321 322 choosen_axis = 0; 323 324 choose_split_axis_and_index_for_axis< 325 Box, 326 0, 327 typename tag<element_indexable_type>::type 328 >::apply(elements, choosen_corner, choosen_index, smallest_sum_of_margins, smallest_overlap, smallest_content, parameters, translator); // MAY THROW 329 } 330 }; 331 332 template <size_t Corner, size_t Dimension, size_t I = 0> 333 struct nth_element 334 { 335 BOOST_STATIC_ASSERT(0 < Dimension); 336 BOOST_STATIC_ASSERT(I < Dimension); 337 338 template <typename Elements, typename Translator> applyboost::geometry::index::detail::rtree::rstar::nth_element339 static inline void apply(Elements & elements, const size_t axis, const size_t index, Translator const& tr) 340 { 341 //BOOST_GEOMETRY_INDEX_ASSERT(axis < Dimension, "unexpected axis value"); 342 343 if ( axis != I ) 344 { 345 nth_element<Corner, Dimension, I + 1>::apply(elements, axis, index, tr); // MAY THROW, BASIC (copy) 346 } 347 else 348 { 349 typedef typename Elements::value_type element_type; 350 typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type; 351 typedef typename tag<indexable_type>::type indexable_tag; 352 353 element_axis_corner_less<element_type, Translator, indexable_tag, Corner, I> less(tr); 354 index::detail::nth_element(elements.begin(), elements.begin() + index, elements.end(), less); // MAY THROW, BASIC (copy) 355 } 356 } 357 }; 358 359 template <size_t Corner, size_t Dimension> 360 struct nth_element<Corner, Dimension, Dimension> 361 { 362 template <typename Elements, typename Translator> applyboost::geometry::index::detail::rtree::rstar::nth_element363 static inline void apply(Elements & /*elements*/, const size_t /*axis*/, const size_t /*index*/, Translator const& /*tr*/) 364 {} 365 }; 366 367 } // namespace rstar 368 369 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators> 370 struct redistribute_elements<Value, Options, Translator, Box, Allocators, rstar_tag> 371 { 372 typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node; 373 typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; 374 typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; 375 376 typedef typename Options::parameters_type parameters_type; 377 378 static const size_t dimension = geometry::dimension<Box>::value; 379 380 typedef typename index::detail::default_margin_result<Box>::type margin_type; 381 typedef typename index::detail::default_content_result<Box>::type content_type; 382 383 template <typename Node> applyboost::geometry::index::detail::rtree::redistribute_elements384 static inline void apply( 385 Node & n, 386 Node & second_node, 387 Box & box1, 388 Box & box2, 389 parameters_type const& parameters, 390 Translator const& translator, 391 Allocators & allocators) 392 { 393 typedef typename rtree::elements_type<Node>::type elements_type; 394 typedef typename elements_type::value_type element_type; 395 396 elements_type & elements1 = rtree::elements(n); 397 elements_type & elements2 = rtree::elements(second_node); 398 399 // copy original elements - use in-memory storage (std::allocator) 400 // TODO: move if noexcept 401 typedef typename rtree::container_from_elements_type<elements_type, element_type>::type 402 container_type; 403 container_type elements_copy(elements1.begin(), elements1.end()); // MAY THROW, STRONG 404 container_type elements_backup(elements1.begin(), elements1.end()); // MAY THROW, STRONG 405 406 size_t split_axis = 0; 407 size_t split_corner = 0; 408 size_t split_index = parameters.get_min_elements(); 409 margin_type smallest_sum_of_margins = (std::numeric_limits<margin_type>::max)(); 410 content_type smallest_overlap = (std::numeric_limits<content_type>::max)(); 411 content_type smallest_content = (std::numeric_limits<content_type>::max)(); 412 413 // NOTE: this function internally copies passed elements 414 // why not pass mutable elements and use the same container for all axes/corners 415 // and again, the same below calling partial_sort/nth_element 416 // It would be even possible to not re-sort/find nth_element if the axis/corner 417 // was found for the last sorting - last combination of axis/corner 418 rstar::choose_split_axis_and_index<Box, dimension> 419 ::apply(elements_copy, 420 split_axis, split_corner, split_index, 421 smallest_sum_of_margins, smallest_overlap, smallest_content, 422 parameters, translator); // MAY THROW, STRONG 423 424 // TODO: awulkiew - get rid of following static_casts? 425 BOOST_GEOMETRY_INDEX_ASSERT(split_axis < dimension, "unexpected value"); 426 BOOST_GEOMETRY_INDEX_ASSERT(split_corner == static_cast<size_t>(min_corner) || split_corner == static_cast<size_t>(max_corner), "unexpected value"); 427 BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= split_index && split_index <= parameters.get_max_elements() - parameters.get_min_elements() + 1, "unexpected value"); 428 429 // TODO: consider using nth_element 430 if ( split_corner == static_cast<size_t>(min_corner) ) 431 { 432 rstar::nth_element<min_corner, dimension> 433 ::apply(elements_copy, split_axis, split_index, translator); // MAY THROW, BASIC (copy) 434 } 435 else 436 { 437 rstar::nth_element<max_corner, dimension> 438 ::apply(elements_copy, split_axis, split_index, translator); // MAY THROW, BASIC (copy) 439 } 440 441 BOOST_TRY 442 { 443 // copy elements to nodes 444 elements1.assign(elements_copy.begin(), elements_copy.begin() + split_index); // MAY THROW, BASIC 445 elements2.assign(elements_copy.begin() + split_index, elements_copy.end()); // MAY THROW, BASIC 446 447 // calculate boxes 448 box1 = rtree::elements_box<Box>(elements1.begin(), elements1.end(), translator); 449 box2 = rtree::elements_box<Box>(elements2.begin(), elements2.end(), translator); 450 } 451 BOOST_CATCH(...) 452 { 453 //elements_copy.clear(); 454 elements1.clear(); 455 elements2.clear(); 456 457 rtree::destroy_elements<Value, Options, Translator, Box, Allocators>::apply(elements_backup, allocators); 458 //elements_backup.clear(); 459 460 BOOST_RETHROW // RETHROW, BASIC 461 } 462 BOOST_CATCH_END 463 } 464 }; 465 466 }} // namespace detail::rtree 467 468 }}} // namespace boost::geometry::index 469 470 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_REDISTRIBUTE_ELEMENTS_HPP 471