rtree/linear/redistribute_elements.hpp

0001 // Boost.Geometry Index
0002 //
0003 // R-tree linear split algorithm implementation
0004 //
0005 // Copyright (c) 2008 Federico J. Fernandez.
0006 // Copyright (c) 2011-2022 Adam Wulkiewicz, Lodz, Poland.
0007 //
0008 // This file was modified by Oracle on 2019-2020.
0009 // Modifications copyright (c) 2019-2020 Oracle and/or its affiliates.
0010 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0011 //
0012 // Use, modification and distribution is subject to the Boost Software License,
0013 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0014 // http://www.boost.org/LICENSE_1_0.txt)
0015
0016 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_LINEAR_REDISTRIBUTE_ELEMENTS_HPP
0017 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_LINEAR_REDISTRIBUTE_ELEMENTS_HPP
0018
0019 #include <type_traits>
0020
0021 #include <boost/core/ignore_unused.hpp>
0022
0023 #include <boost/geometry/core/static_assert.hpp>
0024
0025 #include <boost/geometry/index/detail/algorithms/bounds.hpp>
0026 #include <boost/geometry/index/detail/algorithms/content.hpp>
0027 #include <boost/geometry/index/detail/bounded_view.hpp>
0028
0029 #include <boost/geometry/index/detail/rtree/node/node.hpp>
0030 #include <boost/geometry/index/detail/rtree/visitors/insert.hpp>
0031 #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp>
0032
0033 namespace boost { namespace geometry { namespace index {
0034
0035 namespace detail { namespace rtree {
0036
0037 namespace linear {
0038
0039 template <typename R, typename T>
0040 inline R difference_dispatch(T const& from, T const& to, std::false_type /*is_unsigned*/)
0041 {
0042     return to - from;
0043 }
0044
0045 template <typename R, typename T>
0046 inline R difference_dispatch(T const& from, T const& to, std::true_type /*is_unsigned*/)
0047 {
0048     return from <= to ? R(to - from) : -R(from - to);
0049 }
0050
0051 template <typename R, typename T>
0052 inline R difference(T const& from, T const& to)
0053 {
0054     BOOST_GEOMETRY_STATIC_ASSERT((! std::is_unsigned<R>::value),
0055         "Result can not be an unsigned type.",
0056         R);
0057
0058     return difference_dispatch<R>(from, to, std::is_unsigned<T>());
0059 }
0060
0061 // TODO: awulkiew
0062 // In general, all aerial Indexables in the tree with box-like nodes will be analyzed as boxes
0063 // because they must fit into larger box. Therefore the algorithm could be the same for Bounds type.
0064 // E.g. if Bounds type is sphere, Indexables probably should be analyzed as spheres.
0065 // 1. View could be provided to 'see' all Indexables as Bounds type.
0066 //    Not ok in the case of big types like Ring, however it's possible that Rings won't be supported,
0067 //    only simple types. Even then if we consider storing Box inside the Sphere we must calculate
0068 //    the bounding sphere 2x for each box because there are 2 loops. For each calculation this means
0069 //    4-2d or 8-3d expansions or -, / and sqrt().
0070 // 2. Additional container could be used and reused if the Indexable type is other than the Bounds type.
0071
0072 // IMPORTANT!
0073 // Still probably the best way would be providing specialized algorithms for each Indexable-Bounds pair!
0074 // Probably on pick_seeds algorithm level - For Bounds=Sphere seeds would be choosen differently
0075
0076 // TODO: awulkiew
0077 // there are loops inside find_greatest_normalized_separation::apply()
0078 // iteration is done for each DimensionIndex.
0079 // Separations and seeds for all DimensionIndex(es) could be calculated at once, stored, then the greatest would be choosen.
0080
0081 // The following struct/method was adapted for the preliminary version of the R-tree. Then it was called:
0082 // void find_normalized_separations(std::vector<Box> const& boxes, T& separation, unsigned int& first, unsigned int& second) const
0083
0084 template <typename Elements, typename Parameters, typename Translator, typename Tag, size_t DimensionIndex>
0085 struct find_greatest_normalized_separation
0086 {
0087     typedef typename Elements::value_type element_type;
0088     typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
0089     typedef typename coordinate_type<indexable_type>::type coordinate_type;
0090
0091     typedef std::conditional_t
0092         <
0093             std::is_integral<coordinate_type>::value,
0094             double,
0095             coordinate_type
0096         > separation_type;
0097
0098     typedef typename geometry::point_type<indexable_type>::type point_type;
0099     typedef geometry::model::box<point_type> bounds_type;
0100     typedef index::detail::bounded_view
0101         <
0102             indexable_type, bounds_type,
0103             typename index::detail::strategy_type<Parameters>::type
0104         > bounded_view_type;
0105
0106     static inline void apply(Elements const& elements,
0107                              Parameters const& parameters,
0108                              Translator const& translator,
0109                              separation_type & separation,
0110                              size_t & seed1,
0111                              size_t & seed2)
0112     {
0113         const size_t elements_count = parameters.get_max_elements() + 1;
0114         BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "unexpected number of elements");
0115         BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements_count, "unexpected number of elements");
0116
0117         auto const& strategy = index::detail::get_strategy(parameters);
0118
0119         // find the lowest low, highest high
0120         indexable_type const& indexable_0 = rtree::element_indexable(elements[0], translator);
0121         bounded_view_type const bounded_indexable_0(indexable_0, strategy);
0122         coordinate_type lowest_low = geometry::get<min_corner, DimensionIndex>(bounded_indexable_0);
0123         coordinate_type highest_high = geometry::get<max_corner, DimensionIndex>(bounded_indexable_0);
0124
0125         // and the lowest high
0126         coordinate_type lowest_high = highest_high;
0127         size_t lowest_high_index = 0;
0128         for (size_t i = 1 ; i < elements_count ; ++i)
0129         {
0130             indexable_type const& indexable_i = rtree::element_indexable(elements[i], translator);
0131             bounded_view_type const bounded_indexable(indexable_i, strategy);
0132             coordinate_type min_coord = geometry::get<min_corner, DimensionIndex>(bounded_indexable);
0133             coordinate_type max_coord = geometry::get<max_corner, DimensionIndex>(bounded_indexable);
0134
0135             if (max_coord < lowest_high)
0136             {
0137                 lowest_high = max_coord;
0138                 lowest_high_index = i;
0139             }
0140
0141             if (min_coord < lowest_low)
0142             {
0143                 lowest_low = min_coord;
0144             }
0145
0146             if (highest_high < max_coord)
0147             {
0148                 highest_high = max_coord;
0149             }
0150         }
0151
0152         // find the highest low
0153         size_t highest_low_index = lowest_high_index == 0 ? 1 : 0;
0154         indexable_type const& indexable_hl = rtree::element_indexable(elements[highest_low_index], translator);
0155         bounded_view_type const bounded_indexable_hl(indexable_hl, strategy);
0156         coordinate_type highest_low = geometry::get<min_corner, DimensionIndex>(bounded_indexable_hl);
0157         for (size_t i = highest_low_index ; i < elements_count ; ++i)
0158         {
0159             indexable_type const& indexable = rtree::element_indexable(elements[i], translator);
0160             bounded_view_type const bounded_indexable(indexable, strategy);
0161             coordinate_type min_coord = geometry::get<min_corner, DimensionIndex>(bounded_indexable);
0162             if (highest_low < min_coord && i != lowest_high_index)
0163             {
0164                 highest_low = min_coord;
0165                 highest_low_index = i;
0166             }
0167         }
0168
0169         coordinate_type const width = highest_high - lowest_low;
0170
0171         // highest_low - lowest_high
0172         separation = difference<separation_type>(lowest_high, highest_low);
0173         // BOOST_GEOMETRY_INDEX_ASSERT(0 <= width);
0174         if (std::numeric_limits<coordinate_type>::epsilon() < width)
0175         {
0176             separation /= width;
0177         }
0178
0179         seed1 = highest_low_index;
0180         seed2 = lowest_high_index;
0181
0182         ::boost::ignore_unused(parameters);
0183     }
0184 };
0185
0186 // Version for points doesn't calculate normalized separation since it would always be equal to 1
0187 // It returns two seeds most distant to each other, separation is equal to distance
0188 template <typename Elements, typename Parameters, typename Translator, size_t DimensionIndex>
0189 struct find_greatest_normalized_separation<Elements, Parameters, Translator, point_tag, DimensionIndex>
0190 {
0191     typedef typename Elements::value_type element_type;
0192     typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
0193     typedef typename coordinate_type<indexable_type>::type coordinate_type;
0194
0195     typedef coordinate_type separation_type;
0196
0197     static inline void apply(Elements const& elements,
0198                              Parameters const& parameters,
0199                              Translator const& translator,
0200                              separation_type & separation,
0201                              size_t & seed1,
0202                              size_t & seed2)
0203     {
0204         const size_t elements_count = parameters.get_max_elements() + 1;
0205         BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "unexpected number of elements");
0206         BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements_count, "unexpected number of elements");
0207
0208         // find the lowest low, highest high
0209         coordinate_type lowest = geometry::get<DimensionIndex>(rtree::element_indexable(elements[0], translator));
0210         coordinate_type highest = geometry::get<DimensionIndex>(rtree::element_indexable(elements[0], translator));
0211         size_t lowest_index = 0;
0212         size_t highest_index = 0;
0213         for ( size_t i = 1 ; i < elements_count ; ++i )
0214         {
0215             coordinate_type coord = geometry::get<DimensionIndex>(rtree::element_indexable(elements[i], translator));
0216
0217             if ( coord < lowest )
0218             {
0219                 lowest = coord;
0220                 lowest_index = i;
0221             }
0222
0223             if ( highest < coord )
0224             {
0225                 highest = coord;
0226                 highest_index = i;
0227             }
0228         }
0229
0230         separation = highest - lowest;
0231         seed1 = lowest_index;
0232         seed2 = highest_index;
0233
0234         if ( lowest_index == highest_index )
0235             seed2 = (lowest_index + 1) % elements_count; // % is just in case since if this is true lowest_index is 0
0236
0237         ::boost::ignore_unused(parameters);
0238     }
0239 };
0240
0241 template <typename Elements, typename Parameters, typename Translator, size_t Dimension>
0242 struct pick_seeds_impl
0243 {
0244     BOOST_STATIC_ASSERT(0 < Dimension);
0245
0246     using element_type = typename Elements::value_type;
0247     using indexable_type = typename rtree::element_indexable_type<element_type, Translator>::type;
0248
0249     using find_norm_sep = find_greatest_normalized_separation
0250     <
0251         Elements, Parameters, Translator,
0252         tag_t<indexable_type>, Dimension - 1
0253     >;
0254
0255     using separation_type = typename find_norm_sep::separation_type;
0256
0257     static inline void apply(Elements const& elements,
0258                              Parameters const& parameters,
0259                              Translator const& tr,
0260                              separation_type& separation,
0261                              size_t& seed1,
0262                              size_t& seed2)
0263     {
0264         pick_seeds_impl<Elements, Parameters, Translator, Dimension - 1>::apply(elements, parameters, tr, separation, seed1, seed2);
0265
0266         separation_type current_separation;
0267         size_t s1, s2;
0268         find_norm_sep::apply(elements, parameters, tr, current_separation, s1, s2);
0269
0270         // in the old implementation different operator was used: <= (y axis prefered)
0271         if ( separation < current_separation )
0272         {
0273             separation = current_separation;
0274             seed1 = s1;
0275             seed2 = s2;
0276         }
0277     }
0278 };
0279
0280 template <typename Elements, typename Parameters, typename Translator>
0281 struct pick_seeds_impl<Elements, Parameters, Translator, 1>
0282 {
0283     using element_type = typename Elements::value_type;
0284     using indexable_type = typename rtree::element_indexable_type<element_type, Translator>::type;
0285     using coordinate_type = coordinate_type_t<indexable_type>;
0286
0287     using find_norm_sep = find_greatest_normalized_separation
0288         <
0289             Elements, Parameters, Translator,
0290             tag_t<indexable_type>, 0
0291         >;
0292
0293     using separation_type = typename find_norm_sep::separation_type;
0294
0295     static inline void apply(Elements const& elements,
0296                              Parameters const& parameters,
0297                              Translator const& tr,
0298                              separation_type& separation,
0299                              size_t& seed1,
0300                              size_t& seed2)
0301     {
0302         find_norm_sep::apply(elements, parameters, tr, separation, seed1, seed2);
0303     }
0304 };
0305
0306 // from void linear_pick_seeds(node_pointer const& n, unsigned int &seed1, unsigned int &seed2) const
0307
0308 template <typename Elements, typename Parameters, typename Translator>
0309 inline void pick_seeds(Elements const& elements,
0310                        Parameters const& parameters,
0311                        Translator const& tr,
0312                        size_t & seed1,
0313                        size_t & seed2)
0314 {
0315     typedef typename Elements::value_type element_type;
0316     typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
0317
0318     typedef pick_seeds_impl
0319         <
0320             Elements, Parameters, Translator,
0321             geometry::dimension<indexable_type>::value
0322         > impl;
0323     typedef typename impl::separation_type separation_type;
0324
0325     separation_type separation = 0;
0326     impl::apply(elements, parameters, tr, separation, seed1, seed2);
0327 }
0328
0329 } // namespace linear
0330
0331 // from void split_node(node_pointer const& n, node_pointer& n1, node_pointer& n2) const
0332
0333 template <typename MembersHolder>
0334 struct redistribute_elements<MembersHolder, linear_tag>
0335 {
0336     typedef typename MembersHolder::box_type box_type;
0337     typedef typename MembersHolder::parameters_type parameters_type;
0338     typedef typename MembersHolder::translator_type translator_type;
0339     typedef typename MembersHolder::allocators_type allocators_type;
0340
0341     typedef typename MembersHolder::node node;
0342     typedef typename MembersHolder::internal_node internal_node;
0343     typedef typename MembersHolder::leaf leaf;
0344
0345     template <typename Node>
0346     static inline void apply(Node & n,
0347                              Node & second_node,
0348                              box_type & box1,
0349                              box_type & box2,
0350                              parameters_type const& parameters,
0351                              translator_type const& translator,
0352                              allocators_type & allocators)
0353     {
0354         typedef typename rtree::elements_type<Node>::type elements_type;
0355         typedef typename elements_type::value_type element_type;
0356         typedef typename rtree::element_indexable_type<element_type, translator_type>::type indexable_type;
0357         typedef typename index::detail::default_content_result<box_type>::type content_type;
0358
0359         typename index::detail::strategy_type<parameters_type>::type const&
0360             strategy = index::detail::get_strategy(parameters);
0361
0362         elements_type & elements1 = rtree::elements(n);
0363         elements_type & elements2 = rtree::elements(second_node);
0364         const size_t elements1_count = parameters.get_max_elements() + 1;
0365
0366         BOOST_GEOMETRY_INDEX_ASSERT(elements1.size() == elements1_count, "unexpected number of elements");
0367
0368         // copy original elements - use in-memory storage (std::allocator)
0369         // TODO: move if noexcept
0370         typedef typename rtree::container_from_elements_type<elements_type, element_type>::type
0371             container_type;
0372         container_type elements_copy(elements1.begin(), elements1.end());                                   // MAY THROW, STRONG (alloc, copy)
0373
0374         // calculate initial seeds
0375         size_t seed1 = 0;
0376         size_t seed2 = 0;
0377         linear::pick_seeds(elements_copy, parameters, translator, seed1, seed2);
0378
0379         // prepare nodes' elements containers
0380         elements1.clear();
0381         BOOST_GEOMETRY_INDEX_ASSERT(elements2.empty(), "unexpected container state");
0382
0383         BOOST_TRY
0384         {
0385             // add seeds
0386             elements1.push_back(elements_copy[seed1]);                                                      // MAY THROW, STRONG (copy)
0387             elements2.push_back(elements_copy[seed2]);                                                      // MAY THROW, STRONG (alloc, copy)
0388
0389             // calculate boxes
0390             detail::bounds(rtree::element_indexable(elements_copy[seed1], translator),
0391                            box1, strategy);
0392             detail::bounds(rtree::element_indexable(elements_copy[seed2], translator),
0393                            box2, strategy);
0394
0395             // initialize areas
0396             content_type content1 = index::detail::content(box1);
0397             content_type content2 = index::detail::content(box2);
0398
0399             BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements1_count, "unexpected elements number");
0400             size_t remaining = elements1_count - 2;
0401
0402             // redistribute the rest of the elements
0403             for ( size_t i = 0 ; i < elements1_count ; ++i )
0404             {
0405                 if (i != seed1 && i != seed2)
0406                 {
0407                     element_type const& elem = elements_copy[i];
0408                     indexable_type const& indexable = rtree::element_indexable(elem, translator);
0409
0410                     // if there is small number of elements left and the number of elements in node is lesser than min_elems
0411                     // just insert them to this node
0412                     if ( elements1.size() + remaining <= parameters.get_min_elements() )
0413                     {
0414                         elements1.push_back(elem);                                                          // MAY THROW, STRONG (copy)
0415                         index::detail::expand(box1, indexable, strategy);
0416                         content1 = index::detail::content(box1);
0417                     }
0418                     else if ( elements2.size() + remaining <= parameters.get_min_elements() )
0419                     {
0420                         elements2.push_back(elem);                                                          // MAY THROW, STRONG (alloc, copy)
0421                         index::detail::expand(box2, indexable, strategy);
0422                         content2 = index::detail::content(box2);
0423                     }
0424                     // choose better node and insert element
0425                     else
0426                     {
0427                         // calculate enlarged boxes and areas
0428                         box_type enlarged_box1(box1);
0429                         box_type enlarged_box2(box2);
0430                         index::detail::expand(enlarged_box1, indexable, strategy);
0431                         index::detail::expand(enlarged_box2, indexable, strategy);
0432                         content_type enlarged_content1 = index::detail::content(enlarged_box1);
0433                         content_type enlarged_content2 = index::detail::content(enlarged_box2);
0434
0435                         content_type content_increase1 = enlarged_content1 - content1;
0436                         content_type content_increase2 = enlarged_content2 - content2;
0437
0438                         // choose group which box content have to be enlarged least or has smaller content or has fewer elements
0439                         if ( content_increase1 < content_increase2 ||
0440                                 ( content_increase1 == content_increase2 &&
0441                                     ( content1 < content2 ||
0442                                         ( content1 == content2 && elements1.size() <= elements2.size() ) ) ) )
0443                         {
0444                             elements1.push_back(elem);                                                      // MAY THROW, STRONG (copy)
0445                             box1 = enlarged_box1;
0446                             content1 = enlarged_content1;
0447                         }
0448                         else
0449                         {
0450                             elements2.push_back(elem);                                                      // MAY THROW, STRONG (alloc, copy)
0451                             box2 = enlarged_box2;
0452                             content2 = enlarged_content2;
0453                         }
0454                     }
0455
0456                     BOOST_GEOMETRY_INDEX_ASSERT(0 < remaining, "unexpected value");
0457                     --remaining;
0458                 }
0459             }
0460         }
0461         BOOST_CATCH(...)
0462         {
0463             elements1.clear();
0464             elements2.clear();
0465
0466             rtree::destroy_elements<MembersHolder>::apply(elements_copy, allocators);
0467             //elements_copy.clear();
0468
0469             BOOST_RETHROW                                                                                     // RETHROW, BASIC
0470         }
0471         BOOST_CATCH_END
0472     }
0473 };
0474
0475 }} // namespace detail::rtree
0476
0477 }}} // namespace boost::geometry::index
0478
0479 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_LINEAR_REDISTRIBUTE_ELEMENTS_HPP