hilbert_2d/hilbert_macros.rs
1macro_rules! hilbert_impl {
2 ( $n:literal, $SelfT:ident, $const_bits:ident ) => {
3 #[doc = concat!("Discrete functions for the ", $n, " unsigned integer type.")]
4 pub mod $SelfT {
5 use super::{next_lut_index, next_lut_index_variant, Variant};
6
7 /// Number of bits in `
8 #[doc = stringify!($SelfT)]
9 /// ` for the current platform
10 pub(crate) const $const_bits: u32 = <$SelfT>::MAX.count_ones();
11
12 /// Highest order of the Hilbert curve that can be calculated for `
13 #[doc = stringify!($SelfT)]
14 /// ` in the current platform
15 pub(crate) const ORDER_MAX: u32 = $const_bits / 2;
16
17 /// Lookup tables for the 1D->2D conversions.
18 const LUTS_H2XY: [[($SelfT, $SelfT); 4]; 8] = [
19 // 1 ― 2
20 // | |
21 // 0 3 Index 0b000
22 [(0, 0), (0, 1), (1, 1), (1, 0)],
23 // 3 ― 2
24 // |
25 // 0 ― 1 Index 0b001
26 [(0, 0), (1, 0), (1, 1), (0, 1)],
27 // 1 ― 0
28 // |
29 // 2 ― 3 Index 0b010
30 [(1, 1), (0, 1), (0, 0), (1, 0)],
31 // 3 0
32 // | |
33 // 2 ― 1 Index 0b011
34 [(1, 1), (1, 0), (0, 0), (0, 1)],
35 // 2 ― 1
36 // | |
37 // 3 0 Index 0b100
38 [(1, 0), (1, 1), (0, 1), (0, 0)],
39 // 2 ― 3
40 // |
41 // 1 ― 0 Index 0b101
42 [(1, 0), (0, 0), (0, 1), (1, 1)],
43 // 0 ― 1
44 // |
45 // 3 ― 2 Index 0b110
46 [(0, 1), (1, 1), (1, 0), (0, 0)],
47 // 0 3
48 // | |
49 // 1 ― 2 Index 0b111
50 [(0, 1), (0, 0), (1, 0), (1, 1)],
51 ];
52
53 /// Lookup tables for the 2D->1D conversions.
54 const LUTS_YX2H: [[[$SelfT; 2]; 2]; 8] = [
55 // 1 ― 2
56 // | |
57 // 0 3 Index 0b000
58 [[0, 3], [1, 2]],
59 // 3 ― 2
60 // |
61 // 0 ― 1 Index 0b001
62 [[0, 1], [3, 2]],
63 // 1 ― 0
64 // |
65 // 2 ― 3 Index 0b010
66 [[2, 3], [1, 0]],
67 // 3 0
68 // | |
69 // 2 ― 1 Index 0b011
70 [[2, 1], [3, 0]],
71 // 2 ― 1
72 // | |
73 // 3 0 Index 0b100
74 [[3, 0], [2, 1]],
75 // 2 ― 3
76 // |
77 // 1 ― 0 Index 0b101
78 [[1, 0], [2, 3]],
79 // 0 ― 1
80 // |
81 // 3 ― 2 Index 0b110
82 [[3, 2], [0, 1]],
83 // 0 3
84 // | |
85 // 1 ― 2 Index 0b111
86 [[1, 2], [0, 3]],
87 ];
88
89 /// Maps from a 1D index to a 2D coordinate, using a discrete approximation of the
90 /// Hilbert curve. Recommended for images and matrices.
91 ///
92 /// Given `h`, this method calculates the `(x, y)` coordinates for that index, in the
93 /// Hilbert curve approximation of `order`.
94 ///
95 /// The value of `h` must be in the range `0 <= h < 2^(2 * order)`. The coordinates
96 /// returned will be in the range `0 <= x/y < 2^order`.
97 ///
98 /// With `b` being the number of bits in a `
99 #[doc = stringify!($SelfT)]
100 /// ` for the target platform, the highest approximation order achievable
101 /// by this method is `b / 2`. Therefore, the parameter `order` must be in the range
102 /// `1 <= order <= b / 2`.
103 ///
104 /// The pattern of the Hilbert curve to be constructed must be indicated by the
105 /// `variant` parameter. See [`Variant`] for more details.
106 ///
107 /// # Examples
108 ///
109 /// Basic usage:
110 ///
111 /// ```rust
112 #[doc = concat!("use hilbert_2d::{Variant, ", stringify!($SelfT), "::h2xy_discrete};")]
113 ///
114 /// // Hilbert curve of order 2:
115 /// // 5 ―― 6 9 ― 10
116 /// // | | | |
117 /// // 4 7 ―― 8 11
118 /// // | |
119 /// // 3 ―― 2 13 ― 12
120 /// // | |
121 /// // 0 ―― 1 14 ― 15
122 /// let (x, y) = h2xy_discrete(7, 2, Variant::Hilbert);
123 ///
124 /// assert_eq!(x, 1);
125 /// assert_eq!(y, 2);
126 /// ```
127 ///
128 /// [`Variant`]: ../enum.Variant.html
129 ///
130 pub const fn h2xy_discrete(
131 h: $SelfT,
132 order: $SelfT,
133 variant: Variant,
134 ) -> ($SelfT, $SelfT) {
135 // Records how many >>'s are required to isolate the quadrant crumbs for each subsequent order, starting at 1
136 let mut steps = 2 * (order - 1);
137 if steps as u32 >= $const_bits {
138 steps = $const_bits as $SelfT - 2;
139 }
140 // Extract the crumb for the quadrant of order 1 from `curve_p`
141 let u_h = h as usize;
142 let mut cur_quadrant = (u_h >> steps) & 0b11;
143 // Retrieve the square coordinates for that quadrant, using the root LUT
144 let (mut square_x, mut square_y) = LUTS_H2XY[0b000][cur_quadrant];
145
146 // Stop here if the given order is 1
147 if steps == 0 {
148 return (square_x, square_y);
149 }
150
151 // Depending on the curve variant, the method of choosing the LUT for the `order 1 -> order 2` transition changes
152 let mut lut_index = next_lut_index_variant(0b000, cur_quadrant, variant);
153
154 loop {
155 // Extract the crumb for the next quadrant from `curve_p`
156 steps -= 2;
157 cur_quadrant = (u_h >> steps) & 0b11;
158
159 // Retrieve the square coordinates for that quadrant, using the current LUT
160 square_x = (square_x << 1) | LUTS_H2XY[lut_index][cur_quadrant].0;
161 square_y = (square_y << 1) | LUTS_H2XY[lut_index][cur_quadrant].1;
162
163 if steps > 0 {
164 // From `order 2 -> order 3` and beyond, the same method of choosing the next LUT is used
165 lut_index = next_lut_index(lut_index, cur_quadrant);
166 } else {
167 break;
168 }
169 }
170
171 (square_x, square_y)
172 }
173
174 /// Maps from a 2D coordinate to an 1D index, using a discrete approximation of the
175 /// Hilbert curve. Recommended for images and matrices.
176 ///
177 /// Given `x` and `y`, this method calculates the `h` index for that coordinate, in the
178 /// Hilbert curve approximation of `order`.
179 ///
180 /// The value of `x` and `y` must be in the range `0 <= x/y < 2^order`. The index
181 /// returned will be in the range `0 <= h < 2^(2 * order)`.
182 ///
183 /// With `b` being the number of bits in a `
184 #[doc = stringify!($SelfT)]
185 /// ` for the target platform, the highest approximation order achievable
186 /// by this method is `b / 2`. Therefore, the parameter `order` must be in the range
187 /// `1 <= order <= b / 2`.
188 ///
189 /// The pattern of the Hilbert curve to be constructed must be indicated by the
190 /// `variant` parameter. See [`Variant`] for more details.
191 ///
192 /// # Examples
193 ///
194 /// Basic usage:
195 ///
196 /// ```rust
197 #[doc = concat!("use hilbert_2d::{Variant, ", stringify!($SelfT), "::xy2h_discrete};")]
198 ///
199 /// // Hilbert curve of order 2:
200 /// // 5 ―― 6 9 ― 10
201 /// // | | | |
202 /// // 4 7 ―― 8 11
203 /// // | |
204 /// // 3 ―― 2 13 ― 12
205 /// // | |
206 /// // 0 ―― 1 14 ― 15
207 /// let h = xy2h_discrete(2, 1, 2, Variant::Hilbert);
208 ///
209 /// assert_eq!(h, 13);
210 /// ```
211 ///
212 /// [`Variant`]: ../enum.Variant.html
213 ///
214 pub const fn xy2h_discrete(
215 x: $SelfT,
216 y: $SelfT,
217 order: $SelfT,
218 variant: Variant,
219 ) -> $SelfT {
220 // Records how many >>'s are required to isolate the quadrant bits for each subsequent order, starting at 1
221 let mut steps = order - 1;
222 if steps as u32 >= ORDER_MAX {
223 steps = ORDER_MAX as $SelfT - 1;
224 }
225
226 // Extract the bits for the square region from the `square_x` and `square_x` coordinates
227 let u_x = x as usize;
228 let u_y = y as usize;
229 let mut q_x = (u_x >> steps) & 0b1;
230 let mut q_y = (u_y >> steps) & 0b1;
231
232 // Retrieve the quadrant of order 1 equivalent to that square region
233 let mut cur_quadrant = LUTS_YX2H[0b000][q_y][q_x];
234 let mut curve_p = cur_quadrant;
235
236 // Stop here if the given order is 1
237 if steps == 0 {
238 return curve_p;
239 }
240
241 // Depending on the curve variant, the method of choosing the LUT for the `order 1 -> order 2` transition changes
242 let mut lut_index = next_lut_index_variant(0b000, cur_quadrant as usize, variant);
243
244 loop {
245 // Extract the bits for the next square region from the `square_x` and `square_x` coordinates
246 steps -= 1;
247 q_x = (u_x >> steps) & 0b1;
248 q_y = (u_y >> steps) & 0b1;
249
250 // Retrieve the quadrant equivalent to that square region, using the current LUT
251 cur_quadrant = LUTS_YX2H[lut_index][q_y][q_x];
252 curve_p = (curve_p << 2) | cur_quadrant;
253
254 if steps > 0 {
255 // From `order 2 -> order 3` and beyond, the same method of choosing the next LUT is used
256 lut_index = next_lut_index(lut_index, cur_quadrant as usize);
257 } else {
258 break;
259 }
260 }
261
262 curve_p
263 }
264
265 #[cfg(test)]
266 mod tests {
267 use super::*;
268
269 #[test]
270 fn map_discrete_hilbert() {
271 // Test for the central coordinates of a order 3 curve
272 assert_eq!(h2xy_discrete(8, 3, Variant::Hilbert), (2, 2));
273 assert_eq!(h2xy_discrete(9, 3, Variant::Hilbert), (3, 2));
274 assert_eq!(xy2h_discrete(4, 2, 3, Variant::Hilbert), 54);
275 assert_eq!(xy2h_discrete(5, 2, 3, Variant::Hilbert), 55);
276 assert_eq!(h2xy_discrete(11, 3, Variant::Hilbert), (2, 3));
277 assert_eq!(h2xy_discrete(10, 3, Variant::Hilbert), (3, 3));
278 assert_eq!(xy2h_discrete(4, 3, 3, Variant::Hilbert), 53);
279 assert_eq!(xy2h_discrete(5, 3, 3, Variant::Hilbert), 52);
280 assert_eq!(xy2h_discrete(2, 4, 3, Variant::Hilbert), 30);
281 assert_eq!(xy2h_discrete(3, 4, 3, Variant::Hilbert), 31);
282 assert_eq!(h2xy_discrete(32, 3, Variant::Hilbert), (4, 4));
283 assert_eq!(h2xy_discrete(33, 3, Variant::Hilbert), (5, 4));
284 assert_eq!(xy2h_discrete(2, 5, 3, Variant::Hilbert), 29);
285 assert_eq!(xy2h_discrete(3, 5, 3, Variant::Hilbert), 28);
286 assert_eq!(h2xy_discrete(35, 3, Variant::Hilbert), (4, 5));
287 assert_eq!(h2xy_discrete(34, 3, Variant::Hilbert), (5, 5));
288 }
289
290 #[test]
291 fn map_discrete_moore() {
292 // Test for the central coordinates of a order 3 curve
293 assert_eq!(h2xy_discrete(13, 3, Variant::Moore), (2, 2));
294 assert_eq!(h2xy_discrete(14, 3, Variant::Moore), (3, 2));
295 assert_eq!(xy2h_discrete(4, 2, 3, Variant::Moore), 49);
296 assert_eq!(xy2h_discrete(5, 2, 3, Variant::Moore), 50);
297 assert_eq!(h2xy_discrete(12, 3, Variant::Moore), (2, 3));
298 assert_eq!(h2xy_discrete(15, 3, Variant::Moore), (3, 3));
299 assert_eq!(xy2h_discrete(4, 3, 3, Variant::Moore), 48);
300 assert_eq!(xy2h_discrete(5, 3, 3, Variant::Moore), 51);
301 assert_eq!(xy2h_discrete(2, 4, 3, Variant::Moore), 19);
302 assert_eq!(xy2h_discrete(3, 4, 3, Variant::Moore), 16);
303 assert_eq!(h2xy_discrete(47, 3, Variant::Moore), (4, 4));
304 assert_eq!(h2xy_discrete(44, 3, Variant::Moore), (5, 4));
305 assert_eq!(xy2h_discrete(2, 5, 3, Variant::Moore), 18);
306 assert_eq!(xy2h_discrete(3, 5, 3, Variant::Moore), 17);
307 assert_eq!(h2xy_discrete(46, 3, Variant::Moore), (4, 5));
308 assert_eq!(h2xy_discrete(45, 3, Variant::Moore), (5, 5));
309 }
310
311 #[test]
312 fn map_discrete_liu1() {
313 // Test for the central coordinates of a order 3 curve
314 assert_eq!(h2xy_discrete(2, 3, Variant::Liu1), (2, 2));
315 assert_eq!(h2xy_discrete(3, 3, Variant::Liu1), (3, 2));
316 assert_eq!(xy2h_discrete(4, 2, 3, Variant::Liu1), 60);
317 assert_eq!(xy2h_discrete(5, 2, 3, Variant::Liu1), 61);
318 assert_eq!(h2xy_discrete(1, 3, Variant::Liu1), (2, 3));
319 assert_eq!(h2xy_discrete(0, 3, Variant::Liu1), (3, 3));
320 assert_eq!(xy2h_discrete(4, 3, 3, Variant::Liu1), 63);
321 assert_eq!(xy2h_discrete(5, 3, 3, Variant::Liu1), 62);
322 assert_eq!(xy2h_discrete(2, 4, 3, Variant::Liu1), 30);
323 assert_eq!(xy2h_discrete(3, 4, 3, Variant::Liu1), 31);
324 assert_eq!(h2xy_discrete(32, 3, Variant::Liu1), (4, 4));
325 assert_eq!(h2xy_discrete(33, 3, Variant::Liu1), (5, 4));
326 assert_eq!(xy2h_discrete(2, 5, 3, Variant::Liu1), 29);
327 assert_eq!(xy2h_discrete(3, 5, 3, Variant::Liu1), 28);
328 assert_eq!(h2xy_discrete(35, 3, Variant::Liu1), (4, 5));
329 assert_eq!(h2xy_discrete(34, 3, Variant::Liu1), (5, 5));
330 }
331
332 #[test]
333 fn map_discrete_liu2() {
334 // Test for the central coordinates of a order 3 curve
335 assert_eq!(h2xy_discrete(13, 3, Variant::Liu2), (2, 2));
336 assert_eq!(h2xy_discrete(12, 3, Variant::Liu2), (3, 2));
337 assert_eq!(xy2h_discrete(4, 2, 3, Variant::Liu2), 51);
338 assert_eq!(xy2h_discrete(5, 2, 3, Variant::Liu2), 50);
339 assert_eq!(h2xy_discrete(14, 3, Variant::Liu2), (2, 3));
340 assert_eq!(h2xy_discrete(15, 3, Variant::Liu2), (3, 3));
341 assert_eq!(xy2h_discrete(4, 3, 3, Variant::Liu2), 48);
342 assert_eq!(xy2h_discrete(5, 3, 3, Variant::Liu2), 49);
343 assert_eq!(xy2h_discrete(2, 4, 3, Variant::Liu2), 19);
344 assert_eq!(xy2h_discrete(3, 4, 3, Variant::Liu2), 16);
345 assert_eq!(h2xy_discrete(47, 3, Variant::Liu2), (4, 4));
346 assert_eq!(h2xy_discrete(44, 3, Variant::Liu2), (5, 4));
347 assert_eq!(xy2h_discrete(2, 5, 3, Variant::Liu2), 18);
348 assert_eq!(xy2h_discrete(3, 5, 3, Variant::Liu2), 17);
349 assert_eq!(h2xy_discrete(46, 3, Variant::Liu2), (4, 5));
350 assert_eq!(h2xy_discrete(45, 3, Variant::Liu2), (5, 5));
351 }
352
353 #[test]
354 fn map_discrete_liu3() {
355 // Test for the central coordinates of a order 3 curve
356 assert_eq!(h2xy_discrete(8, 3, Variant::Liu3), (2, 2));
357 assert_eq!(h2xy_discrete(9, 3, Variant::Liu3), (3, 2));
358 assert_eq!(xy2h_discrete(4, 2, 3, Variant::Liu3), 60);
359 assert_eq!(xy2h_discrete(5, 2, 3, Variant::Liu3), 61);
360 assert_eq!(h2xy_discrete(11, 3, Variant::Liu3), (2, 3));
361 assert_eq!(h2xy_discrete(10, 3, Variant::Liu3), (3, 3));
362 assert_eq!(xy2h_discrete(4, 3, 3, Variant::Liu3), 63);
363 assert_eq!(xy2h_discrete(5, 3, 3, Variant::Liu3), 62);
364 assert_eq!(xy2h_discrete(2, 4, 3, Variant::Liu3), 30);
365 assert_eq!(xy2h_discrete(3, 4, 3, Variant::Liu3), 31);
366 assert_eq!(h2xy_discrete(32, 3, Variant::Liu3), (4, 4));
367 assert_eq!(h2xy_discrete(33, 3, Variant::Liu3), (5, 4));
368 assert_eq!(xy2h_discrete(2, 5, 3, Variant::Liu3), 29);
369 assert_eq!(xy2h_discrete(3, 5, 3, Variant::Liu3), 28);
370 assert_eq!(h2xy_discrete(35, 3, Variant::Liu3), (4, 5));
371 assert_eq!(h2xy_discrete(34, 3, Variant::Liu3), (5, 5));
372 }
373
374 #[test]
375 fn map_discrete_liu4() {
376 // Test for the central coordinates of a order 3 curve
377 assert_eq!(h2xy_discrete(13, 3, Variant::Liu4), (2, 2));
378 assert_eq!(h2xy_discrete(12, 3, Variant::Liu4), (3, 2));
379 assert_eq!(xy2h_discrete(4, 2, 3, Variant::Liu4), 49);
380 assert_eq!(xy2h_discrete(5, 2, 3, Variant::Liu4), 50);
381 assert_eq!(h2xy_discrete(14, 3, Variant::Liu4), (2, 3));
382 assert_eq!(h2xy_discrete(15, 3, Variant::Liu4), (3, 3));
383 assert_eq!(xy2h_discrete(4, 3, 3, Variant::Liu4), 48);
384 assert_eq!(xy2h_discrete(5, 3, 3, Variant::Liu4), 51);
385 assert_eq!(xy2h_discrete(2, 4, 3, Variant::Liu4), 19);
386 assert_eq!(xy2h_discrete(3, 4, 3, Variant::Liu4), 16);
387 assert_eq!(h2xy_discrete(47, 3, Variant::Liu4), (4, 4));
388 assert_eq!(h2xy_discrete(44, 3, Variant::Liu4), (5, 4));
389 assert_eq!(xy2h_discrete(2, 5, 3, Variant::Liu4), 18);
390 assert_eq!(xy2h_discrete(3, 5, 3, Variant::Liu4), 17);
391 assert_eq!(h2xy_discrete(46, 3, Variant::Liu4), (4, 5));
392 assert_eq!(h2xy_discrete(45, 3, Variant::Liu4), (5, 5));
393 }
394 }
395 }
396 };
397}