ifc_lite_geometry/
terrain_cdt.rs

1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
4
5//! Small public boundary around the in-tree exact-predicate CDT.
6//!
7//! Format adapters provide an already validated planar straight-line graph;
8//! this module deliberately does not assign domain semantics or invent a
9//! fallback. Keeping that policy outside the geometry crate avoids coupling
10//! the IFC kernel to LandXML (or another source format).
11
12use crate::geom2d::{on_segment, orientation, segments_intersect};
13use crate::Point2;
14use rustc_hash::FxHashSet;
15
16/// Failure to build a constrained terrain mesh.
17#[derive(Clone, Copy, Debug, Eq, PartialEq)]
18pub enum TerrainCdtError {
19    /// Points or segments cannot describe a finite non-degenerate PSLG.
20    InvalidInput,
21    /// Distinct constraint segments intersect or overlap in the plane.
22    IntersectingConstraints,
23    /// The exact CDT could not recover every requested constraint.
24    ConstraintsUnrecoverable,
25    WorkLimitExceeded,
26    Cancelled,
27}
28
29/// A deterministic, f64 constrained triangulation. Indices address `points`.
30#[derive(Clone, Debug, PartialEq)]
31pub struct TerrainCdtMesh {
32    pub points: Vec<[f64; 2]>,
33    pub indices: Vec<usize>,
34}
35
36/// Triangulate a non-crossing PSLG through the repository's exact-predicate
37/// CDT. The output covers the convex hull; callers own closed-region/hole
38/// selection because an open breakline has no fill-side meaning.
39///
40/// No unconstrained or ear-clipping fallback is used. Exact duplicate points
41/// and bad segment indices are rejected before entering the CDT. All-collinear
42/// input is detected by the CDT and reported as `ConstraintsUnrecoverable`.
43pub fn triangulate_terrain_pslg(
44    points: &[[f64; 2]],
45    segments: &[(usize, usize)],
46) -> Result<TerrainCdtMesh, TerrainCdtError> {
47    triangulate_terrain_pslg_with_progress(points, segments, &mut || Ok(()))
48}
49
50/// Triangulate while checking a caller-supplied cancellation/work callback in
51/// source validation, exact CDT construction/recovery, and output emission.
52pub fn triangulate_terrain_pslg_with_progress(
53    points: &[[f64; 2]],
54    segments: &[(usize, usize)],
55    progress: &mut dyn FnMut() -> Result<(), TerrainCdtError>,
56) -> Result<TerrainCdtMesh, TerrainCdtError> {
57    if points.len() < 3
58        || points
59            .iter()
60            .any(|point| !point[0].is_finite() || !point[1].is_finite())
61        || segments
62            .iter()
63            .any(|&(a, b)| a == b || a >= points.len() || b >= points.len())
64    {
65        return Err(TerrainCdtError::InvalidInput);
66    }
67    let mut seen = FxHashSet::default();
68    for point in points {
69        progress()?;
70        let key = (if point[0] == 0.0 { 0 } else { point[0].to_bits() }, if point[1] == 0.0 { 0 } else { point[1].to_bits() });
71        if !seen.insert(key) {
72            return Err(TerrainCdtError::InvalidInput);
73        }
74    }
75    // Validate the producer's graph before the collinear-vertex split.  Doing
76    // this afterwards silently normalises repeated/overlapping source edges
77    // into a harmless-looking deduplicated edge set.
78    validate_original_segments(points, segments, progress)?;
79    let segments = split_segments_at_vertices(points, segments, progress)?;
80    let mut source = Vec::with_capacity(points.len());
81    for point in points {
82        progress()?;
83        source.push(Point2::new(point[0], point[1]));
84    }
85    let Some((output, indices)) = crate::cdt::triangulate_pslg_with_progress(&source, &segments, progress)? else {
86        return Err(TerrainCdtError::ConstraintsUnrecoverable);
87    };
88    let mut output_points = Vec::with_capacity(output.len());
89    for point in output {
90        progress()?;
91        output_points.push([point.x, point.y]);
92    }
93    Ok(TerrainCdtMesh { points: output_points, indices })
94}
95
96fn validate_original_segments(
97    points: &[[f64; 2]],
98    segments: &[(usize, usize)],
99    progress: &mut dyn FnMut() -> Result<(), TerrainCdtError>,
100) -> Result<(), TerrainCdtError> {
101    for (left, &(a, b)) in segments.iter().enumerate() {
102        for &(c, d) in &segments[..left] {
103            progress()?;
104            if !segments_intersect(points[a], points[b], points[c], points[d]) {
105                continue;
106            }
107            // A common authored vertex, or a single endpoint landing on a
108            // different segment, is a legitimate PSLG junction: the latter
109            // is split below.  All other contacts (proper crossings,
110            // repeated edges, and collinear overlap) are ambiguous source
111            // constraints.
112            let shared = [a, b]
113                .into_iter()
114                .filter(|vertex| *vertex == c || *vertex == d)
115                .count();
116            if shared == 0 {
117                let endpoint_contacts = [a, b]
118                    .into_iter()
119                    .filter(|vertex| on_segment(points[c], points[d], points[*vertex]))
120                    .count()
121                    + [c, d]
122                        .into_iter()
123                        .filter(|vertex| on_segment(points[a], points[b], points[*vertex]))
124                        .count();
125                if endpoint_contacts == 1 {
126                    continue;
127                }
128                return Err(TerrainCdtError::IntersectingConstraints);
129            }
130            if shared != 1 {
131                return Err(TerrainCdtError::IntersectingConstraints);
132            }
133            let shared_vertex = [a, b]
134                .into_iter()
135                .find(|vertex| *vertex == c || *vertex == d)
136                .expect("one shared vertex checked above");
137            let ab_other = if a == shared_vertex { b } else { a };
138            let cd_other = if c == shared_vertex { d } else { c };
139            if on_segment(points[a], points[b], points[cd_other])
140                || on_segment(points[c], points[d], points[ab_other])
141            {
142                return Err(TerrainCdtError::IntersectingConstraints);
143            }
144        }
145    }
146    Ok(())
147}
148
149fn split_segments_at_vertices(
150    points: &[[f64; 2]],
151    segments: &[(usize, usize)],
152    progress: &mut dyn FnMut() -> Result<(), TerrainCdtError>,
153) -> Result<Vec<(usize, usize)>, TerrainCdtError> {
154    let mut split = Vec::new();
155    for &(a, b) in segments {
156        let mut vertices = vec![a, b];
157        for (index, &point) in points.iter().enumerate() {
158            progress()?;
159            if index != a
160                && index != b
161                && orientation(points[a], points[b], point) == 0
162                && on_segment(points[a], points[b], point)
163            {
164                vertices.push(index);
165            }
166        }
167        vertices.sort_by(|left, right| {
168            let left_dx = points[*left][0] - points[a][0];
169            let left_dy = points[*left][1] - points[a][1];
170            let right_dx = points[*right][0] - points[a][0];
171            let right_dy = points[*right][1] - points[a][1];
172            (left_dx * left_dx + left_dy * left_dy)
173                .total_cmp(&(right_dx * right_dx + right_dy * right_dy))
174        });
175        split.extend(vertices.windows(2).map(|pair| (pair[0], pair[1])));
176    }
177    split.sort_unstable();
178    split.dedup();
179    Ok(split)
180}
181
182#[cfg(test)]
183#[path = "terrain_cdt_tests.rs"]
184mod terrain_cdt_tests;
ifc_lite_geometry/terrain_cdt.rs

ifc_lite_geometry/
terrain_cdt.rs
