Skip to main content

utz_build/
density.rs

1//! Population density for density-weighted simplification ([GHS-POP
2//! R2023A]).
3//!
4//! The source is the European Commission Joint Research Centre's Global
5//! Human Settlement Layer population grid, © European Union 1995–2023
6//! ([CC BY 4.0]; Schiavina, Freire, Carioli, MacManus 2023,
7//! <https://doi.org/10.2905/2FF68A52-5B5B-4A22-8F40-C41DA8332CFE>).
8//! It is a single global `GeoTIFF` in WGS84 at 30 arc-seconds (~1 km),
9//! storing the population *count* per cell, as a free direct download.
10//! The one-time build fetches the ~460 MB zip through the
11//! [`crate::download`] cache, stream-decodes the tif tile by tile while
12//! summing 8×8 blocks into a 4-arc-minute grid, converts counts to
13//! people/km², and caches the result as a small flat sidecar (~58 MB).
14//! Steady-state builds read only the sidecar.
15//!
16//! The resolution rationale is that weighting only needs
17//! order-of-magnitude density near a boundary: 4′ (~7.4 km) cells are far
18//! below any useful epsilon ceiling while keeping the grid cheap to hold in
19//! memory.
20//!
21//! [GHS-POP R2023A]: https://human-settlement.emergency.copernicus.eu/ghs_pop2023.php
22//! [CC BY 4.0]: https://creativecommons.org/licenses/by/4.0/
23
24use std::io::{BufReader, BufWriter, Read, Write};
25use std::path::{Path, PathBuf};
26
27use tiff::decoder::{Decoder, DecodingResult, Limits};
28
29use crate::Error;
30use tiff::tags::Tag;
31
32/// The URL the GHS-POP population raster downloads from (JRC open data).
33pub const GHS_POP_URL: &str = "https://jeodpp.jrc.ec.europa.eu/ftp/jrc-opendata/GHSL/\
34GHS_POP_GLOBE_R2023A/GHS_POP_E2020_GLOBE_R2023A_4326_30ss/V1-0/\
35GHS_POP_E2020_GLOBE_R2023A_4326_30ss_V1_0.zip";
36
37/// 30″ source cells are summed in 8×8 blocks into the 4′ grid.
38const DOWNSAMPLE: usize = 8;
39/// The sidecar magic and version; bump it on a layout change.
40const SIDECAR_MAGIC: &[u8; 4] = b"uTZd";
41const SIDECAR_NAME: &str = "ghs_pop_e2020_4326_ds8.bin";
42
43/// Returns the path of the decoded density sidecar inside `cache_dir`,
44/// which lets callers fingerprint the density data without loading it
45/// (the webdist blob cache).
46#[must_use]
47pub fn sidecar_path(cache_dir: &Path) -> PathBuf {
48    cache_dir.join(SIDECAR_NAME)
49}
50
51/// Population density (people/km²) on a coarse global lon/lat grid.
52/// Row 0 is the northernmost; `dlat` is positive.
53pub struct DensityGrid {
54    /// The grid's column count.
55    pub width: usize,
56    /// The grid's row count.
57    pub height: usize,
58    /// The west edge of cell (0,0).
59    pub lon0: f64,
60    /// The north edge of cell (0,0).
61    pub lat0: f64,
62    /// The cell width in degrees.
63    pub dlon: f64,
64    /// The cell height in degrees (positive; rows run north to south).
65    pub dlat: f64,
66    /// The row-major density samples in people/km².
67    pub cells: Vec<f32>,
68}
69
70impl DensityGrid {
71    /// Loads the grid from the sidecar cache, building it from GHS-POP on
72    /// first use (downloading the zip via [`crate::download::fetch()`] if
73    /// needed).
74    ///
75    /// # Errors
76    /// Returns an error on a corrupt sidecar, or, on the first build, a
77    /// GHS-POP download failure, a zip extraction or TIFF decode failure,
78    /// or an I/O failure writing the sidecar.
79    pub fn load(cache_dir: &Path) -> crate::Result<Self> {
80        let sidecar = sidecar_path(cache_dir);
81        if sidecar.exists() {
82            return Self::read_sidecar(&sidecar);
83        }
84        let zip_path = crate::download::fetch(GHS_POP_URL, cache_dir)?;
85        let tif_path = extract_tif(&zip_path, cache_dir)?;
86        let grid = Self::from_ghs_pop_tif(&tif_path)?;
87        grid.write_sidecar(&sidecar)?;
88        // keep the zip for ETag revalidation; the extracted tif is redundant
89        let _ = std::fs::remove_file(&tif_path);
90        Ok(grid)
91    }
92
93    /// Returns the density at a point; outside the grid the density is 0.
94    #[must_use]
95    pub fn sample(&self, lon: f64, lat: f64) -> f64 {
96        #[expect(
97            clippy::cast_possible_truncation,
98            reason = "floored cell index fits i64"
99        )]
100        let ix = ((lon - self.lon0) / self.dlon).floor() as i64;
101        #[expect(
102            clippy::cast_possible_truncation,
103            reason = "floored cell index fits i64"
104        )]
105        let iy = ((self.lat0 - lat) / self.dlat).floor() as i64;
106        self.cell_val(ix, iy)
107    }
108
109    /// Returns the maximum density over every grid cell the segment
110    /// `a`–`b` crosses (an Amanatides–Woo traversal in cell space). This,
111    /// not per-vertex sampling, is what boundary weighting uses: a long
112    /// straight edge can cross a metro area without placing a vertex in
113    /// it.
114    #[must_use]
115    pub fn max_along(&self, a: (f64, f64), b: (f64, f64)) -> f64 {
116        // continuous cell-space coordinates (x → lon cells, y → rows south)
117        let (x0, y0) = ((a.0 - self.lon0) / self.dlon, (self.lat0 - a.1) / self.dlat);
118        let (x1, y1) = ((b.0 - self.lon0) / self.dlon, (self.lat0 - b.1) / self.dlat);
119        #[expect(
120            clippy::cast_possible_truncation,
121            reason = "floored cell coords fit i64"
122        )]
123        let (mut ix, mut iy) = (x0.floor() as i64, y0.floor() as i64);
124        #[expect(
125            clippy::cast_possible_truncation,
126            reason = "floored cell coords fit i64"
127        )]
128        let (ex, ey) = (x1.floor() as i64, y1.floor() as i64);
129        let mut best = self.cell_val(ix, iy);
130        let (dx, dy) = (x1 - x0, y1 - y0);
131        let (sx, sy) = (if dx > 0.0 { 1 } else { -1 }, if dy > 0.0 { 1 } else { -1 });
132        // param t along the segment at the next x/y cell-boundary crossing
133        let (mut tx, tdx) = if dx == 0.0 {
134            (f64::INFINITY, f64::INFINITY)
135        } else {
136            #[expect(
137                clippy::cast_precision_loss,
138                reason = "|ix| ~ raster width ≤ 43200/8 for in-range lon; exact in f64"
139            )]
140            let first = (ix + i64::from(dx > 0.0)) as f64;
141            (((first - x0) / dx).abs().max(0.0), (1.0 / dx).abs())
142        };
143        let (mut ty, tdy) = if dy == 0.0 {
144            (f64::INFINITY, f64::INFINITY)
145        } else {
146            #[expect(
147                clippy::cast_precision_loss,
148                reason = "|iy| ~ raster height ≤ 21600/8 for in-range lat; exact in f64"
149            )]
150            let first = (iy + i64::from(dy > 0.0)) as f64;
151            (((first - y0) / dy).abs().max(0.0), (1.0 / dy).abs())
152        };
153        // exactly one boundary crossing per step — no float termination games
154        for _ in 0..(ex - ix).abs() + (ey - iy).abs() {
155            if tx < ty {
156                ix += sx;
157                tx += tdx;
158            } else {
159                iy += sy;
160                ty += tdy;
161            }
162            best = best.max(self.cell_val(ix, iy));
163        }
164        best
165    }
166
167    #[expect(clippy::cast_possible_wrap, reason = "raster dims ≤ 43200 ≪ i64::MAX")]
168    fn cell_val(&self, ix: i64, iy: i64) -> f64 {
169        if iy < 0 || iy >= self.height as i64 {
170            return 0.0;
171        }
172        // wrap longitude when the grid spans the full 360° (it does for
173        // GHS-POP; the guard keeps synthetic test grids honest)
174        #[expect(
175            clippy::cast_precision_loss,
176            reason = "raster width ≤ 43200/8 (GHS-POP downsampled); exact in f64"
177        )]
178        let ix = if (self.width as f64 * self.dlon - 360.0).abs() < 1e-6 {
179            ix.rem_euclid(self.width as i64)
180        } else if ix < 0 || ix >= self.width as i64 {
181            return 0.0;
182        } else {
183            ix
184        };
185        let (ix, iy) = (
186            usize::try_from(ix).expect("checked in range"),
187            usize::try_from(iy).expect("checked in range"),
188        );
189        f64::from(self.cells[iy * self.width + ix])
190    }
191
192    /// Decodes the GHS-POP `GeoTIFF`, summing 8×8 pixel blocks and
193    /// converting population counts to people/km².
194    ///
195    /// # Errors
196    /// Returns an error on an I/O or TIFF decode failure, missing
197    /// geotransform tags, or a sample format other than f32/f64.
198    ///
199    /// # Panics
200    /// Panics if the source raster's dimensions or chunk count exceed u32
201    /// (not reachable for GHS-POP).
202    pub fn from_ghs_pop_tif(tif_path: &Path) -> crate::Result<Self> {
203        use utz_common::KM_PER_DEG;
204        let mut decoder = Decoder::new(BufReader::new(std::fs::File::open(tif_path)?))?
205            .with_limits(Limits::unlimited());
206        let (source_width, source_height) = decoder.dimensions()?;
207        let (source_width, source_height) = (source_width as usize, source_height as usize);
208        // geotransform: pixel scale + tiepoint (don't assume ±180/±90 cover)
209        let scale = decoder.get_tag_f64_vec(Tag::ModelPixelScaleTag)?;
210        let tiepoint = decoder.get_tag_f64_vec(Tag::ModelTiepointTag)?;
211        crate::ensure!(
212            scale.len() >= 2 && tiepoint.len() >= 5,
213            Error::MissingGeotransform
214        );
215        let (source_dlon, source_dlat) = (scale[0], scale[1]);
216        let (lon0, lat0) = (
217            tiepoint[3] - tiepoint[0] * source_dlon,
218            tiepoint[4] + tiepoint[1] * source_dlat,
219        );
220
221        let (width, height) = (
222            source_width.div_ceil(DOWNSAMPLE),
223            source_height.div_ceil(DOWNSAMPLE),
224        );
225        let mut sums = vec![0f64; width * height];
226        let (chunk_width, chunk_height) = decoder.chunk_dimensions();
227        let (chunk_width, chunk_height) = (chunk_width as usize, chunk_height as usize);
228        let across = source_width.div_ceil(chunk_width);
229        for chunk in 0..u32::try_from(across * source_height.div_ceil(chunk_height))
230            .expect("chunk count fits u32")
231        {
232            let (x_offset, y_offset) = (
233                (chunk as usize % across) * chunk_width,
234                (chunk as usize / across) * chunk_height,
235            );
236            // GDAL writes all-nodata ocean tiles as sparse (offset 0) — skip
237            let Ok(data) = decoder.read_chunk(chunk) else {
238                continue;
239            };
240            let (data_width, data_height) = decoder.chunk_data_dimensions(chunk);
241            let (data_width, data_height) = (data_width as usize, data_height as usize);
242            let mut add = |px: usize, py: usize, value: f64| {
243                // nodata is -200 → clamp negatives to zero population
244                if value > 0.0 {
245                    sums[(y_offset + py) / DOWNSAMPLE * width + (x_offset + px) / DOWNSAMPLE] +=
246                        value;
247                }
248            };
249            match data {
250                DecodingResult::F32(samples) => {
251                    for py in 0..data_height {
252                        for px in 0..data_width {
253                            add(px, py, f64::from(samples[py * data_width + px]));
254                        }
255                    }
256                }
257                DecodingResult::F64(samples) => {
258                    for py in 0..data_height {
259                        for px in 0..data_width {
260                            add(px, py, samples[py * data_width + px]);
261                        }
262                    }
263                }
264                other => {
265                    return Err(Error::BadSampleFormat {
266                        format: format!("{other:?}"),
267                    });
268                }
269            }
270        }
271
272        // counts → people/km². 111.32 km/deg with a cos(lat) lon correction
273        // is plenty: weighting needs order-of-magnitude density, not
274        // demographics. cos clamped at 85° (population there ≈ 0 anyway).
275        #[expect(clippy::cast_precision_loss, reason = "DOWNSAMPLE = 8, exact in f64")]
276        let (dlon, dlat) = (
277            source_dlon * DOWNSAMPLE as f64,
278            source_dlat * DOWNSAMPLE as f64,
279        );
280        #[expect(
281            clippy::cast_possible_truncation,
282            reason = "density → f32 grid cell, rounding is fine"
283        )]
284        let cells = (0..width * height)
285            .map(|i| {
286                #[expect(
287                    clippy::cast_precision_loss,
288                    reason = "row index i/width < height ≤ 21600/8; exact in f64"
289                )]
290                let center_lat = lat0 - (((i / width) as f64) + 0.5) * dlat;
291                let coslat = center_lat
292                    .to_radians()
293                    .cos()
294                    .max((85f64).to_radians().cos());
295                let area = (dlat * KM_PER_DEG) * (dlon * KM_PER_DEG * coslat);
296                (sums[i] / area) as f32
297            })
298            .collect();
299        Ok(Self {
300            width,
301            height,
302            lon0,
303            lat0,
304            dlon,
305            dlat,
306            cells,
307        })
308    }
309
310    fn write_sidecar(&self, path: &Path) -> crate::Result<()> {
311        let partial_path = path.with_extension("part");
312        let mut writer = BufWriter::new(std::fs::File::create(&partial_path)?);
313        writer.write_all(SIDECAR_MAGIC)?;
314        writer.write_all(
315            &u32::try_from(self.width)
316                .expect("grid width fits u32")
317                .to_le_bytes(),
318        )?;
319        writer.write_all(
320            &u32::try_from(self.height)
321                .expect("grid height fits u32")
322                .to_le_bytes(),
323        )?;
324        for value in [self.lon0, self.lat0, self.dlon, self.dlat] {
325            writer.write_all(&value.to_le_bytes())?;
326        }
327        for cell in &self.cells {
328            writer.write_all(&cell.to_le_bytes())?;
329        }
330        writer
331            .into_inner()
332            .map_err(std::io::IntoInnerError::into_error)?;
333        std::fs::rename(&partial_path, path)?;
334        Ok(())
335    }
336
337    fn read_sidecar(path: &Path) -> crate::Result<Self> {
338        let mut reader = BufReader::new(std::fs::File::open(path)?);
339        let mut magic = [0u8; 4];
340        reader.read_exact(&mut magic)?;
341        crate::ensure!(&magic == SIDECAR_MAGIC, Error::BadSidecar("bad magic"));
342        let mut word = [0u8; 4];
343        reader.read_exact(&mut word)?;
344        let width = u32::from_le_bytes(word) as usize;
345        reader.read_exact(&mut word)?;
346        let height = u32::from_le_bytes(word) as usize;
347        let mut scalar = [0u8; 8];
348        let mut geotransform = [0f64; 4];
349        for field in &mut geotransform {
350            reader.read_exact(&mut scalar)?;
351            *field = f64::from_le_bytes(scalar);
352        }
353        let mut bytes = Vec::new();
354        reader.read_to_end(&mut bytes)?;
355        crate::ensure!(
356            bytes.len() == width * height * 4,
357            Error::BadSidecar("size mismatch")
358        );
359        let cells = bytes
360            .chunks_exact(4)
361            .map(|cell_bytes| f32::from_le_bytes(cell_bytes.try_into().unwrap()))
362            .collect();
363        Ok(Self {
364            width,
365            height,
366            lon0: geotransform[0],
367            lat0: geotransform[1],
368            dlon: geotransform[2],
369            dlat: geotransform[3],
370            cells,
371        })
372    }
373}
374
375/// Extracts the single `.tif` entry from the GHS-POP zip next to it
376/// (the tiff decoder needs `Seek`, which zip entries don't offer).
377fn extract_tif(zip_path: &Path, cache_dir: &Path) -> crate::Result<PathBuf> {
378    let mut archive = zip::ZipArchive::new(std::fs::File::open(zip_path)?)?;
379    let name = archive
380        .file_names()
381        .find(|entry_name| {
382            Path::new(entry_name)
383                .extension()
384                .is_some_and(|extension| extension.eq_ignore_ascii_case("tif"))
385        })
386        .ok_or_else(|| Error::NoTif {
387            zip: zip_path.into(),
388        })?
389        .to_string();
390    let out = cache_dir.join(name.rsplit('/').next().unwrap());
391    let mut entry = archive.by_name(&name)?;
392    let partial_path = out.with_extension("part");
393    std::io::copy(
394        &mut entry,
395        &mut BufWriter::new(std::fs::File::create(&partial_path)?),
396    )?;
397    std::fs::rename(&partial_path, &out)?;
398    Ok(out)
399}
400
401#[cfg(test)]
402mod tests {
403    use super::*;
404
405    /// 10×10 one-degree cells covering lon/lat [0,10]×[0,10], all zero except
406    /// a hot cell at (5,5)..(6,6).
407    fn grid() -> DensityGrid {
408        let mut cells = vec![0f32; 100];
409        cells[4 * 10 + 5] = 1000.0; // row 4 = lat 5..6 (row 0 is lat 9..10)
410        DensityGrid {
411            width: 10,
412            height: 10,
413            lon0: 0.0,
414            lat0: 10.0,
415            dlon: 1.0,
416            dlat: 1.0,
417            cells,
418        }
419    }
420
421    #[test]
422    #[expect(
423        clippy::float_cmp,
424        reason = "cell values stored exactly (0.0/1000.0); approximate equality would weaken the test"
425    )]
426    fn sample_hits_the_right_cell() {
427        let grid = grid();
428        assert_eq!(grid.sample(5.5, 5.5), 1000.0);
429        assert_eq!(grid.sample(4.5, 5.5), 0.0);
430        assert_eq!(grid.sample(5.5, 4.5), 0.0);
431        assert_eq!(grid.sample(-20.0, 5.5), 0.0); // outside (grid isn't 360°-wide)
432        assert_eq!(grid.sample(5.5, 20.0), 0.0);
433    }
434
435    #[test]
436    #[expect(
437        clippy::float_cmp,
438        reason = "cell values stored exactly (0.0/1000.0); approximate equality would weaken the test"
439    )]
440    fn max_along_sees_cells_between_vertices() {
441        let grid = grid();
442        // horizontal crossing: both endpoints in cold cells, hot in between
443        assert_eq!(grid.max_along((1.5, 5.5), (8.5, 5.5)), 1000.0);
444        // diagonal crossing
445        assert_eq!(grid.max_along((4.2, 4.2), (6.8, 6.8)), 1000.0);
446        // parallel misses
447        assert_eq!(grid.max_along((1.5, 3.5), (8.5, 3.5)), 0.0);
448        // degenerate (point) segment
449        assert_eq!(grid.max_along((5.5, 5.5), (5.5, 5.5)), 1000.0);
450        // vertical through the hot column
451        assert_eq!(grid.max_along((5.5, 1.5), (5.5, 8.5)), 1000.0);
452    }
453
454    #[test]
455    fn sidecar_roundtrip() {
456        let grid = grid();
457        let dir = std::env::temp_dir().join("utz_density_test");
458        std::fs::create_dir_all(&dir).unwrap();
459        let path = dir.join(SIDECAR_NAME);
460        grid.write_sidecar(&path).unwrap();
461        let restored = DensityGrid::read_sidecar(&path).unwrap();
462        assert_eq!(
463            (
464                restored.width,
465                restored.height,
466                restored.lon0,
467                restored.lat0,
468                restored.dlon,
469                restored.dlat
470            ),
471            (10, 10, 0.0, 10.0, 1.0, 1.0)
472        );
473        assert_eq!(restored.cells, grid.cells);
474        std::fs::remove_file(&path).unwrap();
475    }
476}