]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry Index |
2 | // | |
3 | // R-tree R*-tree next node choosing algorithm implementation | |
4 | // | |
92f5a8d4 TL |
5 | // Copyright (c) 2011-2019 Adam Wulkiewicz, Lodz, Poland. |
6 | // | |
1e59de90 TL |
7 | // This file was modified by Oracle on 2019-2021. |
8 | // Modifications copyright (c) 2019-2021 Oracle and/or its affiliates. | |
92f5a8d4 | 9 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle |
7c673cae FG |
10 | // |
11 | // Use, modification and distribution is subject to the Boost Software License, | |
12 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
13 | // http://www.boost.org/LICENSE_1_0.txt) | |
14 | ||
15 | #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_CHOOSE_NEXT_NODE_HPP | |
16 | #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_CHOOSE_NEXT_NODE_HPP | |
17 | ||
18 | #include <algorithm> | |
19 | ||
92f5a8d4 TL |
20 | #include <boost/core/ignore_unused.hpp> |
21 | ||
7c673cae FG |
22 | #include <boost/geometry/algorithms/expand.hpp> |
23 | ||
24 | #include <boost/geometry/index/detail/algorithms/content.hpp> | |
25 | #include <boost/geometry/index/detail/algorithms/intersection_content.hpp> | |
b32b8144 | 26 | #include <boost/geometry/index/detail/algorithms/nth_element.hpp> |
7c673cae FG |
27 | #include <boost/geometry/index/detail/algorithms/union_content.hpp> |
28 | ||
29 | #include <boost/geometry/index/detail/rtree/node/node.hpp> | |
1e59de90 TL |
30 | #include <boost/geometry/index/detail/rtree/options.hpp> |
31 | #include <boost/geometry/index/detail/rtree/visitors/insert.hpp> | |
7c673cae FG |
32 | #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp> |
33 | ||
34 | namespace boost { namespace geometry { namespace index { | |
35 | ||
36 | namespace detail { namespace rtree { | |
37 | ||
f67539c2 TL |
38 | template <typename MembersHolder> |
39 | class choose_next_node<MembersHolder, choose_by_overlap_diff_tag> | |
7c673cae | 40 | { |
f67539c2 TL |
41 | typedef typename MembersHolder::box_type box_type; |
42 | typedef typename MembersHolder::parameters_type parameters_type; | |
43 | ||
44 | typedef typename MembersHolder::node node; | |
45 | typedef typename MembersHolder::internal_node internal_node; | |
46 | typedef typename MembersHolder::leaf leaf; | |
7c673cae FG |
47 | |
48 | typedef typename rtree::elements_type<internal_node>::type children_type; | |
49 | typedef typename children_type::value_type child_type; | |
50 | ||
f67539c2 | 51 | typedef typename index::detail::default_content_result<box_type>::type content_type; |
7c673cae FG |
52 | |
53 | public: | |
54 | template <typename Indexable> | |
55 | static inline size_t apply(internal_node & n, | |
56 | Indexable const& indexable, | |
57 | parameters_type const& parameters, | |
58 | size_t node_relative_level) | |
59 | { | |
92f5a8d4 | 60 | ::boost::ignore_unused(parameters); |
7c673cae FG |
61 | |
62 | children_type & children = rtree::elements(n); | |
63 | ||
64 | // children are leafs | |
65 | if ( node_relative_level <= 1 ) | |
66 | { | |
92f5a8d4 TL |
67 | return choose_by_minimum_overlap_cost(children, indexable, |
68 | parameters.get_overlap_cost_threshold(), | |
69 | index::detail::get_strategy(parameters)); | |
7c673cae FG |
70 | } |
71 | // children are internal nodes | |
72 | else | |
92f5a8d4 TL |
73 | { |
74 | return choose_by_minimum_content_cost(children, indexable, | |
75 | index::detail::get_strategy(parameters)); | |
76 | } | |
7c673cae FG |
77 | } |
78 | ||
79 | private: | |
92f5a8d4 TL |
80 | struct child_contents |
81 | { | |
82 | content_type content_diff; | |
83 | content_type content; | |
84 | size_t i; | |
85 | ||
86 | void set(size_t i_, content_type const& content_, content_type const& content_diff_) | |
87 | { | |
88 | i = i_; | |
89 | content = content_; | |
90 | content_diff = content_diff_; | |
91 | } | |
92 | }; | |
93 | ||
94 | template <typename Indexable, typename Strategy> | |
7c673cae FG |
95 | static inline size_t choose_by_minimum_overlap_cost(children_type const& children, |
96 | Indexable const& indexable, | |
92f5a8d4 TL |
97 | size_t overlap_cost_threshold, |
98 | Strategy const& strategy) | |
7c673cae FG |
99 | { |
100 | const size_t children_count = children.size(); | |
101 | ||
102 | content_type min_content_diff = (std::numeric_limits<content_type>::max)(); | |
103 | content_type min_content = (std::numeric_limits<content_type>::max)(); | |
104 | size_t choosen_index = 0; | |
105 | ||
106 | // create container of children sorted by content enlargement needed to include the new value | |
92f5a8d4 TL |
107 | typename rtree::container_from_elements_type<children_type, child_contents>::type |
108 | children_contents(children_count); | |
7c673cae FG |
109 | |
110 | for ( size_t i = 0 ; i < children_count ; ++i ) | |
111 | { | |
112 | child_type const& ch_i = children[i]; | |
113 | ||
114 | // expanded child node's box | |
f67539c2 | 115 | box_type box_exp(ch_i.first); |
92f5a8d4 | 116 | index::detail::expand(box_exp, indexable, strategy); |
7c673cae FG |
117 | |
118 | // areas difference | |
119 | content_type content = index::detail::content(box_exp); | |
120 | content_type content_diff = content - index::detail::content(ch_i.first); | |
121 | ||
92f5a8d4 | 122 | children_contents[i].set(i, content, content_diff); |
7c673cae FG |
123 | |
124 | if ( content_diff < min_content_diff || | |
125 | (content_diff == min_content_diff && content < min_content) ) | |
126 | { | |
127 | min_content_diff = content_diff; | |
128 | min_content = content; | |
129 | choosen_index = i; | |
130 | } | |
131 | } | |
132 | ||
133 | // is this assumption ok? if min_content_diff == 0 there is no overlap increase? | |
134 | ||
135 | if ( min_content_diff < -std::numeric_limits<double>::epsilon() || std::numeric_limits<double>::epsilon() < min_content_diff ) | |
136 | { | |
137 | size_t first_n_children_count = children_count; | |
138 | if ( 0 < overlap_cost_threshold && overlap_cost_threshold < children.size() ) | |
139 | { | |
140 | first_n_children_count = overlap_cost_threshold; | |
141 | // rearrange by content_diff | |
142 | // in order to calculate nearly minimum overlap cost | |
b32b8144 | 143 | index::detail::nth_element(children_contents.begin(), children_contents.begin() + first_n_children_count, children_contents.end(), content_diff_less); |
7c673cae FG |
144 | } |
145 | ||
146 | // calculate minimum or nearly minimum overlap cost | |
92f5a8d4 TL |
147 | choosen_index = choose_by_minimum_overlap_cost_first_n(children, indexable, |
148 | first_n_children_count, | |
149 | children_count, | |
150 | children_contents, | |
151 | strategy); | |
7c673cae FG |
152 | } |
153 | ||
154 | return choosen_index; | |
155 | } | |
156 | ||
92f5a8d4 | 157 | static inline bool content_diff_less(child_contents const& p1, child_contents const& p2) |
7c673cae | 158 | { |
92f5a8d4 TL |
159 | return p1.content_diff < p2.content_diff |
160 | || (p1.content_diff == p2.content_diff && (p1.content) < (p2.content)); | |
7c673cae FG |
161 | } |
162 | ||
92f5a8d4 | 163 | template <typename Indexable, typename ChildrenContents, typename Strategy> |
7c673cae FG |
164 | static inline size_t choose_by_minimum_overlap_cost_first_n(children_type const& children, |
165 | Indexable const& indexable, | |
166 | size_t const first_n_children_count, | |
167 | size_t const children_count, | |
92f5a8d4 TL |
168 | ChildrenContents const& children_contents, |
169 | Strategy const& strategy) | |
7c673cae FG |
170 | { |
171 | BOOST_GEOMETRY_INDEX_ASSERT(first_n_children_count <= children_count, "unexpected value"); | |
172 | BOOST_GEOMETRY_INDEX_ASSERT(children_contents.size() == children_count, "unexpected number of elements"); | |
173 | ||
174 | // choose index with smallest overlap change value, or content change or smallest content | |
175 | size_t choosen_index = 0; | |
176 | content_type smallest_overlap_diff = (std::numeric_limits<content_type>::max)(); | |
177 | content_type smallest_content_diff = (std::numeric_limits<content_type>::max)(); | |
178 | content_type smallest_content = (std::numeric_limits<content_type>::max)(); | |
179 | ||
180 | // for each child node | |
92f5a8d4 | 181 | for (size_t first_i = 0 ; first_i < first_n_children_count ; ++first_i) |
7c673cae | 182 | { |
92f5a8d4 TL |
183 | size_t i = children_contents[first_i].i; |
184 | content_type const& content = children_contents[first_i].content; | |
185 | content_type const& content_diff = children_contents[first_i].content_diff; | |
186 | ||
7c673cae FG |
187 | child_type const& ch_i = children[i]; |
188 | ||
f67539c2 | 189 | box_type box_exp(ch_i.first); |
7c673cae | 190 | // calculate expanded box of child node ch_i |
92f5a8d4 | 191 | index::detail::expand(box_exp, indexable, strategy); |
7c673cae FG |
192 | |
193 | content_type overlap_diff = 0; | |
194 | ||
195 | // calculate overlap | |
196 | for ( size_t j = 0 ; j < children_count ; ++j ) | |
197 | { | |
198 | if ( i != j ) | |
199 | { | |
200 | child_type const& ch_j = children[j]; | |
201 | ||
92f5a8d4 | 202 | content_type overlap_exp = index::detail::intersection_content(box_exp, ch_j.first, strategy); |
7c673cae FG |
203 | if ( overlap_exp < -std::numeric_limits<content_type>::epsilon() || std::numeric_limits<content_type>::epsilon() < overlap_exp ) |
204 | { | |
92f5a8d4 | 205 | overlap_diff += overlap_exp - index::detail::intersection_content(ch_i.first, ch_j.first, strategy); |
7c673cae FG |
206 | } |
207 | } | |
208 | } | |
209 | ||
7c673cae FG |
210 | // update result |
211 | if ( overlap_diff < smallest_overlap_diff || | |
212 | ( overlap_diff == smallest_overlap_diff && ( content_diff < smallest_content_diff || | |
213 | ( content_diff == smallest_content_diff && content < smallest_content ) ) | |
214 | ) ) | |
215 | { | |
216 | smallest_overlap_diff = overlap_diff; | |
217 | smallest_content_diff = content_diff; | |
218 | smallest_content = content; | |
219 | choosen_index = i; | |
220 | } | |
221 | } | |
222 | ||
223 | return choosen_index; | |
224 | } | |
225 | ||
92f5a8d4 TL |
226 | template <typename Indexable, typename Strategy> |
227 | static inline size_t choose_by_minimum_content_cost(children_type const& children, | |
228 | Indexable const& indexable, | |
229 | Strategy const& strategy) | |
7c673cae FG |
230 | { |
231 | size_t children_count = children.size(); | |
232 | ||
233 | // choose index with smallest content change or smallest content | |
234 | size_t choosen_index = 0; | |
235 | content_type smallest_content_diff = (std::numeric_limits<content_type>::max)(); | |
236 | content_type smallest_content = (std::numeric_limits<content_type>::max)(); | |
237 | ||
238 | // choose the child which requires smallest box expansion to store the indexable | |
239 | for ( size_t i = 0 ; i < children_count ; ++i ) | |
240 | { | |
241 | child_type const& ch_i = children[i]; | |
242 | ||
243 | // expanded child node's box | |
f67539c2 | 244 | box_type box_exp(ch_i.first); |
92f5a8d4 | 245 | index::detail::expand(box_exp, indexable, strategy); |
7c673cae FG |
246 | |
247 | // areas difference | |
248 | content_type content = index::detail::content(box_exp); | |
249 | content_type content_diff = content - index::detail::content(ch_i.first); | |
250 | ||
251 | // update the result | |
252 | if ( content_diff < smallest_content_diff || | |
253 | ( content_diff == smallest_content_diff && content < smallest_content ) ) | |
254 | { | |
255 | smallest_content_diff = content_diff; | |
256 | smallest_content = content; | |
257 | choosen_index = i; | |
258 | } | |
259 | } | |
260 | ||
261 | return choosen_index; | |
262 | } | |
263 | }; | |
264 | ||
265 | }} // namespace detail::rtree | |
266 | ||
267 | }}} // namespace boost::geometry::index | |
268 | ||
269 | #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_CHOOSE_NEXT_NODE_HPP |