topology_checker_core/
model.rs

1use crate::{
2    Error,
3    engine::{
4        cluster::bits,
5        index::{self, Index},
6    },
7};
8use geo::{BoundingRect, CoordsIter, Geometry, LineString, Point, Polygon, Rect};
9use serde::{Deserialize, Serialize};
10use std::{collections::HashSet, sync::OnceLock};
11
12/// A registration index scoped to the topology that returned it.
13/// IDs from another topology must not be reused, even if their indices match.
14#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize)]
15#[serde(transparent)]
16pub struct LayerId(pub(crate) usize);
17impl LayerId {
18    /// Return the zero-based layer registration index.
19    #[must_use]
20    pub fn index(self) -> usize {
21        self.0
22    }
23}
24
25/// Feature provenance within a topology, including an optional original part index.
26#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize)]
27#[non_exhaustive]
28pub struct FeatureRef {
29    /// Topology-scoped layer ID.
30    pub layer: LayerId,
31    /// Signed feature ID, unique within its layer.
32    pub fid: i64,
33    /// Zero-based depth-first part index, including skipped degenerate parts.
34    /// `None` means multiple parts contributed or no single part is identified.
35    pub part: Option<u32>,
36}
37impl FeatureRef {
38    pub(crate) fn feature(self) -> (LayerId, i64) {
39        (self.layer, self.fid)
40    }
41    pub(crate) fn aggregate(&mut self, other: Self) {
42        if self.part != other.part {
43            self.part = None;
44        }
45    }
46}
47
48/// Layer-local part provenance, cached independently of any topology.
49///
50/// It deliberately has no equality or ordering: parts from different layers may
51/// share FIDs, so callers attach a `LayerId` with [`PartRef::at`] before comparing
52/// references that are not known to come from one layer.
53#[derive(Debug, Clone, Copy)]
54pub(crate) struct PartRef {
55    pub fid: i64,
56    pub part: Option<u32>,
57}
58impl PartRef {
59    pub(crate) fn at(self, layer: LayerId) -> FeatureRef {
60        FeatureRef {
61            layer,
62            fid: self.fid,
63            part: self.part,
64        }
65    }
66}
67
68/// A cached layer validation failure, independent of the layer's registration ID.
69#[derive(Debug, Clone, Copy, PartialEq, Eq)]
70pub(crate) enum Invalid {
71    DuplicateFid(i64),
72    NonFinite(i64),
73}
74impl Invalid {
75    pub(crate) fn at(self, layer: LayerId, name: &str) -> Error {
76        let name = name.to_string();
77        match self {
78            Self::DuplicateFid(fid) => Error::DuplicateFid { layer, name, fid },
79            Self::NonFinite(fid) => Error::NonFinite { layer, name, fid },
80        }
81    }
82}
83
84/// Broad input geometry families used to check rule compatibility.
85#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
86#[cfg_attr(feature = "ts", derive(ts_rs::TS))]
87#[serde(rename_all = "lowercase")]
88#[non_exhaustive]
89pub enum GeometryKind {
90    /// Points and multipoints.
91    Point,
92    /// Segments, line strings and multiline strings.
93    Line,
94    /// Polygons, multipolygons, rectangles and triangles.
95    Polygon,
96    /// Geometry collections, whose children are checked recursively for rules.
97    Collection,
98    /// Any geometry family, accepted by the multipart and containment rules.
99    Any,
100}
101impl GeometryKind {
102    /// Classify a geometry without validating its coordinates or collection children.
103    #[must_use]
104    pub fn of(g: &Geometry) -> Self {
105        match g {
106            Geometry::Point(_) | Geometry::MultiPoint(_) => Self::Point,
107            Geometry::Line(_) | Geometry::LineString(_) | Geometry::MultiLineString(_) => {
108                Self::Line
109            }
110            Geometry::Polygon(_)
111            | Geometry::MultiPolygon(_)
112            | Geometry::Rect(_)
113            | Geometry::Triangle(_) => Self::Polygon,
114            Geometry::GeometryCollection(_) => Self::Collection,
115        }
116    }
117    /// Return whether geometry of this family can be a rule input requiring `required`.
118    /// Collections are classified by their children, so they never satisfy a family.
119    #[must_use]
120    pub fn satisfies(self, required: Self) -> bool {
121        required == Self::Any || self == required
122    }
123}
124
125/// An owned planar layer. Cached views cannot be invalidated through mutation.
126///
127/// Caches do not depend on a topology or `LayerId`, so one `Arc<Layer>` can be
128/// registered in several topologies and its cleaned parts, indexes, polygon
129/// union and cross-geometry views are built once and reused.
130///
131/// Construction defers finite-coordinate and duplicate-FID checks until rule
132/// registration, warnings or validation. Cleaning removes consecutive duplicate
133/// coordinates and skips lines with fewer than two coordinates and polygon rings
134/// with fewer than four coordinates or three distinct vertices. A degenerate
135/// exterior skips the polygon; degenerate holes are skipped individually.
136/// Part indices retain the original traversal positions. Coordinate units are
137/// supplied by the caller; the core does not interpret or transform a CRS.
138#[derive(Debug)]
139pub struct Layer {
140    name: String,
141    fids: Vec<i64>,
142    geometries: Vec<Geometry>,
143    parts: OnceLock<Result<Parts, Invalid>>,
144}
145impl Layer {
146    /// Own geometries in input order, assigning signed FIDs starting at zero.
147    /// Validation is deferred until this layer's parts are requested.
148    pub fn from_geometries(
149        name: impl Into<String>,
150        geometries: impl IntoIterator<Item = Geometry>,
151    ) -> Self {
152        Self::from_features(
153            name,
154            geometries
155                .into_iter()
156                .enumerate()
157                .map(|(i, g)| (i as i64, g)),
158        )
159    }
160    /// Own features in input order, preserving signed FIDs and original geometries.
161    /// FIDs must be unique within this layer; validation is deferred.
162    pub fn from_features(
163        name: impl Into<String>,
164        features: impl IntoIterator<Item = (i64, Geometry)>,
165    ) -> Self {
166        let (fids, geometries) = features.into_iter().unzip();
167        Self {
168            name: name.into(),
169            fids,
170            geometries,
171            parts: OnceLock::new(),
172        }
173    }
174    /// Return the caller-supplied layer name, which need not be unique.
175    #[must_use]
176    pub fn name(&self) -> &str {
177        &self.name
178    }
179    /// Iterate original, uncleaned features in input order.
180    pub fn features(&self) -> impl ExactSizeIterator<Item = (i64, &Geometry)> {
181        self.fids.iter().copied().zip(&self.geometries)
182    }
183    /// Return the original feature at a zero-based input position.
184    #[must_use]
185    pub fn feature(&self, index: usize) -> Option<(i64, &Geometry)> {
186        Some((*self.fids.get(index)?, self.geometries.get(index)?))
187    }
188    /// Return the number of original features, including degenerate geometries.
189    #[must_use]
190    pub fn len(&self) -> usize {
191        self.fids.len()
192    }
193    /// Return whether the layer contains no original features.
194    #[must_use]
195    pub fn is_empty(&self) -> bool {
196        self.fids.is_empty()
197    }
198    pub(crate) fn check_kind(&self, id: LayerId, expected: GeometryKind) -> Result<(), Error> {
199        fn check(g: &Geometry, expected: GeometryKind) -> Option<GeometryKind> {
200            if expected == GeometryKind::Any {
201                return None;
202            }
203            if let Geometry::GeometryCollection(c) = g {
204                return c.iter().find_map(|g| check(g, expected));
205            }
206            let found = GeometryKind::of(g);
207            (!found.satisfies(expected)).then_some(found)
208        }
209        for (fid, g) in self.features() {
210            if let Some(found) = check(g, expected) {
211                return Err(Error::GeometryKind {
212                    layer: id,
213                    name: self.name.clone(),
214                    fid,
215                    expected,
216                    found,
217                });
218            }
219        }
220        Ok(())
221    }
222    pub(crate) fn parts(&self) -> Result<&Parts, Invalid> {
223        self.parts
224            .get_or_init(|| self.make_parts())
225            .as_ref()
226            .map_err(|e| *e)
227    }
228    fn make_parts(&self) -> Result<Parts, Invalid> {
229        let mut out = Parts::default();
230        let mut seen = HashSet::new();
231        for (fid, g) in self.features() {
232            if !seen.insert(fid) {
233                return Err(Invalid::DuplicateFid(fid));
234            }
235            if g.coords_iter()
236                .any(|c| !c.x.is_finite() || !c.y.is_finite())
237            {
238                return Err(Invalid::NonFinite(fid));
239            }
240            out.add(g, PartRef { fid, part: Some(0) }, &mut 0);
241        }
242        out.point_index = index::build(
243            out.points
244                .iter()
245                .enumerate()
246                .map(|(i, p)| (i, Rect::new(p.geometry.0, p.geometry.0))),
247        );
248        out.line_index = index::build(
249            out.lines
250                .iter()
251                .enumerate()
252                .filter_map(|(i, p)| p.geometry.bounding_rect().map(|r| (i, r))),
253        );
254        out.polygon_index = index::build(
255            out.polygons
256                .iter()
257                .enumerate()
258                .filter_map(|(i, p)| p.geometry.bounding_rect().map(|r| (i, r))),
259        );
260        Ok(out)
261    }
262}
263#[derive(Debug)]
264pub(crate) struct Part<G> {
265    pub reference: PartRef,
266    pub geometry: G,
267}
268#[derive(Debug, Default)]
269pub(crate) struct Parts {
270    pub points: Vec<Part<Point>>,
271    pub lines: Vec<Part<LineString>>,
272    pub polygons: Vec<Part<Polygon>>,
273    pub point_index: Index,
274    pub line_index: Index,
275    pub polygon_index: Index,
276    pub union: OnceLock<crate::engine::polygons::Union>,
277    pub cross: OnceLock<crate::engine::cross::Views>,
278    pub skipped: usize,
279}
280fn clean_line(line: &LineString) -> LineString {
281    let mut coords = line.0.clone();
282    coords.dedup();
283    LineString(coords)
284}
285fn ring_valid(ring: &LineString) -> bool {
286    ring.0.len() >= 4
287        && ring
288            .0
289            .iter()
290            .map(|c| (bits(c.x), bits(c.y)))
291            .collect::<HashSet<_>>()
292            .len()
293            >= 3
294}
295impl Parts {
296    fn next_reference(mut reference: PartRef, part: &mut u32) -> PartRef {
297        reference.part = Some(*part);
298        *part += 1;
299        reference
300    }
301
302    fn add_point(&mut self, p: &Point, reference: PartRef, part: &mut u32) {
303        self.points.push(Part {
304            reference: Self::next_reference(reference, part),
305            geometry: *p,
306        });
307    }
308
309    fn add_line(&mut self, l: &LineString, reference: PartRef, part: &mut u32) {
310        let reference = Self::next_reference(reference, part);
311        let geometry = clean_line(l);
312        if geometry.0.len() < 2 {
313            self.skipped += 1;
314        } else {
315            self.lines.push(Part {
316                reference,
317                geometry,
318            });
319        }
320    }
321
322    fn add_polygon(&mut self, p: &Polygon, reference: PartRef, part: &mut u32) {
323        let reference = Self::next_reference(reference, part);
324        let exterior = clean_line(p.exterior());
325        if !ring_valid(&exterior) {
326            self.skipped += 1;
327            return;
328        }
329        let holes = p
330            .interiors()
331            .iter()
332            .map(clean_line)
333            .filter(|r| {
334                let valid = ring_valid(r);
335                if !valid {
336                    self.skipped += 1;
337                }
338                valid
339            })
340            .collect();
341        self.polygons.push(Part {
342            reference,
343            geometry: Polygon::new(exterior, holes),
344        });
345    }
346
347    fn add(&mut self, g: &Geometry, reference: PartRef, part: &mut u32) {
348        match g {
349            Geometry::MultiPoint(m) => {
350                for p in m {
351                    self.add_point(p, reference, part);
352                }
353            }
354            Geometry::MultiLineString(m) => {
355                for p in m {
356                    self.add_line(p, reference, part);
357                }
358            }
359            Geometry::MultiPolygon(m) => {
360                for p in m {
361                    self.add_polygon(p, reference, part);
362                }
363            }
364            Geometry::GeometryCollection(m) => {
365                for p in m {
366                    self.add(p, reference, part);
367                }
368            }
369            Geometry::Line(l) => self.add_line(&LineString(vec![l.start, l.end]), reference, part),
370            Geometry::Rect(r) => self.add_polygon(&r.to_polygon(), reference, part),
371            Geometry::Triangle(t) => self.add_polygon(&t.to_polygon(), reference, part),
372            Geometry::Point(p) => self.add_point(p, reference, part),
373            Geometry::LineString(l) => self.add_line(l, reference, part),
374            Geometry::Polygon(p) => self.add_polygon(p, reference, part),
375        }
376    }
377}
378pub(crate) fn part_count(g: &Geometry) -> usize {
379    match g {
380        Geometry::MultiPoint(m) => m.len(),
381        Geometry::MultiLineString(m) => m.0.len(),
382        Geometry::MultiPolygon(m) => m.0.len(),
383        Geometry::GeometryCollection(m) => m.iter().map(part_count).sum(),
384        _ => 1,
385    }
386}
387
388#[cfg(test)]
389mod tests {
390    use super::*;
391    use geo::{GeometryCollection, MultiLineString, MultiPolygon, line_string, polygon};
392
393    #[test]
394    fn multipart_cleaning_keeps_original_positions_and_counts_skipped_rings() {
395        let line = line_string![(x:0.,y:0.),(x:0.,y:0.),(x:1.,y:0.)];
396        let mut polygon = polygon![(x:0.,y:0.),(x:1.,y:0.),(x:1.,y:1.),(x:0.,y:0.)];
397        polygon.interiors_push(LineString::from(vec![(0.5, 0.5); 4]));
398        let geometry = Geometry::GeometryCollection(GeometryCollection(vec![
399            MultiLineString(vec![LineString::empty(), line.clone()]).into(),
400            MultiPolygon(vec![Polygon::empty(), polygon.clone()]).into(),
401            Point::new(4., 5.).into(),
402        ]));
403        let layer = Layer::from_features("parts", [(-12, geometry.clone())]);
404        let parts = layer.parts().unwrap();
405        assert_eq!(parts.skipped, 3);
406        assert_eq!(
407            parts.lines[0].geometry,
408            line_string![(x:0.,y:0.),(x:1.,y:0.)]
409        );
410        assert_eq!(parts.polygons[0].geometry.exterior(), polygon.exterior());
411        assert!(parts.polygons[0].geometry.interiors().is_empty());
412        for (reference, part) in [
413            (parts.lines[0].reference, 1),
414            (parts.polygons[0].reference, 3),
415            (parts.points[0].reference, 4),
416        ] {
417            assert_eq!(
418                reference.at(LayerId(3)),
419                FeatureRef {
420                    layer: LayerId(3),
421                    fid: -12,
422                    part: Some(part)
423                }
424            );
425        }
426        assert_eq!(layer.features().next().unwrap().1, &geometry);
427    }
428
429    #[test]
430    fn multipart_nonfinite_coordinates_are_rejected_before_skipping_degeneracies() {
431        let layer = Layer::from_features(
432            "bad",
433            [(
434                42,
435                MultiLineString(vec![LineString::from(vec![(f64::NAN, 0.)])]).into(),
436            )],
437        );
438        assert_eq!(layer.parts().err(), Some(Invalid::NonFinite(42)));
439    }
440}
topology_checker_core/model.rs

topology_checker_core/
model.rs
