| // Boost.Geometry Index |
| // |
| // R-tree R*-tree next node choosing algorithm implementation |
| // |
| // Copyright (c) 2011-2014 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_RSTAR_CHOOSE_NEXT_NODE_HPP |
| #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_CHOOSE_NEXT_NODE_HPP |
| |
| #include <algorithm> |
| |
| #include <boost/geometry/algorithms/expand.hpp> |
| |
| #include <boost/geometry/index/detail/algorithms/content.hpp> |
| #include <boost/geometry/index/detail/algorithms/intersection_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/is_leaf.hpp> |
| |
| namespace boost { namespace geometry { namespace index { |
| |
| namespace detail { namespace rtree { |
| |
| template <typename Value, typename Options, typename Box, typename Allocators> |
| class choose_next_node<Value, Options, Box, Allocators, choose_by_overlap_diff_tag> |
| { |
| typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node; |
| typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; |
| typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; |
| |
| typedef typename rtree::elements_type<internal_node>::type children_type; |
| typedef typename children_type::value_type child_type; |
| |
| typedef typename Options::parameters_type parameters_type; |
| |
| typedef typename index::detail::default_content_result<Box>::type content_type; |
| |
| public: |
| template <typename Indexable> |
| static inline size_t apply(internal_node & n, |
| Indexable const& indexable, |
| parameters_type const& parameters, |
| size_t node_relative_level) |
| { |
| ::boost::ignore_unused_variable_warning(parameters); |
| |
| children_type & children = rtree::elements(n); |
| |
| // children are leafs |
| if ( node_relative_level <= 1 ) |
| { |
| return choose_by_minimum_overlap_cost(children, indexable, parameters.get_overlap_cost_threshold()); |
| } |
| // children are internal nodes |
| else |
| return choose_by_minimum_content_cost(children, indexable); |
| } |
| |
| private: |
| template <typename Indexable> |
| static inline size_t choose_by_minimum_overlap_cost(children_type const& children, |
| Indexable const& indexable, |
| size_t overlap_cost_threshold) |
| { |
| const size_t children_count = children.size(); |
| |
| content_type min_content_diff = (std::numeric_limits<content_type>::max)(); |
| content_type min_content = (std::numeric_limits<content_type>::max)(); |
| size_t choosen_index = 0; |
| |
| // create container of children sorted by content enlargement needed to include the new value |
| typedef boost::tuple<size_t, content_type, content_type> child_contents; |
| |
| typename rtree::container_from_elements_type<children_type, child_contents>::type children_contents; |
| children_contents.resize(children_count); |
| |
| for ( size_t i = 0 ; i < children_count ; ++i ) |
| { |
| child_type const& ch_i = children[i]; |
| |
| // expanded child node's box |
| Box box_exp(ch_i.first); |
| geometry::expand(box_exp, indexable); |
| |
| // areas difference |
| content_type content = index::detail::content(box_exp); |
| content_type content_diff = content - index::detail::content(ch_i.first); |
| |
| children_contents[i] = boost::make_tuple(i, content_diff, content); |
| |
| if ( content_diff < min_content_diff || |
| (content_diff == min_content_diff && content < min_content) ) |
| { |
| min_content_diff = content_diff; |
| min_content = content; |
| choosen_index = i; |
| } |
| } |
| |
| // is this assumption ok? if min_content_diff == 0 there is no overlap increase? |
| |
| if ( min_content_diff < -std::numeric_limits<double>::epsilon() || std::numeric_limits<double>::epsilon() < min_content_diff ) |
| { |
| size_t first_n_children_count = children_count; |
| if ( 0 < overlap_cost_threshold && overlap_cost_threshold < children.size() ) |
| { |
| first_n_children_count = overlap_cost_threshold; |
| // rearrange by content_diff |
| // in order to calculate nearly minimum overlap cost |
| std::nth_element(children_contents.begin(), children_contents.begin() + first_n_children_count, children_contents.end(), content_diff_less); |
| } |
| |
| // calculate minimum or nearly minimum overlap cost |
| choosen_index = choose_by_minimum_overlap_cost_first_n(children, indexable, first_n_children_count, children_count, children_contents); |
| } |
| |
| return choosen_index; |
| } |
| |
| static inline bool content_diff_less(boost::tuple<size_t, content_type, content_type> const& p1, boost::tuple<size_t, content_type, content_type> const& p2) |
| { |
| return boost::get<1>(p1) < boost::get<1>(p2) || |
| (boost::get<1>(p1) == boost::get<1>(p2) && boost::get<2>(p1) < boost::get<2>(p2)); |
| } |
| |
| template <typename Indexable, typename ChildrenContents> |
| static inline size_t choose_by_minimum_overlap_cost_first_n(children_type const& children, |
| Indexable const& indexable, |
| size_t const first_n_children_count, |
| size_t const children_count, |
| ChildrenContents const& children_contents) |
| { |
| BOOST_GEOMETRY_INDEX_ASSERT(first_n_children_count <= children_count, "unexpected value"); |
| BOOST_GEOMETRY_INDEX_ASSERT(children_contents.size() == children_count, "unexpected number of elements"); |
| |
| // choose index with smallest overlap change value, or content change or smallest content |
| size_t choosen_index = 0; |
| content_type smallest_overlap_diff = (std::numeric_limits<content_type>::max)(); |
| content_type smallest_content_diff = (std::numeric_limits<content_type>::max)(); |
| content_type smallest_content = (std::numeric_limits<content_type>::max)(); |
| |
| // for each child node |
| for (size_t i = 0 ; i < first_n_children_count ; ++i ) |
| { |
| child_type const& ch_i = children[i]; |
| |
| Box box_exp(ch_i.first); |
| // calculate expanded box of child node ch_i |
| geometry::expand(box_exp, indexable); |
| |
| content_type overlap_diff = 0; |
| |
| // calculate overlap |
| for ( size_t j = 0 ; j < children_count ; ++j ) |
| { |
| if ( i != j ) |
| { |
| child_type const& ch_j = children[j]; |
| |
| content_type overlap_exp = index::detail::intersection_content(box_exp, ch_j.first); |
| if ( overlap_exp < -std::numeric_limits<content_type>::epsilon() || std::numeric_limits<content_type>::epsilon() < overlap_exp ) |
| { |
| overlap_diff += overlap_exp - index::detail::intersection_content(ch_i.first, ch_j.first); |
| } |
| } |
| } |
| |
| content_type content = boost::get<2>(children_contents[i]); |
| content_type content_diff = boost::get<1>(children_contents[i]); |
| |
| // update result |
| if ( overlap_diff < smallest_overlap_diff || |
| ( overlap_diff == smallest_overlap_diff && ( content_diff < smallest_content_diff || |
| ( content_diff == smallest_content_diff && content < smallest_content ) ) |
| ) ) |
| { |
| smallest_overlap_diff = overlap_diff; |
| smallest_content_diff = content_diff; |
| smallest_content = content; |
| choosen_index = i; |
| } |
| } |
| |
| return choosen_index; |
| } |
| |
| template <typename Indexable> |
| static inline size_t choose_by_minimum_content_cost(children_type const& children, Indexable const& indexable) |
| { |
| size_t children_count = children.size(); |
| |
| // choose index with smallest content change or smallest content |
| size_t choosen_index = 0; |
| content_type smallest_content_diff = (std::numeric_limits<content_type>::max)(); |
| content_type smallest_content = (std::numeric_limits<content_type>::max)(); |
| |
| // choose the child which requires smallest box expansion to store the indexable |
| for ( size_t i = 0 ; i < children_count ; ++i ) |
| { |
| child_type const& ch_i = children[i]; |
| |
| // expanded child node's box |
| Box box_exp(ch_i.first); |
| geometry::expand(box_exp, indexable); |
| |
| // areas difference |
| content_type content = index::detail::content(box_exp); |
| content_type content_diff = content - index::detail::content(ch_i.first); |
| |
| // update the result |
| if ( content_diff < smallest_content_diff || |
| ( content_diff == smallest_content_diff && content < smallest_content ) ) |
| { |
| smallest_content_diff = content_diff; |
| smallest_content = content; |
| choosen_index = i; |
| } |
| } |
| |
| return choosen_index; |
| } |
| }; |
| |
| }} // namespace detail::rtree |
| |
| }}} // namespace boost::geometry::index |
| |
| #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_CHOOSE_NEXT_NODE_HPP |