hilbert_curve_rust/
hilbert_curve_algorithm.rs

1use crate::coordinate_value::CoordinateValue;
2use std::mem;
3
4pub struct HilbertCurveAlgorithm {
5    order: u16,
6}
7
8impl HilbertCurveAlgorithm {
9    pub fn new(order: u16) -> Self {
10        Self { order }
11    }
12
13    pub fn index_to_point(&self, index: u32) -> CoordinateValue {
14        let number_row = u32::pow(2, self.order.into());
15        let maximum_data_size = u32::pow(number_row, 2);
16        if index >= maximum_data_size {
17            panic!("The index is above the supported amount of space the current order support. Reduce the index or increase the order.");
18        }
19
20        let mut point = CoordinateValue { x: 0, y: 0 };
21        let mut rx: u32;
22        let mut ry: u32;
23        let mut order_index: u32 = 1;
24        let mut quadrant: u32 = index;
25
26        while order_index < number_row {
27            rx = self.get_rx(quadrant);
28            ry = self.get_ry(quadrant, rx);
29            HilbertCurveAlgorithm::rotate_point(&mut point, rx, ry, order_index); // Rotate depending on rx and ry value
30            HilbertCurveAlgorithm::move_point(&mut point, rx, ry, order_index);
31            quadrant = quadrant / 4; // 4 point per quadrant, hence we jump by 4
32            order_index = order_index * 2; // Each order double the size of element per row (and column)
33        }
34        return point;
35    }
36
37    pub fn point_to_index(&self, point: CoordinateValue) -> u32 {
38        let number_of_row = u32::pow(2, self.order.into());
39        if point.x >= number_of_row || point.y >= number_of_row {
40            panic!("The point must be in range with the order");
41        }
42        let mut rx: u32 = 0;
43        let mut ry: u32 = 0;
44        let mut index: u32 = 0;
45
46        let mut row_index = number_of_row / 2;
47        let mut new_point = point.clone(); // Ensure we are not mutating the original
48        while row_index > 0 {
49            HilbertCurveAlgorithm::update_rx_from_point(&mut rx, new_point, row_index);
50            HilbertCurveAlgorithm::update_ry_from_point(&mut ry, new_point, row_index);
51            index += HilbertCurveAlgorithm::get_new_index_from_rows(row_index, rx, ry);
52            HilbertCurveAlgorithm::rotate_point(&mut new_point, rx, ry, number_of_row);
53            row_index /= 2;
54        }
55
56        return index;
57    }
58
59    fn get_rx(&self, quadrant: u32) -> u32 {
60        return 1 & (quadrant / 2);
61    }
62    fn get_ry(&self, quadrant: u32, rx: u32) -> u32 {
63        let asd: u32 = quadrant ^ rx;
64        let and_op: u32 = 1 & asd;
65        return and_op;
66    }
67    fn rotate_point(mut point: &mut CoordinateValue, rx: u32, ry: u32, number_columns: u32) -> () {
68        if ry == 0 {
69            if rx == 1 {
70                point.x = number_columns as u32 - 1 - point.x as u32;
71                point.y = number_columns as u32 - 1 - point.y as u32;
72            }
73            mem::swap(&mut point.x, &mut point.y);
74        }
75    }
76    fn move_point(mut point: &mut CoordinateValue, rx: u32, ry: u32, order_index: u32) -> () {
77        point.x = point.x + order_index * rx;
78        point.y = point.y + order_index * ry;
79    }
80
81    fn update_rx_from_point(rx: &mut u32, point: CoordinateValue, order_index: u32) -> () {
82        *rx = HilbertCurveAlgorithm::update_point_value_from_number(point.x, order_index);
83    }
84
85    fn update_ry_from_point(ry: &mut u32, point: CoordinateValue, order_index: u32) -> () {
86        *ry = HilbertCurveAlgorithm::update_point_value_from_number(point.y, order_index);
87    }
88    fn update_point_value_from_number(number_n: u32, order_index: u32) -> u32 {
89        let and_result = number_n & order_index; // 0, 1, 2
90        return if and_result > 0 { 1 } else { 0 };
91    }
92    fn get_new_index_from_rows(rows_index: u32, rx: u32, ry: u32) -> u32 {
93        return rows_index * rows_index * ((3 * rx) ^ ry);
94    }
95    pub fn offset_point(&self, point: CoordinateValue, projection_width: u32) -> CoordinateValue {
96        let number_of_row: u32 = u32::pow(2, self.order as u32);
97        let len = projection_width / number_of_row;
98        return CoordinateValue {
99            x: point.x * len + len / 2,
100            y: point.y * len + len / 2,
101        };
102    }
103    pub fn deoffset_point(&self, point: CoordinateValue, projection_width: u32) -> CoordinateValue {
104        let number_of_row: u32 = u32::pow(2, self.order as u32);
105        let len = projection_width / number_of_row;
106        return CoordinateValue {
107            x: point.x / len,
108            y: point.y / len,
109        };
110    }
111}
112
113#[cfg(test)]
114mod test_get_rx {
115    use super::*;
116
117    #[test]
118    fn internal_get_rx() {
119        let hilbert_curve = HilbertCurveAlgorithm::new(0);
120        assert_eq!(hilbert_curve.get_rx(0), 0);
121        assert_eq!(hilbert_curve.get_rx(1), 0);
122        assert_eq!(hilbert_curve.get_rx(2), 1);
123        assert_eq!(hilbert_curve.get_rx(3), 1);
124        assert_eq!(hilbert_curve.get_rx(4), 0);
125        assert_eq!(hilbert_curve.get_rx(5), 0);
126        assert_eq!(hilbert_curve.get_rx(6), 1);
127    }
128}
129
130#[cfg(test)]
131mod test_get_ry {
132    use super::*;
133
134    #[test]
135    fn internal_get_ry_with_rx_0() {
136        let hilbert_curve = HilbertCurveAlgorithm::new(0);
137        assert_eq!(hilbert_curve.get_ry(0, 0), 0);
138        assert_eq!(hilbert_curve.get_ry(1, 0), 1);
139        assert_eq!(hilbert_curve.get_ry(2, 0), 0);
140        assert_eq!(hilbert_curve.get_ry(3, 0), 1);
141        assert_eq!(hilbert_curve.get_ry(4, 0), 0);
142        assert_eq!(hilbert_curve.get_ry(5, 0), 1);
143        assert_eq!(hilbert_curve.get_ry(6, 0), 0);
144    }
145
146    #[test]
147    fn internal_get_ry_with_rx_1() {
148        let hilbert_curve = HilbertCurveAlgorithm::new(0);
149        assert_eq!(hilbert_curve.get_ry(0, 1), 1);
150        assert_eq!(hilbert_curve.get_ry(1, 1), 0);
151        assert_eq!(hilbert_curve.get_ry(2, 1), 1);
152        assert_eq!(hilbert_curve.get_ry(3, 1), 0);
153        assert_eq!(hilbert_curve.get_ry(4, 1), 1);
154        assert_eq!(hilbert_curve.get_ry(5, 1), 0);
155        assert_eq!(hilbert_curve.get_ry(6, 1), 1);
156    }
157}
158
159#[cfg(test)]
160mod test_move_point {
161    use super::*;
162
163    #[test]
164    fn internal_move_point_order_1_rx_0_no_move() {
165        let order = 1;
166        let rx = 0;
167        let ry = 0;
168        let mut point = CoordinateValue { x: 123, y: 456 };
169        HilbertCurveAlgorithm::move_point(&mut point, rx, ry, order);
170        assert_eq!(point.x, 123);
171        assert_eq!(point.y, 456);
172    }
173
174    #[test]
175    fn internal_move_point_order_1_rx_1_move() {
176        let order = 1;
177        let rx = 1;
178        let ry = 0;
179        let mut point = CoordinateValue { x: 123, y: 456 };
180        HilbertCurveAlgorithm::move_point(&mut point, rx, ry, order);
181        assert_eq!(point.x, 124);
182        assert_eq!(point.y, 456);
183    }
184
185    #[test]
186    fn internal_move_point_order_1_ry_0_no_move() {
187        let order = 1;
188        let rx = 0;
189        let ry = 0;
190        let mut point = CoordinateValue { x: 123, y: 456 };
191        HilbertCurveAlgorithm::move_point(&mut point, rx, ry, order);
192        assert_eq!(point.x, 123);
193        assert_eq!(point.y, 456);
194    }
195
196    #[test]
197    fn internal_move_point_order_1_ry_1_move() {
198        let order = 1;
199        let rx = 0;
200        let ry = 1;
201        let mut point = CoordinateValue { x: 123, y: 456 };
202        HilbertCurveAlgorithm::move_point(&mut point, rx, ry, order);
203        assert_eq!(point.x, 123);
204        assert_eq!(point.y, 457);
205    }
206    #[test]
207    fn internal_move_point_order_2_rx_0_no_move() {
208        let order = 2;
209        let rx = 0;
210        let ry = 0;
211        let mut point = CoordinateValue { x: 123, y: 456 };
212        HilbertCurveAlgorithm::move_point(&mut point, rx, ry, order);
213        assert_eq!(point.x, 123);
214        assert_eq!(point.y, 456);
215    }
216
217    #[test]
218    fn internal_move_point_order_2_rx_1_move() {
219        let order = 2;
220        let rx = 1;
221        let ry = 0;
222        let mut point = CoordinateValue { x: 123, y: 456 };
223        HilbertCurveAlgorithm::move_point(&mut point, rx, ry, order);
224        assert_eq!(point.x, 125);
225        assert_eq!(point.y, 456);
226    }
227
228    #[test]
229    fn internal_move_point_order_2_ry_0_no_move() {
230        let order = 2;
231        let rx = 0;
232        let ry = 0;
233        let mut point = CoordinateValue { x: 123, y: 456 };
234        HilbertCurveAlgorithm::move_point(&mut point, rx, ry, order);
235        assert_eq!(point.x, 123);
236        assert_eq!(point.y, 456);
237    }
238
239    #[test]
240    fn internal_move_point_order_2_ry_1_move() {
241        let order = 2;
242        let rx = 0;
243        let ry = 1;
244        let mut point = CoordinateValue { x: 123, y: 456 };
245        HilbertCurveAlgorithm::move_point(&mut point, rx, ry, order);
246        assert_eq!(point.x, 123);
247        assert_eq!(point.y, 458);
248    }
249}
250
251#[cfg(test)]
252mod test_get_point_value_from_number {
253    use super::*;
254    #[test]
255    fn internal_get_point_value_from_number_order1() {
256        assert_eq!(
257            0,
258            HilbertCurveAlgorithm::update_point_value_from_number(0, 1)
259        );
260        assert_eq!(
261            1,
262            HilbertCurveAlgorithm::update_point_value_from_number(1, 1)
263        );
264        assert_eq!(
265            0,
266            HilbertCurveAlgorithm::update_point_value_from_number(2, 1)
267        );
268        assert_eq!(
269            1,
270            HilbertCurveAlgorithm::update_point_value_from_number(3, 1)
271        );
272    }
273    #[test]
274    fn internal_get_point_value_from_number_order2() {
275        assert_eq!(
276            0,
277            HilbertCurveAlgorithm::update_point_value_from_number(0, 2)
278        );
279        assert_eq!(
280            0,
281            HilbertCurveAlgorithm::update_point_value_from_number(1, 2)
282        );
283        assert_eq!(
284            1,
285            HilbertCurveAlgorithm::update_point_value_from_number(2, 2)
286        );
287        assert_eq!(
288            1,
289            HilbertCurveAlgorithm::update_point_value_from_number(3, 2)
290        );
291        assert_eq!(
292            0,
293            HilbertCurveAlgorithm::update_point_value_from_number(4, 2)
294        );
295        assert_eq!(
296            0,
297            HilbertCurveAlgorithm::update_point_value_from_number(5, 2)
298        );
299        assert_eq!(
300            1,
301            HilbertCurveAlgorithm::update_point_value_from_number(6, 2)
302        );
303        assert_eq!(
304            1,
305            HilbertCurveAlgorithm::update_point_value_from_number(7, 2)
306        );
307    }
308    #[test]
309    fn internal_get_point_value_from_number_order4() {
310        assert_eq!(
311            0,
312            HilbertCurveAlgorithm::update_point_value_from_number(0, 4)
313        );
314        assert_eq!(
315            0,
316            HilbertCurveAlgorithm::update_point_value_from_number(1, 4)
317        );
318        assert_eq!(
319            0,
320            HilbertCurveAlgorithm::update_point_value_from_number(2, 4)
321        );
322        assert_eq!(
323            0,
324            HilbertCurveAlgorithm::update_point_value_from_number(3, 4)
325        );
326        assert_eq!(
327            1,
328            HilbertCurveAlgorithm::update_point_value_from_number(4, 4)
329        );
330        assert_eq!(
331            1,
332            HilbertCurveAlgorithm::update_point_value_from_number(5, 4)
333        );
334        assert_eq!(
335            1,
336            HilbertCurveAlgorithm::update_point_value_from_number(6, 4)
337        );
338        assert_eq!(
339            1,
340            HilbertCurveAlgorithm::update_point_value_from_number(7, 4)
341        );
342    }
343}
344
345#[cfg(test)]
346mod test_rotate_point {
347    use super::*;
348    #[test]
349    fn internal_rotate_point_0_0_col1_x_0_y_0() {
350        let mut coordinate = CoordinateValue { x: 0, y: 0 };
351        HilbertCurveAlgorithm::rotate_point(&mut coordinate, 0, 0, 1);
352        assert_eq!(0, coordinate.x, "X value is wrong");
353        assert_eq!(0, coordinate.y, "Y value is wrong");
354    }
355    #[test]
356    fn internal_rotate_point_0_0_col1_x_0_y_1() {
357        let mut coordinate = CoordinateValue { x: 0, y: 0 };
358        HilbertCurveAlgorithm::rotate_point(&mut coordinate, 0, 1, 1);
359        assert_eq!(0, coordinate.x, "X value is wrong");
360        assert_eq!(0, coordinate.y, "Y value is wrong");
361    }
362    #[test]
363    fn internal_rotate_point_0_0_col1_x_1_y_0() {
364        let mut coordinate = CoordinateValue { x: 0, y: 0 };
365        HilbertCurveAlgorithm::rotate_point(&mut coordinate, 1, 0, 1);
366        assert_eq!(0, coordinate.x, "X value is wrong");
367        assert_eq!(0, coordinate.y, "Y value is wrong");
368    }
369    #[test]
370    fn internal_rotate_point_1_1_col1_x_1_y_0() {
371        let mut coordinate = CoordinateValue { x: 1, y: 1 };
372        HilbertCurveAlgorithm::rotate_point(&mut coordinate, 1, 0, 2);
373        assert_eq!(0, coordinate.x, "X value is wrong");
374        assert_eq!(0, coordinate.y, "Y value is wrong");
375    }
376    #[test]
377    fn internal_rotate_point_0_0_col1_x_1_y_1() {
378        let mut coordinate = CoordinateValue { x: 0, y: 0 };
379        HilbertCurveAlgorithm::rotate_point(&mut coordinate, 1, 1, 1);
380        assert_eq!(0, coordinate.x, "X value is wrong");
381        assert_eq!(0, coordinate.y, "Y value is wrong");
382    }
383    #[test]
384    fn internal_rotate_point_1_1_col1_x_1_y_1() {
385        let mut coordinate = CoordinateValue { x: 1, y: 1 };
386        HilbertCurveAlgorithm::rotate_point(&mut coordinate, 1, 1, 2);
387        assert_eq!(1, coordinate.x, "X value is wrong");
388        assert_eq!(1, coordinate.y, "Y value is wrong");
389    }
390    #[test]
391    fn internal_rotate_point_1_2_col1_x_0_y_1() {
392        let mut coordinate = CoordinateValue { x: 1, y: 2 };
393        HilbertCurveAlgorithm::rotate_point(&mut coordinate, 0, 1, 2);
394        assert_eq!(1, coordinate.x, "X value is wrong");
395        assert_eq!(2, coordinate.y, "Y value is wrong");
396    }
397    #[test]
398    fn internal_rotate_point_1_2_col1_x_0_y_0() {
399        let mut coordinate = CoordinateValue { x: 1, y: 2 };
400        HilbertCurveAlgorithm::rotate_point(&mut coordinate, 0, 0, 2);
401        assert_eq!(2, coordinate.x, "X value is wrong");
402        assert_eq!(1, coordinate.y, "Y value is wrong");
403    }
404
405    #[test]
406    fn internal_rotate_point_numbercolumn_8_point_0_0_x_0_y_0() {
407        let mut coordinate = CoordinateValue { x: 0, y: 0 };
408        HilbertCurveAlgorithm::rotate_point(&mut coordinate, 0, 0, 8);
409        assert_eq!(0, coordinate.x, "X value is wrong");
410        assert_eq!(0, coordinate.y, "Y value is wrong");
411    }
412    #[test]
413    fn internal_rotate_point_numbercolumn_8_point_0_0_x_0_y_1() {
414        let mut coordinate = CoordinateValue { x: 0, y: 0 };
415        HilbertCurveAlgorithm::rotate_point(&mut coordinate, 0, 1, 8);
416        assert_eq!(0, coordinate.x, "X value is wrong");
417        assert_eq!(0, coordinate.y, "Y value is wrong");
418    }
419    #[test]
420    fn internal_rotate_point_numbercolumn_8_point_0_0_x_1_y_0() {
421        let mut coordinate = CoordinateValue { x: 0, y: 0 };
422        HilbertCurveAlgorithm::rotate_point(&mut coordinate, 1, 0, 8);
423        assert_eq!(7, coordinate.x, "X value is wrong");
424        assert_eq!(7, coordinate.y, "Y value is wrong");
425    }
426    #[test]
427    fn internal_rotate_point_numbercolumn_8_point_1_1_x_1_y_0() {
428        let mut coordinate = CoordinateValue { x: 1, y: 1 };
429        HilbertCurveAlgorithm::rotate_point(&mut coordinate, 1, 0, 8);
430        assert_eq!(6, coordinate.x, "X value is wrong");
431        assert_eq!(6, coordinate.y, "Y value is wrong");
432    }
433    #[test]
434    fn internal_rotate_point_numbercolumn_8_point_0_0_x_1_y_1() {
435        let mut coordinate = CoordinateValue { x: 0, y: 0 };
436        HilbertCurveAlgorithm::rotate_point(&mut coordinate, 1, 1, 8);
437        assert_eq!(0, coordinate.x, "X value is wrong");
438        assert_eq!(0, coordinate.y, "Y value is wrong");
439    }
440}
441
442#[cfg(test)]
443mod test_get_new_index_from_rows {
444    use super::*;
445    #[test]
446    fn get_new_index_from_rows_index_1_x_0_y_0() {
447        let result = HilbertCurveAlgorithm::get_new_index_from_rows(1, 0, 0);
448        assert_eq!(0, result);
449    }
450    #[test]
451    fn get_new_index_from_rows_index_1_x_0_y_1() {
452        let result = HilbertCurveAlgorithm::get_new_index_from_rows(1, 0, 1);
453        assert_eq!(1, result);
454    }
455    #[test]
456    fn get_new_index_from_rows_index_1_x_1_y_0() {
457        let result = HilbertCurveAlgorithm::get_new_index_from_rows(1, 1, 0);
458        assert_eq!(3, result);
459    }
460    #[test]
461    fn get_new_index_from_rows_index_1_x_1_y_1() {
462        let result = HilbertCurveAlgorithm::get_new_index_from_rows(1, 1, 1);
463        assert_eq!(2, result);
464    }
465    #[test]
466    fn get_new_index_from_rows_index_2_x_0_y_0() {
467        let result = HilbertCurveAlgorithm::get_new_index_from_rows(2, 0, 0);
468        assert_eq!(0, result);
469    }
470    #[test]
471    fn get_new_index_from_rows_index_2_x_0_y_1() {
472        let result = HilbertCurveAlgorithm::get_new_index_from_rows(2, 0, 1);
473        assert_eq!(4, result);
474    }
475    #[test]
476    fn get_new_index_from_rows_index_2_x_1_y_0() {
477        let result = HilbertCurveAlgorithm::get_new_index_from_rows(2, 1, 0);
478        assert_eq!(12, result);
479    }
480    #[test]
481    fn get_new_index_from_rows_index_2_x_1_y_1() {
482        let result = HilbertCurveAlgorithm::get_new_index_from_rows(2, 1, 1);
483        assert_eq!(8, result);
484    }
485}
486
487#[cfg(test)]
488mod test_offset_point {
489    use super::*;
490
491    #[test]
492    fn test_offset_point_positive() {
493        let hilbert_curve = HilbertCurveAlgorithm::new(3);
494        let result = hilbert_curve.offset_point(CoordinateValue { x: 0, y: 3 }, 128);
495        assert_eq!(8, result.x, "X value is wrong");
496        assert_eq!(56, result.y, "Y value is wrong");
497    }
498}
499
500#[cfg(test)]
501mod test_deoffset_point {
502    use super::*;
503
504    #[test]
505    fn test_offset_point_positive() {
506        let hilbert_curve = HilbertCurveAlgorithm::new(3);
507        let result = hilbert_curve.deoffset_point(CoordinateValue { x: 8, y: 56 }, 128);
508        assert_eq!(0, result.x, "X value is wrong");
509        assert_eq!(3, result.y, "Y value is wrong");
510    }
511}
hilbert_curve_rust/hilbert_curve_algorithm.rs

hilbert_curve_rust/
hilbert_curve_algorithm.rs
