rtree/rstar/choose_next_node.hpp

0001 // Boost.Geometry Index
0002 //
0003 // R-tree R*-tree next node choosing algorithm implementation
0004 //
0005 // Copyright (c) 2011-2019 Adam Wulkiewicz, Lodz, Poland.
0006 //
0007 // This file was modified by Oracle on 2019-2021.
0008 // Modifications copyright (c) 2019-2021 Oracle and/or its affiliates.
0009 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0010 //
0011 // Use, modification and distribution is subject to the Boost Software License,
0012 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0013 // http://www.boost.org/LICENSE_1_0.txt)
0014
0015 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_CHOOSE_NEXT_NODE_HPP
0016 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_CHOOSE_NEXT_NODE_HPP
0017
0018 #include <algorithm>
0019
0020 #include <boost/core/ignore_unused.hpp>
0021
0022 #include <boost/geometry/algorithms/expand.hpp>
0023
0024 #include <boost/geometry/index/detail/algorithms/content.hpp>
0025 #include <boost/geometry/index/detail/algorithms/intersection_content.hpp>
0026 #include <boost/geometry/index/detail/algorithms/nth_element.hpp>
0027 #include <boost/geometry/index/detail/algorithms/union_content.hpp>
0028
0029 #include <boost/geometry/index/detail/rtree/node/node.hpp>
0030 #include <boost/geometry/index/detail/rtree/options.hpp>
0031 #include <boost/geometry/index/detail/rtree/visitors/insert.hpp>
0032 #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp>
0033
0034 namespace boost { namespace geometry { namespace index {
0035
0036 namespace detail { namespace rtree {
0037
0038 template <typename MembersHolder>
0039 class choose_next_node<MembersHolder, choose_by_overlap_diff_tag>
0040 {
0041     typedef typename MembersHolder::box_type box_type;
0042     typedef typename MembersHolder::parameters_type parameters_type;
0043
0044     typedef typename MembersHolder::node node;
0045     typedef typename MembersHolder::internal_node internal_node;
0046     typedef typename MembersHolder::leaf leaf;
0047
0048     typedef typename rtree::elements_type<internal_node>::type children_type;
0049     typedef typename children_type::value_type child_type;
0050
0051     typedef typename index::detail::default_content_result<box_type>::type content_type;
0052
0053 public:
0054     template <typename Indexable>
0055     static inline size_t apply(internal_node & n,
0056                                Indexable const& indexable,
0057                                parameters_type const& parameters,
0058                                size_t node_relative_level)
0059     {
0060         ::boost::ignore_unused(parameters);
0061
0062         children_type & children = rtree::elements(n);
0063
0064         // children are leafs
0065         if ( node_relative_level <= 1 )
0066         {
0067             return choose_by_minimum_overlap_cost(children, indexable,
0068                                                   parameters.get_overlap_cost_threshold(),
0069                                                   index::detail::get_strategy(parameters));
0070         }
0071         // children are internal nodes
0072         else
0073         {
0074             return choose_by_minimum_content_cost(children, indexable,
0075                                                   index::detail::get_strategy(parameters));
0076         }
0077     }
0078
0079 private:
0080     struct child_contents
0081     {
0082         content_type content_diff;
0083         content_type content;
0084         size_t i;
0085
0086         void set(size_t i_, content_type const& content_, content_type const& content_diff_)
0087         {
0088             i = i_;
0089             content = content_;
0090             content_diff = content_diff_;
0091         }
0092     };
0093
0094     template <typename Indexable, typename Strategy>
0095     static inline size_t choose_by_minimum_overlap_cost(children_type const& children,
0096                                                         Indexable const& indexable,
0097                                                         size_t overlap_cost_threshold,
0098                                                         Strategy const& strategy)
0099     {
0100         const size_t children_count = children.size();
0101
0102         content_type min_content_diff = (std::numeric_limits<content_type>::max)();
0103         content_type min_content = (std::numeric_limits<content_type>::max)();
0104         size_t choosen_index = 0;
0105
0106         // create container of children sorted by content enlargement needed to include the new value
0107         typename rtree::container_from_elements_type<children_type, child_contents>::type
0108             children_contents(children_count);
0109
0110         for ( size_t i = 0 ; i < children_count ; ++i )
0111         {
0112             child_type const& ch_i = children[i];
0113
0114             // expanded child node's box
0115             box_type box_exp(ch_i.first);
0116             index::detail::expand(box_exp, indexable, strategy);
0117
0118             // areas difference
0119             content_type content = index::detail::content(box_exp);
0120             content_type content_diff = content - index::detail::content(ch_i.first);
0121
0122             children_contents[i].set(i, content, content_diff);
0123
0124             if ( content_diff < min_content_diff ||
0125                  (content_diff == min_content_diff && content < min_content) )
0126             {
0127                 min_content_diff = content_diff;
0128                 min_content = content;
0129                 choosen_index = i;
0130             }
0131         }
0132
0133         // is this assumption ok? if min_content_diff == 0 there is no overlap increase?
0134
0135         if ( min_content_diff < -std::numeric_limits<double>::epsilon() || std::numeric_limits<double>::epsilon() < min_content_diff )
0136         {
0137             size_t first_n_children_count = children_count;
0138             if ( 0 < overlap_cost_threshold && overlap_cost_threshold < children.size() )
0139             {
0140                 first_n_children_count = overlap_cost_threshold;
0141                 // rearrange by content_diff
0142                 // in order to calculate nearly minimum overlap cost
0143                 index::detail::nth_element(children_contents.begin(), children_contents.begin() + first_n_children_count, children_contents.end(), content_diff_less);
0144             }
0145
0146             // calculate minimum or nearly minimum overlap cost
0147             choosen_index = choose_by_minimum_overlap_cost_first_n(children, indexable,
0148                                                                    first_n_children_count,
0149                                                                    children_count,
0150                                                                    children_contents,
0151                                                                    strategy);
0152         }
0153
0154         return choosen_index;
0155     }
0156
0157     static inline bool content_diff_less(child_contents const& p1, child_contents const& p2)
0158     {
0159         return p1.content_diff < p2.content_diff
0160             || (p1.content_diff == p2.content_diff && (p1.content) < (p2.content));
0161     }
0162
0163     template <typename Indexable, typename ChildrenContents, typename Strategy>
0164     static inline size_t choose_by_minimum_overlap_cost_first_n(children_type const& children,
0165                                                                 Indexable const& indexable,
0166                                                                 size_t const first_n_children_count,
0167                                                                 size_t const children_count,
0168                                                                 ChildrenContents const& children_contents,
0169                                                                 Strategy const& strategy)
0170     {
0171         BOOST_GEOMETRY_INDEX_ASSERT(first_n_children_count <= children_count, "unexpected value");
0172         BOOST_GEOMETRY_INDEX_ASSERT(children_contents.size() == children_count, "unexpected number of elements");
0173
0174         // choose index with smallest overlap change value, or content change or smallest content
0175         size_t choosen_index = 0;
0176         content_type smallest_overlap_diff = (std::numeric_limits<content_type>::max)();
0177         content_type smallest_content_diff = (std::numeric_limits<content_type>::max)();
0178         content_type smallest_content = (std::numeric_limits<content_type>::max)();
0179
0180         // for each child node
0181         for (size_t first_i = 0 ; first_i < first_n_children_count ; ++first_i)
0182         {
0183             size_t i = children_contents[first_i].i;
0184             content_type const& content = children_contents[first_i].content;
0185             content_type const& content_diff = children_contents[first_i].content_diff;
0186
0187             child_type const& ch_i = children[i];
0188
0189             box_type box_exp(ch_i.first);
0190             // calculate expanded box of child node ch_i
0191             index::detail::expand(box_exp, indexable, strategy);
0192
0193             content_type overlap_diff = 0;
0194
0195             // calculate overlap
0196             for ( size_t j = 0 ; j < children_count ; ++j )
0197             {
0198                 if ( i != j )
0199                 {
0200                     child_type const& ch_j = children[j];
0201
0202                     content_type overlap_exp = index::detail::intersection_content(box_exp, ch_j.first, strategy);
0203                     if ( overlap_exp < -std::numeric_limits<content_type>::epsilon() || std::numeric_limits<content_type>::epsilon() < overlap_exp )
0204                     {
0205                         overlap_diff += overlap_exp - index::detail::intersection_content(ch_i.first, ch_j.first, strategy);
0206                     }
0207                 }
0208             }
0209
0210             // update result
0211             if ( overlap_diff < smallest_overlap_diff ||
0212                 ( overlap_diff == smallest_overlap_diff && ( content_diff < smallest_content_diff ||
0213                 ( content_diff == smallest_content_diff && content < smallest_content ) )
0214                 ) )
0215             {
0216                 smallest_overlap_diff = overlap_diff;
0217                 smallest_content_diff = content_diff;
0218                 smallest_content = content;
0219                 choosen_index = i;
0220             }
0221         }
0222
0223         return choosen_index;
0224     }
0225
0226     template <typename Indexable, typename Strategy>
0227     static inline size_t choose_by_minimum_content_cost(children_type const& children,
0228                                                         Indexable const& indexable,
0229                                                         Strategy const& strategy)
0230     {
0231         size_t children_count = children.size();
0232
0233         // choose index with smallest content change or smallest content
0234         size_t choosen_index = 0;
0235         content_type smallest_content_diff = (std::numeric_limits<content_type>::max)();
0236         content_type smallest_content = (std::numeric_limits<content_type>::max)();
0237
0238         // choose the child which requires smallest box expansion to store the indexable
0239         for ( size_t i = 0 ; i < children_count ; ++i )
0240         {
0241             child_type const& ch_i = children[i];
0242
0243             // expanded child node's box
0244             box_type box_exp(ch_i.first);
0245             index::detail::expand(box_exp, indexable, strategy);
0246
0247             // areas difference
0248             content_type content = index::detail::content(box_exp);
0249             content_type content_diff = content - index::detail::content(ch_i.first);
0250
0251             // update the result
0252             if ( content_diff < smallest_content_diff ||
0253                 ( content_diff == smallest_content_diff && content < smallest_content ) )
0254             {
0255                 smallest_content_diff = content_diff;
0256                 smallest_content = content;
0257                 choosen_index = i;
0258             }
0259         }
0260
0261         return choosen_index;
0262     }
0263 };
0264
0265 }} // namespace detail::rtree
0266
0267 }}} // namespace boost::geometry::index
0268
0269 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_CHOOSE_NEXT_NODE_HPP