map_tile_toolkit/
polygon_slicer.rs

1//! The single-tile **polygon** slicer, [`PolygonSlicerOne`], over the [`clip_ring`] engine; the
2//! all-tiles [`PolygonSlicerAll`](crate::PolygonSlicerAll) produces identical rings per tile from the
3//! same ring-closing core, and [`PolygonMosaic`](crate::PolygonMosaic) reassembles them (see
4//! `docs/polygon-slicer.md`).
5//!
6//! A polygon is an exterior ring plus zero or more interior rings (holes). Each ring is clipped to
7//! the tile's buffered box keeping original vertices, and closed with synthetic clip-boundary corners
8//! that live strictly outside the box (invisible to a renderer that clips to the tile). One input
9//! polygon yields at most one output ring per input ring per tile; a ring that misses the tile is
10//! dropped, and a tile fully inside the polygon is filled.
11//!
12//! The two generic axes match the polyline slicers: a per-vertex [`PolyVertex`] payload `V` (default
13//! [`Coord<i32>`]) and a per-feature attribute `A` (default `()`).
14
15use geo_types::Coord;
16
17use crate::TileError;
18use crate::clip_polygon::{ClipScratch, RingClip, clip_ring};
19use crate::clip_polyline::to_local;
20use crate::grid::Grid;
21use crate::polygon_view::{PolygonView, offset};
22use crate::tile::TileId;
23use crate::vertex::PolyVertex;
24
25/// One polygon feature clipped into the tile: where its rings (exterior first, then holes) end, and
26/// its attribute.
27#[derive(Debug, Clone, PartialEq, Eq)]
28struct FeatureEntry<A> {
29    rings_end: u32,
30    attr: A,
31}
32
33/// Slices integer **polygons** into pieces for **one fixed tile**, keeping original vertices.
34///
35/// The polygon counterpart to [`SlicerOne`](crate::SlicerOne): each polygon added is clipped only to
36/// this slicer's [`tile`](Self::tile). Generic over the [`PolyVertex`] type `V` (default
37/// [`Coord<i32>`]) and the per-feature attribute `A` (default `()`).
38#[derive(Debug, Clone, PartialEq, Eq)]
39pub struct PolygonSlicerOne<V: PolyVertex = Coord<i32>, A = ()> {
40    grid: Grid,
41    tile: TileId,
42    /// Every kept ring's tile-local vertices (each ring closed), and where each ring ends.
43    verts: Vec<V>,
44    ring_ends: Vec<u32>,
45    features: Vec<FeatureEntry<A>>,
46    /// The clip's working memory, kept for its capacity (never part of the slicer's value).
47    scratch: ClipScratch<V>,
48}
49
50impl<V: PolyVertex, A> PolygonSlicerOne<V, A> {
51    /// Create a slicer bound to `tile`, with the given tile side / per-tile output resolution
52    /// `extent` and `buffer` (same coordinate model as [`SlicerOne`](crate::SlicerOne)).
53    ///
54    /// # Errors
55    ///
56    /// - [`TileError::InvalidExtent`] if `extent` is `0` or greater than `i32::MAX`.
57    /// - [`TileError::BufferTooLarge`] if `buffer` is not strictly less than half the `extent`.
58    pub fn new(extent: u32, buffer: u16, tile: TileId) -> Result<Self, TileError> {
59        Ok(Self {
60            grid: Grid::new(extent, buffer)?,
61            tile,
62            verts: Vec::new(),
63            ring_ends: Vec::new(),
64            features: Vec::new(),
65            scratch: ClipScratch::new(),
66        })
67    }
68
69    /// The tile side / per-tile output resolution.
70    #[must_use]
71    pub fn extent(&self) -> u32 {
72        self.grid.extent()
73    }
74
75    /// The buffer kept around the tile, in tile-space units.
76    #[must_use]
77    pub fn buffer(&self) -> u16 {
78        self.grid.buffer()
79    }
80
81    /// The tile this slicer clips into.
82    #[must_use]
83    pub fn tile(&self) -> TileId {
84        self.tile
85    }
86
87    /// Add one polygon — `exterior` ring plus `holes` — as an independent feature carrying `attr`,
88    /// clipped to this slicer's [`tile`](Self::tile). Chainable. Recorded only if the exterior
89    /// survives in the tile; otherwise `attr` is dropped. Rings may be given open or closed (a
90    /// repeated first/last vertex is fine).
91    ///
92    /// When `A = ()`, prefer [`add_feature`](Self::add_feature).
93    ///
94    /// Atomic: on error the accumulator is unchanged.
95    ///
96    /// # Errors
97    ///
98    /// - [`TileError::Overflow`] if the tile's box, a synthetic corner, or a kept vertex overflows
99    ///   `i32`.
100    /// - [`TileError::GeometryTooLarge`] if the tile's vertices exceed the `u32` indexing of the
101    ///   storage.
102    pub fn add_feature_with(
103        &mut self,
104        exterior: &[V],
105        holes: &[&[V]],
106        attr: A,
107    ) -> Result<&mut Self, TileError> {
108        let (min, max) = self.grid.tile_buffered_bounds(self.tile)?;
109        let origin = self
110            .tile
111            .origin(self.grid.extent())
112            .ok_or(TileError::Overflow)?;
113
114        let (verts_before, rings_before) = (self.verts.len(), self.ring_ends.len());
115        let kept = self
116            .clip_feature(exterior, holes, min, max, origin)
117            .and_then(|kept| kept.then(|| offset(self.ring_ends.len())).transpose());
118        match kept {
119            Ok(Some(rings_end)) => self.features.push(FeatureEntry { rings_end, attr }),
120            other => {
121                // Absent from the tile, or failed: either way nothing of it stays.
122                self.verts.truncate(verts_before);
123                self.ring_ends.truncate(rings_before);
124                other?;
125            }
126        }
127        Ok(self)
128    }
129
130    /// Append the feature's clipped rings; `false` if it leaves nothing in the tile.
131    fn clip_feature(
132        &mut self,
133        exterior: &[V],
134        holes: &[&[V]],
135        min: Coord<i32>,
136        max: Coord<i32>,
137        origin: Coord<i32>,
138    ) -> Result<bool, TileError> {
139        // Clip the exterior first — if it misses the tile entirely, the whole feature is absent here.
140        // Rings go straight into `verts`; the caller truncates them if the feature is dropped.
141        let start = self.verts.len();
142        if clip_ring(exterior, min, max, &mut self.scratch, &mut self.verts)? == RingClip::Outside {
143            return Ok(false);
144        }
145        self.end_ring(start, origin)?;
146        for hole in holes {
147            let start = self.verts.len();
148            match clip_ring(hole, min, max, &mut self.scratch, &mut self.verts)? {
149                // A hole that covers the whole tile leaves nothing to draw here — drop the feature
150                // entirely rather than emit a fill exactly cancelled by its hole.
151                RingClip::Covers => return Ok(false),
152                RingClip::Clipped => self.end_ring(start, origin)?,
153                RingClip::Outside => {}
154            }
155        }
156        Ok(true)
157    }
158
159    /// End the ring appended from `start` (global frame), moving it to the tile-local frame
160    /// (`vertex − origin`).
161    fn end_ring(&mut self, start: usize, origin: Coord<i32>) -> Result<(), TileError> {
162        for v in &mut self.verts[start..] {
163            *v = to_local(*v, origin)?;
164        }
165        self.ring_ends.push(offset(self.verts.len())?);
166        Ok(())
167    }
168
169    /// Iterate the tile's polygon features that reach it, in the order added, each as the
170    /// [`PolygonView`] of its clipped rings and [`attr`](PolygonView::attr).
171    pub fn iter_features(&self) -> impl Iterator<Item = PolygonView<'_, V, A>> {
172        let (verts, ring_ends, features) = (&self.verts, &self.ring_ends, &self.features);
173        (0..features.len()).map(move |f| {
174            let start = f
175                .checked_sub(1)
176                .map_or(0, |p| features[p].rings_end as usize);
177            let rings = start..features[f].rings_end as usize;
178            PolygonView::new(verts, ring_ends, rings, &features[f].attr)
179        })
180    }
181
182    /// Number of polygon features accumulated for the tile.
183    #[must_use]
184    pub fn len(&self) -> usize {
185        self.features.len()
186    }
187
188    /// Whether nothing has been accumulated yet.
189    #[must_use]
190    pub fn is_empty(&self) -> bool {
191        self.features.is_empty()
192    }
193
194    /// Discard everything accumulated, keeping the extent/buffer/tile config and buffer capacity.
195    pub fn clear(&mut self) {
196        self.verts.clear();
197        self.ring_ends.clear();
198        self.features.clear();
199    }
200}
201
202impl<V: PolyVertex> PolygonSlicerOne<V, ()> {
203    /// Add one polygon (`exterior` + `holes`) with no attribute — shorthand for
204    /// [`add_feature_with`](Self::add_feature_with)`(…, ())`. Available only when `A = ()`.
205    ///
206    /// # Errors
207    ///
208    /// As in [`add_feature_with`](Self::add_feature_with).
209    pub fn add_feature(&mut self, exterior: &[V], holes: &[&[V]]) -> Result<&mut Self, TileError> {
210        self.add_feature_with(exterior, holes, ())
211    }
212}
213
214#[cfg(test)]
215mod tests {
216    use geo_types::Coord;
217
218    use super::*;
219
220    fn ring(pts: &[(i32, i32)]) -> Vec<Coord<i32>> {
221        pts.iter().map(|&(x, y)| Coord { x, y }).collect()
222    }
223
224    #[test]
225    fn inside_polygon_is_kept_local() {
226        // Extent 25, tile (0,0): a square fully inside is kept verbatim in local coords.
227        let mut s = PolygonSlicerOne::<Coord<i32>>::new(25, 0, TileId::new(0, 0)).unwrap();
228        let ext = ring(&[(5, 5), (20, 5), (20, 20), (5, 20), (5, 5)]);
229        s.add_feature(&ext, &[]).unwrap();
230        assert_eq!(s.len(), 1);
231        let f = s.iter_features().next().unwrap();
232        let rings: Vec<_> = f.iter_rings().collect();
233        assert_eq!(rings.len(), 1);
234        assert!(!rings[0].is_hole());
235        assert_eq!(rings[0].vertices(), ext.as_slice());
236    }
237
238    #[test]
239    fn polygon_missing_the_tile_is_dropped() {
240        let mut s = PolygonSlicerOne::<Coord<i32>>::new(25, 0, TileId::new(0, 0)).unwrap();
241        // Entirely in tile (4,4)'s area, far from tile (0,0), and not enclosing it.
242        let ext = ring(&[(105, 105), (120, 105), (120, 120), (105, 120), (105, 105)]);
243        s.add_feature(&ext, &[]).unwrap();
244        assert!(
245            s.is_empty(),
246            "a polygon that misses the tile records nothing"
247        );
248    }
249
250    #[test]
251    fn tile_fully_inside_polygon_is_filled() {
252        // A polygon enclosing tile (1,1) (covering 0..75) with no edge near it → solid fill, all
253        // vertices synthetic (outside the tile's buffered box).
254        let mut s = PolygonSlicerOne::<Coord<i32>>::new(25, 0, TileId::new(1, 1)).unwrap();
255        let ext = ring(&[(-10, -10), (80, -10), (80, 80), (-10, 80), (-10, -10)]);
256        s.add_feature(&ext, &[]).unwrap();
257        let f = s.iter_features().next().expect("filled feature");
258        let rings: Vec<_> = f.iter_rings().collect();
259        assert_eq!(rings.len(), 1);
260        // Local frame: the fill box spans just beyond [0,24] on each axis.
261        let xs: Vec<i32> = rings[0].vertices().iter().map(|c| c.x).collect();
262        assert!(
263            xs.iter().all(|&x| !(0..25).contains(&x)),
264            "fill box is outside the core cell"
265        );
266    }
267
268    #[test]
269    fn hole_inside_the_tile_is_kept() {
270        let mut s = PolygonSlicerOne::<Coord<i32>>::new(25, 0, TileId::new(0, 0)).unwrap();
271        let ext = ring(&[(2, 2), (22, 2), (22, 22), (2, 22), (2, 2)]);
272        let hole = ring(&[(8, 8), (16, 8), (16, 16), (8, 16), (8, 8)]);
273        s.add_feature(&ext, &[&hole]).unwrap();
274        let f = s.iter_features().next().unwrap();
275        let rings: Vec<_> = f.iter_rings().collect();
276        assert_eq!(rings.len(), 2);
277        assert!(!rings[0].is_hole());
278        assert!(rings[1].is_hole());
279        assert_eq!(rings[1].vertices(), hole.as_slice());
280    }
281
282    #[test]
283    fn tile_fully_inside_hole_records_nothing() {
284        // Exterior covers tiles 0..2 on each axis; the hole covers tile (1,1) [25,49] entirely. That
285        // tile is all hole, so there is nothing to draw — no feature is recorded (rather than a fill
286        // exactly cancelled by its hole).
287        let ext = ring(&[(2, 2), (72, 2), (72, 72), (2, 72), (2, 2)]);
288        let hole = ring(&[(22, 22), (22, 52), (52, 52), (52, 22), (22, 22)]);
289
290        let mut inside = PolygonSlicerOne::<Coord<i32>>::new(25, 0, TileId::new(1, 1)).unwrap();
291        inside.add_feature(&ext, &[&hole]).unwrap();
292        assert!(
293            inside.is_empty(),
294            "a tile entirely inside a hole records nothing"
295        );
296
297        // A neighbor the hole only partially covers still keeps its (holed) fill.
298        let mut edge = PolygonSlicerOne::<Coord<i32>>::new(25, 0, TileId::new(0, 1)).unwrap();
299        edge.add_feature(&ext, &[&hole]).unwrap();
300        assert_eq!(
301            edge.len(),
302            1,
303            "a partially-holed tile still records a feature"
304        );
305    }
306
307    #[test]
308    fn attribute_rides_through() {
309        let mut s = PolygonSlicerOne::<Coord<i32>, &str>::new(25, 0, TileId::new(0, 0)).unwrap();
310        let ext = ring(&[(5, 5), (20, 5), (20, 20), (5, 20), (5, 5)]);
311        s.add_feature_with(&ext, &[], "lake").unwrap();
312        assert_eq!(*s.iter_features().next().unwrap().attr(), "lake");
313    }
314}
map_tile_toolkit/polygon_slicer.rs

map_tile_toolkit/
polygon_slicer.rs
