umsh_node/
location.rs

1//! Variable-precision geographic location encoding.
2//!
3//! [`NodeLocation`] represents a geographic position as a 1–7 byte grid code.
4//! Each byte refines the location to a 16×16 sub-grid of the parent cell, with the
5//! high nibble indexing longitude and the low nibble indexing latitude.
6//!
7//! The encoding has a useful truncation property: dropping trailing bytes gives the
8//! correct lower-precision encoding of the same position — no recomputation needed.
9//!
10//! # Encoding
11//!
12//! For a given precision N (1–7 bytes), two 4N-bit indices are computed:
13//!
14//! ```text
15//! lon_index = floor((lon + 180) × 16^N / 360)
16//! lat_index = floor((lat +  90) × 16^N / 180)
17//! ```
18//!
19//! Nibbles are extracted most-significant-first into bytes:
20//!
21//! ```text
22//! byte[k] = ((lon_index >> (4×(N-1-k))) & 0xF) << 4
23//!         | ((lat_index >> (4×(N-1-k))) & 0xF)
24//! ```
25//!
26//! # Precision
27//!
28//! | Bytes | Equator cell size (approx.) |
29//! |------:|:----------------------------:|
30//! |   1   | 2,500 × 1,250 km            |
31//! |   2   | 156 × 78 km                 |
32//! |   3   | 9.8 × 4.9 km                |
33//! |   4   | 610 × 305 m                 |
34//! |   5   | 38 × 19 m                   |
35//! |   6   | 2.4 × 1.2 m                 |
36//! |   7   | 15 × 7.5 cm                 |
37//!
38//! # Feature: `f64`
39//!
40//! By default all floating-point arithmetic uses `f32`, which is adequate for
41//! precisions 1–5 (cells ≥ 19 m). Enable the `f64` crate feature for accurate
42//! encoding and decoding at 6–7 byte precision.
43
44use core::fmt;
45
46/// Maximum supported precision in bytes.
47pub const MAX_PRECISION: u8 = 7;
48
49/// A variable-precision geographic location encoded as a 1–7 byte grid code.
50///
51/// Each byte refines the location to a 16×16 sub-grid. Within each byte, the
52/// high nibble indexes longitude and the low nibble indexes latitude. All
53/// `(longitude, latitude)` tuples in this type use that order.
54///
55/// The zero-length `UNSPECIFIED` sentinel represents an unknown location.
56#[derive(Clone, Copy, PartialEq, Eq, Hash)]
57pub struct NodeLocation {
58    len: u8,
59    bytes: [u8; MAX_PRECISION as usize],
60}
61
62impl NodeLocation {
63    /// An unspecified location with zero-byte precision.
64    pub const UNSPECIFIED: NodeLocation = NodeLocation {
65        len: 0,
66        bytes: [0; MAX_PRECISION as usize],
67    };
68
69    /// Construct from a byte slice, silently truncating to [`MAX_PRECISION`].
70    /// Never panics.
71    pub fn from_bytes(bytes: &[u8]) -> Self {
72        let len = bytes.len().min(MAX_PRECISION as usize) as u8;
73        let mut buf = [0u8; MAX_PRECISION as usize];
74        buf[..len as usize].copy_from_slice(&bytes[..len as usize]);
75        Self { len, bytes: buf }
76    }
77
78    /// Encode a `(longitude, latitude)` position in degrees at the given precision.
79    ///
80    /// `precision` is clamped to [`MAX_PRECISION`]. Inputs are clamped to valid
81    /// ranges (`[-180, +180]` and `[-90, +90]`).
82    ///
83    /// Internal arithmetic uses `f32` by default. Enable the `f64` crate feature
84    /// for accurate results at 6–7 byte precision.
85    pub fn from_lat_lon(lon: f32, lat: f32, precision: u8) -> Self {
86        let precision = precision.min(MAX_PRECISION);
87        if precision == 0 {
88            return Self::UNSPECIFIED;
89        }
90        let lon = lon.clamp(-180.0, 180.0);
91        let lat = lat.clamp(-90.0, 90.0);
92        let (lon_idx, lat_idx) = encode_indices(lon, lat, precision as u32);
93
94        let mut bytes = [0u8; MAX_PRECISION as usize];
95        for k in 0..precision as usize {
96            let shift = 4 * (precision as usize - 1 - k);
97            let hi = ((lon_idx >> shift) & 0xF) as u8;
98            let lo = ((lat_idx >> shift) & 0xF) as u8;
99            bytes[k] = (hi << 4) | lo;
100        }
101        Self {
102            len: precision,
103            bytes,
104        }
105    }
106
107    /// Encode a `(longitude, latitude)` position in degrees at the given precision.
108    ///
109    /// Only available with the `f64` crate feature. Prefer this over
110    /// [`from_lat_lon`](Self::from_lat_lon) when working with f64 coordinates and
111    /// 6–7 byte precision.
112    #[cfg(feature = "f64")]
113    pub fn from_lat_lon_f64(lon: f64, lat: f64, precision: u8) -> Self {
114        Self::from_lat_lon(lon as f32, lat as f32, precision)
115    }
116
117    /// The raw encoded bytes.
118    pub fn as_bytes(&self) -> &[u8] {
119        &self.bytes[..self.len as usize]
120    }
121
122    /// Number of encoded bytes (0 if unspecified).
123    pub fn len(&self) -> usize {
124        self.len as usize
125    }
126
127    /// Returns `true` if this location is unspecified (zero-byte precision).
128    pub fn is_unspecified(&self) -> bool {
129        self.len == 0
130    }
131
132    /// Precision level (0–7). Zero means unspecified.
133    pub fn precision(&self) -> u8 {
134        self.len
135    }
136
137    /// Return a copy truncated to at most `precision` bytes.
138    ///
139    /// Because the encoding is strictly hierarchical, the truncated value is the
140    /// correct encoding of the same position at the lower precision.
141    pub fn clamped(&self, precision: u8) -> Self {
142        Self {
143            len: self.len.min(precision.min(MAX_PRECISION)),
144            bytes: self.bytes,
145        }
146    }
147
148    /// The grid cell as `((lon_min, lat_min), (lon_max, lat_max))`, in degrees.
149    ///
150    /// Cell bounds are half-open `[lo, hi)`, matching the floor-based encoding.
151    /// An unspecified location returns the full globe `((-180, -90), (180, 90))`.
152    pub fn bounds(&self) -> ((f32, f32), (f32, f32)) {
153        if self.len == 0 {
154            return ((-180.0, -90.0), (180.0, 90.0));
155        }
156        let (lon_idx, lat_idx) = self.decode_indices();
157        let n = self.len as u32;
158        let (lon_lo, lon_hi) = decode_range(lon_idx, 360.0, -180.0, n);
159        let (lat_lo, lat_hi) = decode_range(lat_idx, 180.0, -90.0, n);
160        ((lon_lo, lat_lo), (lon_hi, lat_hi))
161    }
162
163    /// Center of the encoded grid cell as `(longitude, latitude)`, in degrees.
164    pub fn center(&self) -> (f32, f32) {
165        let ((lon_lo, lat_lo), (lon_hi, lat_hi)) = self.bounds();
166        ((lon_lo + lon_hi) * 0.5, (lat_lo + lat_hi) * 0.5)
167    }
168
169    /// Returns `true` if `(longitude, latitude)` falls within this cell.
170    ///
171    /// An unspecified location contains all points.
172    pub fn contains(&self, lon: f32, lat: f32) -> bool {
173        let ((lon_lo, lat_lo), (lon_hi, lat_hi)) = self.bounds();
174        lon >= lon_lo && lon < lon_hi && lat >= lat_lo && lat < lat_hi
175    }
176
177    /// Returns `true` if `other` is the same cell or a sub-cell of this one.
178    ///
179    /// An unspecified location contains everything. A finer location cannot
180    /// contain a coarser one.
181    pub fn contains_location(&self, other: &Self) -> bool {
182        if self.len == 0 {
183            return true;
184        }
185        if other.len < self.len {
186            return false;
187        }
188        other.bytes[..self.len as usize] == self.bytes[..self.len as usize]
189    }
190
191    /// Reconstruct the longitude and latitude grid indices from the stored bytes.
192    fn decode_indices(&self) -> (u32, u32) {
193        let mut lon = 0u32;
194        let mut lat = 0u32;
195        for &b in &self.bytes[..self.len as usize] {
196            lon = (lon << 4) | ((b >> 4) as u32);
197            lat = (lat << 4) | ((b & 0xF) as u32);
198        }
199        (lon, lat)
200    }
201}
202
203// --- Internal float helpers (cfg-selected) ---
204
205/// Compute (lon_idx, lat_idx) from clamped f32 coordinates and precision.
206#[inline]
207fn encode_indices(lon: f32, lat: f32, n: u32) -> (u32, u32) {
208    #[cfg(feature = "f64")]
209    {
210        let scale = (1u64 << (4 * n)) as f64;
211        let lon_idx = ((lon as f64 + 180.0) * scale / 360.0) as u32;
212        let lat_idx = ((lat as f64 + 90.0) * scale / 180.0) as u32;
213        let max_idx = (scale as u32).saturating_sub(1);
214        (lon_idx.min(max_idx), lat_idx.min(max_idx))
215    }
216    #[cfg(not(feature = "f64"))]
217    {
218        let scale = (1u64 << (4 * n)) as f32;
219        let lon_idx = ((lon + 180.0) * scale / 360.0) as u32;
220        let lat_idx = ((lat + 90.0) * scale / 180.0) as u32;
221        let max_idx = (scale as u32).saturating_sub(1);
222        (lon_idx.min(max_idx), lat_idx.min(max_idx))
223    }
224}
225
226/// Decode one axis: returns (cell_lo, cell_hi) in degrees.
227#[inline]
228fn decode_range(idx: u32, range: f32, offset: f32, n: u32) -> (f32, f32) {
229    #[cfg(feature = "f64")]
230    {
231        let scale = (1u64 << (4 * n)) as f64;
232        let lo = (idx as f64 * range as f64 / scale + offset as f64) as f32;
233        let hi = ((idx as f64 + 1.0) * range as f64 / scale + offset as f64) as f32;
234        (lo, hi)
235    }
236    #[cfg(not(feature = "f64"))]
237    {
238        let scale = (1u64 << (4 * n)) as f32;
239        let lo = idx as f32 * range / scale + offset;
240        let hi = (idx as f32 + 1.0) * range / scale + offset;
241        (lo, hi)
242    }
243}
244
245// --- Trait impls ---
246
247impl Default for NodeLocation {
248    fn default() -> Self {
249        Self::UNSPECIFIED
250    }
251}
252
253/// Displays as `"longitude, latitude"` with decimal places matched to the encoded precision.
254///
255/// An unspecified location displays as `"(unspecified)"`.
256impl fmt::Display for NodeLocation {
257    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
258        if self.len == 0 {
259            return f.write_str("(unspecified)");
260        }
261        let (lon, lat) = self.center();
262        let dp = self.len.saturating_sub(1) as usize;
263        write!(f, "{:.*}, {:.*}", dp, lon, dp, lat)
264    }
265}
266
267impl fmt::Debug for NodeLocation {
268    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
269        if self.len == 0 {
270            return write!(f, "NodeLocation(unspecified)");
271        }
272        write!(f, "NodeLocation({} @ precision {})", self, self.len)
273    }
274}
275
276/// Converts to the `(longitude, latitude)` center of the cell.
277impl From<NodeLocation> for (f32, f32) {
278    fn from(loc: NodeLocation) -> Self {
279        loc.center()
280    }
281}
282
283/// Encodes a `(longitude, latitude)` pair at maximum precision (7 bytes).
284impl From<(f32, f32)> for NodeLocation {
285    fn from((lon, lat): (f32, f32)) -> Self {
286        Self::from_lat_lon(lon, lat, MAX_PRECISION)
287    }
288}
289
290/// Encodes a `(longitude, latitude)` pair at maximum precision (7 bytes).
291///
292/// Only available with the `f64` crate feature.
293#[cfg(feature = "f64")]
294impl From<(f64, f64)> for NodeLocation {
295    fn from((lon, lat): (f64, f64)) -> Self {
296        Self::from_lat_lon(lon as f32, lat as f32, MAX_PRECISION)
297    }
298}
299
300#[cfg(test)]
301mod tests {
302    use super::*;
303
304    // --- from_bytes ---
305
306    #[test]
307    fn from_bytes_roundtrips() {
308        let src = [0x2B, 0x95, 0x51];
309        let loc = NodeLocation::from_bytes(&src);
310        assert_eq!(loc.as_bytes(), &src);
311        assert_eq!(loc.len(), 3);
312    }
313
314    #[test]
315    fn from_bytes_truncates_to_max_precision() {
316        let loc = NodeLocation::from_bytes(&[0u8; 10]);
317        assert_eq!(loc.len(), MAX_PRECISION as usize);
318    }
319
320    #[test]
321    fn from_bytes_empty_is_unspecified() {
322        let loc = NodeLocation::from_bytes(&[]);
323        assert!(loc.is_unspecified());
324        assert_eq!(loc, NodeLocation::UNSPECIFIED);
325    }
326
327    // --- encoding ---
328
329    #[test]
330    fn san_jose_3_byte() {
331        // (LON, LAT) = (−121.883°, 37.331°) → 2B 95 51 per spec worked example.
332        let loc = NodeLocation::from_lat_lon(-121.883, 37.331, 3);
333        assert_eq!(loc.as_bytes(), &[0x2B, 0x95, 0x51]);
334    }
335
336    #[test]
337    fn encode_contains_source_point() {
338        let (lon, lat) = (13.405f32, 52.52f32); // Berlin
339        // f32 inputs have ~2 m resolution near this longitude; at precision 6–7
340        // (cells ≤ 1.2 m) mixed f32/f64 rounding can place the boundary at the
341        // input value, making the round-trip unreliable. Cap at precision 5.
342        for precision in 1..=5u8 {
343            let loc = NodeLocation::from_lat_lon(lon, lat, precision);
344            assert!(loc.contains(lon, lat), "failed at precision={precision}");
345        }
346    }
347
348    /// With the `f64` feature the decode path uses f64 arithmetic. Verify the cell
349    /// width at precision 5 (scale = 16^5 = 2^20, width ≈ 3.43e-4°) where f32
350    /// output still has enough resolution to represent the difference accurately.
351    #[cfg(feature = "f64")]
352    #[test]
353    fn f64_decode_cell_width_precision_5() {
354        let loc = NodeLocation::from_lat_lon(13.405, 52.52, 5);
355        let ((lon_lo, _), (lon_hi, _)) = loc.bounds();
356        let expected = 360.0f64 / (1u64 << 20) as f64;
357        let actual = (lon_hi - lon_lo) as f64;
358        assert!(
359            (actual - expected).abs() < 1e-7,
360            "cell width {actual} != {expected}"
361        );
362    }
363
364    #[test]
365    fn antimeridian_does_not_panic() {
366        let _ = NodeLocation::from_lat_lon(180.0, 0.0, 7);
367        let _ = NodeLocation::from_lat_lon(-180.0, 0.0, 7);
368    }
369
370    #[test]
371    fn poles_do_not_panic() {
372        let _ = NodeLocation::from_lat_lon(0.0, 90.0, 7);
373        let _ = NodeLocation::from_lat_lon(0.0, -90.0, 7);
374    }
375
376    #[test]
377    fn zero_precision_gives_unspecified() {
378        assert_eq!(
379            NodeLocation::from_lat_lon(0.0, 0.0, 0),
380            NodeLocation::UNSPECIFIED
381        );
382    }
383
384    #[test]
385    fn excess_precision_clamped_to_max() {
386        assert_eq!(
387            NodeLocation::from_lat_lon(0.0, 0.0, 255).len(),
388            MAX_PRECISION as usize
389        );
390    }
391
392    // --- truncation property ---
393
394    #[test]
395    fn truncation_matches_direct_lower_precision() {
396        let (lon, lat) = (-0.118f32, 51.509f32); // London
397        let full = NodeLocation::from_lat_lon(lon, lat, 7);
398        for k in 1..=7u8 {
399            let direct = NodeLocation::from_lat_lon(lon, lat, k);
400            let truncated = full.clamped(k);
401            assert_eq!(
402                direct.as_bytes(),
403                truncated.as_bytes(),
404                "mismatch at precision={k}"
405            );
406        }
407    }
408
409    // --- bounds and center ---
410
411    #[test]
412    fn center_is_within_bounds() {
413        let loc = NodeLocation::from_lat_lon(2.349, 48.864, 5); // Paris
414        let (lon_c, lat_c) = loc.center();
415        assert!(loc.contains(lon_c, lat_c));
416    }
417
418    #[test]
419    fn unspecified_bounds_is_whole_globe() {
420        let ((lon_lo, lat_lo), (lon_hi, lat_hi)) = NodeLocation::UNSPECIFIED.bounds();
421        assert_eq!(
422            (lon_lo, lat_lo, lon_hi, lat_hi),
423            (-180.0, -90.0, 180.0, 90.0)
424        );
425    }
426
427    #[test]
428    fn bounds_span_shrinks_by_16_per_byte() {
429        let (lon, lat) = (0.0f32, 0.0f32);
430        let loc1 = NodeLocation::from_lat_lon(lon, lat, 1);
431        let loc2 = NodeLocation::from_lat_lon(lon, lat, 2);
432        let ((lo1, _), (hi1, _)) = loc1.bounds();
433        let ((lo2, _), (hi2, _)) = loc2.bounds();
434        let ratio = (hi1 - lo1) / (hi2 - lo2);
435        assert!((ratio - 16.0).abs() < 1e-4, "expected 16×, got {ratio}");
436    }
437
438    // --- contains ---
439
440    #[test]
441    fn contains_source_point() {
442        let loc = NodeLocation::from_lat_lon(-87.629, 41.878, 4); // Chicago
443        assert!(loc.contains(-87.629, 41.878));
444    }
445
446    #[test]
447    fn contains_location_coarser_contains_finer() {
448        let coarse = NodeLocation::from_lat_lon(139.691, 35.689, 3); // Tokyo area
449        let fine = NodeLocation::from_lat_lon(139.691, 35.689, 6);
450        assert!(coarse.contains_location(&fine));
451        assert!(!fine.contains_location(&coarse));
452    }
453
454    #[test]
455    fn unspecified_contains_everything() {
456        let anywhere = NodeLocation::from_lat_lon(77.209, 28.614, 7); // New Delhi
457        assert!(NodeLocation::UNSPECIFIED.contains_location(&anywhere));
458    }
459
460    // --- From traits ---
461
462    #[test]
463    fn from_f32_tuple_roundtrips_approximately() {
464        let (lon, lat) = (151.209f32, -33.868f32); // Sydney
465        let loc = NodeLocation::from((lon, lat));
466        let (out_lon, out_lat): (f32, f32) = loc.into();
467        assert!((out_lon - lon).abs() < 0.001, "lon drift={}", out_lon - lon);
468        assert!((out_lat - lat).abs() < 0.001, "lat drift={}", out_lat - lat);
469    }
470
471    // --- Display ---
472
473    #[test]
474    fn display_unspecified() {
475        assert_eq!(NodeLocation::UNSPECIFIED.to_string(), "(unspecified)");
476    }
477
478    #[test]
479    fn display_precision_one_no_decimal_point() {
480        let loc = NodeLocation::from_lat_lon(0.0, 0.0, 1);
481        let s = loc.to_string();
482        assert!(!s.contains('.'), "unexpected decimal in '{s}'");
483    }
484
485    #[test]
486    fn display_precision_four_has_three_decimal_places() {
487        let loc = NodeLocation::from_lat_lon(0.0, 0.0, 4);
488        let s = loc.to_string();
489        for part in s.split(", ") {
490            let dp = part.find('.').map(|i| part.len() - i - 1).unwrap_or(0);
491            assert_eq!(dp, 3, "wrong decimal places in '{s}'");
492        }
493    }
494}
umsh_node/location.rs

umsh_node/
location.rs
