Skip to main content

utz_encode/
grid.rs

1//! The grid and interned-CSR builder.
2//!
3//! The builder makes two passes over the geometry:
4//! 1. The edge walk: every cell a ring passes through collects that feature
5//!    id into its candidate set, and a cell with ≥2 candidates is a border
6//!    cell needing PIP.
7//! 2. The scanline fill on a subdivision-finer grid: an even-odd span fill
8//!    per polygon gives per-subcell ownership, aggregated to a dominant
9//!    zone per cell (the interior fill for the primary array and the
10//!    `lookup_coarse` answer).
11
12use std::collections::{HashMap, HashSet};
13
14use ndarray::Array2;
15
16use crate::Feat;
17use utz_common::{NO_ZONE, grid_cell};
18
19/// The grid dimensions for a cell size, `(ncols, nrows)` =
20/// `ceil(360/deg) × ceil(180/deg)`. The sweep tools share this with the
21/// encoder so their cell counts measure exactly the grid it builds.
22#[must_use]
23pub fn grid_dims(deg: f64) -> (usize, usize) {
24    #[expect(
25        clippy::cast_possible_truncation,
26        clippy::cast_sign_loss,
27        reason = "deg >= 0.1 so at most 3600 cells; float as saturates"
28    )]
29    let dims = ((360.0 / deg).ceil() as usize, (180.0 / deg).ceil() as usize);
30    dims
31}
32
33/// Walks the segment `start`→`end` in `deg`-sized steps at 2×
34/// oversampling (the rasterizer's edge density), visiting every
35/// interpolated point including both endpoints. Cell membership per
36/// point is [`utz_common::grid_cell()`]; the sweep tools share this walk
37/// so a change to the sampling density cannot leave them measuring a
38/// different rasterization than the encoder's.
39pub fn walk_edge(start: (f64, f64), end: (f64, f64), deg: f64, visit: &mut impl FnMut(f64, f64)) {
40    let (x0, y0) = start;
41    let (x1, y1) = end;
42    #[expect(
43        clippy::cast_possible_truncation,
44        clippy::cast_sign_loss,
45        reason = "span/deg bounded by world size; float as saturates"
46    )]
47    let steps = ((((x1 - x0).abs()).max((y1 - y0).abs()) / deg * 2.0).ceil() as usize).max(1);
48    for step in 0..=steps {
49        #[expect(
50            clippy::cast_precision_loss,
51            reason = "step ≤ steps ≤ 2·360/deg ≪ 2^53; interpolation parameter"
52        )]
53        let t = step as f64 / steps as f64;
54        visit(x0 + (x1 - x0) * t, y0 + (y1 - y0) * t);
55    }
56}
57
58/// Cell arrays are `[row, col]`-indexed and iterate row-major, the same
59/// order the primary table serializes in.
60pub struct CellGrid {
61    pub deg: f64,
62    /// The sorted candidate feature ids per cell, from the edge walk; an
63    /// empty set means no ring passes through the cell.
64    pub sets: Array2<Vec<u16>>,
65    /// The dominant zone per cell from subcell ownership, or `NO_ZONE` if
66    /// nothing filled the cell.
67    pub dominant: Array2<u16>,
68    /// The per-cell subcell ownership tallies, mapping a candidate id to
69    /// the number of subcells it owns.
70    pub tallies: Array2<Vec<(u16, u32)>>,
71}
72
73impl CellGrid {
74    #[must_use]
75    pub fn ncols(&self) -> usize {
76        self.dominant.ncols()
77    }
78
79    #[must_use]
80    pub fn nrows(&self) -> usize {
81        self.dominant.nrows()
82    }
83}
84
85/// Rasterizes `feats` onto a `deg`-cell grid, with ownership sampled on a
86/// grid `subdivision`× finer (subdivision = 8 at 2° gives 0.25° subcells).
87///
88/// # Panics
89///
90/// Panics if any coordinate is NaN (scanline crossings become unsortable).
91#[must_use]
92pub fn build(feats: &[Feat], deg: f64, subdivision: usize) -> CellGrid {
93    let (ncols, nrows) = grid_dims(deg);
94
95    let mut sets = edge_walk(feats, deg, ncols, nrows);
96    let owner = subcell_owners(
97        feats,
98        deg,
99        subdivision,
100        ncols * subdivision,
101        nrows * subdivision,
102    );
103
104    // ---- aggregate subcell owners to per-cell tallies + dominant ----
105    let mut counts: Array2<HashMap<u16, u32>> = Array2::from_elem((nrows, ncols), HashMap::new());
106    for ((fine_row, fine_col), &zone) in owner.indexed_iter() {
107        if zone != NO_ZONE {
108            *counts[[fine_row / subdivision, fine_col / subdivision]]
109                .entry(zone)
110                .or_insert(0) += 1;
111        }
112    }
113    // tie-break by smallest id: HashMap iteration order is seeded per process,
114    // and a tie decided by it made the whole container nondeterministic
115    let dominant: Array2<u16> = counts.map(|tally| {
116        tally
117            .iter()
118            .max_by_key(|&(&zone, &count)| (count, core::cmp::Reverse(zone)))
119            .map_or(NO_ZONE, |(&zone, _)| zone)
120    });
121    let tallies: Array2<Vec<(u16, u32)>> = counts.map(|tally| {
122        let mut entries: Vec<(u16, u32)> =
123            tally.iter().map(|(&zone, &count)| (zone, count)).collect();
124        entries.sort_unstable();
125        entries
126    });
127    // candidate set = edge walk ∪ subcell owners. The union matters where TZBB
128    // zones deliberately OVERLAP (e.g. Asia/Shanghai + Asia/Urumqi over
129    // Xinjiang): a zone covering a whole cell leaves no ring in it, so the edge
130    // walk alone misses it and would mislabel the cell interior.
131    for (set, tally) in sets.iter_mut().zip(tallies.iter()) {
132        set.extend(tally.iter().map(|&(zone, _)| zone));
133    }
134    let sets: Array2<Vec<u16>> = sets.map(|set| {
135        let mut sorted_ids: Vec<u16> = set.iter().copied().collect();
136        sorted_ids.sort_unstable();
137        sorted_ids
138    });
139
140    CellGrid {
141        deg,
142        sets,
143        dominant,
144        tallies,
145    }
146}
147
148/// Pass 1 walks every ring edge in `deg`-sized steps. Every cell an edge
149/// passes through collects that feature id into its candidate set, and a
150/// cell with ≥2 candidates is a border cell needing PIP.
151fn edge_walk(feats: &[Feat], deg: f64, ncols: usize, nrows: usize) -> Array2<HashSet<u16>> {
152    let mut sets: Array2<HashSet<u16>> = Array2::from_elem((nrows, ncols), HashSet::new());
153    for (feature_id, feature) in feats.iter().enumerate() {
154        let feature_id = u16::try_from(feature_id).expect("feature id fits u16");
155        for poly in &feature.polys {
156            for ring in poly {
157                let ring_len = ring.len();
158                for i in 0..ring_len {
159                    walk_edge(ring[i], ring[(i + 1) % ring_len], deg, &mut |lon, lat| {
160                        let (row, col) = grid_cell(lon, lat, deg, ncols, nrows);
161                        sets[[row, col]].insert(feature_id);
162                    });
163                }
164            }
165        }
166    }
167    sets
168}
169
170/// Pass 2 runs an even-odd scanline fill per polygon on the
171/// `subdivision`×-finer grid, yielding per-subcell ownership (later
172/// aggregated to a dominant zone per cell).
173///
174/// # Panics
175/// Panics if any coordinate is NaN (the crossing xs become unsortable).
176fn subcell_owners(
177    feats: &[Feat],
178    deg: f64,
179    subdivision: usize,
180    fine_cols: usize,
181    fine_rows: usize,
182) -> Array2<u16> {
183    #[expect(
184        clippy::cast_precision_loss,
185        reason = "subdivision factor = 8 in practice, ≪ 2^53; exact in f64"
186    )]
187    let subcell_deg = deg / subdivision as f64;
188    let mut owner: Array2<u16> = Array2::from_elem((fine_rows, fine_cols), NO_ZONE);
189    // crossing xs per row, reused per poly
190    let mut row_x: Vec<Vec<f32>> = vec![Vec::new(); fine_rows];
191    for (feature_id, feature) in feats.iter().enumerate() {
192        for poly in &feature.polys {
193            // bucket edge crossings of every ring (exterior + holes) by row: even-odd
194            let mut touched: Vec<u32> = Vec::new();
195            for ring in poly {
196                let ring_len = ring.len();
197                for i in 0..ring_len {
198                    let (x0, y0) = ring[i];
199                    let (x1, y1) = ring[(i + 1) % ring_len];
200                    #[expect(
201                        clippy::float_cmp,
202                        reason = "skip exactly-horizontal edges before dividing by y1-y0; near-horizontal must still cross"
203                    )]
204                    if y0 == y1 {
205                        continue;
206                    }
207                    let (ylo, yhi) = if y0 < y1 { (y0, y1) } else { (y1, y0) };
208                    // rows whose center lat is in [ylo, yhi)
209                    #[expect(
210                        clippy::cast_possible_truncation,
211                        clippy::cast_sign_loss,
212                        reason = "row index bounded to [0, fine_rows); float as saturates"
213                    )]
214                    let j0 = (((ylo + 90.0) / subcell_deg - 0.5).ceil().max(0.0)) as usize;
215                    #[expect(
216                        clippy::cast_possible_truncation,
217                        reason = "row index bounded to [0, fine_rows); float as saturates"
218                    )]
219                    #[expect(
220                        clippy::cast_precision_loss,
221                        reason = "fine_rows = nrows*subdivision ≤ 8*1800; exact in f64"
222                    )]
223                    let j1 = (((yhi + 90.0) / subcell_deg - 0.5)
224                        .floor()
225                        .min(fine_rows as f64 - 1.0)) as isize;
226                    let mut j = j0.cast_signed();
227                    while j <= j1 {
228                        #[expect(
229                            clippy::cast_precision_loss,
230                            reason = "row index j < fine_rows ≤ 8*1800; exact in f64"
231                        )]
232                        let lat = -90.0 + (j as f64 + 0.5) * subcell_deg;
233                        if lat >= ylo && lat < yhi {
234                            let x = x0 + (lat - y0) / (y1 - y0) * (x1 - x0);
235                            if row_x[j.cast_unsigned()].is_empty() {
236                                touched.push(u32::try_from(j).expect("row index fits u32"));
237                            }
238                            #[expect(
239                                clippy::cast_possible_truncation,
240                                reason = "crossing x stored at f32 by design (row_x)"
241                            )]
242                            row_x[j.cast_unsigned()].push(x as f32);
243                        }
244                        j += 1;
245                    }
246                }
247            }
248            // fill alternate spans
249            for &j in &touched {
250                let xs = &mut row_x[j as usize];
251                xs.sort_unstable_by(|a, b| a.partial_cmp(b).unwrap());
252                for pair in xs.chunks_exact(2) {
253                    let (xa, xb) = (f64::from(pair[0]), f64::from(pair[1]));
254                    #[expect(
255                        clippy::cast_possible_truncation,
256                        clippy::cast_sign_loss,
257                        reason = "col index bounded to [0, fine_cols); float as saturates"
258                    )]
259                    let i0 = (((xa + 180.0) / subcell_deg - 0.5).ceil().max(0.0)) as usize;
260                    #[expect(
261                        clippy::cast_possible_truncation,
262                        reason = "col index bounded to [0, fine_cols); float as saturates"
263                    )]
264                    #[expect(
265                        clippy::cast_precision_loss,
266                        reason = "fine_cols = ncols*subdivision ≤ 8*3600; exact in f64"
267                    )]
268                    let i1 = (((xb + 180.0) / subcell_deg - 0.5)
269                        .floor()
270                        .min(fine_cols as f64 - 1.0)) as isize;
271                    let mut row = owner.row_mut(j as usize);
272                    let mut i = i0.cast_signed();
273                    while i <= i1 {
274                        row[i.cast_unsigned()] =
275                            u16::try_from(feature_id).expect("feature id fits u16");
276                        i += 1;
277                    }
278                }
279                xs.clear();
280            }
281        }
282    }
283    owner
284}
285
286/// The candidate-list ordering inside the interned CSR.
287#[derive(Clone, Copy, PartialEq, Debug)]
288pub enum Order {
289    /// Ascending feature id, which gives maximal interning (the baseline).
290    IdSorted,
291    /// Descending global zone area, which is deterministic per set and
292    /// interns the same as `IdSorted`.
293    AreaDesc,
294    /// This cell's dominant zone first with the rest id-sorted, which gives
295    /// the best early-exit but breaks interning.
296    CellDominantFirst,
297}
298
299/// The serializable grid prefilter: it stores one u16 per cell plus the
300/// interned candidate lists in compressed-sparse-row form.
301pub struct Csr {
302    /// One u16 per cell. With the high bit clear the value is a zone id
303    /// (`NO_ZONE` marker semantics are left to the container); with the
304    /// high bit set it is an index into the interned lists.
305    pub primary: Vec<u16>,
306    /// The start offset of each interned list in [`Csr::list_ids`].
307    pub list_offsets: Vec<u16>,
308    /// The interned candidate lists, concatenated.
309    pub list_ids: Vec<u16>,
310    /// The number of distinct interned lists.
311    pub uniq_lists: usize,
312}
313
314impl Csr {
315    #[must_use]
316    pub fn bytes(&self) -> usize {
317        self.primary.len() * 2 + self.list_offsets.len() * 2 + self.list_ids.len() * 2
318    }
319}
320
321/// Builds the interned CSR. `areas` (global zone area, in any consistent
322/// unit) is used by `AreaDesc` and `CellDominantFirst`.
323///
324/// # Panics
325///
326/// Panics with `AreaDesc` if a candidate's `areas` entry is NaN.
327#[must_use]
328pub fn intern_csr(grid: &CellGrid, order: Order, areas: &[f64]) -> Csr {
329    let mut primary = vec![0u16; grid.dominant.len()];
330    let mut lists: Vec<Vec<u16>> = Vec::new();
331    let mut index: HashMap<Vec<u16>, u16> = HashMap::new();
332    let by_area = |list: &mut Vec<u16>| {
333        list.sort_unstable_by(|&a, &b| {
334            areas[b as usize]
335                .partial_cmp(&areas[a as usize])
336                .unwrap()
337                .then(a.cmp(&b))
338        });
339    };
340    // row-major zip: primary cell c ↔ the arrays' cell c
341    for ((set, &dominant), primary_cell) in grid
342        .sets
343        .iter()
344        .zip(grid.dominant.iter())
345        .zip(primary.iter_mut())
346    {
347        if set.len() > 1 {
348            let mut list = set.clone(); // already id-sorted
349            match order {
350                Order::IdSorted => {}
351                Order::AreaDesc => by_area(&mut list),
352                Order::CellDominantFirst => {
353                    if let Some(position) = list.iter().position(|&zone| zone == dominant) {
354                        list.remove(position);
355                        list.insert(0, dominant);
356                    }
357                }
358            }
359            let next = u16::try_from(lists.len())
360                .expect("interned list index fits u16 (encode re-checks 15-bit)");
361            let list_index = *index.entry(list.clone()).or_insert_with(|| {
362                lists.push(list);
363                next
364            });
365            *primary_cell = utz_common::BORDER_FLAG | list_index;
366        } else {
367            // interior (single candidate) or no-ring cell: dominant zone
368            let zone = if set.len() == 1 { set[0] } else { dominant };
369            // an unclaimed cell already carries the wire marker (ids stay
370            // below NO_ZONE by the 15-bit guard)
371            *primary_cell = zone;
372        }
373    }
374    let mut list_offsets = Vec::with_capacity(lists.len() + 1);
375    let mut list_ids = Vec::new();
376    list_offsets.push(0u16);
377    for list in &lists {
378        list_ids.extend_from_slice(list);
379        list_offsets.push(
380            u16::try_from(list_ids.len()).expect("list ids fit u16 offsets (encode re-checks)"),
381        );
382    }
383    Csr {
384        primary,
385        list_offsets,
386        list_ids,
387        uniq_lists: lists.len(),
388    }
389}
390
391/// Approximates the global area per feature (an equirectangular shoelace
392/// with cos-lat correction; exteriors minus holes, clamped ≥ 0). The
393/// values serve ranking only.
394#[must_use]
395pub fn feat_areas(feats: &[Feat]) -> Vec<f64> {
396    feats
397        .iter()
398        .map(|feature| {
399            let mut area = 0.0f64;
400            for poly in &feature.polys {
401                for (ring_index, ring) in poly.iter().enumerate() {
402                    let ring_contribution = ring_area(ring);
403                    if ring_index == 0 {
404                        area += ring_contribution;
405                    } else {
406                        area -= ring_contribution;
407                    }
408                }
409            }
410            area.max(0.0)
411        })
412        .collect()
413}
414
415fn ring_area(ring: &[(f64, f64)]) -> f64 {
416    if ring.len() < 3 {
417        return 0.0;
418    }
419    #[expect(
420        clippy::cast_precision_loss,
421        reason = "ring.len() ≪ 2^53; mean latitude"
422    )]
423    let midlat = ring.iter().map(|&(_, y)| y).sum::<f64>() / ring.len() as f64;
424    let mut sum = 0.0;
425    for i in 0..ring.len() {
426        let (x0, y0) = ring[i];
427        let (x1, y1) = ring[(i + 1) % ring.len()];
428        sum += x0 * y1 - x1 * y0;
429    }
430    (sum.abs() / 2.0) * midlat.to_radians().cos().abs()
431}