tile_grid/
hilbert.rs

1#![allow(clippy::unreadable_literal)]
2
3use crate::tms_iterator::TileIterator;
4
5// From https://github.com/stadiamaps/pmtiles-rs/blob/b5a9f82/src/tile.rs (Apache/MIT)
6
7const PYRAMID_SIZE_BY_ZOOM: [u64; 21] = [
8    /*  0 */ 0,
9    /*  1 */ 1,
10    /*  2 */ 5,
11    /*  3 */ 21,
12    /*  4 */ 85,
13    /*  5 */ 341,
14    /*  6 */ 1365,
15    /*  7 */ 5461,
16    /*  8 */ 21845,
17    /*  9 */ 87381,
18    /* 10 */ 349525,
19    /* 11 */ 1398101,
20    /* 12 */ 5592405,
21    /* 13 */ 22369621,
22    /* 14 */ 89478485,
23    /* 15 */ 357913941,
24    /* 16 */ 1431655765,
25    /* 17 */ 5726623061,
26    /* 18 */ 22906492245,
27    /* 19 */ 91625968981,
28    /* 20 */ 366503875925,
29];
30
31pub(crate) fn tile_id(z: u8, x: u64, y: u64) -> u64 {
32    // The 0/0/0 case is not needed for the base id computation, but it will fail hilbert_2d::u64::xy2h_discrete
33    if z == 0 {
34        return 0;
35    }
36
37    let tile_id = hilbert_2d::u64::xy2h_discrete(x, y, z.into(), hilbert_2d::Variant::Hilbert);
38
39    base_id(z) + tile_id
40}
41
42fn base_id(z: u8) -> u64 {
43    let z_ind = usize::from(z);
44    if z_ind < PYRAMID_SIZE_BY_ZOOM.len() {
45        PYRAMID_SIZE_BY_ZOOM[z_ind]
46    } else {
47        let last_ind = PYRAMID_SIZE_BY_ZOOM.len() - 1;
48        PYRAMID_SIZE_BY_ZOOM[last_ind] + (last_ind..z_ind).map(|i| 1_u64 << (i << 1)).sum::<u64>()
49    }
50}
51
52#[cfg(test)]
53mod test {
54    use super::tile_id;
55
56    #[test]
57    fn test_tile_id() {
58        assert_eq!(tile_id(0, 0, 0), 0);
59        assert_eq!(tile_id(1, 1, 0), 4);
60        assert_eq!(tile_id(2, 1, 3), 11);
61        assert_eq!(tile_id(3, 3, 0), 26);
62        assert_eq!(tile_id(20, 0, 0), 366503875925);
63        assert_eq!(tile_id(21, 0, 0), 1466015503701);
64        assert_eq!(tile_id(22, 0, 0), 5864062014805);
65        assert_eq!(tile_id(22, 0, 0), 5864062014805);
66        assert_eq!(tile_id(23, 0, 0), 23456248059221);
67        assert_eq!(tile_id(24, 0, 0), 93824992236885);
68        assert_eq!(tile_id(25, 0, 0), 375299968947541);
69        assert_eq!(tile_id(26, 0, 0), 1501199875790165);
70        assert_eq!(tile_id(27, 0, 0), 6004799503160661);
71        assert_eq!(tile_id(28, 0, 0), 24019198012642645);
72    }
73}
74
75use crate::{Tms, Xyz};
76
77/// Get the tile corresponding to a Hilbert index
78pub(crate) fn hilbert_tile(h: u64) -> Xyz {
79    if let Some(z) = (0..27).find(|z| h >= base_id(*z) && h < base_id(*z + 1)) {
80        let (x, y) = if h > 0 {
81            hilbert_2d::u64::h2xy_discrete(h - base_id(z), z as u64, hilbert_2d::Variant::Hilbert)
82        } else {
83            (0, 0)
84        };
85        Xyz::new(x, y, z)
86    } else {
87        Xyz::new(0, 0, 0)
88    }
89}
90
91impl Tms {
92    /// Get the hilbert index of a tile
93    pub fn hilbert_id(&self, tile: &Xyz) -> u64 {
94        tile_id(tile.z, tile.x, tile.y)
95    }
96
97    /// Get the tile corresponding to a Hilbert index
98    pub fn hilbert_to_tile(&self, h: u64) -> Xyz {
99        hilbert_tile(h)
100    }
101}
102
103/// Hilbert iterator
104pub struct HilbertIterator {
105    h: u64,
106    base_id: u64,
107    next_base_id: u64,
108    z: u8,
109    z_max: u8,
110}
111
112impl HilbertIterator {
113    pub(crate) fn new(z_min: u8, z_max: u8) -> HilbertIterator {
114        let z = z_min;
115        let h = tile_id(z, 0, 0);
116        HilbertIterator {
117            h,
118            base_id: base_id(z),
119            next_base_id: base_id(z + 1),
120            z,
121            z_max,
122        }
123    }
124}
125
126impl Iterator for HilbertIterator {
127    type Item = Xyz;
128
129    fn next(&mut self) -> Option<Self::Item> {
130        if self.z > self.z_max {
131            return None;
132        }
133
134        // current Xyz
135        let (x, y) = if self.h > 0 {
136            hilbert_2d::u64::h2xy_discrete(
137                self.h - self.base_id,
138                self.z.into(),
139                hilbert_2d::Variant::Hilbert,
140            )
141        } else {
142            (0, 0)
143        };
144        let current = Xyz::new(x, y, self.z);
145
146        // increment
147        self.h += 1;
148        if self.h >= self.next_base_id {
149            self.z += 1;
150            self.base_id = base_id(self.z);
151            self.next_base_id = base_id(self.z + 1);
152        }
153
154        Some(current)
155    }
156}
157
158impl TileIterator for HilbertIterator {}
159
160#[cfg(test)]
161mod test_tms {
162    use super::*;
163
164    #[test]
165    fn hilbert_iter() {
166        let griditer = HilbertIterator::new(0, 2);
167        let cells = griditer.collect::<Vec<_>>();
168        assert_eq!(
169            cells,
170            vec![
171                Xyz::new(0, 0, 0),
172                Xyz::new(0, 0, 1),
173                Xyz::new(0, 1, 1),
174                Xyz::new(1, 1, 1),
175                Xyz::new(1, 0, 1),
176                Xyz::new(0, 0, 2),
177                Xyz::new(1, 0, 2),
178                Xyz::new(1, 1, 2),
179                Xyz::new(0, 1, 2),
180                Xyz::new(0, 2, 2),
181                Xyz::new(0, 3, 2),
182                Xyz::new(1, 3, 2),
183                Xyz::new(1, 2, 2),
184                Xyz::new(2, 2, 2),
185                Xyz::new(2, 3, 2),
186                Xyz::new(3, 3, 2),
187                Xyz::new(3, 2, 2),
188                Xyz::new(3, 1, 2),
189                Xyz::new(2, 1, 2),
190                Xyz::new(2, 0, 2),
191                Xyz::new(3, 0, 2)
192            ]
193        );
194
195        let griditer = HilbertIterator::new(1, 1);
196        let cells = griditer.collect::<Vec<_>>();
197        assert_eq!(
198            cells,
199            vec![
200                Xyz::new(0, 0, 1),
201                Xyz::new(0, 1, 1),
202                Xyz::new(1, 1, 1),
203                Xyz::new(1, 0, 1),
204            ]
205        );
206
207        let griditer = HilbertIterator::new(21, 20);
208        assert_eq!(griditer.count(), 0);
209    }
210
211    #[test]
212    fn test_hilbert_tile() {
213        assert_eq!(hilbert_tile(0), Xyz::new(0, 0, 0));
214        assert_eq!(hilbert_tile(4), Xyz::new(1, 0, 1));
215        assert_eq!(hilbert_tile(11), Xyz::new(1, 3, 2));
216        assert_eq!(hilbert_tile(26), Xyz::new(3, 0, 3));
217    }
218}
tile_grid/hilbert.rs

tile_grid/
hilbert.rs
