hilbert_curve/
lib.rs

1//! **hilbert_curve** is a simple implementation of
2//! [Hilbert curve](https://en.wikipedia.org/wiki/Hilbert_curve) mapping algorithms in Rust.
3//!
4//! It assumes a square space divided into n by n cells (n being a power of 2) with integral
5//! coordinates: (0, 0) in the lower left corner, (n − 1, n − 1) in the upper right corner, and a
6//! distance d that starts at 0 in the lower left corner and goes to n^2 − 1 in the lower-right
7//! corner.
8
9use std::mem;
10
11/// Convert a one-dimensional distance `d` to a pair of (x, y) coordinates.
12pub fn convert_1d_to_2d(d: usize, n: usize) -> (usize, usize) {
13    assert!((n & (n - 1)) == 0, "n must be a power of 2");
14    let mut s = 1;
15    let mut t = d;
16    let (mut x, mut y) = (0, 0);
17    let (mut rx, mut ry);
18
19    while s < n {
20        rx = 1 & (t / 2);
21        ry = 1 & (t ^ rx);
22        rotate(s, &mut x, &mut y, rx, ry);
23        x += s * rx;
24        y += s * ry;
25        t /= 4;
26        s *= 2;
27    }
28
29    (x, y)
30}
31
32/// Convert a pair of (x, y) coordinates to a one-dimensional distance.
33pub fn convert_2d_to_1d (x: usize, y: usize, n: usize) -> usize {
34    assert!((n & (n - 1)) == 0, "n must be a power of 2");
35    let mut d = 0;
36    let mut s = n / 2;
37    let (mut x, mut y) = (x, y);
38    let (mut rx, mut ry);
39
40    while s > 0 {
41        rx = if (x & s) > 0 { 1 } else { 0 };
42        ry = if (y & s) > 0 { 1 } else { 0 };
43        d += s * s * ((3 * rx) ^ ry);
44        rotate(s, &mut x, &mut y, rx, ry);
45        s /= 2
46    }
47
48    d
49}
50
51// Rotate a quadrant
52fn rotate(n: usize, x: &mut usize, y: &mut usize, rx: usize, ry: usize) {
53    if ry == 0 {
54        if rx == 1 {
55            *x = n.wrapping_sub(1).wrapping_sub(*x);
56            *y = n.wrapping_sub(1).wrapping_sub(*y);
57        }
58
59        mem::swap(x, y);
60    }
61}
62
63#[cfg(test)]
64mod tests {
65    use super::*;
66
67    #[test]
68    fn reversibility() {
69        for &n in &[2, 4, 8, 16, 32, 64, 128, 256] {
70            for d in 0..(n * n) {
71                let (x, y) = convert_1d_to_2d(d, n);
72                assert_eq!(convert_2d_to_1d(x, y, n), d);
73            }
74        }
75    }
76}
hilbert_curve/lib.rs

hilbert_curve/
lib.rs
