]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry Index |
2 | // | |
3 | // R-tree R*-tree next node choosing algorithm implementation | |
4 | // | |
5 | // Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland. | |
6 | // | |
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) | |
10 | ||
11 | #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_CHOOSE_NEXT_NODE_HPP | |
12 | #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_CHOOSE_NEXT_NODE_HPP | |
13 | ||
14 | #include <algorithm> | |
15 | ||
16 | #include <boost/geometry/algorithms/expand.hpp> | |
17 | ||
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> | |
21 | ||
22 | #include <boost/geometry/index/detail/rtree/node/node.hpp> | |
23 | #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp> | |
24 | ||
25 | namespace boost { namespace geometry { namespace index { | |
26 | ||
27 | namespace detail { namespace rtree { | |
28 | ||
29 | template <typename Value, typename Options, typename Box, typename Allocators> | |
30 | class choose_next_node<Value, Options, Box, Allocators, choose_by_overlap_diff_tag> | |
31 | { | |
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; | |
35 | ||
36 | typedef typename rtree::elements_type<internal_node>::type children_type; | |
37 | typedef typename children_type::value_type child_type; | |
38 | ||
39 | typedef typename Options::parameters_type parameters_type; | |
40 | ||
41 | typedef typename index::detail::default_content_result<Box>::type content_type; | |
42 | ||
43 | public: | |
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) | |
49 | { | |
50 | ::boost::ignore_unused_variable_warning(parameters); | |
51 | ||
52 | children_type & children = rtree::elements(n); | |
53 | ||
54 | // children are leafs | |
55 | if ( node_relative_level <= 1 ) | |
56 | { | |
57 | return choose_by_minimum_overlap_cost(children, indexable, parameters.get_overlap_cost_threshold()); | |
58 | } | |
59 | // children are internal nodes | |
60 | else | |
61 | return choose_by_minimum_content_cost(children, indexable); | |
62 | } | |
63 | ||
64 | private: | |
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) | |
69 | { | |
70 | const size_t children_count = children.size(); | |
71 | ||
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; | |
75 | ||
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; | |
78 | ||
79 | typename rtree::container_from_elements_type<children_type, child_contents>::type children_contents; | |
80 | children_contents.resize(children_count); | |
81 | ||
82 | for ( size_t i = 0 ; i < children_count ; ++i ) | |
83 | { | |
84 | child_type const& ch_i = children[i]; | |
85 | ||
86 | // expanded child node's box | |
87 | Box box_exp(ch_i.first); | |
88 | geometry::expand(box_exp, indexable); | |
89 | ||
90 | // areas difference | |
91 | content_type content = index::detail::content(box_exp); | |
92 | content_type content_diff = content - index::detail::content(ch_i.first); | |
93 | ||
94 | children_contents[i] = boost::make_tuple(i, content_diff, content); | |
95 | ||
96 | if ( content_diff < min_content_diff || | |
97 | (content_diff == min_content_diff && content < min_content) ) | |
98 | { | |
99 | min_content_diff = content_diff; | |
100 | min_content = content; | |
101 | choosen_index = i; | |
102 | } | |
103 | } | |
104 | ||
105 | // is this assumption ok? if min_content_diff == 0 there is no overlap increase? | |
106 | ||
107 | if ( min_content_diff < -std::numeric_limits<double>::epsilon() || std::numeric_limits<double>::epsilon() < min_content_diff ) | |
108 | { | |
109 | size_t first_n_children_count = children_count; | |
110 | if ( 0 < overlap_cost_threshold && overlap_cost_threshold < children.size() ) | |
111 | { | |
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); | |
116 | } | |
117 | ||
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); | |
120 | } | |
121 | ||
122 | return choosen_index; | |
123 | } | |
124 | ||
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) | |
126 | { | |
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)); | |
129 | } | |
130 | ||
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) | |
137 | { | |
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"); | |
140 | ||
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)(); | |
146 | ||
147 | // for each child node | |
148 | for (size_t i = 0 ; i < first_n_children_count ; ++i ) | |
149 | { | |
150 | child_type const& ch_i = children[i]; | |
151 | ||
152 | Box box_exp(ch_i.first); | |
153 | // calculate expanded box of child node ch_i | |
154 | geometry::expand(box_exp, indexable); | |
155 | ||
156 | content_type overlap_diff = 0; | |
157 | ||
158 | // calculate overlap | |
159 | for ( size_t j = 0 ; j < children_count ; ++j ) | |
160 | { | |
161 | if ( i != j ) | |
162 | { | |
163 | child_type const& ch_j = children[j]; | |
164 | ||
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 ) | |
167 | { | |
168 | overlap_diff += overlap_exp - index::detail::intersection_content(ch_i.first, ch_j.first); | |
169 | } | |
170 | } | |
171 | } | |
172 | ||
173 | content_type content = boost::get<2>(children_contents[i]); | |
174 | content_type content_diff = boost::get<1>(children_contents[i]); | |
175 | ||
176 | // update result | |
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 ) ) | |
180 | ) ) | |
181 | { | |
182 | smallest_overlap_diff = overlap_diff; | |
183 | smallest_content_diff = content_diff; | |
184 | smallest_content = content; | |
185 | choosen_index = i; | |
186 | } | |
187 | } | |
188 | ||
189 | return choosen_index; | |
190 | } | |
191 | ||
192 | template <typename Indexable> | |
193 | static inline size_t choose_by_minimum_content_cost(children_type const& children, Indexable const& indexable) | |
194 | { | |
195 | size_t children_count = children.size(); | |
196 | ||
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)(); | |
201 | ||
202 | // choose the child which requires smallest box expansion to store the indexable | |
203 | for ( size_t i = 0 ; i < children_count ; ++i ) | |
204 | { | |
205 | child_type const& ch_i = children[i]; | |
206 | ||
207 | // expanded child node's box | |
208 | Box box_exp(ch_i.first); | |
209 | geometry::expand(box_exp, indexable); | |
210 | ||
211 | // areas difference | |
212 | content_type content = index::detail::content(box_exp); | |
213 | content_type content_diff = content - index::detail::content(ch_i.first); | |
214 | ||
215 | // update the result | |
216 | if ( content_diff < smallest_content_diff || | |
217 | ( content_diff == smallest_content_diff && content < smallest_content ) ) | |
218 | { | |
219 | smallest_content_diff = content_diff; | |
220 | smallest_content = content; | |
221 | choosen_index = i; | |
222 | } | |
223 | } | |
224 | ||
225 | return choosen_index; | |
226 | } | |
227 | }; | |
228 | ||
229 | }} // namespace detail::rtree | |
230 | ||
231 | }}} // namespace boost::geometry::index | |
232 | ||
233 | #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_RSTAR_CHOOSE_NEXT_NODE_HPP |