hilbert_curve_generator/
lib.rs

1use std::error::Error;
2mod brgc;
3mod skilling_transform;
4/*
5 * The main feature of the library
6 *
7 * The Hilbert Curve constructor takes two parameters:
8 *      n: the number of dimensions
9 *          (can be either 2d for planar curves, or 3d for cubes)
10 *      p: the number of binary bits used to represent the position of each vertex
11 *          (your resulting curve/cube will have 2^n * 2^n vertices in each face)
12 *
13 * The resulting Vector of (u32,u32,u32) represents the ordered traversal of each
14 * (x,y,z) vertex in a Hilbert space filling curve defined by n and p.
15 */
16#[derive(Debug)]
17pub struct HilbertCurve {
18    pub coordinates: Vec<(u32, u32, u32)>,
19}
20
21impl HilbertCurve {
22    pub fn new(n: u32, p: u32) -> Result<Self, Box<dyn Error>> {
23        if !(n == 2 || n == 3) {
24            return Err("invalid value for n | allowed values for n are 2 and 3".into());
25        }
26
27        let brgc = brgc::Brgc { index: 0 };
28        let num_vertices = u32::pow(u32::pow(2, p), n).try_into().unwrap();
29        let brgc_vec = brgc.take(num_vertices).collect();
30
31        let hilbert_indices = skilling_transform::skilling_transform(brgc_vec, n, p);
32
33        match n {
34            2 => {
35                let coordinates = hilbert_indices
36                    .iter()
37                    .map(|index| into_xyz_decimal_2d(*index, n, p))
38                    .collect();
39                Ok(Self { coordinates })
40            }
41            3 => {
42                let coordinates = hilbert_indices
43                    .iter()
44                    .map(|index| into_xyz_decimal_3d(*index, n, p))
45                    .collect();
46                Ok(Self { coordinates })
47            }
48            _ => Err("invalid value for n | allowed values for n are 2 and 3".into()),
49        }
50    }
51}
52
53pub fn into_xyz_binary_2d(hilbert_coordinates: u32, n: u32, p: u32) -> (u32, u32) {
54    let binary_hilbert_encoded_coordinates = format!("{:b}", hilbert_coordinates);
55    // insert any necessary leading zeros so that the string is N * P characters
56    // this is necessary to ensure each bit is correctly
57    //      assigned to its x,y, or z axis
58    let mut padding = String::new();
59    while binary_hilbert_encoded_coordinates.len() + padding.len() < (n * p) as usize {
60        padding.push_str("0");
61    }
62    padding.push_str(&binary_hilbert_encoded_coordinates);
63    let padded_hilbert_coordinate_string = padding;
64    // take every nth character and assign it to its axis
65    // two axis decoding, only x and y coordinates
66    let x = padded_hilbert_coordinate_string
67        .chars()
68        .step_by(2)
69        .collect::<String>()
70        .parse::<u32>()
71        .unwrap();
72    let y = padded_hilbert_coordinate_string
73        .chars()
74        .skip(1)
75        .step_by(2)
76        .collect::<String>()
77        .parse::<u32>()
78        .unwrap();
79    (x, y)
80}
81
82pub fn into_xyz_binary_3d(hilbert_coordinates: u32, n: u32, p: u32) -> (u32, u32, u32) {
83    let binary_hilbert_encoded_coordinates = format!("{:b}", hilbert_coordinates);
84    // insert any necessary leading zeros so that the string is N * P characters
85    // this is necessary to ensure each bit is correctly
86    // assigned to its x,y, or z axis
87    let mut padding = String::new();
88    while binary_hilbert_encoded_coordinates.len() + padding.len() < (n * p) as usize {
89        padding.push_str("0");
90    }
91    padding.push_str(&binary_hilbert_encoded_coordinates);
92    let padded_hilbert_coordinate_string = padding;
93
94    // take every nth character and assign it to its axis
95    // three axis decoding, x,y,z coordinates
96    let x = padded_hilbert_coordinate_string
97        .chars()
98        .step_by(3)
99        .collect::<String>()
100        .parse::<u32>()
101        .unwrap();
102    let y = padded_hilbert_coordinate_string
103        .chars()
104        .skip(1)
105        .step_by(3)
106        .collect::<String>()
107        .parse::<u32>()
108        .unwrap();
109    let z = padded_hilbert_coordinate_string
110        .chars()
111        .skip(2)
112        .step_by(3)
113        .collect::<String>()
114        .parse::<u32>()
115        .unwrap();
116    (x, y, z)
117}
118
119pub fn into_xyz_decimal_2d(hilbert_coordinates: u32, n: u32, p: u32) -> (u32, u32, u32) {
120    let (x_bin, y_bin) = into_xyz_binary_2d(hilbert_coordinates, n, p);
121    let x_dec = u32::from_str_radix(&x_bin.to_string(), 2).unwrap();
122    let y_dec = u32::from_str_radix(&y_bin.to_string(), 2).unwrap();
123    (x_dec, y_dec, 0)
124}
125
126pub fn into_xyz_decimal_3d(hilbert_coordinates: u32, n: u32, p: u32) -> (u32, u32, u32) {
127    let (x_bin, y_bin, z_bin) = into_xyz_binary_3d(hilbert_coordinates, n, p);
128    let x_dec = u32::from_str_radix(&x_bin.to_string(), 2).unwrap();
129    let y_dec = u32::from_str_radix(&y_bin.to_string(), 2).unwrap();
130    let z_dec = u32::from_str_radix(&z_bin.to_string(), 2).unwrap();
131    (x_dec, y_dec, z_dec)
132}
hilbert_curve_generator/lib.rs

hilbert_curve_generator/
lib.rs
