1use crate::*;
6
7#[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 pub budget: f64,
15 pub merged_vertices: usize,
17 pub inserted_nodes: usize,
20 pub max_displacement: f64,
23}
24
25impl ContactNormalization {
26 pub fn changed(&self) -> bool {
29 self.max_displacement > 0.
30 }
31}
32
33pub 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
49fn 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
68struct 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
146fn 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
159fn 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
170fn 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 .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
208pub 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
221pub 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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}