Skip to main content

cadkit_geom/
boolean.rs

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/// Regularized area operation using caller-coordinate and squared-area error budgets; each operand
18/// collection represents a union.
19#[cfg_attr(feature = "schemars", schemars(transform = crate::unit_enum_schema))]
20pub enum PolygonBooleanOperation {
21    /// Union of both operand collections; area semantics use the explicit squared-unit budget.
22    Union,
23    /// Common area or analytic intersection, according to the enclosing result or operation; input
24    /// coordinate units are retained.
25    Intersection,
26    /// Area in the subject collection outside the clip collection; uses the explicit squared-unit
27    /// budget.
28    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/// Unit-independent identity of an input operand collection in a boolean call.
34#[cfg_attr(feature = "schemars", schemars(transform = crate::unit_enum_schema))]
35pub enum BooleanOperand {
36    /// Subject operand collection, independent of units.
37    Subject,
38    /// Clip operand collection, independent of units.
39    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)]
49/// Unit-independent ring reference into one polygon; hole indices preserve input order.
50pub enum PolygonRing {
51    /// Exterior ring reference, independent of units.
52    Exterior,
53    /// Hole ring reference, independent of units.
54    Hole {
55        /// Zero-based hole index within the polygon; dimensionless.
56        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)]
62/// Collection of polygons in the same caller coordinate system; empty collections represent zero
63/// area. Operations use explicit tolerances.
64pub struct MultiPolygon {
65    /// Polygon components in the same caller coordinate system.
66    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)]
71/// Boolean error budgets in caller units and squared units, with dimensionless resource limits.
72/// Coordinate error must not exceed the supplied linear tolerance.
73pub struct PolygonBooleanOptions {
74    /// Positive coordinate-unit deviation budget, no larger than the supplied linear tolerance.
75    pub max_coordinate_error: f64,
76    /// Positive squared-unit budget for the total operation's area error, separate from minimum
77    /// valid area.
78    pub max_area_error: f64,
79    /// Dimensionless input edge cap, 3-16384; default 8192.
80    pub max_input_edges: usize,
81    /// Dimensionless output edge cap, 3-262144; default 65536.
82    pub max_output_edges: usize,
83    /// Dimensionless candidate-pair check cap, 1-10000000; default 1000000.
84    pub max_pair_checks: usize,
85    /// Dimensionless generated-edge cap, 3-262144; default 131072.
86    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    /// Construct boolean options with coordinate and squared-area budgets, retaining default
102    /// resource caps. Validation occurs when used.
103    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)]
144/// Reference into the original boolean call's operand, polygon, ring and edge order; indices are
145/// dimensionless and zero-based.
146pub struct BooleanSourceEdge {
147    /// Input operand collection; independent of coordinates or units.
148    pub operand: BooleanOperand,
149    /// Zero-based polygon index in the referenced collection; dimensionless.
150    pub polygon_index: usize,
151    /// Ring reference retaining its polygon's original order; dimensionless.
152    pub ring: PolygonRing,
153    /// Zero-based edge index within the referenced ring; dimensionless.
154    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)]
159/// Directed interval on a source edge. Parameters are dimensionless in 0-1, and deviation uses
160/// caller coordinate units.
161pub struct BooleanSourceSpan {
162    /// Original edge reference in input order; indices are dimensionless.
163    pub source: BooleanSourceEdge,
164    /// Directed start fraction along the original edge, in 0-1; dimensionless.
165    pub start_parameter: f64,
166    /// Directed end fraction along the original edge, in 0-1; may be less than start_parameter when
167    /// reversed.
168    pub end_parameter: f64,
169    /// Largest measured deviation from the source edge in coordinate units.
170    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)]
175/// Output edge index and all contributing source spans; indices retain ring order and deviations
176/// use caller units.
177pub struct BooleanEdgeProvenance {
178    /// Zero-based edge index within the referenced ring; dimensionless.
179    pub edge_index: usize,
180    /// All contributing source spans, including coincident edges; each deviation uses caller units.
181    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)]
186/// Output polygon/ring reference and edge provenance in the boolean result's coordinate system.
187pub struct BooleanBoundaryProvenance {
188    /// Zero-based polygon index in the referenced collection; dimensionless.
189    pub polygon_index: usize,
190    /// Ring reference retaining its polygon's original order; dimensionless.
191    pub ring: PolygonRing,
192    /// Edge provenance in output ring order; indices are dimensionless.
193    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)]
198/// Measured displacements and conservative error bounds in caller units, areas in squared units,
199/// plus dimensionless resource counts.
200pub struct BooleanDiagnostics {
201    /// Stable identifier of the numerical boolean profile; independent of units.
202    pub profile: String,
203    /// Boolean dependency name and version; independent of units.
204    pub kernel: String,
205    /// World-coordinate origin used by the local integer adapter, in caller units.
206    pub local_origin: Point2,
207    /// Quantization grid spacing in caller coordinate units.
208    pub grid_size: f64,
209    /// Maximum absolute integer grid coordinate; dimensionless, currently 2^50.
210    pub integer_coordinate_limit: i64,
211    /// Largest measured input encode/decode displacement in coordinate units.
212    pub max_input_displacement: f64,
213    /// Largest measured preflight intersection displacement between representations, in coordinate
214    /// units.
215    pub max_intersection_displacement: f64,
216    /// Largest measured output-to-source edge deviation in coordinate units.
217    pub max_output_boundary_deviation: f64,
218    /// Conservative linear boundary displacement bound in caller coordinate units.
219    pub coordinate_error_bound: f64,
220    /// Total conservative area error bound in squared caller units.
221    pub area_error_bound: f64,
222    /// Arithmetic contribution to the total area error bound, in squared caller units.
223    pub arithmetic_area_error_bound: f64,
224    /// Number of source edges, dimensionless.
225    pub input_edge_count: usize,
226    /// Number of output edges, dimensionless.
227    pub output_edge_count: usize,
228    /// Number of candidate-pair and interior-node checks, dimensionless.
229    pub pair_checks: usize,
230    /// Only area geometry is returned; point and edge contacts are not separate area
231    /// components.
232    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)]
237/// Regularized area geometry, diagnostics and source provenance in caller coordinates; area is in
238/// squared units.
239pub struct PolygonBooleanResult {
240    /// Area operation performed; coordinate and area budgets are recorded in diagnostics.
241    pub operation: PolygonBooleanOperation,
242    /// Polygon components in input coordinate units; empty output is valid zero area.
243    pub geometry: MultiPolygon,
244    /// Area in squared caller coordinate units.
245    pub area: f64,
246    /// Measured and bounded errors in the input coordinate and squared-area units.
247    pub diagnostics: BooleanDiagnostics,
248    /// Output boundary provenance referencing original input edge order.
249    pub boundaries: Vec<BooleanBoundaryProvenance>,
250}
251
252/// Split closed regions with zero-width separators without consuming area. Open ends do not
253/// close a region; output pieces are checked against area and coordinate budgets in the
254/// caller's units.
255pub 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    // Only edges whose budget-expanded boxes contain the output point can meet the distance
357    // budget. Validate all lines at the first point to preserve the exhaustive scan's first
358    // error.
359    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    /// Regularized union in input coordinate units, preserving all source edge provenance under
442    /// explicit coordinate, area and validation budgets.
443    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    /// Regularized common area in input coordinate units with explicit coordinate, squared-area and
458    /// validation budgets.
459    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    /// Subtract the second polygon from the first in input coordinate units under explicit
474    /// coordinate, area and validation budgets.
475    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
491/// Each operand collection represents a union; overlapping clips are subtracted only once.
492/// Coordinates and linear budgets use caller units; area budgets use squared units.
493pub 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            // The dependency trait cannot return Result. Record the failure and
922            // reject the entire operation immediately after kernel extraction.
923            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    // Disjoint expanded boxes cannot produce intersections or contacts within the linear
964    // tolerance. Visit remaining pairs in exhaustive order to preserve both the first error
965    // and the result.
966    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
1080/// Preflight box enclosing local and quantized endpoints. Padding covers the linear proximity
1081/// threshold, quantization displacement, local comparison roundoff and world-to-local
1082/// subtraction roundoff.
1083fn 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
1118/// Grid of interior intersection nodes. Cells have width 2 * cell, so all nodes within cell
1119/// distance occur in the nine neighboring cells despite division roundoff. Unrepresentable
1120/// cell coordinates use the full list.
1121struct 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    /// Insert a point and return (distinct node within tolerance, comparison count). Exact
1149    /// duplicates are not inserted again.
1150    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}
1182/// Robust predicates classify contacts. Shared endpoints and collinear overlaps reuse existing
1183/// endpoints instead of dividing by a small angle and adding construction error.
1184fn 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}