1use std::collections::{HashMap, HashSet};
13
14use ndarray::Array2;
15
16use crate::Feat;
17use utz_common::{NO_ZONE, grid_cell};
18
19#[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
33pub 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
58pub struct CellGrid {
61 pub deg: f64,
62 pub sets: Array2<Vec<u16>>,
65 pub dominant: Array2<u16>,
68 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#[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 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 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 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
148fn 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
170fn 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 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 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 #[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 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#[derive(Clone, Copy, PartialEq, Debug)]
288pub enum Order {
289 IdSorted,
291 AreaDesc,
294 CellDominantFirst,
297}
298
299pub struct Csr {
302 pub primary: Vec<u16>,
306 pub list_offsets: Vec<u16>,
308 pub list_ids: Vec<u16>,
310 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#[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 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(); 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 let zone = if set.len() == 1 { set[0] } else { dominant };
369 *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#[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}