Skip to main content

qualia_geospatial/
hilbert.rs

1//! 2D Hilbert Space-Filling Curve Mapping.
2//!
3//! Maps 2D spatial coordinates $(x, y)$ to a 1D scalar index $d$ and vice-versa,
4//! preserving spatial proximity for memory-mapped chunk caching and GPU spatial lookups.
5
6/// Converts 2D grid coordinates $(x, y)$ to a 1D Hilbert index $d$.
7///
8/// `order`: Bits per dimension (e.g. order 6 for $64 \times 64$ grid, order 16 for $65536 \times 65536$).
9pub fn xy_to_hilbert(mut x: u32, mut y: u32, order: usize) -> u64 {
10    let mut d = 0u64;
11    let mut s = 1u32 << (order - 1);
12
13    while s > 0 {
14        let rx = if (x & s) > 0 { 1u32 } else { 0u32 };
15        let ry = if (y & s) > 0 { 1u32 } else { 0u32 };
16
17        d += (s as u64) * (s as u64) * ((3 * rx) ^ ry) as u64;
18
19        rot(s, &mut x, &mut y, rx, ry);
20        s >>= 1;
21    }
22
23    d
24}
25
26/// Converts a 1D Hilbert index $d$ back to 2D grid coordinates $(x, y)$.
27pub fn hilbert_to_xy(mut d: u64, order: usize) -> (u32, u32) {
28    let mut x = 0u32;
29    let mut y = 0u32;
30    let mut s = 1u32;
31
32    while s < (1u32 << order) {
33        let rx = 1 & (d / 2) as u32;
34        let ry = 1 & (d as u32 ^ rx);
35
36        rot(s, &mut x, &mut y, rx, ry);
37        x += s * rx;
38        y += s * ry;
39        d /= 4;
40        s <<= 1;
41    }
42
43    (x, y)
44}
45
46/// Rotation / reflection transform for Hilbert quadrants.
47#[inline]
48fn rot(n: u32, x: &mut u32, y: &mut u32, rx: u32, ry: u32) {
49    if ry == 0 {
50        if rx == 1 {
51            *x = (n - 1).wrapping_sub(*x);
52            *y = (n - 1).wrapping_sub(*y);
53        }
54        std::mem::swap(x, y);
55    }
56}