osm-katana/src/shared/geometry.rs
#![allow(clippy::arithmetic_side_effects)]
/// Decode a WKB byte slice into a flat list of (lon, lat) pairs.
/// Handles Point (1), LineString (2), and Polygon exterior ring (3).
/// Returns `None` for unsupported or malformed WKB.
pub fn decode_coords(wkb: &[u8]) -> Option<Vec<(f64, f64)>> {
if wkb.len() < 5 {
return None;
}
let wkb_type = u32::from_le_bytes(wkb.get(1..5)?.try_into().ok()?);
match wkb_type {
1 => {
let x = f64::from_le_bytes(wkb.get(5..13)?.try_into().ok()?);
let y = f64::from_le_bytes(wkb.get(13..21)?.try_into().ok()?);
Some(vec![(x, y)])
}
2 => decode_linestring(wkb),
3 => decode_polygon_exterior(wkb),
_ => None,
}
}
fn decode_linestring(wkb: &[u8]) -> Option<Vec<(f64, f64)>> {
let n = u32::from_le_bytes(wkb.get(5..9)?.try_into().ok()?) as usize;
let mut coords = Vec::with_capacity(n);
for i in 0..n {
let base = 9 + i * 16;
let x = f64::from_le_bytes(wkb.get(base..base + 8)?.try_into().ok()?);
let y = f64::from_le_bytes(wkb.get(base + 8..base + 16)?.try_into().ok()?);
coords.push((x, y));
}
Some(coords)
}
fn decode_polygon_exterior(wkb: &[u8]) -> Option<Vec<(f64, f64)>> {
// 1 byte order + 4 type + 4 ring_count = 9; ring point count at offset 9
let n = u32::from_le_bytes(wkb.get(9..13)?.try_into().ok()?) as usize;
let mut coords = Vec::with_capacity(n);
for i in 0..n {
let base = 13 + i * 16;
let x = f64::from_le_bytes(wkb.get(base..base + 8)?.try_into().ok()?);
let y = f64::from_le_bytes(wkb.get(base + 8..base + 16)?.try_into().ok()?);
coords.push((x, y));
}
Some(coords)
}
// ── The RING-PRESERVING codec ───────────────────────────────────────────────────
//
// # The defect this exists to make impossible
//
// Every decoder in the tree before this one returned a **flat** vertex list. For a
// Point or a LineString that is lossless; for a Polygon it silently concatenates
// ring 1's last vertex to ring 2's first, and every consumer downstream then treats
// the seam as a real edge. MEASURED consequence on 2026-08-03: the tiler decoded a
// multi-ring polygon to one flat list, ran Douglas-Peucker ACROSS the ring boundary,
// and wrote a `LineString`. Facett's hole punching was unreachable from any tile
// osm-katana could produce, and a lake's island became a notch cut to its shore.
//
// A second, quieter one: WKB type 6 (MultiPolygon) fell through every decoder's
// `_ => {}` arm and yielded an EMPTY list. `assemble_relations` has emitted type 6
// since it was written, so the moment relation geometry reached a tiler the feature
// would have vanished with no error — the exact shape of a silent green.
//
// So: ONE ring-preserving decoder and ONE ring encoder, here, used by the relation
// assembler and the tiler alike (LAW 5). A polygon that survives a round trip
// through this pair keeps its ring count.
/// The geometry class a WKB blob carries, kept ring-wise.
#[derive(Debug, Clone, PartialEq)]
pub enum WkbShape {
/// A single position.
Point((f64, f64)),
/// One or more open vertex runs (`LineString`, `MultiLineString`).
Lines(Vec<Vec<(f64, f64)>>),
/// One or more polygons, each `(outer_ring, holes)`. Rings are as stored.
Polys(Vec<(Vec<(f64, f64)>, Vec<Vec<(f64, f64)>>)>),
}
impl WkbShape {
/// Total vertex count across every ring/run — for budgeting, not for geometry.
pub fn vertex_count(&self) -> usize {
match self {
Self::Point(_) => 1,
Self::Lines(rs) => rs.iter().map(Vec::len).sum(),
Self::Polys(ps) => ps
.iter()
.map(|(o, h)| o.len() + h.iter().map(Vec::len).sum::<usize>())
.sum(),
}
}
/// The bounding box over every vertex, or `None` when there are none.
pub fn bbox(&self) -> Option<(f64, f64, f64, f64)> {
let mut it = self.vertices();
let (x, y) = it.next()?;
let (mut a, mut b, mut c, mut d) = (x, y, x, y);
for (x, y) in it {
if x < a {
a = x;
}
if y < b {
b = y;
}
if x > c {
c = x;
}
if y > d {
d = y;
}
}
Some((a, b, c, d))
}
/// Every vertex in storage order. The FLAT view — only for bbox/budget work,
/// never for re-encoding, because it is exactly the lossy step this type exists
/// to remove from the geometry path.
pub fn vertices(&self) -> Box<dyn Iterator<Item = (f64, f64)> + '_> {
match self {
Self::Point(p) => Box::new(std::iter::once(*p)),
Self::Lines(rs) => Box::new(rs.iter().flat_map(|r| r.iter().copied())),
Self::Polys(ps) => Box::new(
ps.iter()
.flat_map(|(o, h)| o.iter().chain(h.iter().flatten()).copied()),
),
}
}
}
/// **The ring-preserving WKB decoder.** Handles Point (1), LineString (2),
/// Polygon (3), MultiPoint (4), MultiLineString (5), MultiPolygon (6) and
/// GeometryCollection (7, flattened into the classes above), either byte order,
/// and tolerates the `Z`/`M`/`ZM` type offsets (`% 1000`) by reading XY only when
/// the blob is 2-D — a 3-D blob is refused rather than misread.
///
/// Returns `None` for a blob that is truncated or whose type is unknown, so a
/// caller can tell "no geometry" from "geometry I could not read".
pub fn decode_wkb(b: &[u8]) -> Option<WkbShape> {
let mut c = Cursor { b, o: 0 };
let s = read_geom(&mut c, 0)?;
Some(s)
}
struct Cursor<'a> {
b: &'a [u8],
o: usize,
}
impl Cursor<'_> {
fn u8(&mut self) -> Option<u8> {
let v = *self.b.get(self.o)?;
self.o += 1;
Some(v)
}
fn u32(&mut self, le: bool) -> Option<u32> {
let a: [u8; 4] = self.b.get(self.o..self.o + 4)?.try_into().ok()?;
self.o += 4;
Some(if le {
u32::from_le_bytes(a)
} else {
u32::from_be_bytes(a)
})
}
fn f64(&mut self, le: bool) -> Option<f64> {
let a: [u8; 8] = self.b.get(self.o..self.o + 8)?.try_into().ok()?;
self.o += 8;
Some(if le {
f64::from_le_bytes(a)
} else {
f64::from_be_bytes(a)
})
}
fn ring(&mut self, le: bool) -> Option<Vec<(f64, f64)>> {
let n = self.u32(le)? as usize;
// A point is 16 bytes; refuse a count the buffer cannot hold rather than
// reserving on a corrupt length (an unbounded `with_capacity` on attacker
// -shaped bytes is how a decoder becomes an OOM).
if n.checked_mul(16)? > self.b.len().saturating_sub(self.o) {
return None;
}
let mut v = Vec::with_capacity(n);
for _ in 0..n {
let x = self.f64(le)?;
let y = self.f64(le)?;
v.push((x, y));
}
Some(v)
}
}
/// One geometry at the cursor. `depth` bounds `GeometryCollection` nesting.
fn read_geom(c: &mut Cursor, depth: u32) -> Option<WkbShape> {
if depth > 8 {
return None;
}
let le = c.u8()? == 1;
let raw = c.u32(le)?;
// Refuse 3-D/measured geometry outright: reading its XY and dropping Z would
// put a silently different geometry on the map. osm-katana never writes one.
if raw % 1000 != raw {
return None;
}
match raw {
1 => {
let x = c.f64(le)?;
let y = c.f64(le)?;
Some(WkbShape::Point((x, y)))
}
2 => Some(WkbShape::Lines(vec![c.ring(le)?])),
3 => {
let nrings = c.u32(le)? as usize;
let mut rings = Vec::with_capacity(nrings.min(1024));
for _ in 0..nrings {
rings.push(c.ring(le)?);
}
let mut it = rings.into_iter();
let outer = it.next()?;
Some(WkbShape::Polys(vec![(outer, it.collect())]))
}
4 | 5 | 6 | 7 => {
let n = c.u32(le)? as usize;
let mut pts: Vec<(f64, f64)> = Vec::new();
let mut lines: Vec<Vec<(f64, f64)>> = Vec::new();
let mut polys: Vec<(Vec<(f64, f64)>, Vec<Vec<(f64, f64)>>)> = Vec::new();
for _ in 0..n {
match read_geom(c, depth + 1)? {
WkbShape::Point(p) => pts.push(p),
WkbShape::Lines(mut r) => lines.append(&mut r),
WkbShape::Polys(mut p) => polys.append(&mut p),
}
}
// A collection is reported as its RICHEST class, so a mixed
// GeometryCollection never downgrades a polygon into a line.
if !polys.is_empty() {
Some(WkbShape::Polys(polys))
} else if !lines.is_empty() {
Some(WkbShape::Lines(lines))
} else if pts.len() == 1 {
Some(WkbShape::Point(pts[0]))
} else if pts.is_empty() {
None
} else {
Some(WkbShape::Lines(vec![pts]))
}
}
_ => None,
}
}
// ── The ONE ring encoder ────────────────────────────────────────────────────────
/// Encode polygons (each `(outer_ring, holes)`) as a WKB MultiPolygon (type 6),
/// little-endian, coordinates in (lon, lat). Every ring is emitted closed.
///
/// The single encoder for ring geometry in the tree: the relation assembler
/// (`relations::build_multipolygon`) and the tiler both call it, so an assembled
/// multipolygon and a tiled one can never disagree about their bytes.
pub fn encode_wkb_multipolygon(polys: &[(Vec<(f64, f64)>, Vec<Vec<(f64, f64)>>)]) -> Vec<u8> {
let mut buf = Vec::new();
encode_wkb_multipolygon_into(polys, &mut buf);
buf
}
/// [`encode_wkb_multipolygon`] into a caller-owned buffer — the ONE implementation
/// (LAW 5); the allocating form above is a three-line wrapper over it.
///
/// `buf` is cleared first, matching [`encode_wkb_line_into`]. The generalisation pass
/// encodes one blob per row PER RUNG, so a fresh `Vec` per call is three allocations
/// per feature whose whole life is one `BinaryBuilder::append_value` copy.
pub fn encode_wkb_multipolygon_into(
polys: &[(Vec<(f64, f64)>, Vec<Vec<(f64, f64)>>)],
buf: &mut Vec<u8>,
) {
buf.clear();
buf.reserve(9 + polys.len() * 32);
buf.push(1u8); // little-endian
buf.extend_from_slice(&6u32.to_le_bytes()); // WKB MultiPolygon
buf.extend_from_slice(&(polys.len() as u32).to_le_bytes());
for (outer, holes) in polys {
buf.push(1u8);
buf.extend_from_slice(&3u32.to_le_bytes()); // WKB Polygon
let ring_count = 1 + holes.len();
buf.extend_from_slice(&(ring_count as u32).to_le_bytes());
push_ring(buf, outer);
for hole in holes {
push_ring(buf, hole);
}
}
}
/// **WKB `MultiLineString` (type 5)**, little-endian, into a caller-owned buffer.
///
/// The line-shaped sibling of [`encode_wkb_multipolygon_into`], and it exists for the
/// same reason: [`crate::shared::generalise`] simplifies a multi-run line RUN BY RUN
/// (never over the concatenated vertex list — that puts a chord across the gap between
/// two disjoint runs, which is the ring defect in its line form), so it needs an encoder
/// that can put the runs back as runs. Encoding them as one `LineString` is precisely
/// the loss the per-run simplification exists to avoid.
///
/// A single-run list is still emitted as a `MultiLineString`; callers that want the
/// plainer `LineString` for one run pick [`encode_wkb_line_into`] themselves.
pub fn encode_wkb_multilinestring_into(runs: &[Vec<(f64, f64)>], buf: &mut Vec<u8>) {
buf.clear();
buf.reserve(9 + runs.iter().map(|r| 9 + r.len() * 16).sum::<usize>());
buf.push(1u8); // little-endian
buf.extend_from_slice(&5u32.to_le_bytes()); // WKB MultiLineString
#[allow(clippy::cast_possible_truncation)]
buf.extend_from_slice(&(runs.len() as u32).to_le_bytes());
for r in runs {
buf.push(1u8);
buf.extend_from_slice(&2u32.to_le_bytes()); // WKB LineString
#[allow(clippy::cast_possible_truncation)]
buf.extend_from_slice(&(r.len() as u32).to_le_bytes());
for &(x, y) in r {
buf.extend_from_slice(&x.to_le_bytes());
buf.extend_from_slice(&y.to_le_bytes());
}
}
}
/// Append one WKB linear ring (point count + closed point list).
fn push_ring(buf: &mut Vec<u8>, ring: &[(f64, f64)]) {
let closed_extra = if ring.len() > 1 && ring.first() != ring.last() {
1
} else {
0
};
let n = ring.len() + closed_extra;
buf.extend_from_slice(&(n as u32).to_le_bytes());
for &(x, y) in ring {
buf.extend_from_slice(&x.to_le_bytes());
buf.extend_from_slice(&y.to_le_bytes());
}
if closed_extra == 1 {
if let Some(&(x, y)) = ring.first() {
buf.extend_from_slice(&x.to_le_bytes());
buf.extend_from_slice(&y.to_le_bytes());
}
}
}
/// WKB (little-endian) `Point`.
pub fn encode_wkb_point(lon: f64, lat: f64) -> Vec<u8> {
let mut b = Vec::with_capacity(21);
push_wkb_point(&mut b, lon, lat);
b
}
/// [`encode_wkb_point`] APPENDED to a caller-owned buffer — the ONE implementation
/// (LAW 5); the allocating form above is a three-line wrapper over it.
///
/// Note the deliberate difference from [`encode_wkb_line_into`], which CLEARS its
/// buffer: this one appends, because its caller ([`crate::tiles::TileRows`])
/// concatenates every row of a tile into one flat buffer and a clearing encoder
/// would erase the rows already in it. `katana-9`.
#[inline]
pub fn push_wkb_point(buf: &mut Vec<u8>, lon: f64, lat: f64) {
buf.reserve(21);
buf.push(1u8);
buf.extend_from_slice(&1u32.to_le_bytes());
buf.extend_from_slice(&lon.to_le_bytes());
buf.extend_from_slice(&lat.to_le_bytes());
}
/// WKB (little-endian) `LineString`.
pub fn encode_wkb_line(pts: &[(f64, f64)]) -> Vec<u8> {
let mut b = Vec::with_capacity(9 + pts.len() * 16);
encode_wkb_line_into(pts, &mut b);
b
}
/// [`encode_wkb_line`] into a caller-owned buffer — the ONE implementation (LAW 5);
/// the allocating form above is a two-line wrapper over it.
///
/// `buf` is cleared first. The tile scan encodes one line per way PER ZOOM and then
/// hands the bytes to an `Arc<[u8]>`, which copies them anyway — so a fresh `Vec` per
/// call is an allocation whose whole life is one `Arc::from`. Lending a per-worker
/// buffer makes that one allocation instead of two (`tilemem-2`).
pub fn encode_wkb_line_into(pts: &[(f64, f64)], buf: &mut Vec<u8>) {
buf.clear();
buf.reserve(9 + pts.len() * 16);
buf.push(1u8);
buf.extend_from_slice(&2u32.to_le_bytes());
buf.extend_from_slice(&(pts.len() as u32).to_le_bytes());
for (lon, lat) in pts {
buf.extend_from_slice(&lon.to_le_bytes());
buf.extend_from_slice(&lat.to_le_bytes());
}
}
#[cfg(test)]
mod tests {
use super::*;
fn sq(x: f64, y: f64, s: f64) -> Vec<(f64, f64)> {
vec![(x, y), (x + s, y), (x + s, y + s), (x, y + s), (x, y)]
}
/// ★ **RED-when-broken: a polygon's RINGS survive the round trip.**
///
/// The pre-`decode_wkb` decoders (`shared::geometry::decode_coords`,
/// `tiles::decode_wkb_coords`) both answered a two-ring polygon with ONE flat
/// 10-vertex list, and there is no value in that answer that says where ring 1
/// ended. Assert the ring STRUCTURE, not the vertex count: a decoder that
/// re-flattened would still return 10 vertices and pass a count check.
#[test]
fn a_polygon_with_a_hole_keeps_its_two_rings() {
let wkb = encode_wkb_multipolygon(&[(sq(0.0, 0.0, 10.0), vec![sq(2.0, 2.0, 3.0)])]);
let Some(WkbShape::Polys(ps)) = decode_wkb(&wkb) else {
panic!("multipolygon decoded to something that is not Polys");
};
assert_eq!(ps.len(), 1, "one polygon");
assert_eq!(ps[0].1.len(), 1, "the HOLE must survive as its own ring");
assert_eq!(ps[0].0.len(), 5, "outer ring keeps its 5 (closed) vertices");
assert_eq!(
ps[0].1[0].len(),
5,
"inner ring keeps its 5 (closed) vertices"
);
// And the seam the flat decoder invented does not exist: no vertex run
// joins the outer ring's last point to the inner ring's first.
assert_ne!(ps[0].0.last(), ps[0].1[0].first());
}
/// ★ **RED-when-broken: WKB type 6 is not silently empty.**
///
/// `tiles::decode_wkb_coords` matched only 1/2/3 and fell through `_ => {}` to
/// an empty Vec for type 6 — and `assemble_relations` has emitted type 6 since
/// it was written. Feeding relation geometry to that tiler would have dropped
/// every multipolygon with no error at all.
#[test]
fn a_multipolygon_does_not_decode_to_nothing() {
let wkb =
encode_wkb_multipolygon(&[(sq(0.0, 0.0, 1.0), vec![]), (sq(5.0, 5.0, 1.0), vec![])]);
assert_eq!(wkb[1], 6, "encoder really wrote WKB type 6");
let s = decode_wkb(&wkb).expect("type 6 must decode");
assert_eq!(s.vertex_count(), 10, "both squares survive");
let WkbShape::Polys(ps) = &s else {
panic!("not Polys")
};
assert_eq!(ps.len(), 2, "TWO separate polygons, not one merged run");
// The old flat decoder's answer for these bytes, verbatim:
assert_eq!(
super::decode_coords(&wkb),
None,
"the flat decoder still cannot read it"
);
}
/// Big-endian and the legacy shapes still read, so replacing the old decoder
/// cannot regress what already worked.
#[test]
fn point_line_and_big_endian_still_decode() {
assert_eq!(
decode_wkb(&encode_wkb_point(11.0, 57.0)),
Some(WkbShape::Point((11.0, 57.0)))
);
let line = encode_wkb_line(&[(0.0, 0.0), (1.0, 1.0), (2.0, 0.0)]);
let Some(WkbShape::Lines(ls)) = decode_wkb(&line) else {
panic!("line")
};
assert_eq!(ls, vec![vec![(0.0, 0.0), (1.0, 1.0), (2.0, 0.0)]]);
// Same point, big-endian.
let mut be = vec![0u8];
be.extend_from_slice(&1u32.to_be_bytes());
be.extend_from_slice(&11.0f64.to_be_bytes());
be.extend_from_slice(&57.0f64.to_be_bytes());
assert_eq!(decode_wkb(&be), Some(WkbShape::Point((11.0, 57.0))));
}
/// A truncated or 3-D blob is REFUSED, not half-read. `None` and
/// `Some(empty)` must not be the same answer — the whole point of the
/// `Option` is that a caller can tell them apart.
#[test]
fn truncated_and_3d_blobs_are_refused_not_half_read() {
let full = encode_wkb_line(&[(0.0, 0.0), (1.0, 1.0), (2.0, 0.0)]);
assert!(
decode_wkb(&full[..full.len() - 4]).is_none(),
"truncated line must refuse"
);
// A LineString claiming 4 billion points in a 9-byte body.
let mut bomb = vec![1u8];
bomb.extend_from_slice(&2u32.to_le_bytes());
bomb.extend_from_slice(&u32::MAX.to_le_bytes());
assert!(
decode_wkb(&bomb).is_none(),
"a bogus point count must not allocate"
);
// LineStringZ (1002).
let mut z = vec![1u8];
z.extend_from_slice(&1002u32.to_le_bytes());
z.extend_from_slice(&1u32.to_le_bytes());
z.extend_from_slice(&[0u8; 24]);
assert!(
decode_wkb(&z).is_none(),
"3-D geometry must be refused, not XY-truncated"
);
}
}