Skip to main content

cadkit_geom/
contacts.rs

1//! Numerical contact normalization. Different evaluation orders may separate identical
2//! analytic contacts by floating-point roundoff; robust booleans deliberately classify this as
3//! ambiguity. Only contacts within the caller's explicit coordinate budget are joined. Larger
4//! gaps remain. Callers operate on a derived copy and report the applied budget.
5use crate::*;
6
7/// Measured normalization budget and changes, in caller coordinate units unless stated
8/// otherwise.
9#[derive(Debug, Clone, Copy, Default, PartialEq, Serialize, Deserialize)]
10#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
11#[serde(rename_all = "camelCase", deny_unknown_fields)]
12pub struct ContactNormalization {
13    /// Maximum endpoint-to-endpoint or endpoint-to-edge merge distance, in coordinate units.
14    pub budget: f64,
15    /// Number of vertices moved to an earlier vertex within the budget; dimensionless.
16    pub merged_vertices: usize,
17    /// Number of contact or intersection nodes inserted on edges, including exact contacts;
18    /// dimensionless.
19    pub inserted_nodes: usize,
20    /// Largest measured distance of moved or inserted vertices from the original boundary, in
21    /// coordinate units.
22    pub max_displacement: f64,
23}
24
25impl ContactNormalization {
26    /// Whether boundary geometry moved by a positive distance. Inserting an exact contact
27    /// alone does not change geometry; no additional tolerance is applied.
28    pub fn changed(&self) -> bool {
29        self.max_displacement > 0.
30    }
31}
32
33/// Four ulps of the largest coordinate magnitude, with scale at least 1. The result uses
34/// coordinate units and only measures roundoff; it is not an application tolerance.
35pub fn contact_roundoff_budget(points: impl IntoIterator<Item = Point2>) -> f64 {
36    let scale = points
37        .into_iter()
38        .fold(1_f64, |size, p| size.max(p.x.abs()).max(p.y.abs()));
39    (scale.next_up() - scale) * 4.
40}
41
42fn edges(polygon: &Polygon) -> Vec<LineSegment> {
43    std::iter::once(&polygon.exterior)
44        .chain(&polygon.holes)
45        .flat_map(|ring| crate::polygon::ring_segments(ring))
46        .collect()
47}
48
49/// Edge box padded by margin plus coordinate-scale roundoff.
50fn line_box(line: LineSegment, margin: f64) -> crate::polygon::SegmentBox {
51    let scale = [line.start.x, line.start.y, line.end.x, line.end.y]
52        .into_iter()
53        .fold(1_f64, |scale, value| scale.max(value.abs()));
54    let margin = margin + 16. * f64::EPSILON * scale;
55    crate::polygon::SegmentBox {
56        min_x: line.start.x.min(line.end.x) - margin,
57        max_x: line.start.x.max(line.end.x) + margin,
58        min_y: line.start.y.min(line.end.y) - margin,
59        max_y: line.start.y.max(line.end.y) + margin,
60    }
61}
62
63fn inside(bounds: crate::polygon::SegmentBox, p: Point2) -> bool {
64    crate::polygon::full_scan()
65        || p.x >= bounds.min_x && p.x <= bounds.max_x && p.y >= bounds.min_y && p.y <= bounds.max_y
66}
67
68/// Canonical vertices. Query returns the first inserted vertex within budget, matching
69/// exhaustive order. Cell width 2 * budget keeps candidates in the nine neighboring cells
70/// despite division roundoff; unrepresentable cells use the full list.
71struct CanonicalPoints {
72    budget: f64,
73    points: Vec<Point2>,
74    cells: std::collections::HashMap<(i64, i64), Vec<usize>>,
75    unindexed: Vec<usize>,
76}
77
78impl CanonicalPoints {
79    fn new(budget: f64) -> Self {
80        Self {
81            budget,
82            points: Vec::new(),
83            cells: std::collections::HashMap::new(),
84            unindexed: Vec::new(),
85        }
86    }
87
88    fn key(&self, point: Point2) -> Option<(i64, i64)> {
89        const LIMIT: f64 = (1_i64 << 52) as f64;
90        let cell = 2. * self.budget;
91        let x = (point.x / cell).floor();
92        let y = (point.y / cell).floor();
93        (cell > 0. && x.abs() < LIMIT && y.abs() < LIMIT).then_some((x as i64, y as i64))
94    }
95
96    fn first_within(&self, point: Point2) -> GeometryResult<Option<Point2>> {
97        let first_within = |indices: &[usize]| -> GeometryResult<Option<usize>> {
98            for &index in indices {
99                if at(&self.points, index)?.distance(point) <= self.budget {
100                    return Ok(Some(index));
101                }
102            }
103            Ok(None)
104        };
105        let key = self.key(point).filter(|_| !crate::polygon::full_scan());
106        let Some((x, y)) = key else {
107            return Ok(self
108                .points
109                .iter()
110                .copied()
111                .find(|p| p.distance(point) <= self.budget));
112        };
113        let mut best = first_within(&self.unindexed)?;
114        for dx in -1..=1 {
115            for dy in -1..=1 {
116                if let Some(bucket) = self.cells.get(&(x + dx, y + dy))
117                    && let Some(index) = first_within(bucket)?
118                {
119                    best = Some(best.map_or(index, |b| b.min(index)));
120                }
121            }
122        }
123        best.map(|index| at(&self.points, index).copied())
124            .transpose()
125    }
126
127    fn push(&mut self, point: Point2) {
128        let index = self.points.len();
129        self.points.push(point);
130        match self.key(point) {
131            Some(key) => self.cells.entry(key).or_default().push(index),
132            None => self.unindexed.push(index),
133        }
134    }
135}
136
137fn resource(field: &str, message: &str) -> GeometryError {
138    GeometryError::unsupported(
139        GeometryReason::ResourceLimit,
140        field,
141        "contacts.normalize",
142        message,
143    )
144}
145
146/// Distance from an inserted node to the supporting line; robust orientation preserves exact
147/// zero contacts.
148fn offset(line: LineSegment, point: Point2) -> f64 {
149    let coordinate = |p: Point2| robust::Coord { x: p.x, y: p.y };
150    robust::orient2d(
151        coordinate(line.start),
152        coordinate(line.end),
153        coordinate(point),
154    )
155    .abs()
156        / line.length()
157}
158
159/// Whether the projection lies within the segment interval, padded by the budget.
160fn within(line: LineSegment, point: Point2, budget: f64) -> bool {
161    let length = line.length();
162    let station = line
163        .start
164        .vector_to(point)
165        .dot(line.start.vector_to(line.end))
166        / length;
167    station >= -budget && station <= length + budget
168}
169
170/// Common-node candidates for two edges. Shallow intersections may produce constructions
171/// separated along the edges beyond the budget. Certify a candidate with robust orientation
172/// distances: it must lie within half the budget of both edges and inside both segment
173/// intervals. Uncertified intersections remain errors.
174fn crossing_nodes(
175    a: LineSegment,
176    b: LineSegment,
177    fine: &GeometryTolerance,
178    budget: f64,
179) -> GeometryResult<Vec<Point2>> {
180    match a.intersection(&b, fine) {
181        Ok(SegmentIntersection::None) => Ok(vec![]),
182        Ok(SegmentIntersection::Point(point)) => Ok(vec![point]),
183        Ok(SegmentIntersection::Overlap(line)) => Ok(vec![line.start, line.end]),
184        Err(error) if error.diagnostic().reason == GeometryReason::NumericalErrorBudgetExceeded => {
185            let r = a.start.vector_to(a.end);
186            let s = b.start.vector_to(b.end);
187            let q = a.start.vector_to(b.start);
188            let denominator = r.cross(s);
189            [
190                a.start.translated(r.scaled(q.cross(s) / denominator)),
191                b.start.translated(s.scaled(q.cross(r) / denominator)),
192            ]
193            .into_iter()
194            .filter(|p| p.x.is_finite() && p.y.is_finite())
195            .map(|p| (offset(a, p).max(offset(b, p)), p))
196            // Reserve half the budget for roundoff in the later f64 projection check.
197            .filter(|(distance, p)| {
198                *distance <= budget * 0.5 && within(a, *p, budget) && within(b, *p, budget)
199            })
200            .min_by(|x, y| x.0.total_cmp(&y.0))
201            .map(|(_, p)| vec![p])
202            .ok_or(error)
203        }
204        Err(error) => Err(error),
205    }
206}
207
208/// Join endpoint and edge contacts within an explicit coordinate-unit budget. Earlier vertices
209/// win, so place geometry to preserve first. Larger gaps remain untouched. Default boolean
210/// limits bound input and generated nodes. Nodes within budget of each other or an endpoint
211/// are deduplicated. Tolerances use the same coordinates.
212pub fn normalize_contacts(
213    polygons: &mut [Polygon],
214    separators: &mut Vec<LineSegment>,
215    budget: f64,
216    tolerance: &GeometryTolerance,
217) -> GeometryResult<ContactNormalization> {
218    normalize_contacts_with_spacing(polygons, separators, budget, budget, tolerance)
219}
220
221/// Normalize contacts with an explicit minimum node spacing in coordinate units. A node closer
222/// than spacing to a neighbor or endpoint is not inserted. Using tolerance.linear prevents
223/// newly inserted edges below that tolerance; unresolved contacts remain for the boolean
224/// kernel to classify.
225pub fn normalize_contacts_with_spacing(
226    polygons: &mut [Polygon],
227    separators: &mut Vec<LineSegment>,
228    budget: f64,
229    spacing: f64,
230    tolerance: &GeometryTolerance,
231) -> GeometryResult<ContactNormalization> {
232    let mut summary = ContactNormalization {
233        budget,
234        ..Default::default()
235    };
236    let count = polygons
237        .iter()
238        .map(|p| p.exterior.len() + p.holes.iter().map(Vec::len).sum::<usize>())
239        .sum::<usize>()
240        + separators.len();
241    let limits = PolygonBooleanOptions::default();
242    if count > limits.max_input_edges {
243        return Err(resource(
244            "maxInputEdges",
245            "Contact noding input budget exceeded",
246        ));
247    }
248    let mut canonical = CanonicalPoints::new(budget);
249    for point in polygons
250        .iter_mut()
251        .flat_map(|p| p.exterior.iter_mut().chain(p.holes.iter_mut().flatten()))
252        .chain(
253            separators
254                .iter_mut()
255                .flat_map(|line| [&mut line.start, &mut line.end]),
256        )
257    {
258        if let Some(existing) = canonical.first_within(*point)? {
259            if *point != existing {
260                summary.merged_vertices += 1;
261                summary.max_displacement = summary.max_displacement.max(existing.distance(*point));
262            }
263            *point = existing;
264        } else {
265            canonical.push(*point);
266        }
267    }
268    let mut points: Vec<_> = polygons
269        .iter()
270        .flat_map(|p| p.exterior.iter().chain(p.holes.iter().flatten()).copied())
271        .chain(separators.iter().flat_map(|line| [line.start, line.end]))
272        .collect();
273    // Three or more edges can compute the same intersection in different orders. Construct it
274    // once and add the same node to every participating edge.
275    let lines: Vec<_> = polygons
276        .iter()
277        .flat_map(edges)
278        .chain(separators.iter().copied())
279        .collect();
280    let fine = GeometryTolerance {
281        linear: budget,
282        angular: 64. * f64::EPSILON,
283        area: f64::MIN_POSITIVE,
284    };
285    // Sweep budget-expanded boxes to select candidate pairs, retain the original box predicate
286    // below, and visit pairs in exhaustive order.
287    let candidates = crate::polygon::overlapping_box_pairs(
288        &lines
289            .iter()
290            .map(|line| line_box(*line, budget))
291            .collect::<Vec<_>>(),
292        limits.max_pair_checks,
293    )
294    .ok_or_else(|| resource("maxInputEdges", "Contact noding input budget exceeded"))?;
295    let mut crossings = Vec::new();
296    for (i, j) in candidates {
297        let (a, b) = (at(&lines, i)?, at(&lines, j)?);
298        {
299            if a.start.x.min(a.end.x) > b.start.x.max(b.end.x) + budget
300                || b.start.x.min(b.end.x) > a.start.x.max(a.end.x) + budget
301                || a.start.y.min(a.end.y) > b.start.y.max(b.end.y) + budget
302                || b.start.y.min(b.end.y) > a.start.y.max(a.end.y) + budget
303            {
304                continue;
305            }
306            // An endpoint already within budget of the other edge is already a candidate node.
307            // Recomputing a shallow T-junction can introduce a spurious microscopic edge. Do
308            // not close larger gaps.
309            let endpoint_contact = [(a.start, b), (a.end, b), (b.start, a), (b.end, a)]
310                .into_iter()
311                .any(|(point, line)| {
312                    line.nearest_point(point, &fine)
313                        .is_ok_and(|nearest| nearest.distance(point) <= budget)
314                });
315            if endpoint_contact {
316                continue;
317            }
318            let intersections = crossing_nodes(*a, *b, &fine, budget)?;
319            let conditioning = a
320                .start
321                .vector_to(a.end)
322                .cross(b.start.vector_to(b.end))
323                .abs()
324                / (a.length() * b.length());
325            for point in intersections {
326                crossings.push((conditioning, point, i, j));
327            }
328            if crossings.len() + points.len() > limits.max_generated_edges {
329                return Err(resource(
330                    "maxGeneratedEdges",
331                    "Contact noding intersection budget exceeded",
332                ));
333            }
334        }
335    }
336    // Construct multiway nodes from the best-conditioned, nearly perpendicular pair first.
337    // Longitudinal roundoff amplified by a shallow angle must not determine the node.
338    crossings.sort_by(|a, b| b.0.total_cmp(&a.0));
339    for (_, point, a, b) in crossings {
340        let a = *at(&lines, a)?;
341        let b = *at(&lines, b)?;
342        // A known node lies near either the candidate or both edges within budget. In either
343        // case it lies inside both boxes expanded by four budgets; points outside cannot
344        // affect the result.
345        let (box_a, box_b) = (line_box(a, 4. * budget), line_box(b, 4. * budget));
346        let known = points.iter().any(|p| {
347            inside(box_a, *p)
348                && inside(box_b, *p)
349                && (p.distance(point) <= budget
350                    || [a, b].iter().all(|line| {
351                        line.nearest_point(*p, &fine)
352                            .is_ok_and(|nearest| nearest.distance(*p) <= budget)
353                    }))
354        });
355        if !known {
356            points.push(point);
357        }
358    }
359    let split = |line: LineSegment,
360                 summary: &mut ContactNormalization|
361     -> GeometryResult<Vec<Point2>> {
362        let direction = line.start.vector_to(line.end);
363        let mut nodes = vec![(0., line.start), (1., line.end)];
364        // A point outside the expanded box is farther from the edge than the budget. Preserve
365        // the first validation error because nearest_point also validates its segment.
366        let near = line_box(line, 2. * budget);
367        let mut validated = false;
368        for point in &points {
369            let station = line.start.vector_to(*point).dot(direction) / direction.dot(direction);
370            if station > 0. && station < 1. {
371                if !inside(near, *point) {
372                    if !validated {
373                        line.validate(tolerance)?;
374                        point.validate()?;
375                        validated = true;
376                    }
377                    continue;
378                }
379                validated = true;
380                if line.nearest_point(*point, tolerance)?.distance(*point) <= budget {
381                    nodes.push((station, *point));
382                }
383            }
384        }
385        nodes.sort_by(|a, b| a.0.total_cmp(&b.0));
386        nodes.dedup_by(|a, b| a.1.distance(b.1) <= spacing);
387        for (_, node) in nodes
388            .iter()
389            .filter(|(_, p)| *p != line.start && *p != line.end)
390        {
391            summary.inserted_nodes += 1;
392            summary.max_displacement = summary.max_displacement.max(offset(line, *node));
393        }
394        Ok(nodes.into_iter().map(|(_, p)| p).collect())
395    };
396    for polygon in polygons {
397        for ring in std::iter::once(&mut polygon.exterior).chain(&mut polygon.holes) {
398            let mut next = Vec::new();
399            for segment in crate::polygon::ring_segments(ring) {
400                let mut nodes = split(segment, &mut summary)?;
401                nodes.pop();
402                next.extend(nodes);
403            }
404            *ring = next;
405        }
406    }
407    let mut next = Vec::new();
408    for line in separators.iter() {
409        let nodes = split(*line, &mut summary)?;
410        next.extend(
411            nodes
412                .iter()
413                .zip(nodes.iter().skip(1))
414                .map(|(start, end)| LineSegment {
415                    start: *start,
416                    end: *end,
417                }),
418        );
419    }
420    *separators = next;
421    Ok(summary)
422}
423
424#[cfg(test)]
425mod tests {
426    use super::*;
427
428    fn rect(x0: f64, y0: f64, x1: f64, y1: f64) -> Polygon {
429        Polygon {
430            exterior: vec![
431                Point2::new(x0, y0),
432                Point2::new(x1, y0),
433                Point2::new(x1, y1),
434                Point2::new(x0, y1),
435            ],
436            holes: vec![],
437        }
438    }
439
440    #[test]
441    fn shallow_multiway_contact_does_not_create_a_microscopic_edge() {
442        let origin = Point2::new(2.731, 9.314);
443        let direction = |angle: f64| Vector2 {
444            x: angle.cos(),
445            y: angle.sin(),
446        };
447        let mut polygons: Vec<_> = [0.11, 0.111, 1.1]
448            .into_iter()
449            .map(|angle| {
450                let d = direction(angle);
451                let normal = Vector2 { x: -d.y, y: d.x };
452                Polygon {
453                    exterior: vec![
454                        origin.translated(d.scaled(-4.)),
455                        origin.translated(d.scaled(4.)),
456                        origin.translated(normal.scaled(0.5)),
457                    ],
458                    holes: vec![],
459                }
460            })
461            .collect();
462        let tolerance = GeometryTolerance::default();
463        let before: Vec<_> = polygons
464            .iter()
465            .map(|p| p.area(&tolerance).unwrap())
466            .collect();
467        let budget = (16_f64.next_up() - 16.) * 4.;
468        normalize_contacts(&mut polygons, &mut vec![], budget, &tolerance).unwrap();
469        for (polygon, area) in polygons.iter().zip(before) {
470            polygon.validate(&tolerance).unwrap();
471            assert!((polygon.area(&tolerance).unwrap() - area).abs() < 1e-12);
472        }
473    }
474
475    /// Synthetic elongated polygon with slope 0.104 and a quadrilateral crossing its side at
476    /// about 8e-5 radians, with small lateral offsets.
477    fn shallow_crossing() -> (Polygon, Polygon, LineSegment, LineSegment) {
478        let norm = (1. + 0.104_f64 * 0.104).sqrt();
479        let (c, s) = (1. / norm, 0.104 / norm);
480        let at = |station: f64, lateral: f64| {
481            Point2::new(
482                -1.5 + station * c - lateral * s,
483                9.54 + station * s + lateral * c,
484            )
485        };
486        let strip = Polygon {
487            exterior: vec![at(0., -0.2), at(18.1, -0.2), at(18.1, 0.), at(0., 0.)],
488            holes: vec![],
489        };
490        // One endpoint lies 1.4e-5 coordinate units inside the side, the other 4.5e-5 outside.
491        let (a, b) = (at(5.5, -1.4e-5), at(6.2, 4.5e-5));
492        let d = a.vector_to(b).scaled(1. / a.distance(b));
493        let n = Vector2 { x: -d.y, y: d.x };
494        let quadrilateral = Polygon {
495            exterior: vec![
496                a,
497                b,
498                b.translated(n.scaled(0.7)),
499                a.translated(n.scaled(0.7)),
500            ],
501            holes: vec![],
502        };
503        let face = LineSegment {
504            start: at(18.1, 0.),
505            end: at(0., 0.),
506        };
507        (strip, quadrilateral, LineSegment { start: a, end: b }, face)
508    }
509
510    #[test]
511    fn shallow_crossing_gets_a_certified_node_instead_of_failing_the_whole_set() {
512        let tolerance = GeometryTolerance::default();
513        let (strip, quadrilateral, edge, face) = shallow_crossing();
514        let budget = contact_roundoff_budget(
515            strip
516                .exterior
517                .iter()
518                .chain(&quadrilateral.exterior)
519                .copied()
520                .collect::<Vec<_>>(),
521        );
522        let fine = GeometryTolerance {
523            linear: budget,
524            angular: 64. * f64::EPSILON,
525            area: f64::MIN_POSITIVE,
526        };
527        // The two supporting-line constructions differ by more than the budget; the previous
528        // noding path rejected the entire set.
529        assert_eq!(
530            edge.intersection(&face, &fine)
531                .unwrap_err()
532                .diagnostic()
533                .reason,
534            GeometryReason::NumericalErrorBudgetExceeded
535        );
536        let mut polygons = vec![strip, quadrilateral];
537        let summary = normalize_contacts(&mut polygons, &mut vec![], budget, &tolerance).unwrap();
538        assert!(summary.max_displacement <= budget, "{summary:?}");
539        // Two sides of the quadrilateral cross the elongated polygon. Both rings must share
540        // both certified nodes; the shallow node must also lie within budget of its source
541        // edge.
542        let shared: Vec<_> = polygons[0]
543            .exterior
544            .iter()
545            .filter(|p| polygons[1].exterior.contains(p))
546            .copied()
547            .collect();
548        assert_eq!(shared.len(), 2, "{polygons:?}");
549        assert!(shared.iter().all(|p| offset(face, *p) <= budget));
550        assert!(shared.iter().any(|p| offset(edge, *p) <= budget));
551        for polygon in &polygons {
552            polygon.validate(&tolerance).unwrap();
553        }
554        let frame = rect(-10., 0., 30., 20.);
555        polygon_boolean(
556            &[frame],
557            &polygons,
558            PolygonBooleanOperation::Difference,
559            PolygonBooleanOptions::with_error_budget(tolerance.linear * 0.25, 1e-3),
560            &tolerance,
561        )
562        .unwrap();
563    }
564
565    #[test]
566    fn roundoff_budget_is_four_ulps_of_the_largest_coordinate() {
567        assert_eq!(contact_roundoff_budget([]), 4. * f64::EPSILON);
568        let budget = contact_roundoff_budget([Point2::new(-16.6, 3.), Point2::new(2., 8.47)]);
569        assert_eq!(budget, (16.6_f64.next_up() - 16.6) * 4.);
570        assert!(budget < 1.5e-14);
571    }
572
573    #[test]
574    fn one_ulp_face_and_cap_contacts_become_shared_nodes_but_real_gaps_stay() {
575        // 8.47 - 0.1 and 16.6 + 0.1 differ by one ulp from the directly specified 8.37 and
576        // 16.7 coordinates.
577        let written = rect(16.5, 8.37, 16.7, 10.86);
578        let derived = rect(16.5, 8.47 - 0.1, 16.6 + 0.1, 10.76);
579        assert_ne!(derived.exterior[0].y, 8.37);
580        assert_ne!(derived.exterior[1].x, 16.7);
581        let tolerance = GeometryTolerance::default();
582        let error = polygon_boolean(
583            std::slice::from_ref(&derived),
584            std::slice::from_ref(&written),
585            PolygonBooleanOperation::Difference,
586            PolygonBooleanOptions::default(),
587            &tolerance,
588        )
589        .unwrap_err();
590        assert_eq!(error.diagnostic().reason, GeometryReason::BooleanAmbiguity);
591        let mut polygons = vec![written.clone(), derived];
592        let budget = contact_roundoff_budget(
593            polygons
594                .iter()
595                .flat_map(|p| p.exterior.iter().copied())
596                .collect::<Vec<_>>(),
597        );
598        let summary = normalize_contacts(&mut polygons, &mut vec![], budget, &tolerance).unwrap();
599        assert!(summary.changed());
600        assert_eq!(summary.budget, budget);
601        assert!(summary.max_displacement > 0. && summary.max_displacement <= budget);
602        // The first input retains its specified vertices.
603        assert!(
604            written
605                .exterior
606                .iter()
607                .all(|p| polygons[0].exterior.contains(p))
608        );
609        assert!(polygons[1].exterior.contains(&Point2::new(16.7, 8.37)));
610        for polygon in &polygons {
611            polygon.validate(&tolerance).unwrap();
612        }
613        let result = polygon_boolean(
614            &polygons[1..],
615            &polygons[..1],
616            PolygonBooleanOperation::Difference,
617            PolygonBooleanOptions::default(),
618            &tolerance,
619        )
620        .unwrap();
621        assert_eq!(result.area, 0.);
622
623        // Gaps larger than the budget remain open; exact contacts only add nodes and boolean
624        // ambiguity remains explicit.
625        let gap = rect(16.5, 8.37 + 5e-9, 16.7, 10.76);
626        let mut polygons = vec![written.clone(), gap.clone()];
627        let summary = normalize_contacts_with_spacing(
628            &mut polygons,
629            &mut vec![],
630            budget,
631            tolerance.linear,
632            &tolerance,
633        )
634        .unwrap();
635        assert!(!summary.changed(), "{summary:?}");
636        assert_eq!(summary.merged_vertices, 0);
637        assert_eq!(polygons[1], gap);
638        for polygon in &polygons {
639            polygon.validate(&tolerance).unwrap();
640        }
641        let error = polygon_boolean(
642            &polygons[1..],
643            &polygons[..1],
644            PolygonBooleanOperation::Difference,
645            PolygonBooleanOptions::default(),
646            &tolerance,
647        )
648        .unwrap_err();
649        assert_eq!(error.diagnostic().reason, GeometryReason::BooleanAmbiguity);
650        // With budget-sized spacing, an exact contact 5e-9 from an endpoint creates a below-
651        // tolerance edge. Use linear-tolerance spacing to avoid that insertion.
652        let mut polygons = vec![written, gap];
653        normalize_contacts(&mut polygons, &mut vec![], budget, &tolerance).unwrap();
654        assert_eq!(
655            polygons[0]
656                .validate(&tolerance)
657                .unwrap_err()
658                .diagnostic()
659                .reason,
660            GeometryReason::BelowTolerance
661        );
662    }
663}