1 // Boost.Geometry Index
3 // R-tree R*-tree next node choosing 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_CHOOSE_NEXT_NODE_HPP
12 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_CHOOSE_NEXT_NODE_HPP
16 #include <boost/geometry/algorithms/expand.hpp>
18 #include <boost/geometry/index/detail/algorithms/content.hpp>
19 #include <boost/geometry/index/detail/algorithms/intersection_content.hpp>
20 #include <boost/geometry/index/detail/algorithms/union_content.hpp>
22 #include <boost/geometry/index/detail/rtree/node/node.hpp>
23 #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp>
25 namespace boost { namespace geometry { namespace index {
27 namespace detail { namespace rtree {
29 template <typename Value, typename Options, typename Box, typename Allocators>
30 class choose_next_node<Value, Options, Box, Allocators, choose_by_overlap_diff_tag>
32 typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node;
33 typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
34 typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
36 typedef typename rtree::elements_type<internal_node>::type children_type;
37 typedef typename children_type::value_type child_type;
39 typedef typename Options::parameters_type parameters_type;
41 typedef typename index::detail::default_content_result<Box>::type content_type;
44 template <typename Indexable>
45 static inline size_t apply(internal_node & n,
46 Indexable const& indexable,
47 parameters_type const& parameters,
48 size_t node_relative_level)
50 ::boost::ignore_unused_variable_warning(parameters);
52 children_type & children = rtree::elements(n);
55 if ( node_relative_level <= 1 )
57 return choose_by_minimum_overlap_cost(children, indexable, parameters.get_overlap_cost_threshold());
59 // children are internal nodes
61 return choose_by_minimum_content_cost(children, indexable);
65 template <typename Indexable>
66 static inline size_t choose_by_minimum_overlap_cost(children_type const& children,
67 Indexable const& indexable,
68 size_t overlap_cost_threshold)
70 const size_t children_count = children.size();
72 content_type min_content_diff = (std::numeric_limits<content_type>::max)();
73 content_type min_content = (std::numeric_limits<content_type>::max)();
74 size_t choosen_index = 0;
76 // create container of children sorted by content enlargement needed to include the new value
77 typedef boost::tuple<size_t, content_type, content_type> child_contents;
79 typename rtree::container_from_elements_type<children_type, child_contents>::type children_contents;
80 children_contents.resize(children_count);
82 for ( size_t i = 0 ; i < children_count ; ++i )
84 child_type const& ch_i = children[i];
86 // expanded child node's box
87 Box box_exp(ch_i.first);
88 geometry::expand(box_exp, indexable);
91 content_type content = index::detail::content(box_exp);
92 content_type content_diff = content - index::detail::content(ch_i.first);
94 children_contents[i] = boost::make_tuple(i, content_diff, content);
96 if ( content_diff < min_content_diff ||
97 (content_diff == min_content_diff && content < min_content) )
99 min_content_diff = content_diff;
100 min_content = content;
105 // is this assumption ok? if min_content_diff == 0 there is no overlap increase?
107 if ( min_content_diff < -std::numeric_limits<double>::epsilon() || std::numeric_limits<double>::epsilon() < min_content_diff )
109 size_t first_n_children_count = children_count;
110 if ( 0 < overlap_cost_threshold && overlap_cost_threshold < children.size() )
112 first_n_children_count = overlap_cost_threshold;
113 // rearrange by content_diff
114 // in order to calculate nearly minimum overlap cost
115 std::nth_element(children_contents.begin(), children_contents.begin() + first_n_children_count, children_contents.end(), content_diff_less);
118 // calculate minimum or nearly minimum overlap cost
119 choosen_index = choose_by_minimum_overlap_cost_first_n(children, indexable, first_n_children_count, children_count, children_contents);
122 return choosen_index;
125 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)
127 return boost::get<1>(p1) < boost::get<1>(p2) ||
128 (boost::get<1>(p1) == boost::get<1>(p2) && boost::get<2>(p1) < boost::get<2>(p2));
131 template <typename Indexable, typename ChildrenContents>
132 static inline size_t choose_by_minimum_overlap_cost_first_n(children_type const& children,
133 Indexable const& indexable,
134 size_t const first_n_children_count,
135 size_t const children_count,
136 ChildrenContents const& children_contents)
138 BOOST_GEOMETRY_INDEX_ASSERT(first_n_children_count <= children_count, "unexpected value");
139 BOOST_GEOMETRY_INDEX_ASSERT(children_contents.size() == children_count, "unexpected number of elements");
141 // choose index with smallest overlap change value, or content change or smallest content
142 size_t choosen_index = 0;
143 content_type smallest_overlap_diff = (std::numeric_limits<content_type>::max)();
144 content_type smallest_content_diff = (std::numeric_limits<content_type>::max)();
145 content_type smallest_content = (std::numeric_limits<content_type>::max)();
147 // for each child node
148 for (size_t i = 0 ; i < first_n_children_count ; ++i )
150 child_type const& ch_i = children[i];
152 Box box_exp(ch_i.first);
153 // calculate expanded box of child node ch_i
154 geometry::expand(box_exp, indexable);
156 content_type overlap_diff = 0;
159 for ( size_t j = 0 ; j < children_count ; ++j )
163 child_type const& ch_j = children[j];
165 content_type overlap_exp = index::detail::intersection_content(box_exp, ch_j.first);
166 if ( overlap_exp < -std::numeric_limits<content_type>::epsilon() || std::numeric_limits<content_type>::epsilon() < overlap_exp )
168 overlap_diff += overlap_exp - index::detail::intersection_content(ch_i.first, ch_j.first);
173 content_type content = boost::get<2>(children_contents[i]);
174 content_type content_diff = boost::get<1>(children_contents[i]);
177 if ( overlap_diff < smallest_overlap_diff ||
178 ( overlap_diff == smallest_overlap_diff && ( content_diff < smallest_content_diff ||
179 ( content_diff == smallest_content_diff && content < smallest_content ) )
182 smallest_overlap_diff = overlap_diff;
183 smallest_content_diff = content_diff;
184 smallest_content = content;
189 return choosen_index;
192 template <typename Indexable>
193 static inline size_t choose_by_minimum_content_cost(children_type const& children, Indexable const& indexable)
195 size_t children_count = children.size();
197 // choose index with smallest content change or smallest content
198 size_t choosen_index = 0;
199 content_type smallest_content_diff = (std::numeric_limits<content_type>::max)();
200 content_type smallest_content = (std::numeric_limits<content_type>::max)();
202 // choose the child which requires smallest box expansion to store the indexable
203 for ( size_t i = 0 ; i < children_count ; ++i )
205 child_type const& ch_i = children[i];
207 // expanded child node's box
208 Box box_exp(ch_i.first);
209 geometry::expand(box_exp, indexable);
212 content_type content = index::detail::content(box_exp);
213 content_type content_diff = content - index::detail::content(ch_i.first);
216 if ( content_diff < smallest_content_diff ||
217 ( content_diff == smallest_content_diff && content < smallest_content ) )
219 smallest_content_diff = content_diff;
220 smallest_content = content;
225 return choosen_index;
229 }} // namespace detail::rtree
231 }}} // namespace boost::geometry::index
233 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_CHOOSE_NEXT_NODE_HPP