1use crate::polygon::{SegmentBox, full_scan, overlapping_box_pairs};
2use crate::*;
3use i_overlay::core::edge_data::{EdgeDataMerge, OverlayEdgeData};
4use i_overlay::core::edge_overlay::{EdgeOverlay, InputEdge};
5use i_overlay::core::fill_rule::FillRule;
6use i_overlay::core::overlay::{IntOverlayOptions, ShapeType};
7use i_overlay::core::overlay_rule::OverlayRule;
8use i_overlay::i_float::int::point::IntPoint;
9use i_overlay::string::slice::IntSlice;
10use std::f64::consts::{PI, SQRT_2};
11
12const INTEGER_LIMIT: i64 = 1_i64 << 50;
13
14#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
15#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
16#[serde(rename_all = "snake_case")]
17#[cfg_attr(feature = "schemars", schemars(transform = crate::unit_enum_schema))]
20pub enum PolygonBooleanOperation {
21 Union,
23 Intersection,
26 Difference,
29}
30#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
31#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
32#[serde(rename_all = "snake_case")]
33#[cfg_attr(feature = "schemars", schemars(transform = crate::unit_enum_schema))]
35pub enum BooleanOperand {
36 Subject,
38 Clip,
40}
41#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
42#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
43#[serde(
44 tag = "type",
45 content = "data",
46 rename_all = "snake_case",
47 deny_unknown_fields
48)]
49pub enum PolygonRing {
51 Exterior,
53 Hole {
55 index: usize,
57 },
58}
59#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
60#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
61#[serde(rename_all = "camelCase", deny_unknown_fields)]
62pub struct MultiPolygon {
65 pub polygons: Vec<Polygon>,
67}
68#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
69#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
70#[serde(rename_all = "camelCase", deny_unknown_fields)]
71pub struct PolygonBooleanOptions {
74 pub max_coordinate_error: f64,
76 pub max_area_error: f64,
79 pub max_input_edges: usize,
81 pub max_output_edges: usize,
83 pub max_pair_checks: usize,
85 pub max_generated_edges: usize,
87}
88impl Default for PolygonBooleanOptions {
89 fn default() -> Self {
90 Self {
91 max_coordinate_error: 2.5e-9,
92 max_area_error: 1e-6,
93 max_input_edges: 8192,
94 max_output_edges: 65536,
95 max_pair_checks: 1_000_000,
96 max_generated_edges: 131072,
97 }
98 }
99}
100impl PolygonBooleanOptions {
101 pub fn with_error_budget(max_coordinate_error: f64, max_area_error: f64) -> Self {
104 Self {
105 max_coordinate_error,
106 max_area_error,
107 ..Self::default()
108 }
109 }
110 fn validate(self, t: &GeometryTolerance) -> GeometryResult<()> {
111 t.validate()?;
112 positive(self.max_coordinate_error, "Boolean coordinate error budget")
113 .map_err(|e| e.at("maxCoordinateError", "polygon.boolean"))?;
114 positive(self.max_area_error, "Boolean area error budget")
115 .map_err(|e| e.at("maxAreaError", "polygon.boolean"))?;
116 if self.max_coordinate_error > t.linear {
117 return Err(invalid(
118 GeometryReason::InvalidParameterRange,
119 "maxCoordinateError",
120 "Boolean coordinate budget must not exceed the linear tolerance",
121 ));
122 }
123 if self.max_input_edges < 3
124 || self.max_input_edges > 16384
125 || self.max_output_edges < 3
126 || self.max_output_edges > 262144
127 || self.max_pair_checks == 0
128 || self.max_pair_checks > 10_000_000
129 || self.max_generated_edges < 3
130 || self.max_generated_edges > 262144
131 {
132 return Err(invalid(
133 GeometryReason::InvalidParameterRange,
134 "limits",
135 "Boolean resource limits are outside the supported range",
136 ));
137 }
138 Ok(())
139 }
140}
141#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
142#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
143#[serde(rename_all = "camelCase", deny_unknown_fields)]
144pub struct BooleanSourceEdge {
147 pub operand: BooleanOperand,
149 pub polygon_index: usize,
151 pub ring: PolygonRing,
153 pub edge_index: usize,
155}
156#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
157#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
158#[serde(rename_all = "camelCase", deny_unknown_fields)]
159pub struct BooleanSourceSpan {
162 pub source: BooleanSourceEdge,
164 pub start_parameter: f64,
166 pub end_parameter: f64,
169 pub max_deviation: f64,
171}
172#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
173#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
174#[serde(rename_all = "camelCase", deny_unknown_fields)]
175pub struct BooleanEdgeProvenance {
178 pub edge_index: usize,
180 pub sources: Vec<BooleanSourceSpan>,
182}
183#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
184#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
185#[serde(rename_all = "camelCase", deny_unknown_fields)]
186pub struct BooleanBoundaryProvenance {
188 pub polygon_index: usize,
190 pub ring: PolygonRing,
192 pub edges: Vec<BooleanEdgeProvenance>,
194}
195#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
196#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
197#[serde(rename_all = "camelCase", deny_unknown_fields)]
198pub struct BooleanDiagnostics {
201 pub profile: String,
203 pub kernel: String,
205 pub local_origin: Point2,
207 pub grid_size: f64,
209 pub integer_coordinate_limit: i64,
211 pub max_input_displacement: f64,
213 pub max_intersection_displacement: f64,
216 pub max_output_boundary_deviation: f64,
218 pub coordinate_error_bound: f64,
220 pub area_error_bound: f64,
222 pub arithmetic_area_error_bound: f64,
224 pub input_edge_count: usize,
226 pub output_edge_count: usize,
228 pub pair_checks: usize,
230 pub regularized_area_only: bool,
233}
234#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
235#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
236#[serde(rename_all = "camelCase", deny_unknown_fields)]
237pub struct PolygonBooleanResult {
240 pub operation: PolygonBooleanOperation,
242 pub geometry: MultiPolygon,
244 pub area: f64,
246 pub diagnostics: BooleanDiagnostics,
248 pub boundaries: Vec<BooleanBoundaryProvenance>,
250}
251
252pub fn polygon_slice(
256 polygons: &[Polygon],
257 separators: &[LineSegment],
258 options: PolygonBooleanOptions,
259 tolerance: &GeometryTolerance,
260) -> GeometryResult<MultiPolygon> {
261 options.validate(tolerance)?;
262 if separators.is_empty() {
263 for polygon in polygons {
264 polygon.validate(tolerance)?;
265 }
266 return Ok(MultiPolygon {
267 polygons: polygons.to_vec(),
268 });
269 }
270 let mut points = Vec::new();
271 let mut lines = Vec::new();
272 let mut input_area = 0.;
273 for polygon in polygons {
274 input_area += polygon.area(tolerance)?;
275 for ring in std::iter::once(&polygon.exterior).chain(&polygon.holes) {
276 points.extend(ring.iter().copied());
277 lines.extend(crate::polygon::ring_segments(ring));
278 }
279 }
280 for separator in separators {
281 separator.validate(tolerance)?;
282 points.extend([separator.start, separator.end]);
283 lines.push(*separator);
284 }
285 if lines.len() > options.max_input_edges {
286 return Err(resource("maxInputEdges"));
287 }
288 let perimeter: f64 = lines.iter().map(LineSegment::length).sum();
289 let adapter = Adapter::new(&points, perimeter, options)?;
290 let sources = lines
291 .iter()
292 .enumerate()
293 .map(|(index, line)| {
294 Ok(SourceEdge {
295 reference: BooleanSourceEdge {
296 operand: BooleanOperand::Subject,
297 polygon_index: 0,
298 ring: PolygonRing::Exterior,
299 edge_index: index,
300 },
301 world_line: *line,
302 line: LineSegment {
303 start: adapter.local(line.start),
304 end: adapter.local(line.end),
305 },
306 quantized: LineSegment {
307 start: adapter.decode_local(adapter.encode(line.start)?),
308 end: adapter.decode_local(adapter.encode(line.end)?),
309 },
310 })
311 })
312 .collect::<GeometryResult<Vec<_>>>()?;
313 let (intersection_error, _) = preflight(&sources, &adapter, options, tolerance)?;
314 let error_bound = intersection_error + adapter.grid * 4. * SQRT_2 + adapter.roundoff;
315 if error_bound > options.max_coordinate_error {
316 return Err(ambiguity(
317 "maxCoordinateError",
318 "Slicing coordinate error budget exceeded",
319 ));
320 }
321 let mut shapes = Vec::new();
322 for polygon in polygons {
323 let mut shape = Vec::new();
324 for (index, ring) in std::iter::once(&polygon.exterior)
325 .chain(&polygon.holes)
326 .enumerate()
327 {
328 let mut encoded = ring
329 .iter()
330 .map(|p| adapter.encode(*p))
331 .collect::<GeometryResult<Vec<_>>>()?;
332 if (signed_ring_area(ring)? > 0.) != (index == 0) {
333 encoded.reverse();
334 }
335 shape.push(encoded);
336 }
337 shapes.push(shape);
338 }
339 let paths = separators
340 .iter()
341 .map(|line| Ok(vec![adapter.encode(line.start)?, adapter.encode(line.end)?]))
342 .collect::<GeometryResult<Vec<_>>>()?;
343 let sliced = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
344 shapes.slice_by_paths(&paths, FillRule::NonZero)
345 }))
346 .map_err(|_| {
347 invalid(
348 GeometryReason::BooleanKernelFailure,
349 "kernel",
350 "Polygon slicing kernel failed to produce a result",
351 )
352 })?;
353 if sliced.iter().flatten().map(Vec::len).sum::<usize>() > options.max_output_edges {
354 return Err(resource("maxOutputEdges"));
355 }
356 let scale = points
360 .iter()
361 .fold(1_f64, |scale, p| scale.max(p.x.abs()).max(p.y.abs()));
362 let margin = options.max_coordinate_error + 16. * f64::EPSILON * scale;
363 let boxes: Vec<SegmentBox> = lines
364 .iter()
365 .map(|line| SegmentBox {
366 min_x: line.start.x.min(line.end.x) - margin,
367 max_x: line.start.x.max(line.end.x) + margin,
368 min_y: line.start.y.min(line.end.y) - margin,
369 max_y: line.start.y.max(line.end.y) + margin,
370 })
371 .collect();
372 let mut by_min_x: Vec<_> = boxes.iter().enumerate().collect();
373 by_min_x.sort_by(|a, b| a.1.min_x.total_cmp(&b.1.min_x));
374 let mut lines_validated = false;
375 let mut result = Vec::new();
376 let mut output_area = 0.;
377 for shape in sliced {
378 let mut rings = shape
379 .iter()
380 .map(|ring| {
381 ring.iter()
382 .map(|p| adapter.decode(*p))
383 .collect::<GeometryResult<Vec<_>>>()
384 })
385 .collect::<GeometryResult<Vec<_>>>()?;
386 if rings.is_empty() {
387 return Err(ambiguity(
388 "output",
389 "Slicing kernel returned an empty shell",
390 ));
391 }
392 let polygon = Polygon {
393 exterior: rings.remove(0),
394 holes: rings,
395 };
396 output_area += polygon.area(tolerance)?;
397 for ring in std::iter::once(&polygon.exterior).chain(&polygon.holes) {
398 for segment in crate::polygon::ring_segments(ring) {
399 for point in [segment.start, segment.start.lerp(segment.end, 0.5)] {
400 if !lines_validated {
401 for line in &lines {
402 line.validate(tolerance)?;
403 point.validate()?;
404 }
405 lines_validated = true;
406 }
407 let end = if full_scan() {
408 by_min_x.len()
409 } else {
410 by_min_x.partition_point(|(_, bounds)| bounds.min_x <= point.x)
411 };
412 let mut distance = f64::INFINITY;
413 for &(index, bounds) in by_min_x.iter().take(end) {
414 if full_scan()
415 || point.x <= bounds.max_x
416 && point.y >= bounds.min_y
417 && point.y <= bounds.max_y
418 {
419 let nearest = at(&lines, index)?.nearest_point(point, tolerance)?;
420 distance = distance.min(nearest.distance(point));
421 }
422 }
423 if distance > options.max_coordinate_error {
424 return Err(ambiguity(
425 "boundary",
426 "Sliced boundary deviates from source edges",
427 ));
428 }
429 }
430 }
431 }
432 result.push(polygon);
433 }
434 if (input_area - output_area).abs() > options.max_area_error {
435 return Err(ambiguity("area", "A zero-width separator changed the area"));
436 }
437 Ok(MultiPolygon { polygons: result })
438}
439
440impl Polygon {
441 pub fn union(
444 &self,
445 other: &Self,
446 options: PolygonBooleanOptions,
447 t: &GeometryTolerance,
448 ) -> GeometryResult<PolygonBooleanResult> {
449 polygon_boolean(
450 std::slice::from_ref(self),
451 std::slice::from_ref(other),
452 PolygonBooleanOperation::Union,
453 options,
454 t,
455 )
456 }
457 pub fn intersection(
460 &self,
461 other: &Self,
462 options: PolygonBooleanOptions,
463 t: &GeometryTolerance,
464 ) -> GeometryResult<PolygonBooleanResult> {
465 polygon_boolean(
466 std::slice::from_ref(self),
467 std::slice::from_ref(other),
468 PolygonBooleanOperation::Intersection,
469 options,
470 t,
471 )
472 }
473 pub fn difference(
476 &self,
477 other: &Self,
478 options: PolygonBooleanOptions,
479 t: &GeometryTolerance,
480 ) -> GeometryResult<PolygonBooleanResult> {
481 polygon_boolean(
482 std::slice::from_ref(self),
483 std::slice::from_ref(other),
484 PolygonBooleanOperation::Difference,
485 options,
486 t,
487 )
488 }
489}
490
491pub fn polygon_boolean(
494 subjects: &[Polygon],
495 clips: &[Polygon],
496 operation: PolygonBooleanOperation,
497 options: PolygonBooleanOptions,
498 t: &GeometryTolerance,
499) -> GeometryResult<PolygonBooleanResult> {
500 options.validate(t)?;
501 let count = subjects
502 .iter()
503 .chain(clips)
504 .try_fold(0_usize, |count, polygon| {
505 polygon
506 .holes
507 .iter()
508 .chain(std::iter::once(&polygon.exterior))
509 .try_fold(count, |sum, ring| {
510 sum.checked_add(ring.len())
511 .ok_or_else(|| resource("maxInputEdges"))
512 })
513 })?;
514 if count > options.max_input_edges {
515 return Err(resource("maxInputEdges"));
516 }
517 for polygon in subjects.iter().chain(clips) {
518 polygon.validate(t)?;
519 }
520 let input_points: Vec<_> = subjects
521 .iter()
522 .chain(clips)
523 .flat_map(|p| std::iter::once(&p.exterior).chain(&p.holes))
524 .flatten()
525 .copied()
526 .collect();
527 let perimeter: f64 = subjects
528 .iter()
529 .chain(clips)
530 .map(|p| p.perimeter(t))
531 .collect::<GeometryResult<Vec<_>>>()?
532 .into_iter()
533 .sum();
534 finite(perimeter)?;
535 let adapter = Adapter::new(&input_points, perimeter, options)?;
536 let mut sources = Vec::with_capacity(count);
537 let mut overlay: EdgeOverlay<i64, SourceSet> = EdgeOverlay::new(count);
538 overlay.options = IntOverlayOptions::keep_all_points();
539 overlay.data_store_mut().max_members = options.max_generated_edges.saturating_mul(16);
540 let mut max_input_displacement = 0_f64;
541 for (operand, polygons) in [
542 (BooleanOperand::Subject, subjects),
543 (BooleanOperand::Clip, clips),
544 ] {
545 for (polygon_index, polygon) in polygons.iter().enumerate() {
546 for (ring_index, ring) in std::iter::once(&polygon.exterior)
547 .chain(&polygon.holes)
548 .enumerate()
549 {
550 let ring_ref = if ring_index == 0 {
551 PolygonRing::Exterior
552 } else {
553 PolygonRing::Hole {
554 index: ring_index - 1,
555 }
556 };
557 let local: Vec<_> = ring.iter().map(|p| adapter.local(*p)).collect();
558 let integers = ring
559 .iter()
560 .map(|p| adapter.encode(*p))
561 .collect::<GeometryResult<Vec<_>>>()?;
562 let decoded = integers
563 .iter()
564 .map(|p| adapter.decode(*p))
565 .collect::<GeometryResult<Vec<_>>>()?;
566 for (a, b) in ring.iter().zip(&decoded) {
567 max_input_displacement = max_input_displacement.max(a.distance(*b));
568 }
569 let forward = (signed_ring_area(&local)? > 0.) == (ring_index == 0);
570 for index in 0..ring.len() {
571 let next = (index + 1) % ring.len();
572 if *at(&integers, index)? == *at(&integers, next)? {
573 return Err(ambiguity("edges", "Quantization collapses a source edge"));
574 }
575 let source_index = sources.len();
576 sources.push(SourceEdge {
577 reference: BooleanSourceEdge {
578 operand,
579 polygon_index,
580 ring: ring_ref,
581 edge_index: index,
582 },
583 world_line: LineSegment {
584 start: *at(ring, index)?,
585 end: *at(ring, next)?,
586 },
587 line: LineSegment {
588 start: *at(&local, index)?,
589 end: *at(&local, next)?,
590 },
591 quantized: LineSegment {
592 start: adapter.decode_local(*at(&integers, index)?),
593 end: adapter.decode_local(*at(&integers, next)?),
594 },
595 });
596 overlay.data_store_mut().sets.push(vec![source_index]);
597 overlay.data_store_mut().members += 1;
598 let (a, b) = if forward {
599 (*at(&integers, index)?, *at(&integers, next)?)
600 } else {
601 (*at(&integers, next)?, *at(&integers, index)?)
602 };
603 overlay.add_edge(
604 InputEdge {
605 a,
606 b,
607 data: SourceSet(source_index),
608 },
609 if operand == BooleanOperand::Subject {
610 ShapeType::Subject
611 } else {
612 ShapeType::Clip
613 },
614 );
615 }
616 }
617 }
618 }
619 if max_input_displacement > options.max_coordinate_error {
620 return Err(ambiguity(
621 "maxCoordinateError",
622 "Input quantization displacement exceeds the budget",
623 ));
624 }
625 let (max_intersection_displacement, pair_checks) = preflight(&sources, &adapter, options, t)?;
626 let coordinate_error_bound = max_input_displacement.max(max_intersection_displacement)
627 + adapter.grid * 4. * SQRT_2
628 + adapter.roundoff;
629 if coordinate_error_bound > options.max_coordinate_error {
630 return Err(invalid(
631 GeometryReason::NumericalErrorBudgetExceeded,
632 "maxCoordinateError",
633 "Boolean coordinate error bound exceeds the budget",
634 ));
635 }
636 let area_error_bound = 2. * perimeter * coordinate_error_bound
637 + PI * coordinate_error_bound.powi(2) * count as f64;
638 if !area_error_bound.is_finite() || area_error_bound > options.max_area_error {
639 return Err(invalid(
640 GeometryReason::NumericalErrorBudgetExceeded,
641 "maxAreaError",
642 "Boolean area error bound exceeds the budget",
643 ));
644 }
645 let rule = match operation {
646 PolygonBooleanOperation::Union => OverlayRule::Union,
647 PolygonBooleanOperation::Intersection => OverlayRule::Intersect,
648 PolygonBooleanOperation::Difference => OverlayRule::Difference,
649 };
650 let shapes = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
651 overlay.build_vector_shapes(rule, FillRule::NonZero)
652 }))
653 .map_err(|_| {
654 invalid(
655 GeometryReason::BooleanKernelFailure,
656 "kernel",
657 "Boolean kernel failed to produce a result",
658 )
659 })?;
660 if overlay.data_store().invalid_reference {
661 return Err(invalid(
662 GeometryReason::BooleanKernelFailure,
663 "provenance",
664 "Boolean kernel referenced an invalid source set",
665 ));
666 }
667 if overlay.data_store().exceeded {
668 return Err(resource("provenance"));
669 }
670 let output_edge_count: usize = shapes.iter().flatten().map(Vec::len).sum();
671 if output_edge_count > options.max_output_edges {
672 return Err(resource("maxOutputEdges"));
673 }
674 let mut polygons = vec![];
675 let mut boundaries = vec![];
676 let mut area = 0.;
677 let mut max_output_boundary_deviation = 0_f64;
678 for (polygon_index, shape) in shapes.iter().enumerate() {
679 let mut rings = vec![];
680 for (ring_index, path) in shape.iter().enumerate() {
681 let ring = if ring_index == 0 {
682 PolygonRing::Exterior
683 } else {
684 PolygonRing::Hole {
685 index: ring_index - 1,
686 }
687 };
688 let mut points = vec![];
689 let mut provenance = vec![];
690 for (edge_index, edge) in path.iter().enumerate() {
691 let start = adapter.decode(edge.a)?;
692 let end = adapter.decode(edge.b)?;
693 points.push(start);
694 let source_ids = overlay.data_store().sets.get(edge.data.0).ok_or_else(|| {
695 invalid(
696 GeometryReason::BooleanKernelFailure,
697 "provenance",
698 "Boolean source edge record is missing",
699 )
700 })?;
701 let mut spans = vec![];
702 for id in source_ids {
703 let source = sources.get(*id).ok_or_else(|| {
704 invalid(
705 GeometryReason::BooleanKernelFailure,
706 "provenance",
707 "Invalid boolean source index",
708 )
709 })?;
710 let (a, da) = source_parameter(
711 source,
712 adapter.local(start),
713 options.max_coordinate_error,
714 )?;
715 let (b, db) =
716 source_parameter(source, adapter.local(end), options.max_coordinate_error)?;
717 let max_deviation = da.max(db);
718 max_output_boundary_deviation =
719 max_output_boundary_deviation.max(max_deviation);
720 spans.push(BooleanSourceSpan {
721 source: source.reference.clone(),
722 start_parameter: a,
723 end_parameter: b,
724 max_deviation,
725 });
726 }
727 if spans.is_empty() {
728 return Err(invalid(
729 GeometryReason::BooleanKernelFailure,
730 "provenance",
731 "Output edge has no source reference",
732 ));
733 }
734 provenance.push(BooleanEdgeProvenance {
735 edge_index,
736 sources: spans,
737 });
738 }
739 rings.push(points);
740 boundaries.push(BooleanBoundaryProvenance {
741 polygon_index,
742 ring,
743 edges: provenance,
744 });
745 }
746 if rings.is_empty() {
747 return Err(invalid(
748 GeometryReason::BooleanKernelFailure,
749 "output",
750 "Boolean kernel returned an empty shell",
751 ));
752 }
753 let polygon = Polygon {
754 exterior: rings.remove(0),
755 holes: rings,
756 };
757 polygon.validate(t).map_err(|_| {
758 ambiguity(
759 "output",
760 "Boolean output cannot form valid rings or preserves detail below the tolerance",
761 )
762 })?;
763 area += polygon.area(t)?;
764 polygons.push(polygon);
765 }
766 finite(area)?;
767 let coordinate_error_bound = coordinate_error_bound.max(max_output_boundary_deviation);
768 let arithmetic_area_error_bound =
769 32. * f64::EPSILON * adapter.span * adapter.span * (count + output_edge_count) as f64;
770 let area_error_bound = 2. * perimeter * coordinate_error_bound
771 + PI * coordinate_error_bound.powi(2) * count as f64
772 + arithmetic_area_error_bound;
773 if !area_error_bound.is_finite() || area_error_bound > options.max_area_error {
774 return Err(invalid(
775 GeometryReason::NumericalErrorBudgetExceeded,
776 "maxAreaError",
777 "Output area exceeds the geometric and arithmetic error budget",
778 ));
779 }
780 Ok(PolygonBooleanResult {
781 operation,
782 geometry: MultiPolygon { polygons },
783 area,
784 boundaries,
785 diagnostics: BooleanDiagnostics {
786 profile: "linear_polygon_i64_v1".into(),
787 kernel: "i_overlay@9.0.0".into(),
788 local_origin: adapter.origin,
789 grid_size: adapter.grid,
790 integer_coordinate_limit: INTEGER_LIMIT,
791 max_input_displacement,
792 max_intersection_displacement,
793 max_output_boundary_deviation,
794 coordinate_error_bound,
795 area_error_bound,
796 arithmetic_area_error_bound,
797 input_edge_count: count,
798 output_edge_count,
799 pair_checks,
800 regularized_area_only: true,
801 },
802 })
803}
804
805struct Adapter {
806 origin: Point2,
807 grid: f64,
808 roundoff: f64,
809 span: f64,
810}
811impl Adapter {
812 fn new(
813 points: &[Point2],
814 perimeter: f64,
815 options: PolygonBooleanOptions,
816 ) -> GeometryResult<Self> {
817 let bounds = if points.is_empty() {
818 Bounds2 {
819 min: Point2::new(0., 0.),
820 max: Point2::new(0., 0.),
821 }
822 } else {
823 Bounds2::from_points(points)?
824 };
825 let dx = bounds.max.x - bounds.min.x;
826 let dy = bounds.max.y - bounds.min.y;
827 finite(dx)?;
828 finite(dy)?;
829 let origin = Point2::new(bounds.min.x + dx / 2., bounds.min.y + dy / 2.);
830 origin.validate()?;
831 let magnitude = [bounds.min.x, bounds.max.x, bounds.min.y, bounds.max.y]
832 .into_iter()
833 .map(f64::abs)
834 .fold(0., f64::max);
835 let roundoff = (magnitude.next_up() - magnitude) * SQRT_2;
836 if !roundoff.is_finite() || roundoff >= options.max_coordinate_error / 4. {
837 return Err(invalid(
838 GeometryReason::NumericalErrorBudgetExceeded,
839 "maxCoordinateError",
840 "World coordinate resolution exceeds the boolean error budget",
841 ));
842 }
843 let target = (options.max_coordinate_error / 16.)
844 .min(options.max_area_error / (64. * perimeter.max(1.)));
845 let grid = 2_f64.powf(target.log2().floor());
846 positive(grid, "Boolean grid")?;
847 let span = dx.max(dy);
848 if !((span / 2.) / grid).is_finite() || span / 2. / grid > INTEGER_LIMIT as f64 {
849 return Err(invalid(
850 GeometryReason::QuantizationRangeExceeded,
851 "gridSize",
852 "Requested error budget exceeds the safe integer coordinate range",
853 ));
854 }
855 Ok(Self {
856 origin,
857 grid,
858 roundoff,
859 span,
860 })
861 }
862 fn local(&self, p: Point2) -> Point2 {
863 Point2::new(p.x - self.origin.x, p.y - self.origin.y)
864 }
865 fn encode(&self, p: Point2) -> GeometryResult<IntPoint<i64>> {
866 let local = self.local(p);
867 let x = (local.x / self.grid).round();
868 let y = (local.y / self.grid).round();
869 if !x.is_finite()
870 || !y.is_finite()
871 || x.abs() > INTEGER_LIMIT as f64
872 || y.abs() > INTEGER_LIMIT as f64
873 {
874 return Err(invalid(
875 GeometryReason::QuantizationRangeExceeded,
876 "coordinates",
877 "Integer conversion exceeds the safe range",
878 ));
879 }
880 Ok(IntPoint::new(x as i64, y as i64))
881 }
882 fn decode_local(&self, p: IntPoint<i64>) -> Point2 {
883 Point2::new(p.x as f64 * self.grid, p.y as f64 * self.grid)
884 }
885 fn decode(&self, p: IntPoint<i64>) -> GeometryResult<Point2> {
886 let local = self.decode_local(p);
887 let result = Point2::new(self.origin.x + local.x, self.origin.y + local.y);
888 result.validate()?;
889 Ok(result)
890 }
891}
892struct SourceEdge {
893 reference: BooleanSourceEdge,
894 line: LineSegment,
895 world_line: LineSegment,
896 quantized: LineSegment,
897}
898#[derive(Clone, Copy, PartialEq)]
899struct SourceSet(usize);
900#[derive(Default)]
901struct SourceStore {
902 sets: Vec<Vec<usize>>,
903 members: usize,
904 max_members: usize,
905 exceeded: bool,
906 invalid_reference: bool,
907}
908impl OverlayEdgeData for SourceSet {
909 type Store = SourceStore;
910 fn merge(
911 context: EdgeDataMerge<i_overlay::segm::boolean::ShapeCountBoolean, Self>,
912 store: &mut SourceStore,
913 ) -> Self {
914 if context.lhs_data == context.rhs_data {
915 return context.lhs_data;
916 }
917 let (Some(left), Some(right)) = (
918 store.sets.get(context.lhs_data.0),
919 store.sets.get(context.rhs_data.0),
920 ) else {
921 store.invalid_reference = true;
924 return context.lhs_data;
925 };
926 let mut merged = left.clone();
927 merged.extend_from_slice(right);
928 merged.sort_unstable();
929 merged.dedup();
930 if store.members.saturating_add(merged.len()) > store.max_members {
931 store.exceeded = true;
932 return context.lhs_data;
933 }
934 store.members += merged.len();
935 let index = store.sets.len();
936 store.sets.push(merged);
937 Self(index)
938 }
939}
940fn preflight(
941 sources: &[SourceEdge],
942 adapter: &Adapter,
943 options: PolygonBooleanOptions,
944 t: &GeometryTolerance,
945) -> GeometryResult<(f64, usize)> {
946 let numeric = 64. * f64::EPSILON * adapter.span.max(1.);
947 if numeric > options.max_coordinate_error / 4. {
948 return Err(invalid(
949 GeometryReason::NumericalErrorBudgetExceeded,
950 "maxCoordinateError",
951 "Local segment comparison exceeds the error budget",
952 ));
953 }
954 let fine = GeometryTolerance {
955 linear: numeric.max(f64::MIN_POSITIVE),
956 angular: 64. * f64::EPSILON,
957 area: f64::MIN_POSITIVE,
958 };
959 let mut max_shift = 0_f64;
960 let mut checks = 0;
961 let mut generated = sources.len();
962 let mut interior_intersections = NearPoints::new(t.linear);
963 let pairs = overlapping_box_pairs(
967 &preflight_boxes(sources, options, t, numeric),
968 options.max_pair_checks,
969 )
970 .ok_or_else(|| resource("maxPairChecks"))?;
971 for (i, j) in pairs {
972 let (a, b) = (at(sources, i)?, at(sources, j)?);
973 {
974 checks += 1;
975 if checks > options.max_pair_checks {
976 return Err(resource("maxPairChecks"));
977 }
978 let exact_relation = relation(a.world_line, b.world_line)?;
979 let original = intersection_with_relation(a.line, b.line, exact_relation, &fine)
980 .map_err(|_| ambiguity("input", "Source edge relation is numerically unstable"))?;
981 let quantized = intersection_with_relation(
982 a.quantized,
983 b.quantized,
984 relation(a.quantized, b.quantized)?,
985 &fine,
986 )
987 .map_err(|_| ambiguity("gridSize", "Edge relation is unstable after quantization"))?;
988 match original {
989 SegmentIntersection::None if exact_relation != 0 => {
990 return Err(ambiguity(
991 "input",
992 "Numerical segment relation disagrees with the robust predicate",
993 ));
994 }
995 SegmentIntersection::Point(_) if exact_relation != 1 => {
996 return Err(ambiguity(
997 "input",
998 "Near segment contact cannot be resolved as an exact intersection",
999 ));
1000 }
1001 SegmentIntersection::Overlap(_) if exact_relation != 2 => {
1002 return Err(ambiguity(
1003 "input",
1004 "Nearby supporting lines cannot be resolved as an exact overlap",
1005 ));
1006 }
1007 _ => {}
1008 }
1009 for (point, line) in [
1010 (a.line.start, b.line),
1011 (a.line.end, b.line),
1012 (b.line.start, a.line),
1013 (b.line.end, a.line),
1014 ] {
1015 let on_support = orientation(line.start, line.end, point)? == 0.;
1016 let distance = if point == line.start || point == line.end {
1017 0.
1018 } else {
1019 line.nearest_point(point, &fine)?.distance(point)
1020 };
1021 if !on_support && distance > 0. && distance <= t.linear {
1022 return Err(ambiguity(
1023 "input",
1024 "Distinct boundaries lie within the linear tolerance; implicit merging is not permitted",
1025 ));
1026 }
1027 }
1028 match (original, quantized) {
1029 (SegmentIntersection::None, SegmentIntersection::None) => {}
1030 (
1031 SegmentIntersection::Point(point),
1032 SegmentIntersection::Point(quantized_point),
1033 ) => {
1034 if [a.line.start, a.line.end, b.line.start, b.line.end]
1035 .iter()
1036 .all(|end| end.distance(point) > numeric)
1037 {
1038 let (near, compared) = interior_intersections.insert(point);
1039 checks += compared;
1040 if checks > options.max_pair_checks {
1041 return Err(resource("maxPairChecks"));
1042 }
1043 if near {
1044 return Err(ambiguity(
1045 "intersections",
1046 "Distinct intersection nodes may merge within the linear tolerance",
1047 ));
1048 }
1049 }
1050 max_shift = max_shift.max(point.distance(quantized_point));
1051 generated = generated.saturating_add(4);
1052 }
1053 (SegmentIntersection::Overlap(a), SegmentIntersection::Overlap(b)) => {
1054 let shift = (a.start.distance(b.start).max(a.end.distance(b.end)))
1055 .min(a.start.distance(b.end).max(a.end.distance(b.start)));
1056 max_shift = max_shift.max(shift);
1057 generated = generated.saturating_add(4);
1058 }
1059 _ => {
1060 return Err(ambiguity(
1061 "gridSize",
1062 "Quantization changes edge contact or intersection topology",
1063 ));
1064 }
1065 }
1066 if max_shift > options.max_coordinate_error / 2. {
1067 return Err(ambiguity(
1068 "gridSize",
1069 "Quantization moves an intersection outside the error budget",
1070 ));
1071 }
1072 if generated > options.max_generated_edges {
1073 return Err(resource("maxGeneratedEdges"));
1074 }
1075 }
1076 }
1077 Ok((max_shift, checks))
1078}
1079
1080fn preflight_boxes(
1084 sources: &[SourceEdge],
1085 options: PolygonBooleanOptions,
1086 t: &GeometryTolerance,
1087 numeric: f64,
1088) -> Vec<SegmentBox> {
1089 let scale = sources
1090 .iter()
1091 .flat_map(|s| [s.world_line.start, s.world_line.end])
1092 .fold(1_f64, |scale, p| scale.max(p.x.abs()).max(p.y.abs()));
1093 let margin =
1094 t.linear + options.max_coordinate_error + 4. * numeric + 16. * f64::EPSILON * scale;
1095 sources
1096 .iter()
1097 .map(|s| {
1098 let points = [s.line.start, s.line.end, s.quantized.start, s.quantized.end];
1099 let (min_x, max_x, min_y, max_y) = points.iter().fold(
1100 (
1101 f64::INFINITY,
1102 f64::NEG_INFINITY,
1103 f64::INFINITY,
1104 f64::NEG_INFINITY,
1105 ),
1106 |(a, b, c, d), p| (a.min(p.x), b.max(p.x), c.min(p.y), d.max(p.y)),
1107 );
1108 SegmentBox {
1109 min_x: min_x - margin,
1110 max_x: max_x + margin,
1111 min_y: min_y - margin,
1112 max_y: max_y + margin,
1113 }
1114 })
1115 .collect()
1116}
1117
1118struct NearPoints {
1122 cell: f64,
1123 cells: std::collections::HashMap<(i64, i64), Vec<Point2>>,
1124 unindexed: Vec<Point2>,
1125 all: Vec<Point2>,
1126}
1127
1128impl NearPoints {
1129 fn new(cell: f64) -> Self {
1130 Self {
1131 cell,
1132 cells: std::collections::HashMap::new(),
1133 unindexed: Vec::new(),
1134 all: Vec::new(),
1135 }
1136 }
1137
1138 fn key(&self, point: Point2) -> Option<(i64, i64)> {
1139 const LIMIT: f64 = (1_i64 << 52) as f64;
1140 if full_scan() {
1141 return None;
1142 }
1143 let x = (point.x / (2. * self.cell)).floor();
1144 let y = (point.y / (2. * self.cell)).floor();
1145 (x.abs() < LIMIT && y.abs() < LIMIT).then_some((x as i64, y as i64))
1146 }
1147
1148 fn insert(&mut self, point: Point2) -> (bool, usize) {
1151 let near = |previous: &Point2| {
1152 let distance = previous.distance(point);
1153 distance > 0. && distance <= self.cell
1154 };
1155 let Some((x, y)) = self.key(point) else {
1156 let found = self.all.iter().any(near);
1157 if !found && !self.all.contains(&point) {
1158 self.all.push(point);
1159 self.unindexed.push(point);
1160 }
1161 return (found, self.all.len());
1162 };
1163 let mut compared = self.unindexed.len();
1164 let mut found = self.unindexed.iter().any(near);
1165 let mut duplicate = self.unindexed.contains(&point);
1166 for dx in -1..=1 {
1167 for dy in -1..=1 {
1168 if let Some(bucket) = self.cells.get(&(x + dx, y + dy)) {
1169 compared += bucket.len();
1170 found |= bucket.iter().any(near);
1171 duplicate |= bucket.contains(&point);
1172 }
1173 }
1174 }
1175 if !found && !duplicate {
1176 self.all.push(point);
1177 self.cells.entry((x, y)).or_default().push(point);
1178 }
1179 (found, compared)
1180 }
1181}
1182fn intersection_with_relation(
1185 a: LineSegment,
1186 b: LineSegment,
1187 kind: u8,
1188 tolerance: &GeometryTolerance,
1189) -> GeometryResult<SegmentIntersection> {
1190 match kind {
1191 0 => Ok(SegmentIntersection::None),
1192 1 => {
1193 if let Some(point) = [a.start, a.end]
1194 .into_iter()
1195 .find(|p| *p == b.start || *p == b.end)
1196 {
1197 Ok(SegmentIntersection::Point(point))
1198 } else {
1199 a.intersection(&b, tolerance)
1200 }
1201 }
1202 2 => {
1203 let use_x = (a.end.x - a.start.x).abs() >= (a.end.y - a.start.y).abs();
1204 let mut points = [a.start, a.end, b.start, b.end];
1205 points.sort_by(|a, b| {
1206 if use_x {
1207 a.x.total_cmp(&b.x)
1208 } else {
1209 a.y.total_cmp(&b.y)
1210 }
1211 });
1212 Ok(SegmentIntersection::Overlap(LineSegment {
1213 start: points[1],
1214 end: points[2],
1215 }))
1216 }
1217 _ => Err(ambiguity("input", "Unknown edge relation")),
1218 }
1219}
1220
1221fn source_parameter(source: &SourceEdge, point: Point2, budget: f64) -> GeometryResult<(f64, f64)> {
1222 let direction = source
1223 .line
1224 .start
1225 .vector_to(source.line.end)
1226 .scaled(1. / source.line.length());
1227 let offset = source.line.start.vector_to(point);
1228 let along = offset.dot(direction);
1229 let perpendicular = offset.cross(direction).abs();
1230 let outside = (-along).max(along - source.line.length()).max(0.);
1231 let deviation = perpendicular.hypot(outside);
1232 finite(along)?;
1233 finite(deviation)?;
1234 if deviation > budget || along < -budget || along > source.line.length() + budget {
1235 return Err(ambiguity(
1236 "provenance",
1237 "Output edge lies outside the source edge error budget",
1238 ));
1239 }
1240 Ok(((along / source.line.length()).clamp(0., 1.), deviation))
1241}
1242fn invalid(reason: GeometryReason, field: &str, message: &str) -> GeometryError {
1243 GeometryError::invalid(reason, field, "polygon.boolean", message)
1244}
1245fn ambiguity(field: &str, message: &str) -> GeometryError {
1246 invalid(GeometryReason::BooleanAmbiguity, field, message)
1247}
1248fn resource(field: &str) -> GeometryError {
1249 GeometryError::unsupported(
1250 GeometryReason::ResourceLimit,
1251 field,
1252 "polygon.boolean",
1253 "Boolean resource limit exceeded",
1254 )
1255}
1256
1257fn orientation(a: Point2, b: Point2, c: Point2) -> GeometryResult<f64> {
1258 let scale = [a.x, a.y, b.x, b.y, c.x, c.y]
1259 .into_iter()
1260 .map(f64::abs)
1261 .fold(0., f64::max);
1262 let divisor = if scale == 0. {
1263 1.
1264 } else {
1265 2_f64.powf(scale.log2().floor())
1266 };
1267 let points = [a, b, c].map(|p| robust::Coord {
1268 x: p.x / divisor,
1269 y: p.y / divisor,
1270 });
1271 for (i, a) in points.iter().enumerate() {
1272 for b in points.iter().skip(i + 1) {
1273 for delta in [a.x - b.x, a.y - b.y] {
1274 if delta != 0. && delta.abs() < 1e-100 {
1275 return Err(ambiguity(
1276 "input",
1277 "Predicate exponent range is outside the supported numerical profile",
1278 ));
1279 }
1280 }
1281 }
1282 }
1283 let value = robust::orient2d(points[0], points[1], points[2]);
1284 finite(value)?;
1285 Ok(value)
1286}
1287fn relation(a: LineSegment, b: LineSegment) -> GeometryResult<u8> {
1288 let ab = [
1289 orientation(a.start, a.end, b.start)?,
1290 orientation(a.start, a.end, b.end)?,
1291 ];
1292 let ba = [
1293 orientation(b.start, b.end, a.start)?,
1294 orientation(b.start, b.end, a.end)?,
1295 ];
1296 if ab == [0., 0.] && ba == [0., 0.] {
1297 let use_x = (a.end.x - a.start.x).abs() >= (a.end.y - a.start.y).abs();
1298 let coordinates = [a.start, a.end, b.start, b.end].map(|p| if use_x { p.x } else { p.y });
1299 let lo = coordinates[0]
1300 .min(coordinates[1])
1301 .max(coordinates[2].min(coordinates[3]));
1302 let hi = coordinates[0]
1303 .max(coordinates[1])
1304 .min(coordinates[2].max(coordinates[3]));
1305 return Ok(if lo < hi {
1306 2
1307 } else if lo == hi {
1308 1
1309 } else {
1310 0
1311 });
1312 }
1313 let straddles = |v: [f64; 2]| {
1314 v[0] == 0. || v[1] == 0. || v[0].is_sign_positive() != v[1].is_sign_positive()
1315 };
1316 Ok(if straddles(ab) && straddles(ba) { 1 } else { 0 })
1317}