Chris@16
|
1 // Boost.Geometry Index
|
Chris@16
|
2 //
|
Chris@16
|
3 // R-tree algorithms parameters
|
Chris@16
|
4 //
|
Chris@16
|
5 // Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland.
|
Chris@16
|
6 //
|
Chris@16
|
7 // Use, modification and distribution is subject to the Boost Software License,
|
Chris@16
|
8 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
|
Chris@16
|
9 // http://www.boost.org/LICENSE_1_0.txt)
|
Chris@16
|
10
|
Chris@16
|
11 #ifndef BOOST_GEOMETRY_INDEX_PARAMETERS_HPP
|
Chris@16
|
12 #define BOOST_GEOMETRY_INDEX_PARAMETERS_HPP
|
Chris@16
|
13
|
Chris@16
|
14 #include <limits>
|
Chris@16
|
15
|
Chris@16
|
16 namespace boost { namespace geometry { namespace index {
|
Chris@16
|
17
|
Chris@16
|
18 namespace detail {
|
Chris@16
|
19
|
Chris@16
|
20 template <size_t MaxElements>
|
Chris@16
|
21 struct default_min_elements_s
|
Chris@16
|
22 {
|
Chris@16
|
23 static const size_t raw_value = (MaxElements * 3) / 10;
|
Chris@16
|
24 static const size_t value = 1 <= raw_value ? raw_value : 1;
|
Chris@16
|
25 };
|
Chris@16
|
26
|
Chris@16
|
27 inline size_t default_min_elements_d()
|
Chris@16
|
28 {
|
Chris@16
|
29 return (std::numeric_limits<size_t>::max)();
|
Chris@16
|
30 }
|
Chris@16
|
31
|
Chris@16
|
32 inline size_t default_min_elements_d_calc(size_t max_elements, size_t min_elements)
|
Chris@16
|
33 {
|
Chris@16
|
34 if ( default_min_elements_d() == min_elements )
|
Chris@16
|
35 {
|
Chris@16
|
36 size_t raw_value = (max_elements * 3) / 10;
|
Chris@16
|
37 return 1 <= raw_value ? raw_value : 1;
|
Chris@16
|
38 }
|
Chris@16
|
39
|
Chris@16
|
40 return min_elements;
|
Chris@16
|
41 }
|
Chris@16
|
42
|
Chris@16
|
43 template <size_t MaxElements>
|
Chris@16
|
44 struct default_rstar_reinserted_elements_s
|
Chris@16
|
45 {
|
Chris@16
|
46 static const size_t value = (MaxElements * 3) / 10;
|
Chris@16
|
47 };
|
Chris@16
|
48
|
Chris@16
|
49 inline size_t default_rstar_reinserted_elements_d()
|
Chris@16
|
50 {
|
Chris@16
|
51 return (std::numeric_limits<size_t>::max)();
|
Chris@16
|
52 }
|
Chris@16
|
53
|
Chris@16
|
54 inline size_t default_rstar_reinserted_elements_d_calc(size_t max_elements, size_t reinserted_elements)
|
Chris@16
|
55 {
|
Chris@16
|
56 if ( default_rstar_reinserted_elements_d() == reinserted_elements )
|
Chris@16
|
57 {
|
Chris@16
|
58 return (max_elements * 3) / 10;
|
Chris@16
|
59 }
|
Chris@16
|
60
|
Chris@16
|
61 return reinserted_elements;
|
Chris@16
|
62 }
|
Chris@16
|
63
|
Chris@16
|
64 } // namespace detail
|
Chris@16
|
65
|
Chris@16
|
66 /*!
|
Chris@16
|
67 \brief Linear r-tree creation algorithm parameters.
|
Chris@16
|
68
|
Chris@16
|
69 \tparam MaxElements Maximum number of elements in nodes.
|
Chris@16
|
70 \tparam MinElements Minimum number of elements in nodes. Default: 0.3*Max.
|
Chris@16
|
71 */
|
Chris@16
|
72 template <size_t MaxElements,
|
Chris@101
|
73 size_t MinElements = detail::default_min_elements_s<MaxElements>::value>
|
Chris@16
|
74 struct linear
|
Chris@16
|
75 {
|
Chris@16
|
76 BOOST_MPL_ASSERT_MSG((0 < MinElements && 2*MinElements <= MaxElements+1),
|
Chris@16
|
77 INVALID_STATIC_MIN_MAX_PARAMETERS, (linear));
|
Chris@16
|
78
|
Chris@16
|
79 static const size_t max_elements = MaxElements;
|
Chris@16
|
80 static const size_t min_elements = MinElements;
|
Chris@16
|
81
|
Chris@16
|
82 static size_t get_max_elements() { return MaxElements; }
|
Chris@16
|
83 static size_t get_min_elements() { return MinElements; }
|
Chris@16
|
84 };
|
Chris@16
|
85
|
Chris@16
|
86 /*!
|
Chris@16
|
87 \brief Quadratic r-tree creation algorithm parameters.
|
Chris@16
|
88
|
Chris@16
|
89 \tparam MaxElements Maximum number of elements in nodes.
|
Chris@16
|
90 \tparam MinElements Minimum number of elements in nodes. Default: 0.3*Max.
|
Chris@16
|
91 */
|
Chris@16
|
92 template <size_t MaxElements,
|
Chris@16
|
93 size_t MinElements = detail::default_min_elements_s<MaxElements>::value>
|
Chris@16
|
94 struct quadratic
|
Chris@16
|
95 {
|
Chris@16
|
96 BOOST_MPL_ASSERT_MSG((0 < MinElements && 2*MinElements <= MaxElements+1),
|
Chris@16
|
97 INVALID_STATIC_MIN_MAX_PARAMETERS, (quadratic));
|
Chris@16
|
98
|
Chris@16
|
99 static const size_t max_elements = MaxElements;
|
Chris@16
|
100 static const size_t min_elements = MinElements;
|
Chris@16
|
101
|
Chris@16
|
102 static size_t get_max_elements() { return MaxElements; }
|
Chris@16
|
103 static size_t get_min_elements() { return MinElements; }
|
Chris@16
|
104 };
|
Chris@16
|
105
|
Chris@16
|
106 /*!
|
Chris@16
|
107 \brief R*-tree creation algorithm parameters.
|
Chris@16
|
108
|
Chris@16
|
109 \tparam MaxElements Maximum number of elements in nodes.
|
Chris@16
|
110 \tparam MinElements Minimum number of elements in nodes. Default: 0.3*Max.
|
Chris@16
|
111 \tparam ReinsertedElements The number of elements reinserted by forced reinsertions algorithm.
|
Chris@16
|
112 If 0 forced reinsertions are disabled. Maximum value is Max+1-Min.
|
Chris@16
|
113 Greater values are truncated. Default: 0.3*Max.
|
Chris@16
|
114 \tparam OverlapCostThreshold The number of most suitable leafs taken into account while choosing
|
Chris@16
|
115 the leaf node to which currently inserted value will be added. If
|
Chris@16
|
116 value is in range (0, MaxElements) - the algorithm calculates
|
Chris@16
|
117 nearly minimum overlap cost, otherwise all leafs are analyzed
|
Chris@16
|
118 and true minimum overlap cost is calculated. Default: 32.
|
Chris@16
|
119 */
|
Chris@16
|
120 template <size_t MaxElements,
|
Chris@16
|
121 size_t MinElements = detail::default_min_elements_s<MaxElements>::value,
|
Chris@16
|
122 size_t ReinsertedElements = detail::default_rstar_reinserted_elements_s<MaxElements>::value,
|
Chris@16
|
123 size_t OverlapCostThreshold = 32>
|
Chris@16
|
124 struct rstar
|
Chris@16
|
125 {
|
Chris@16
|
126 BOOST_MPL_ASSERT_MSG((0 < MinElements && 2*MinElements <= MaxElements+1),
|
Chris@16
|
127 INVALID_STATIC_MIN_MAX_PARAMETERS, (rstar));
|
Chris@16
|
128
|
Chris@16
|
129 static const size_t max_elements = MaxElements;
|
Chris@16
|
130 static const size_t min_elements = MinElements;
|
Chris@16
|
131 static const size_t reinserted_elements = ReinsertedElements;
|
Chris@16
|
132 static const size_t overlap_cost_threshold = OverlapCostThreshold;
|
Chris@16
|
133
|
Chris@16
|
134 static size_t get_max_elements() { return MaxElements; }
|
Chris@16
|
135 static size_t get_min_elements() { return MinElements; }
|
Chris@16
|
136 static size_t get_reinserted_elements() { return ReinsertedElements; }
|
Chris@16
|
137 static size_t get_overlap_cost_threshold() { return OverlapCostThreshold; }
|
Chris@16
|
138 };
|
Chris@16
|
139
|
Chris@16
|
140 //template <size_t MaxElements, size_t MinElements>
|
Chris@16
|
141 //struct kmeans
|
Chris@16
|
142 //{
|
Chris@16
|
143 // static const size_t max_elements = MaxElements;
|
Chris@16
|
144 // static const size_t min_elements = MinElements;
|
Chris@16
|
145 //};
|
Chris@16
|
146
|
Chris@16
|
147 /*!
|
Chris@16
|
148 \brief Linear r-tree creation algorithm parameters - run-time version.
|
Chris@16
|
149 */
|
Chris@16
|
150 class dynamic_linear
|
Chris@16
|
151 {
|
Chris@16
|
152 public:
|
Chris@16
|
153 /*!
|
Chris@16
|
154 \brief The constructor.
|
Chris@16
|
155
|
Chris@16
|
156 \param max_elements Maximum number of elements in nodes.
|
Chris@16
|
157 \param min_elements Minimum number of elements in nodes. Default: 0.3*Max.
|
Chris@16
|
158 */
|
Chris@16
|
159 dynamic_linear(size_t max_elements,
|
Chris@16
|
160 size_t min_elements = detail::default_min_elements_d())
|
Chris@16
|
161 : m_max_elements(max_elements)
|
Chris@16
|
162 , m_min_elements(detail::default_min_elements_d_calc(max_elements, min_elements))
|
Chris@16
|
163 {
|
Chris@16
|
164 if (!(0 < m_min_elements && 2*m_min_elements <= m_max_elements+1))
|
Chris@16
|
165 detail::throw_invalid_argument("invalid min or/and max parameters of dynamic_linear");
|
Chris@16
|
166 }
|
Chris@16
|
167
|
Chris@16
|
168 size_t get_max_elements() const { return m_max_elements; }
|
Chris@16
|
169 size_t get_min_elements() const { return m_min_elements; }
|
Chris@16
|
170
|
Chris@16
|
171 private:
|
Chris@16
|
172 size_t m_max_elements;
|
Chris@16
|
173 size_t m_min_elements;
|
Chris@16
|
174 };
|
Chris@16
|
175
|
Chris@16
|
176 /*!
|
Chris@16
|
177 \brief Quadratic r-tree creation algorithm parameters - run-time version.
|
Chris@16
|
178 */
|
Chris@16
|
179 class dynamic_quadratic
|
Chris@16
|
180 {
|
Chris@16
|
181 public:
|
Chris@16
|
182 /*!
|
Chris@16
|
183 \brief The constructor.
|
Chris@16
|
184
|
Chris@16
|
185 \param max_elements Maximum number of elements in nodes.
|
Chris@16
|
186 \param min_elements Minimum number of elements in nodes. Default: 0.3*Max.
|
Chris@16
|
187 */
|
Chris@16
|
188 dynamic_quadratic(size_t max_elements,
|
Chris@16
|
189 size_t min_elements = detail::default_min_elements_d())
|
Chris@16
|
190 : m_max_elements(max_elements)
|
Chris@16
|
191 , m_min_elements(detail::default_min_elements_d_calc(max_elements, min_elements))
|
Chris@16
|
192 {
|
Chris@16
|
193 if (!(0 < m_min_elements && 2*m_min_elements <= m_max_elements+1))
|
Chris@16
|
194 detail::throw_invalid_argument("invalid min or/and max parameters of dynamic_quadratic");
|
Chris@16
|
195 }
|
Chris@16
|
196
|
Chris@16
|
197 size_t get_max_elements() const { return m_max_elements; }
|
Chris@16
|
198 size_t get_min_elements() const { return m_min_elements; }
|
Chris@16
|
199
|
Chris@16
|
200 private:
|
Chris@16
|
201 size_t m_max_elements;
|
Chris@16
|
202 size_t m_min_elements;
|
Chris@16
|
203 };
|
Chris@16
|
204
|
Chris@16
|
205 /*!
|
Chris@16
|
206 \brief R*-tree creation algorithm parameters - run-time version.
|
Chris@16
|
207 */
|
Chris@16
|
208 class dynamic_rstar
|
Chris@16
|
209 {
|
Chris@16
|
210 public:
|
Chris@16
|
211 /*!
|
Chris@16
|
212 \brief The constructor.
|
Chris@16
|
213
|
Chris@16
|
214 \param max_elements Maximum number of elements in nodes.
|
Chris@16
|
215 \param min_elements Minimum number of elements in nodes. Default: 0.3*Max.
|
Chris@16
|
216 \param reinserted_elements The number of elements reinserted by forced reinsertions algorithm.
|
Chris@16
|
217 If 0 forced reinsertions are disabled. Maximum value is Max-Min+1.
|
Chris@16
|
218 Greater values are truncated. Default: 0.3*Max.
|
Chris@16
|
219 \param overlap_cost_threshold The number of most suitable leafs taken into account while choosing
|
Chris@16
|
220 the leaf node to which currently inserted value will be added. If
|
Chris@16
|
221 value is in range (0, MaxElements) - the algorithm calculates
|
Chris@16
|
222 nearly minimum overlap cost, otherwise all leafs are analyzed
|
Chris@16
|
223 and true minimum overlap cost is calculated. Default: 32.
|
Chris@16
|
224 */
|
Chris@16
|
225 dynamic_rstar(size_t max_elements,
|
Chris@16
|
226 size_t min_elements = detail::default_min_elements_d(),
|
Chris@16
|
227 size_t reinserted_elements = detail::default_rstar_reinserted_elements_d(),
|
Chris@16
|
228 size_t overlap_cost_threshold = 32)
|
Chris@16
|
229 : m_max_elements(max_elements)
|
Chris@16
|
230 , m_min_elements(detail::default_min_elements_d_calc(max_elements, min_elements))
|
Chris@16
|
231 , m_reinserted_elements(detail::default_rstar_reinserted_elements_d_calc(max_elements, reinserted_elements))
|
Chris@16
|
232 , m_overlap_cost_threshold(overlap_cost_threshold)
|
Chris@16
|
233 {
|
Chris@16
|
234 if (!(0 < m_min_elements && 2*m_min_elements <= m_max_elements+1))
|
Chris@16
|
235 detail::throw_invalid_argument("invalid min or/and max parameters of dynamic_rstar");
|
Chris@16
|
236 }
|
Chris@16
|
237
|
Chris@16
|
238 size_t get_max_elements() const { return m_max_elements; }
|
Chris@16
|
239 size_t get_min_elements() const { return m_min_elements; }
|
Chris@16
|
240 size_t get_reinserted_elements() const { return m_reinserted_elements; }
|
Chris@16
|
241 size_t get_overlap_cost_threshold() const { return m_overlap_cost_threshold; }
|
Chris@16
|
242
|
Chris@16
|
243 private:
|
Chris@16
|
244 size_t m_max_elements;
|
Chris@16
|
245 size_t m_min_elements;
|
Chris@16
|
246 size_t m_reinserted_elements;
|
Chris@16
|
247 size_t m_overlap_cost_threshold;
|
Chris@16
|
248 };
|
Chris@16
|
249
|
Chris@16
|
250 }}} // namespace boost::geometry::index
|
Chris@16
|
251
|
Chris@16
|
252 #endif // BOOST_GEOMETRY_INDEX_PARAMETERS_HPP
|