Skip to main content

neco_geometry/
intersection.rs

1use alloc::boxed::Box;
2use alloc::format;
3use alloc::string::String;
4use alloc::vec;
5use alloc::vec::Vec;
6use core::cmp::Ordering;
7use core::num::NonZeroUsize;
8
9use neco_algnum::RealAlgebraic;
10use neco_bigint::{BigInt, BigUint, BigintError, Dyadic, RawRational, Sign};
11use neco_calculus::{
12    CalculusFailure, ConvergenceStatus as CalculusConvergenceStatus, DerivativeOrder, Enclosure,
13    ExactExpressionRequirement, NecoImplementationSource, OwnerId, Polynomial, PolynomialFailure,
14    RootBracket as CalculusRootBracket, RootEvidence as CalculusRootEvidence,
15    RootIsolation as CalculusRootIsolation, RootMultiplicity, RootRefinementMethod,
16    SurfacePolynomial,
17};
18use neco_geometry_foundation::{CheckedRay3, Direction3, Point2, Point3, Ray3, Vector3};
19
20use crate::evaluation::{
21    evaluate_shape, evaluate_surface_witness_checked, evaluate_surface_witness_exact,
22};
23use crate::types::{
24    point_on_loop, CertifiedShapeEvaluation, CoordinateEnclosure3, ExactShapeEvaluation,
25    GeometryFailure, ImplicitSurfaceDeclaration, SeamContact, ShapeCoordinate, ShapeDeclaration,
26    ShapeEvaluation, ShapeEvaluationRequest, SurfaceCrossingCandidate, SurfaceEvaluationWitness,
27    SurfaceParameterPoint, TrimClassification,
28};
29
30pub type BranchIdentitySet = Vec<BranchIdentity>;
31pub type CurveBranchSet = Vec<CurveBranch>;
32pub type IntersectionPointSet = Vec<IntersectionPoint>;
33pub type RootBracketSet = Vec<RootBracket>;
34pub type BranchIdentityRef = Option<BranchIdentity>;
35
36#[derive(Debug, Eq, PartialEq)]
37pub struct IntersectionDomain {
38    parameterization: String,
39    restriction: String,
40    support: String,
41}
42
43impl IntersectionDomain {
44    fn new(parameterization: String, restriction: String, support: String) -> Self {
45        Self {
46            parameterization,
47            restriction,
48            support,
49        }
50    }
51
52    pub fn parameterization(&self) -> &str {
53        &self.parameterization
54    }
55
56    pub fn restriction(&self) -> &str {
57        &self.restriction
58    }
59
60    pub fn support(&self) -> &str {
61        &self.support
62    }
63}
64
65#[derive(Debug, Eq, PartialEq)]
66pub struct ResidualFunction {
67    left_expression: String,
68    right_expression: String,
69    combined_expression: String,
70}
71
72impl ResidualFunction {
73    fn new(left_expression: String, right_expression: String) -> Self {
74        let combined_expression = format!("({left_expression}) - ({right_expression})");
75        Self {
76            left_expression,
77            right_expression,
78            combined_expression,
79        }
80    }
81
82    pub fn left_expression(&self) -> &str {
83        &self.left_expression
84    }
85
86    pub fn right_expression(&self) -> &str {
87        &self.right_expression
88    }
89
90    pub fn combined_expression(&self) -> &str {
91        &self.combined_expression
92    }
93}
94
95#[derive(Clone, Copy, Debug, Eq, PartialEq)]
96pub enum SupportEvidence {
97    CanonicalSupportAndChart,
98    CompatibleParametricSupports,
99    DistinctEvaluatedScalars,
100    EqualEvaluatedScalars,
101    EvaluatedSpatialCoordinates,
102    ImplicitSupportPair,
103}
104
105#[derive(Clone, Copy, Debug, Eq, PartialEq)]
106pub enum SupportUndeterminedReason {
107    IncompleteEvaluatedScalar,
108    NoCommonParameterization,
109    UnclassifiedEvidence,
110}
111
112#[derive(Debug, Eq, PartialEq)]
113pub enum SupportRelation {
114    Coincident { evidence: SupportEvidence },
115    Curve { evidence: SupportEvidence },
116    Disjoint { evidence: SupportEvidence },
117    Finite { evidence: SupportEvidence },
118    Undetermined { reason: SupportUndeterminedReason },
119}
120
121#[derive(Clone, Copy, Debug, Eq, PartialEq)]
122pub enum RankDegeneracyReason {
123    InsufficientCommonRank,
124}
125
126#[derive(Clone, Copy, Debug, Eq, PartialEq)]
127pub enum RankUndeterminedReason {
128    SupportRelationUnresolved,
129}
130
131#[derive(Debug, Eq, PartialEq)]
132pub enum RankEvidence {
133    Sufficient { rank: usize },
134    Degenerate { reason: RankDegeneracyReason },
135    Undetermined { reason: RankUndeterminedReason },
136}
137
138#[derive(Clone, Copy, Debug, Eq, PartialEq)]
139pub enum RootSign {
140    Negative,
141    Positive,
142    Zero,
143}
144
145#[derive(Clone, Copy, Debug, Eq, PartialEq)]
146pub enum RootUndeterminedReason {
147    ExactEvidenceUnavailable,
148    ExactMultiplicityUnavailable,
149    SignChangePointUnavailable,
150}
151
152#[derive(Clone, Debug, Eq, PartialEq)]
153pub struct ResidualSourceId(String);
154
155impl ResidualSourceId {
156    fn new(value: &str) -> Self {
157        Self(String::from(value))
158    }
159
160    pub fn as_str(&self) -> &str {
161        &self.0
162    }
163}
164
165#[derive(Debug, Eq, PartialEq)]
166pub enum RootEvidence {
167    SignChange {
168        lower_sign: RootSign,
169        upper_sign: RootSign,
170        derivative_enclosure: Enclosure,
171        source: ResidualSourceId,
172    },
173    EvenMultiplicityTouch {
174        order: usize,
175        point: RealAlgebraic,
176        source: ResidualSourceId,
177    },
178    HigherOrder {
179        order: usize,
180        point: RealAlgebraic,
181        source: ResidualSourceId,
182    },
183    SimpleRoot {
184        point: RealAlgebraic,
185        source: ResidualSourceId,
186    },
187    Undetermined {
188        reason: RootUndeterminedReason,
189        source: ResidualSourceId,
190    },
191}
192
193#[derive(Debug, Eq, PartialEq)]
194pub struct IntersectionConstraint {
195    left_operand: IntersectionOperand,
196    right_operand: IntersectionOperand,
197    residual_function: ResidualFunction,
198    domain: IntersectionDomain,
199    support_relation: SupportRelation,
200    rank_evidence: RankEvidence,
201}
202
203impl IntersectionConstraint {
204    fn new(
205        left_operand: IntersectionOperand,
206        right_operand: IntersectionOperand,
207        residual_function: ResidualFunction,
208        domain: IntersectionDomain,
209        support_relation: SupportRelation,
210        rank_evidence: RankEvidence,
211    ) -> Self {
212        Self {
213            left_operand,
214            right_operand,
215            residual_function,
216            domain,
217            support_relation,
218            rank_evidence,
219        }
220    }
221
222    pub fn left_operand(&self) -> &IntersectionOperand {
223        &self.left_operand
224    }
225
226    pub fn right_operand(&self) -> &IntersectionOperand {
227        &self.right_operand
228    }
229
230    pub fn residual_function(&self) -> &ResidualFunction {
231        &self.residual_function
232    }
233
234    pub fn domain(&self) -> &IntersectionDomain {
235        &self.domain
236    }
237
238    pub fn support_relation(&self) -> &SupportRelation {
239        &self.support_relation
240    }
241
242    pub fn rank_evidence(&self) -> &RankEvidence {
243        &self.rank_evidence
244    }
245
246    fn rank_is_undetermined(&self) -> bool {
247        matches!(
248            self.rank_evidence,
249            RankEvidence::Degenerate { .. } | RankEvidence::Undetermined { .. }
250        )
251    }
252}
253
254#[derive(Clone, Copy, Debug, Eq, PartialEq)]
255enum OperandSource {
256    Declaration,
257    Evaluated,
258}
259
260#[derive(Debug, Eq, PartialEq)]
261struct OperandDescriptor {
262    source: OperandSource,
263    family: crate::types::ShapeFamily,
264    support_id: String,
265    chart_id: String,
266    domain: String,
267    parameter_bounds: Option<(RealAlgebraic, RealAlgebraic)>,
268    expression: String,
269    polynomial: Option<Polynomial>,
270    exact_scalar: Option<RealAlgebraic>,
271    exact_point: Option<Point3>,
272    certified_scalar: Option<(
273        Enclosure,
274        OwnerId,
275        ExactExpressionRequirement,
276        NecoImplementationSource,
277    )>,
278}
279
280#[derive(Debug, Eq, PartialEq)]
281struct DerivedRootProblem {
282    constraint: IntersectionConstraint,
283    polynomial: Option<Polynomial>,
284    domain: Option<Enclosure>,
285}
286
287type PartitionCellId = usize;
288
289#[derive(Debug, Eq, PartialEq)]
290struct PartitionCell {
291    id: PartitionCellId,
292    depth: usize,
293    enclosure: Enclosure,
294    disposition: CellDisposition,
295}
296
297#[derive(Debug, Eq, PartialEq)]
298enum CellDisposition {
299    Candidate,
300    Coincident,
301    RootFree,
302    Unresolved { reason: PartitionUnresolvedReason },
303}
304
305#[derive(Debug, Eq, PartialEq)]
306enum RootCandidateBracket {
307    Exact { parameter: RealAlgebraic },
308    Certified(CalculusRootBracket),
309    Unresolved { enclosure: Enclosure },
310}
311
312#[derive(Debug, Eq, PartialEq)]
313struct RootCandidate {
314    bracket: RootCandidateBracket,
315    evidence: RootEvidence,
316    source_cell: PartitionCellId,
317}
318
319#[derive(Debug, Eq, PartialEq)]
320struct RootEnumeration {
321    candidates: Vec<RootCandidate>,
322    cells: Vec<PartitionCell>,
323}
324
325impl RootEnumeration {
326    fn incomplete(domain: Option<&Enclosure>) -> Self {
327        let cells = domain
328            .and_then(|enclosure| {
329                Some(vec![PartitionCell {
330                    id: 0,
331                    depth: 0,
332                    enclosure: clone_enclosure(enclosure).ok()?,
333                    disposition: CellDisposition::Unresolved {
334                        reason: PartitionUnresolvedReason::DomainUnavailable,
335                    },
336                }])
337            })
338            .unwrap_or_default();
339        Self {
340            candidates: Vec::new(),
341            cells,
342        }
343    }
344}
345
346type RootCandidateSet = RootEnumeration;
347
348#[derive(Clone, Copy, Debug, Eq, PartialEq)]
349enum PartitionUnresolvedReason {
350    DomainUnavailable,
351    MultipleExactDyadicRoots,
352    SignChangeUniqueness,
353    UncertifiedRoot,
354}
355
356enum CellAssessment {
357    Candidate(Vec<RootCandidate>),
358    ExactTouch {
359        candidate: Box<RootCandidate>,
360        pivot: Dyadic,
361    },
362    RootFree,
363    Unresolved(PartitionUnresolvedReason),
364}
365
366struct PendingPartitionCell {
367    id: PartitionCellId,
368    depth: usize,
369    enclosure: Enclosure,
370    suppressed_exact_endpoints: Vec<Dyadic>,
371}
372
373const ROOT_INTERVAL_PRECISION_BITS: u32 = 32;
374pub const MAX_ROOT_PARTITION_DEPTH: usize = 19;
375pub const MAX_ROOT_PARTITION_CELLS: usize = 65_535;
376
377fn partition_cells_for_depth(depth: usize) -> usize {
378    1usize
379        .checked_shl((depth + 1) as u32)
380        .and_then(|value| value.checked_sub(1))
381        .unwrap_or(MAX_ROOT_PARTITION_CELLS)
382        .min(MAX_ROOT_PARTITION_CELLS)
383}
384
385fn ensure_partition_cell_capacity(
386    completed_cells: usize,
387    pending_cells: usize,
388    child_cells: usize,
389    maximum_cells: usize,
390) -> Result<(), GeometryFailure> {
391    let requested_cells = completed_cells
392        .checked_add(pending_cells)
393        .and_then(|value| value.checked_add(child_cells))
394        .ok_or(GeometryFailure::RootPartitionIdentifierOverflow {
395            current_identifier: usize::MAX,
396            increment: child_cells,
397        })?;
398    if requested_cells > maximum_cells {
399        return Err(GeometryFailure::RootPartitionCellLimit {
400            requested_cells,
401            maximum_cells,
402        });
403    }
404    Ok(())
405}
406
407fn take_partition_cell_id(next_cell_id: &mut usize) -> Result<usize, GeometryFailure> {
408    let current_identifier = *next_cell_id;
409    *next_cell_id = current_identifier.checked_add(1).ok_or(
410        GeometryFailure::RootPartitionIdentifierOverflow {
411            current_identifier,
412            increment: 1,
413        },
414    )?;
415    Ok(current_identifier)
416}
417
418#[derive(Debug, Eq, PartialEq)]
419pub struct RootIsolation {
420    brackets: RootBracketSet,
421    completeness: ExistenceWitness,
422    method: RootRefinementMethod,
423    source_domain: IntersectionDomain,
424    source_function: ResidualFunction,
425    non_overlap: UniquenessWitness,
426}
427
428impl RootIsolation {
429    fn new(
430        brackets: RootBracketSet,
431        completeness: ExistenceWitness,
432        method: RootRefinementMethod,
433        source_domain: IntersectionDomain,
434        source_function: ResidualFunction,
435        non_overlap: UniquenessWitness,
436    ) -> Self {
437        Self {
438            brackets,
439            completeness,
440            method,
441            source_domain,
442            source_function,
443            non_overlap,
444        }
445    }
446
447    pub fn brackets(&self) -> &[RootBracket] {
448        &self.brackets
449    }
450
451    pub fn completeness(&self) -> &ExistenceWitness {
452        &self.completeness
453    }
454
455    pub fn method(&self) -> RootRefinementMethod {
456        self.method
457    }
458
459    pub fn source_domain(&self) -> &IntersectionDomain {
460        &self.source_domain
461    }
462
463    pub fn source_function(&self) -> &ResidualFunction {
464        &self.source_function
465    }
466
467    pub fn non_overlap(&self) -> &UniquenessWitness {
468        &self.non_overlap
469    }
470}
471
472#[derive(Debug, Eq, PartialEq)]
473pub struct BranchIdentity {
474    branch_id: String,
475    chart_id: String,
476    support_id: String,
477}
478
479impl BranchIdentity {
480    fn new(branch_id: String, chart_id: String, support_id: String) -> Self {
481        Self {
482            branch_id,
483            chart_id,
484            support_id,
485        }
486    }
487
488    pub fn branch_id(&self) -> &str {
489        &self.branch_id
490    }
491
492    pub fn chart_id(&self) -> &str {
493        &self.chart_id
494    }
495
496    pub fn support_id(&self) -> &str {
497        &self.support_id
498    }
499}
500
501#[derive(Debug, Eq, PartialEq)]
502pub struct IntersectionCurve {
503    branch_identity: BranchIdentity,
504    contact_order: ContactOrder,
505    residual: IntersectionResidual,
506    support_id: String,
507    witness: IntersectionWitness,
508}
509
510impl IntersectionCurve {
511    fn new(
512        branch_identity: BranchIdentity,
513        contact_order: ContactOrder,
514        residual: IntersectionResidual,
515        support_id: String,
516        witness: IntersectionWitness,
517    ) -> Self {
518        Self {
519            branch_identity,
520            contact_order,
521            residual,
522            support_id,
523            witness,
524        }
525    }
526
527    pub fn branch_identity(&self) -> &BranchIdentity {
528        &self.branch_identity
529    }
530
531    pub fn contact_order(&self) -> &ContactOrder {
532        &self.contact_order
533    }
534
535    pub fn residual(&self) -> &IntersectionResidual {
536        &self.residual
537    }
538
539    pub fn support_id(&self) -> &str {
540        &self.support_id
541    }
542
543    pub fn witness(&self) -> &IntersectionWitness {
544        &self.witness
545    }
546}
547
548#[derive(Debug, Eq, PartialEq)]
549pub struct CurveBranch {
550    branch_identity: BranchIdentity,
551    contact_order: ContactOrder,
552    residual: IntersectionResidual,
553    witness: IntersectionWitness,
554}
555
556impl CurveBranch {
557    fn new(
558        branch_identity: BranchIdentity,
559        contact_order: ContactOrder,
560        residual: IntersectionResidual,
561        witness: IntersectionWitness,
562    ) -> Self {
563        Self {
564            branch_identity,
565            contact_order,
566            residual,
567            witness,
568        }
569    }
570
571    pub fn branch_identity(&self) -> &BranchIdentity {
572        &self.branch_identity
573    }
574
575    pub fn contact_order(&self) -> &ContactOrder {
576        &self.contact_order
577    }
578
579    pub fn residual(&self) -> &IntersectionResidual {
580        &self.residual
581    }
582
583    pub fn witness(&self) -> &IntersectionWitness {
584        &self.witness
585    }
586}
587
588#[derive(Debug, Eq, PartialEq)]
589pub struct IntersectionPoint {
590    branch_identity: BranchIdentityRef,
591    contact_order: ContactOrder,
592    point: Point3,
593    residual: IntersectionResidual,
594    witness: IntersectionWitness,
595}
596
597impl IntersectionPoint {
598    fn new(
599        branch_identity: BranchIdentityRef,
600        contact_order: ContactOrder,
601        point: Point3,
602        residual: IntersectionResidual,
603        witness: IntersectionWitness,
604    ) -> Self {
605        Self {
606            branch_identity,
607            contact_order,
608            point,
609            residual,
610            witness,
611        }
612    }
613
614    pub fn branch_identity(&self) -> Option<&BranchIdentity> {
615        self.branch_identity.as_ref()
616    }
617
618    pub fn contact_order(&self) -> &ContactOrder {
619        &self.contact_order
620    }
621
622    pub fn point(&self) -> &Point3 {
623        &self.point
624    }
625
626    pub fn residual(&self) -> &IntersectionResidual {
627        &self.residual
628    }
629
630    pub fn witness(&self) -> &IntersectionWitness {
631        &self.witness
632    }
633}
634
635#[derive(Debug, Eq, PartialEq)]
636pub struct IntersectionResidual {
637    combined: ResidualValue,
638    left: ResidualValue,
639    right: ResidualValue,
640}
641
642impl IntersectionResidual {
643    fn new(combined: ResidualValue, left: ResidualValue, right: ResidualValue) -> Self {
644        Self {
645            combined,
646            left,
647            right,
648        }
649    }
650
651    pub fn combined(&self) -> &ResidualValue {
652        &self.combined
653    }
654
655    pub fn left(&self) -> &ResidualValue {
656        &self.left
657    }
658
659    pub fn right(&self) -> &ResidualValue {
660        &self.right
661    }
662}
663
664#[derive(Debug, Eq, PartialEq)]
665pub struct RootBracket {
666    contact_order: ContactOrder,
667    convergence: ConvergenceWitness,
668    lower: RealAlgebraic,
669    sign_change: bool,
670    upper: RealAlgebraic,
671    evidence: RootEvidence,
672    exact_parameter: Option<RealAlgebraic>,
673}
674
675impl RootBracket {
676    fn from_calculus(
677        bracket: &CalculusRootBracket,
678        isolation: &CalculusRootIsolation,
679        evidence: RootEvidence,
680    ) -> Result<Self, GeometryFailure> {
681        let contact_order = contact_order_from_evidence(&evidence);
682        Ok(Self {
683            contact_order,
684            convergence: ConvergenceWitness::from_calculus(isolation.witness())?,
685            lower: dyadic_to_real(bracket.enclosure().lower())?,
686            sign_change: matches!(bracket.evidence(), CalculusRootEvidence::SignChange { .. }),
687            upper: dyadic_to_real(bracket.enclosure().upper())?,
688            evidence,
689            exact_parameter: None,
690        })
691    }
692
693    fn from_unresolved(
694        enclosure: &Enclosure,
695        evidence: RootEvidence,
696        policy: &RootIsolationPolicy,
697    ) -> Result<Self, GeometryFailure> {
698        let lower = dyadic_to_real(enclosure.lower())?;
699        let upper = dyadic_to_real(enclosure.upper())?;
700        Ok(Self {
701            contact_order: contact_order_from_evidence(&evidence),
702            convergence: ConvergenceWitness::new(
703                lower.try_clone()?,
704                upper.try_clone()?,
705                lower.try_clone()?,
706                upper.try_clone()?,
707                0,
708                policy.method,
709                CalculusConvergenceStatus::IterationLimit,
710            ),
711            lower,
712            sign_change: false,
713            upper,
714            evidence,
715            exact_parameter: None,
716        })
717    }
718
719    fn from_exact(
720        parameter: RealAlgebraic,
721        evidence: RootEvidence,
722        policy: &RootIsolationPolicy,
723    ) -> Result<Self, GeometryFailure> {
724        let lower = parameter.try_clone()?;
725        let upper = parameter.try_clone()?;
726        Ok(Self {
727            contact_order: contact_order_from_evidence(&evidence),
728            convergence: ConvergenceWitness::new(
729                parameter.try_clone()?,
730                parameter.try_clone()?,
731                parameter.try_clone()?,
732                parameter.try_clone()?,
733                0,
734                policy.method,
735                CalculusConvergenceStatus::ExactDyadicRoot,
736            ),
737            lower,
738            sign_change: false,
739            upper,
740            evidence,
741            exact_parameter: Some(parameter),
742        })
743    }
744
745    pub fn contact_order(&self) -> &ContactOrder {
746        &self.contact_order
747    }
748
749    pub fn convergence(&self) -> &ConvergenceWitness {
750        &self.convergence
751    }
752
753    pub fn lower(&self) -> &RealAlgebraic {
754        &self.lower
755    }
756
757    pub fn sign_change(&self) -> bool {
758        self.sign_change
759    }
760
761    pub fn upper(&self) -> &RealAlgebraic {
762        &self.upper
763    }
764
765    pub fn evidence(&self) -> &RootEvidence {
766        &self.evidence
767    }
768}
769
770#[derive(Debug, Eq, PartialEq)]
771pub struct ExistenceWitness {
772    evidence: ExistenceEvidence,
773    method: WitnessMethod,
774    status: WitnessStatus,
775}
776
777impl ExistenceWitness {
778    fn new(evidence: ExistenceEvidence, method: WitnessMethod, status: WitnessStatus) -> Self {
779        Self {
780            evidence,
781            method,
782            status,
783        }
784    }
785
786    pub fn evidence(&self) -> ExistenceEvidence {
787        self.evidence
788    }
789
790    pub fn method(&self) -> WitnessMethod {
791        self.method
792    }
793
794    pub fn status(&self) -> &WitnessStatus {
795        &self.status
796    }
797}
798
799#[derive(Debug, Eq, PartialEq)]
800pub struct UniquenessWitness {
801    evidence: UniquenessEvidence,
802    method: WitnessMethod,
803    status: WitnessStatus,
804}
805
806impl UniquenessWitness {
807    fn new(evidence: UniquenessEvidence, method: WitnessMethod, status: WitnessStatus) -> Self {
808        Self {
809            evidence,
810            method,
811            status,
812        }
813    }
814
815    pub fn evidence(&self) -> UniquenessEvidence {
816        self.evidence
817    }
818
819    pub fn method(&self) -> WitnessMethod {
820        self.method
821    }
822
823    pub fn status(&self) -> &WitnessStatus {
824        &self.status
825    }
826}
827
828#[derive(Debug, Eq, PartialEq)]
829pub struct IntersectionWitness {
830    existence: ExistenceWitness,
831    uniqueness: UniquenessWitness,
832    root_isolation: RootIsolation,
833    constraint: IntersectionConstraint,
834}
835
836impl IntersectionWitness {
837    fn from_isolation_and_constraint(
838        isolation: RootIsolation,
839        constraint: IntersectionConstraint,
840    ) -> Self {
841        Self {
842            existence: clone_existence(&isolation.completeness),
843            uniqueness: clone_uniqueness(&isolation.non_overlap),
844            root_isolation: isolation,
845            constraint,
846        }
847    }
848
849    pub fn existence(&self) -> &ExistenceWitness {
850        &self.existence
851    }
852
853    pub fn uniqueness(&self) -> &UniquenessWitness {
854        &self.uniqueness
855    }
856
857    pub fn root_isolation(&self) -> &RootIsolation {
858        &self.root_isolation
859    }
860
861    pub fn constraint(&self) -> &IntersectionConstraint {
862        &self.constraint
863    }
864}
865
866#[derive(Debug, Eq, PartialEq)]
867pub struct ConvergenceWitness {
868    final_lower: RealAlgebraic,
869    final_upper: RealAlgebraic,
870    initial_lower: RealAlgebraic,
871    initial_upper: RealAlgebraic,
872    iterations: usize,
873    method: RootRefinementMethod,
874    status: CalculusConvergenceStatus,
875}
876
877impl ConvergenceWitness {
878    fn new(
879        final_lower: RealAlgebraic,
880        final_upper: RealAlgebraic,
881        initial_lower: RealAlgebraic,
882        initial_upper: RealAlgebraic,
883        iterations: usize,
884        method: RootRefinementMethod,
885        status: CalculusConvergenceStatus,
886    ) -> Self {
887        Self {
888            final_lower,
889            final_upper,
890            initial_lower,
891            initial_upper,
892            iterations,
893            method,
894            status,
895        }
896    }
897
898    pub fn final_lower(&self) -> &RealAlgebraic {
899        &self.final_lower
900    }
901
902    pub fn final_upper(&self) -> &RealAlgebraic {
903        &self.final_upper
904    }
905
906    pub fn initial_lower(&self) -> &RealAlgebraic {
907        &self.initial_lower
908    }
909
910    pub fn initial_upper(&self) -> &RealAlgebraic {
911        &self.initial_upper
912    }
913
914    pub fn iterations(&self) -> usize {
915        self.iterations
916    }
917
918    pub fn method(&self) -> RootRefinementMethod {
919        self.method
920    }
921
922    pub fn status(&self) -> CalculusConvergenceStatus {
923        self.status
924    }
925
926    fn from_calculus(witness: &neco_calculus::ConvergenceWitness) -> Result<Self, GeometryFailure> {
927        Ok(Self::new(
928            dyadic_to_real(witness.final_enclosure().lower())?,
929            dyadic_to_real(witness.final_enclosure().upper())?,
930            dyadic_to_real(witness.initial().lower())?,
931            dyadic_to_real(witness.initial().upper())?,
932            witness.iterations(),
933            witness.method(),
934            witness.status(),
935        ))
936    }
937}
938
939#[derive(Clone, Debug, Eq, PartialEq)]
940pub struct ContactOrder {
941    kind: ContactOrderKind,
942    order: usize,
943}
944
945impl ContactOrder {
946    fn new(kind: ContactOrderKind, order: usize) -> Self {
947        Self { kind, order }
948    }
949
950    pub fn kind(&self) -> ContactOrderKind {
951        self.kind
952    }
953
954    pub fn order(&self) -> usize {
955        self.order
956    }
957}
958
959#[derive(Debug, Eq, PartialEq)]
960pub struct IntersectionConstructionRequestBody {
961    left_operand: IntersectionOperand,
962    right_operand: IntersectionOperand,
963    root_isolation_policy: RootIsolationPolicy,
964}
965
966impl IntersectionConstructionRequestBody {
967    pub fn new(
968        left_operand: IntersectionOperand,
969        right_operand: IntersectionOperand,
970        root_isolation_policy: RootIsolationPolicy,
971    ) -> Self {
972        Self {
973            left_operand,
974            right_operand,
975            root_isolation_policy,
976        }
977    }
978
979    pub fn left_operand(&self) -> &IntersectionOperand {
980        &self.left_operand
981    }
982
983    pub fn right_operand(&self) -> &IntersectionOperand {
984        &self.right_operand
985    }
986
987    pub fn root_isolation_policy(&self) -> &RootIsolationPolicy {
988        &self.root_isolation_policy
989    }
990}
991
992#[derive(Debug, Eq, PartialEq)]
993pub struct IntersectionConstructionRequest {
994    body: IntersectionConstructionRequestBody,
995}
996
997impl IntersectionConstructionRequest {
998    pub fn new(body: IntersectionConstructionRequestBody) -> Self {
999        Self { body }
1000    }
1001
1002    pub fn body(&self) -> &IntersectionConstructionRequestBody {
1003        &self.body
1004    }
1005
1006    fn into_body(self) -> IntersectionConstructionRequestBody {
1007        self.body
1008    }
1009}
1010
1011#[derive(Debug, Eq, PartialEq)]
1012pub struct CoincidentSupport {
1013    left_support: ShapeDeclaration,
1014    residual: IntersectionResidual,
1015    right_support: ShapeDeclaration,
1016    witness: IntersectionWitness,
1017}
1018
1019impl CoincidentSupport {
1020    fn new(
1021        left_support: ShapeDeclaration,
1022        residual: IntersectionResidual,
1023        right_support: ShapeDeclaration,
1024        witness: IntersectionWitness,
1025    ) -> Self {
1026        Self {
1027            left_support,
1028            residual,
1029            right_support,
1030            witness,
1031        }
1032    }
1033
1034    pub fn left_support(&self) -> &ShapeDeclaration {
1035        &self.left_support
1036    }
1037
1038    pub fn residual(&self) -> &IntersectionResidual {
1039        &self.residual
1040    }
1041
1042    pub fn right_support(&self) -> &ShapeDeclaration {
1043        &self.right_support
1044    }
1045
1046    pub fn witness(&self) -> &IntersectionWitness {
1047        &self.witness
1048    }
1049}
1050
1051#[derive(Debug, Eq, PartialEq)]
1052pub struct RootIsolationPolicy {
1053    max_cells: usize,
1054    max_iterations: usize,
1055    method: RootRefinementMethod,
1056    target_width: Enclosure,
1057}
1058
1059impl RootIsolationPolicy {
1060    pub fn new(
1061        max_iterations: usize,
1062        method: RootRefinementMethod,
1063        target_width: Enclosure,
1064    ) -> Result<Self, GeometryFailure> {
1065        if max_iterations == 0 {
1066            return Err(GeometryFailure::RootIsolationPolicyInvalid);
1067        }
1068        if max_iterations > MAX_ROOT_PARTITION_DEPTH {
1069            return Err(GeometryFailure::RootIsolationResourceLimit {
1070                requested_depth: max_iterations,
1071                maximum_depth: MAX_ROOT_PARTITION_DEPTH,
1072            });
1073        }
1074        Ok(Self {
1075            max_cells: partition_cells_for_depth(max_iterations),
1076            max_iterations,
1077            method,
1078            target_width,
1079        })
1080    }
1081
1082    pub fn with_limits(
1083        max_iterations: usize,
1084        max_cells: usize,
1085        method: RootRefinementMethod,
1086        target_width: Enclosure,
1087    ) -> Result<Self, GeometryFailure> {
1088        if max_cells == 0 {
1089            return Err(GeometryFailure::RootIsolationPolicyInvalid);
1090        }
1091        if max_cells > MAX_ROOT_PARTITION_CELLS {
1092            return Err(GeometryFailure::RootPartitionCellLimit {
1093                requested_cells: max_cells,
1094                maximum_cells: MAX_ROOT_PARTITION_CELLS,
1095            });
1096        }
1097        let mut policy = Self::new(max_iterations, method, target_width)?;
1098        policy.max_cells = max_cells;
1099        Ok(policy)
1100    }
1101
1102    pub fn max_cells(&self) -> usize {
1103        self.max_cells
1104    }
1105
1106    pub fn max_iterations(&self) -> usize {
1107        self.max_iterations
1108    }
1109
1110    pub fn method(&self) -> RootRefinementMethod {
1111        self.method
1112    }
1113
1114    pub fn target_width(&self) -> &Enclosure {
1115        &self.target_width
1116    }
1117}
1118
1119#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1120pub enum IntersectionUndeterminedReason {
1121    BranchIdentityUndetermined,
1122    CoincidenceUndetermined,
1123    EvaluationUndetermined,
1124    MultiplicityUndetermined,
1125    RootIsolationIncomplete,
1126}
1127
1128#[derive(Debug, Eq, PartialEq)]
1129pub enum ResidualValue {
1130    Certified {
1131        owner: OwnerId,
1132        requirement: ExactExpressionRequirement,
1133        source: NecoImplementationSource,
1134        value: Enclosure,
1135    },
1136    Exact {
1137        value: RealAlgebraic,
1138    },
1139    Undetermined {
1140        reason: ResidualUndeterminedReason,
1141    },
1142}
1143
1144#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1145pub enum ResidualUndeterminedReason {
1146    OperandEvidenceUnresolved,
1147    ScalarResidualUnavailable,
1148}
1149
1150#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
1151pub struct IntersectionComponentIdentity(usize);
1152
1153impl IntersectionComponentIdentity {
1154    pub fn ordinal(&self) -> usize {
1155        self.0
1156    }
1157}
1158
1159#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1160pub enum IntersectionKind {
1161    Coincident,
1162    Curve,
1163    CurveBranches,
1164    Empty,
1165    FinitePoints,
1166    Point,
1167    Undetermined,
1168}
1169
1170pub enum ComponentEvidenceRef<'a> {
1171    Point(&'a IntersectionPoint),
1172    Curve(&'a IntersectionCurve),
1173    CurveBranch(&'a CurveBranch),
1174    Coincident(&'a CoincidentSupport),
1175}
1176
1177impl<'a> ComponentEvidenceRef<'a> {
1178    pub fn branch_identity(&self) -> Option<&'a BranchIdentity> {
1179        match self {
1180            Self::Point(value) => value.branch_identity(),
1181            Self::Curve(value) => Some(value.branch_identity()),
1182            Self::CurveBranch(value) => Some(value.branch_identity()),
1183            Self::Coincident(_) => None,
1184        }
1185    }
1186
1187    pub fn contact_order(&self) -> Option<&'a ContactOrder> {
1188        match self {
1189            Self::Point(value) => Some(value.contact_order()),
1190            Self::Curve(value) => Some(value.contact_order()),
1191            Self::CurveBranch(value) => Some(value.contact_order()),
1192            Self::Coincident(_) => None,
1193        }
1194    }
1195}
1196
1197pub struct IntersectionComponentViewEntry<'a> {
1198    identity: IntersectionComponentIdentity,
1199    evidence: ComponentEvidenceRef<'a>,
1200}
1201
1202impl<'a> IntersectionComponentViewEntry<'a> {
1203    pub fn identity(&self) -> IntersectionComponentIdentity {
1204        self.identity
1205    }
1206    pub fn evidence(&self) -> &ComponentEvidenceRef<'a> {
1207        &self.evidence
1208    }
1209}
1210
1211pub struct IntersectionComponentIter<'a> {
1212    inner: core::slice::Iter<'a, OwnedIntersectionComponent>,
1213}
1214
1215impl<'a> Iterator for IntersectionComponentIter<'a> {
1216    type Item = IntersectionComponentViewEntry<'a>;
1217
1218    fn next(&mut self) -> Option<Self::Item> {
1219        self.inner.next().map(|entry| {
1220            let evidence = match &entry.evidence {
1221                OwnedIntersectionEvidence::Point(value) => {
1222                    ComponentEvidenceRef::Point(value.as_ref())
1223                }
1224                OwnedIntersectionEvidence::Curve(value) => {
1225                    ComponentEvidenceRef::Curve(value.as_ref())
1226                }
1227                OwnedIntersectionEvidence::CurveBranch(value) => {
1228                    ComponentEvidenceRef::CurveBranch(value.as_ref())
1229                }
1230                OwnedIntersectionEvidence::Coincident(value) => {
1231                    ComponentEvidenceRef::Coincident(value.as_ref())
1232                }
1233            };
1234            IntersectionComponentViewEntry {
1235                identity: entry.identity,
1236                evidence,
1237            }
1238        })
1239    }
1240
1241    fn size_hint(&self) -> (usize, Option<usize>) {
1242        self.inner.size_hint()
1243    }
1244}
1245
1246impl ExactSizeIterator for IntersectionComponentIter<'_> {}
1247
1248pub enum IntersectionComponentView<'a> {
1249    Components(IntersectionComponentIter<'a>),
1250    NoComponents,
1251    Undetermined(IntersectionUndeterminedReason),
1252}
1253
1254#[derive(Debug, Eq, PartialEq)]
1255enum OwnedIntersectionEvidence {
1256    Point(Box<IntersectionPoint>),
1257    Curve(Box<IntersectionCurve>),
1258    CurveBranch(Box<CurveBranch>),
1259    Coincident(Box<CoincidentSupport>),
1260}
1261
1262#[derive(Debug, Eq, PartialEq)]
1263struct OwnedIntersectionComponent {
1264    identity: IntersectionComponentIdentity,
1265    evidence: OwnedIntersectionEvidence,
1266}
1267
1268impl OwnedIntersectionComponent {
1269    fn validate(&self) -> Result<(), GeometryFailure> {
1270        match self.evidence {
1271            OwnedIntersectionEvidence::Point(_)
1272            | OwnedIntersectionEvidence::Curve(_)
1273            | OwnedIntersectionEvidence::CurveBranch(_)
1274            | OwnedIntersectionEvidence::Coincident(_) => Ok(()),
1275        }
1276    }
1277}
1278
1279#[derive(Debug, Eq, PartialEq)]
1280#[must_use]
1281pub struct IntersectionSet {
1282    kind: IntersectionKind,
1283    witness: IntersectionWitness,
1284    residual: IntersectionResidual,
1285    reason: Option<IntersectionUndeterminedReason>,
1286    components: Vec<OwnedIntersectionComponent>,
1287}
1288
1289impl IntersectionSet {
1290    pub fn kind(&self) -> IntersectionKind {
1291        self.kind
1292    }
1293    pub fn witness(&self) -> &IntersectionWitness {
1294        &self.witness
1295    }
1296    pub fn residual(&self) -> &IntersectionResidual {
1297        &self.residual
1298    }
1299    pub fn component_view(&self) -> IntersectionComponentView<'_> {
1300        if let Some(reason) = self.reason {
1301            return IntersectionComponentView::Undetermined(reason);
1302        }
1303        if self.components.is_empty() {
1304            return IntersectionComponentView::NoComponents;
1305        }
1306        IntersectionComponentView::Components(IntersectionComponentIter {
1307            inner: self.components.iter(),
1308        })
1309    }
1310
1311    fn empty(residual: IntersectionResidual, witness: IntersectionWitness) -> Self {
1312        Self {
1313            kind: IntersectionKind::Empty,
1314            witness,
1315            residual,
1316            reason: None,
1317            components: Vec::new(),
1318        }
1319    }
1320
1321    fn undetermined(
1322        reason: IntersectionUndeterminedReason,
1323        residual: IntersectionResidual,
1324        witness: IntersectionWitness,
1325    ) -> Self {
1326        Self {
1327            kind: IntersectionKind::Undetermined,
1328            witness,
1329            residual,
1330            reason: Some(reason),
1331            components: Vec::new(),
1332        }
1333    }
1334
1335    fn from_components(
1336        kind: IntersectionKind,
1337        residual: IntersectionResidual,
1338        witness: IntersectionWitness,
1339        evidence: Vec<OwnedIntersectionEvidence>,
1340    ) -> Result<Self, GeometryFailure> {
1341        let expected = match kind {
1342            IntersectionKind::Coincident | IntersectionKind::Point | IntersectionKind::Curve => 1,
1343            IntersectionKind::FinitePoints | IntersectionKind::CurveBranches => {
1344                if evidence.is_empty() {
1345                    return Err(if kind == IntersectionKind::FinitePoints {
1346                        GeometryFailure::EmptyFinitePointComponents
1347                    } else {
1348                        GeometryFailure::EmptyCurveBranchComponents
1349                    });
1350                }
1351                evidence.len()
1352            }
1353            IntersectionKind::Empty | IntersectionKind::Undetermined => {
1354                return Err(GeometryFailure::ComponentIdentityEvidenceMismatch);
1355            }
1356        };
1357        if evidence.len() != expected {
1358            return Err(GeometryFailure::ComponentIdentityEvidenceMismatch);
1359        }
1360        let components = evidence
1361            .into_iter()
1362            .enumerate()
1363            .map(|(ordinal, evidence)| OwnedIntersectionComponent {
1364                identity: IntersectionComponentIdentity(ordinal),
1365                evidence,
1366            })
1367            .collect::<Vec<_>>();
1368        if components
1369            .windows(2)
1370            .any(|pair| pair[0].identity >= pair[1].identity)
1371        {
1372            return Err(GeometryFailure::DuplicateIntersectionComponentIdentity);
1373        }
1374        for component in &components {
1375            component
1376                .validate()
1377                .map_err(|_| GeometryFailure::ComponentIdentityEvidenceMismatch)?;
1378        }
1379        if components.len() != expected {
1380            return Err(GeometryFailure::ComponentIdentityCanonicalizationFailure);
1381        }
1382        let kind_matches = match kind {
1383            IntersectionKind::Coincident => matches!(
1384                components[0].evidence,
1385                OwnedIntersectionEvidence::Coincident(_)
1386            ),
1387            IntersectionKind::Point | IntersectionKind::FinitePoints => components
1388                .iter()
1389                .all(|entry| matches!(entry.evidence, OwnedIntersectionEvidence::Point(_))),
1390            IntersectionKind::Curve => {
1391                matches!(components[0].evidence, OwnedIntersectionEvidence::Curve(_))
1392            }
1393            IntersectionKind::CurveBranches => components
1394                .iter()
1395                .all(|entry| matches!(entry.evidence, OwnedIntersectionEvidence::CurveBranch(_))),
1396            IntersectionKind::Empty | IntersectionKind::Undetermined => false,
1397        };
1398        if !kind_matches {
1399            return Err(GeometryFailure::ComponentIdentityEvidenceMismatch);
1400        }
1401        Ok(Self {
1402            kind,
1403            witness,
1404            residual,
1405            reason: None,
1406            components,
1407        })
1408    }
1409}
1410
1411#[derive(Debug, Eq, PartialEq)]
1412pub enum IntersectionOperand {
1413    Declaration(ShapeDeclaration),
1414    Evaluated(ShapeEvaluation),
1415}
1416
1417#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1418pub enum ContactOrderKind {
1419    HigherOrder,
1420    Tangent,
1421    Transverse,
1422    Undetermined,
1423}
1424
1425#[derive(Debug, Eq, PartialEq)]
1426pub enum WitnessStatus {
1427    Proved,
1428    Undetermined { reason: WitnessUndeterminedReason },
1429}
1430
1431#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1432pub enum WitnessMethod {
1433    CanonicalLowerEndpointOrdering,
1434    DeterministicDyadicCandidatePartition,
1435}
1436
1437#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1438pub enum ExistenceEvidence {
1439    CompleteCandidatePartition,
1440}
1441
1442#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1443pub enum UniquenessEvidence {
1444    PairwiseNonOverlappingBrackets,
1445}
1446
1447#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1448pub enum WitnessUndeterminedReason {
1449    BracketSetInvalid,
1450    PartitionOrCandidatesIncomplete,
1451}
1452
1453#[derive(Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
1454pub struct RayCrossingTargetId(String);
1455
1456impl RayCrossingTargetId {
1457    pub fn new(value: impl Into<String>) -> Result<Self, GeometryFailure> {
1458        let value = value.into();
1459        if value.is_empty() {
1460            return Err(GeometryFailure::InvalidRayCrossingPolicy);
1461        }
1462        Ok(Self(value))
1463    }
1464    pub fn as_str(&self) -> &str {
1465        &self.0
1466    }
1467}
1468
1469#[derive(Debug, Eq, PartialEq)]
1470pub struct ExactTriangleTarget {
1471    pub id: RayCrossingTargetId,
1472    pub a: Point3,
1473    pub b: Point3,
1474    pub c: Point3,
1475}
1476
1477impl ExactTriangleTarget {
1478    pub fn new(
1479        id: RayCrossingTargetId,
1480        a: Point3,
1481        b: Point3,
1482        c: Point3,
1483    ) -> Result<Self, GeometryFailure> {
1484        if exact_triangle_is_degenerate(&a, &b, &c)? {
1485            return Err(GeometryFailure::DegenerateTriangle);
1486        }
1487        Ok(Self { id, a, b, c })
1488    }
1489}
1490
1491#[derive(Debug, PartialEq)]
1492pub struct CheckedTriangleTarget {
1493    pub id: RayCrossingTargetId,
1494    pub vertices: [[f64; 3]; 3],
1495    owner: OwnerId,
1496    requirement: ExactExpressionRequirement,
1497    source: NecoImplementationSource,
1498}
1499
1500impl CheckedTriangleTarget {
1501    pub fn new(
1502        id: RayCrossingTargetId,
1503        vertices: [[f64; 3]; 3],
1504        owner: OwnerId,
1505        requirement: ExactExpressionRequirement,
1506        source: NecoImplementationSource,
1507    ) -> Result<Self, GeometryFailure> {
1508        if vertices.iter().flatten().any(|value| !value.is_finite()) {
1509            return Err(GeometryFailure::DegenerateTriangle);
1510        }
1511        if checked_triangle_is_degenerate(vertices) {
1512            return Err(GeometryFailure::DegenerateTriangle);
1513        }
1514        Ok(Self {
1515            id,
1516            vertices,
1517            owner,
1518            requirement,
1519            source,
1520        })
1521    }
1522
1523    pub const fn owner(&self) -> OwnerId {
1524        self.owner
1525    }
1526
1527    pub fn requirement(&self) -> &ExactExpressionRequirement {
1528        &self.requirement
1529    }
1530
1531    pub const fn source(&self) -> NecoImplementationSource {
1532        self.source
1533    }
1534}
1535
1536fn exact_triangle_is_degenerate(
1537    a: &Point3,
1538    b: &Point3,
1539    c: &Point3,
1540) -> Result<bool, GeometryFailure> {
1541    let ab = [a.x.sub(&b.x)?, a.y.sub(&b.y)?, a.z.sub(&b.z)?];
1542    let ac = [a.x.sub(&c.x)?, a.y.sub(&c.y)?, a.z.sub(&c.z)?];
1543    let cross = [
1544        ab[1].mul(&ac[2])?.sub(&ab[2].mul(&ac[1])?)?,
1545        ab[2].mul(&ac[0])?.sub(&ab[0].mul(&ac[2])?)?,
1546        ab[0].mul(&ac[1])?.sub(&ab[1].mul(&ac[0])?)?,
1547    ];
1548    Ok(cross.iter().all(RealAlgebraic::is_zero))
1549}
1550
1551fn checked_triangle_is_degenerate(vertices: [[f64; 3]; 3]) -> bool {
1552    let ab = [
1553        vertices[1][0] - vertices[0][0],
1554        vertices[1][1] - vertices[0][1],
1555        vertices[1][2] - vertices[0][2],
1556    ];
1557    let ac = [
1558        vertices[2][0] - vertices[0][0],
1559        vertices[2][1] - vertices[0][1],
1560        vertices[2][2] - vertices[0][2],
1561    ];
1562    let cross = [
1563        ab[1] * ac[2] - ab[2] * ac[1],
1564        ab[2] * ac[0] - ab[0] * ac[2],
1565        ab[0] * ac[1] - ab[1] * ac[0],
1566    ];
1567    cross == [0.0; 3]
1568}
1569
1570#[derive(Debug, Eq, PartialEq)]
1571pub struct TrimmedParametricSurfaceTarget {
1572    id: RayCrossingTargetId,
1573    candidate: SurfaceCrossingCandidate,
1574}
1575
1576impl TrimmedParametricSurfaceTarget {
1577    pub fn new(id: RayCrossingTargetId, candidate: SurfaceCrossingCandidate) -> Self {
1578        Self { id, candidate }
1579    }
1580    pub fn id(&self) -> &RayCrossingTargetId {
1581        &self.id
1582    }
1583    pub fn candidate(&self) -> &SurfaceCrossingCandidate {
1584        &self.candidate
1585    }
1586}
1587
1588#[derive(Debug, Eq, PartialEq)]
1589pub struct CheckedTrimmedParametricSurfaceTarget {
1590    id: RayCrossingTargetId,
1591    candidate: SurfaceCrossingCandidate,
1592    owner: OwnerId,
1593    requirement: ExactExpressionRequirement,
1594    source: NecoImplementationSource,
1595}
1596
1597impl CheckedTrimmedParametricSurfaceTarget {
1598    pub fn new(
1599        id: RayCrossingTargetId,
1600        candidate: SurfaceCrossingCandidate,
1601        owner: OwnerId,
1602        requirement: ExactExpressionRequirement,
1603        source: NecoImplementationSource,
1604    ) -> Self {
1605        Self {
1606            id,
1607            candidate,
1608            owner,
1609            requirement,
1610            source,
1611        }
1612    }
1613
1614    pub fn id(&self) -> &RayCrossingTargetId {
1615        &self.id
1616    }
1617
1618    pub fn candidate(&self) -> &SurfaceCrossingCandidate {
1619        &self.candidate
1620    }
1621
1622    pub const fn owner(&self) -> OwnerId {
1623        self.owner
1624    }
1625
1626    pub fn requirement(&self) -> &ExactExpressionRequirement {
1627        &self.requirement
1628    }
1629
1630    pub const fn source(&self) -> NecoImplementationSource {
1631        self.source
1632    }
1633}
1634
1635#[derive(Debug, PartialEq)]
1636pub enum ExactRayCrossingTarget {
1637    Triangle(ExactTriangleTarget),
1638    TrimmedSurface(TrimmedParametricSurfaceTarget),
1639    ImplicitSurface {
1640        id: RayCrossingTargetId,
1641        surface: ImplicitSurfaceDeclaration,
1642    },
1643}
1644#[derive(Debug, PartialEq)]
1645pub enum CheckedRayCrossingTarget {
1646    Triangle(CheckedTriangleTarget),
1647    TrimmedSurface(Box<CheckedTrimmedParametricSurfaceTarget>),
1648}
1649
1650#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1651enum RayCrossingTargetFamily {
1652    Triangle,
1653    TrimmedSurface,
1654    ImplicitSurface,
1655}
1656
1657#[derive(Debug, PartialEq)]
1658pub struct ExactRayCrossingTargetSet(Vec<ExactRayCrossingTarget>);
1659impl ExactRayCrossingTargetSet {
1660    pub fn new(targets: Vec<ExactRayCrossingTarget>) -> Result<Self, GeometryFailure> {
1661        if targets.is_empty() {
1662            return Err(GeometryFailure::EmptyRayCrossingTargetSet);
1663        }
1664        let families = targets.iter().map(exact_target_family).collect::<Vec<_>>();
1665        if families.windows(2).any(|pair| pair[0] != pair[1]) {
1666            return Err(GeometryFailure::MixedRayCrossingTargetFamily);
1667        }
1668        let ids = targets.iter().map(exact_target_id).collect::<Vec<_>>();
1669        validate_target_ids(ids)?;
1670        Ok(Self(targets))
1671    }
1672    pub fn targets(&self) -> &[ExactRayCrossingTarget] {
1673        &self.0
1674    }
1675}
1676#[derive(Debug, PartialEq)]
1677pub struct CheckedRayCrossingTargetSet(Vec<CheckedRayCrossingTarget>);
1678impl CheckedRayCrossingTargetSet {
1679    pub fn new(targets: Vec<CheckedRayCrossingTarget>) -> Result<Self, GeometryFailure> {
1680        if targets.is_empty() {
1681            return Err(GeometryFailure::EmptyRayCrossingTargetSet);
1682        }
1683        let families = targets
1684            .iter()
1685            .map(checked_target_family)
1686            .collect::<Vec<_>>();
1687        if families.windows(2).any(|pair| pair[0] != pair[1]) {
1688            return Err(GeometryFailure::MixedRayCrossingTargetFamily);
1689        }
1690        let ids = targets.iter().map(checked_target_id).collect::<Vec<_>>();
1691        validate_target_ids(ids)?;
1692        Ok(Self(targets))
1693    }
1694    pub fn targets(&self) -> &[CheckedRayCrossingTarget] {
1695        &self.0
1696    }
1697}
1698
1699fn exact_target_family(target: &ExactRayCrossingTarget) -> RayCrossingTargetFamily {
1700    match target {
1701        ExactRayCrossingTarget::Triangle(_) => RayCrossingTargetFamily::Triangle,
1702        ExactRayCrossingTarget::TrimmedSurface(_) => RayCrossingTargetFamily::TrimmedSurface,
1703        ExactRayCrossingTarget::ImplicitSurface { .. } => RayCrossingTargetFamily::ImplicitSurface,
1704    }
1705}
1706fn checked_target_family(target: &CheckedRayCrossingTarget) -> RayCrossingTargetFamily {
1707    match target {
1708        CheckedRayCrossingTarget::Triangle(_) => RayCrossingTargetFamily::Triangle,
1709        CheckedRayCrossingTarget::TrimmedSurface(_) => RayCrossingTargetFamily::TrimmedSurface,
1710    }
1711}
1712fn exact_target_id(target: &ExactRayCrossingTarget) -> &RayCrossingTargetId {
1713    match target {
1714        ExactRayCrossingTarget::Triangle(target) => &target.id,
1715        ExactRayCrossingTarget::TrimmedSurface(target) => target.id(),
1716        ExactRayCrossingTarget::ImplicitSurface { id, .. } => id,
1717    }
1718}
1719fn checked_target_id(target: &CheckedRayCrossingTarget) -> &RayCrossingTargetId {
1720    match target {
1721        CheckedRayCrossingTarget::Triangle(target) => &target.id,
1722        CheckedRayCrossingTarget::TrimmedSurface(target) => target.id(),
1723    }
1724}
1725fn validate_target_ids(mut ids: Vec<&RayCrossingTargetId>) -> Result<(), GeometryFailure> {
1726    ids.sort_unstable();
1727    if ids.windows(2).any(|pair| pair[0] == pair[1]) {
1728        return Err(GeometryFailure::DuplicateRayCrossingTargetIdentity);
1729    }
1730    Ok(())
1731}
1732
1733#[derive(Debug, Eq, PartialEq)]
1734pub struct RayCrossingPolicy {
1735    pub root_isolation: RootIsolationPolicy,
1736    pub max_targets: NonZeroUsize,
1737    pub max_hits: NonZeroUsize,
1738}
1739impl RayCrossingPolicy {
1740    pub fn new(
1741        root_isolation: RootIsolationPolicy,
1742        max_targets: usize,
1743        max_hits: usize,
1744    ) -> Result<Self, GeometryFailure> {
1745        Ok(Self {
1746            root_isolation,
1747            max_targets: NonZeroUsize::new(max_targets)
1748                .ok_or(GeometryFailure::InvalidRayCrossingPolicy)?,
1749            max_hits: NonZeroUsize::new(max_hits)
1750                .ok_or(GeometryFailure::InvalidRayCrossingPolicy)?,
1751        })
1752    }
1753}
1754
1755#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1756pub enum RayOriginContact {
1757    None,
1758    Interior,
1759    Boundary,
1760}
1761#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1762pub enum RayCrossingLocation {
1763    Interior,
1764    TrimBoundary,
1765    HoleBoundary,
1766    Seam,
1767    Edge,
1768    Vertex,
1769}
1770#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1771pub enum CrossingMultiplicity {
1772    Simple,
1773    Odd(usize),
1774    Even(usize),
1775    Undetermined,
1776}
1777#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1778pub enum CrossingContribution {
1779    Toggle,
1780    NoToggle,
1781    Undetermined,
1782}
1783#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1784pub enum CrossingParity {
1785    Even,
1786    Odd,
1787    Undetermined,
1788}
1789#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1790pub enum RayCrossingUndeterminedReason {
1791    Edge,
1792    Vertex,
1793    TrimBoundary,
1794    HoleBoundary,
1795    DuplicateParameter,
1796    CoplanarOverlap,
1797    Coincident,
1798    InvalidMultiplicity,
1799    UnresolvedSeam,
1800    NormalIndeterminate,
1801}
1802
1803#[derive(Debug, Eq, PartialEq)]
1804pub enum RayNormal {
1805    Regular(Direction3),
1806    Undetermined,
1807}
1808
1809#[derive(Debug, Eq, PartialEq)]
1810pub struct RayCrossingHit {
1811    target_id: RayCrossingTargetId,
1812    parameter: RealAlgebraic,
1813    point: Point3,
1814    location: RayCrossingLocation,
1815    multiplicity: CrossingMultiplicity,
1816    contribution: CrossingContribution,
1817    normal: RayNormal,
1818}
1819
1820impl RayCrossingHit {
1821    pub fn new(
1822        target_id: RayCrossingTargetId,
1823        parameter: RealAlgebraic,
1824        point: Point3,
1825        location: RayCrossingLocation,
1826        multiplicity: CrossingMultiplicity,
1827        contribution: CrossingContribution,
1828        normal: RayNormal,
1829    ) -> Self {
1830        Self {
1831            target_id,
1832            parameter,
1833            point,
1834            location,
1835            multiplicity,
1836            contribution,
1837            normal,
1838        }
1839    }
1840    pub fn target_id(&self) -> &RayCrossingTargetId {
1841        &self.target_id
1842    }
1843    pub fn parameter(&self) -> &RealAlgebraic {
1844        &self.parameter
1845    }
1846    pub fn point(&self) -> &Point3 {
1847        &self.point
1848    }
1849    pub fn location(&self) -> RayCrossingLocation {
1850        self.location
1851    }
1852    pub fn multiplicity(&self) -> CrossingMultiplicity {
1853        self.multiplicity
1854    }
1855    pub fn contribution(&self) -> CrossingContribution {
1856        self.contribution
1857    }
1858
1859    pub fn normal(&self) -> &RayNormal {
1860        &self.normal
1861    }
1862}
1863
1864#[derive(Debug, PartialEq)]
1865pub struct CheckedRayCrossingHit {
1866    target_id: RayCrossingTargetId,
1867    parameter: Enclosure,
1868    point: CoordinateEnclosure3,
1869    location: RayCrossingLocation,
1870    multiplicity: CrossingMultiplicity,
1871    contribution: CrossingContribution,
1872    owner: OwnerId,
1873    requirement: ExactExpressionRequirement,
1874    source: NecoImplementationSource,
1875    normal: RayNormal,
1876}
1877
1878struct CheckedHitGeometry {
1879    location: RayCrossingLocation,
1880    multiplicity: CrossingMultiplicity,
1881    contribution: CrossingContribution,
1882    owner: OwnerId,
1883    requirement: ExactExpressionRequirement,
1884    source: NecoImplementationSource,
1885    normal: RayNormal,
1886}
1887
1888impl CheckedRayCrossingHit {
1889    fn from_exact_hit(
1890        target_id: RayCrossingTargetId,
1891        parameter: Enclosure,
1892        point: CoordinateEnclosure3,
1893        geometry: CheckedHitGeometry,
1894    ) -> Self {
1895        Self {
1896            target_id,
1897            parameter,
1898            point,
1899            location: geometry.location,
1900            multiplicity: geometry.multiplicity,
1901            contribution: geometry.contribution,
1902            owner: geometry.owner,
1903            requirement: geometry.requirement,
1904            source: geometry.source,
1905            normal: geometry.normal,
1906        }
1907    }
1908    pub fn target_id(&self) -> &RayCrossingTargetId {
1909        &self.target_id
1910    }
1911    pub fn parameter(&self) -> &Enclosure {
1912        &self.parameter
1913    }
1914    pub fn point(&self) -> &CoordinateEnclosure3 {
1915        &self.point
1916    }
1917    pub fn location(&self) -> RayCrossingLocation {
1918        self.location
1919    }
1920    pub fn multiplicity(&self) -> CrossingMultiplicity {
1921        self.multiplicity
1922    }
1923    pub fn contribution(&self) -> CrossingContribution {
1924        self.contribution
1925    }
1926    pub const fn owner(&self) -> OwnerId {
1927        self.owner
1928    }
1929
1930    pub fn requirement(&self) -> &ExactExpressionRequirement {
1931        &self.requirement
1932    }
1933
1934    pub const fn source(&self) -> NecoImplementationSource {
1935        self.source
1936    }
1937    pub fn normal(&self) -> &RayNormal {
1938        &self.normal
1939    }
1940}
1941
1942#[derive(Debug, Eq, PartialEq)]
1943pub struct RayCrossingWitness {
1944    target_count: usize,
1945    target_ids: Vec<RayCrossingTargetId>,
1946    parity: CrossingParity,
1947}
1948impl RayCrossingWitness {
1949    pub fn new(target_ids: Vec<RayCrossingTargetId>, parity: CrossingParity) -> Self {
1950        let target_count = target_ids.len();
1951        Self {
1952            target_count,
1953            target_ids,
1954            parity,
1955        }
1956    }
1957    pub fn target_count(&self) -> usize {
1958        self.target_count
1959    }
1960    pub fn target_ids(&self) -> &[RayCrossingTargetId] {
1961        &self.target_ids
1962    }
1963    pub fn parity(&self) -> CrossingParity {
1964        self.parity
1965    }
1966}
1967
1968#[derive(Debug, PartialEq)]
1969pub struct CheckedRayCrossingWitness {
1970    target_count: usize,
1971    target_ids: Vec<RayCrossingTargetId>,
1972    parity: CrossingParity,
1973}
1974impl CheckedRayCrossingWitness {
1975    pub fn new(target_ids: Vec<RayCrossingTargetId>, parity: CrossingParity) -> Self {
1976        let target_count = target_ids.len();
1977        Self {
1978            target_count,
1979            target_ids,
1980            parity,
1981        }
1982    }
1983    pub fn target_count(&self) -> usize {
1984        self.target_count
1985    }
1986    pub fn target_ids(&self) -> &[RayCrossingTargetId] {
1987        &self.target_ids
1988    }
1989    pub fn parity(&self) -> CrossingParity {
1990        self.parity
1991    }
1992}
1993#[derive(Debug, Eq, PartialEq)]
1994pub enum RayCrossingResult {
1995    Proved {
1996        origin_contact: RayOriginContact,
1997        parity: CrossingParity,
1998        hits: Vec<RayCrossingHit>,
1999        witness: RayCrossingWitness,
2000    },
2001    Undetermined {
2002        reason: RayCrossingUndeterminedReason,
2003        origin_contact: RayOriginContact,
2004        hits: Vec<RayCrossingHit>,
2005        witness: RayCrossingWitness,
2006    },
2007}
2008
2009#[derive(Debug, PartialEq)]
2010pub enum CheckedRayCrossingResult {
2011    Proved {
2012        origin_contact: RayOriginContact,
2013        parity: CrossingParity,
2014        hits: Vec<CheckedRayCrossingHit>,
2015        witness: CheckedRayCrossingWitness,
2016    },
2017    Undetermined {
2018        reason: RayCrossingUndeterminedReason,
2019        origin_contact: RayOriginContact,
2020        hits: Vec<CheckedRayCrossingHit>,
2021        witness: CheckedRayCrossingWitness,
2022    },
2023}
2024
2025pub fn cross_ray3(
2026    ray: Ray3,
2027    targets: ExactRayCrossingTargetSet,
2028    range: crate::types::PositiveRayParameterRange,
2029    policy: RayCrossingPolicy,
2030) -> Result<RayCrossingResult, GeometryFailure> {
2031    validate_policy(&policy.root_isolation)?;
2032    if targets.targets().len() > policy.max_targets.get() {
2033        return Err(GeometryFailure::RayCrossingTargetLimitExceeded);
2034    }
2035
2036    let mut origin_contact = RayOriginContact::None;
2037    let mut hits = Vec::new();
2038    let mut undetermined = None;
2039    for target in targets.targets() {
2040        match target {
2041            ExactRayCrossingTarget::Triangle(triangle) => {
2042                let evaluation = cross_exact_triangle(&ray, triangle, &range)?;
2043                origin_contact = combine_origin_contact(origin_contact, evaluation.origin_contact);
2044                if let Some(reason) = evaluation.reason {
2045                    undetermined.get_or_insert(reason);
2046                }
2047                if let Some(hit) = evaluation.hit {
2048                    hits.push(hit);
2049                }
2050            }
2051            ExactRayCrossingTarget::ImplicitSurface { id, surface } => {
2052                let evaluation =
2053                    cross_exact_implicit(&ray, id, surface, &range, &policy.root_isolation)?;
2054                origin_contact = combine_origin_contact(origin_contact, evaluation.origin_contact);
2055                if let Some(reason) = evaluation.reason {
2056                    undetermined.get_or_insert(reason);
2057                }
2058                hits.extend(evaluation.hits);
2059            }
2060            ExactRayCrossingTarget::TrimmedSurface(surface) => {
2061                let evaluation =
2062                    cross_exact_trimmed_surface(&ray, surface.id(), surface.candidate(), &range)?;
2063                origin_contact = combine_origin_contact(origin_contact, evaluation.origin_contact);
2064                if let Some(reason) = evaluation.reason {
2065                    undetermined.get_or_insert(reason);
2066                }
2067                if let Some(hit) = evaluation.hit {
2068                    hits.push(hit);
2069                }
2070            }
2071        }
2072        if hits.len() > policy.max_hits.get() {
2073            return Err(GeometryFailure::RayCrossingHitLimitExceeded);
2074        }
2075    }
2076    hits.sort_by(
2077        |left, right| match left.parameter.compare(&right.parameter) {
2078            Ok(Ordering::Equal) => left.target_id.cmp(&right.target_id),
2079            Ok(ordering) => ordering,
2080            Err(_) => Ordering::Equal,
2081        },
2082    );
2083    if hits.windows(2).any(|pair| {
2084        pair[0]
2085            .parameter
2086            .compare(&pair[1].parameter)
2087            .is_ok_and(|ordering| ordering == Ordering::Equal)
2088    }) {
2089        undetermined.get_or_insert(RayCrossingUndeterminedReason::DuplicateParameter);
2090    }
2091    let parity = if undetermined.is_some() {
2092        CrossingParity::Undetermined
2093    } else if hits
2094        .iter()
2095        .filter(|hit| hit.contribution == CrossingContribution::Toggle)
2096        .count()
2097        % 2
2098        == 0
2099    {
2100        CrossingParity::Even
2101    } else {
2102        CrossingParity::Odd
2103    };
2104    let target_ids = targets
2105        .targets()
2106        .iter()
2107        .map(exact_target_id)
2108        .map(|id| RayCrossingTargetId(id.0.clone()))
2109        .collect();
2110    let witness = RayCrossingWitness::new(target_ids, parity);
2111    Ok(match undetermined {
2112        Some(reason) => RayCrossingResult::Undetermined {
2113            reason,
2114            origin_contact,
2115            hits,
2116            witness,
2117        },
2118        None => RayCrossingResult::Proved {
2119            origin_contact,
2120            parity,
2121            hits,
2122            witness,
2123        },
2124    })
2125}
2126
2127pub fn cross_checked_ray3(
2128    ray: CheckedRay3,
2129    targets: CheckedRayCrossingTargetSet,
2130    range: crate::types::PositiveRayParameterRange,
2131    policy: RayCrossingPolicy,
2132) -> Result<CheckedRayCrossingResult, GeometryFailure> {
2133    validate_policy(&policy.root_isolation)?;
2134    if targets.targets().len() > policy.max_targets.get() {
2135        return Err(GeometryFailure::RayCrossingTargetLimitExceeded);
2136    }
2137    let exact_ray = match exact_ray_from_checked(&ray) {
2138        Some(exact_ray) => exact_ray,
2139        None => {
2140            return Ok(checked_undetermined_result(
2141                &targets,
2142                RayCrossingUndeterminedReason::InvalidMultiplicity,
2143            ));
2144        }
2145    };
2146    let mut origin_contact = RayOriginContact::None;
2147    let mut hits = Vec::new();
2148    let mut undetermined = None;
2149    for target in targets.targets() {
2150        match target {
2151            CheckedRayCrossingTarget::Triangle(triangle) => {
2152                let exact_triangle = match exact_triangle_from_checked(triangle) {
2153                    Some(exact_triangle) => exact_triangle,
2154                    None => {
2155                        undetermined
2156                            .get_or_insert(RayCrossingUndeterminedReason::InvalidMultiplicity);
2157                        continue;
2158                    }
2159                };
2160                let evaluation = cross_exact_triangle(&exact_ray, &exact_triangle, &range)?;
2161                origin_contact = combine_origin_contact(origin_contact, evaluation.origin_contact);
2162                if let Some(reason) = evaluation.reason {
2163                    undetermined.get_or_insert(reason);
2164                }
2165                if let Some(hit) = evaluation.hit {
2166                    hits.push(checked_hit_from_exact(
2167                        hit,
2168                        triangle.owner(),
2169                        clone_requirement(triangle.requirement())?,
2170                        triangle.source(),
2171                    )?);
2172                }
2173            }
2174            CheckedRayCrossingTarget::TrimmedSurface(surface) => {
2175                let evaluation = cross_exact_trimmed_surface(
2176                    &exact_ray,
2177                    surface.id(),
2178                    surface.candidate(),
2179                    &range,
2180                )?;
2181                origin_contact = combine_origin_contact(origin_contact, evaluation.origin_contact);
2182                if let Some(reason) = evaluation.reason {
2183                    undetermined.get_or_insert(reason);
2184                }
2185                if let Some(hit) = evaluation.hit {
2186                    hits.push(checked_surface_hit(hit, surface)?);
2187                }
2188            }
2189        }
2190        if hits.len() > policy.max_hits.get() {
2191            return Err(GeometryFailure::RayCrossingHitLimitExceeded);
2192        }
2193    }
2194    hits.sort_by(
2195        |left, right| match compare_enclosures(left.parameter(), right.parameter()) {
2196            Ok(ordering) => ordering.then(left.target_id().cmp(right.target_id())),
2197            Err(_) => left.target_id().cmp(right.target_id()),
2198        },
2199    );
2200    if hits
2201        .windows(2)
2202        .any(|pair| enclosures_overlap(pair[0].parameter(), pair[1].parameter()).unwrap_or(false))
2203    {
2204        undetermined.get_or_insert(RayCrossingUndeterminedReason::DuplicateParameter);
2205    }
2206    let parity = if undetermined.is_some() {
2207        CrossingParity::Undetermined
2208    } else if hits
2209        .iter()
2210        .filter(|hit| hit.contribution() == CrossingContribution::Toggle)
2211        .count()
2212        % 2
2213        == 0
2214    {
2215        CrossingParity::Even
2216    } else {
2217        CrossingParity::Odd
2218    };
2219    let target_ids = targets
2220        .targets()
2221        .iter()
2222        .map(checked_target_id)
2223        .map(|id| RayCrossingTargetId(id.0.clone()))
2224        .collect();
2225    let witness = CheckedRayCrossingWitness::new(target_ids, parity);
2226    Ok(match undetermined {
2227        Some(reason) => CheckedRayCrossingResult::Undetermined {
2228            reason,
2229            origin_contact,
2230            hits,
2231            witness,
2232        },
2233        None => CheckedRayCrossingResult::Proved {
2234            origin_contact,
2235            parity,
2236            hits,
2237            witness,
2238        },
2239    })
2240}
2241
2242struct ExactTriangleCrossing {
2243    origin_contact: RayOriginContact,
2244    hit: Option<RayCrossingHit>,
2245    reason: Option<RayCrossingUndeterminedReason>,
2246}
2247
2248struct ExactImplicitCrossing {
2249    origin_contact: RayOriginContact,
2250    hits: Vec<RayCrossingHit>,
2251    reason: Option<RayCrossingUndeterminedReason>,
2252}
2253
2254fn cross_exact_implicit(
2255    ray: &Ray3,
2256    id: &RayCrossingTargetId,
2257    surface: &ImplicitSurfaceDeclaration,
2258    range: &crate::types::PositiveRayParameterRange,
2259    policy: &RootIsolationPolicy,
2260) -> Result<ExactImplicitCrossing, GeometryFailure> {
2261    let polynomial = ray_polynomial(ray, surface)?;
2262    if polynomial.degree() == 0 {
2263        return Ok(ExactImplicitCrossing {
2264            origin_contact: RayOriginContact::None,
2265            hits: Vec::new(),
2266            reason: if polynomial.coefficients()[0].is_zero() {
2267                Some(RayCrossingUndeterminedReason::Coincident)
2268            } else {
2269                None
2270            },
2271        });
2272    }
2273
2274    let bound = isolation_bound(&polynomial)?;
2275    let domain = Enclosure::new(
2276        Dyadic::new(
2277            bound.integer().negated().map_err(map_bigint_failure)?,
2278            bound.exponent(),
2279        ),
2280        bound,
2281    )
2282    .map_err(|error| GeometryFailure::CalculusFailure {
2283        error: CalculusFailure::Interval(error),
2284    })?;
2285    let constraint = ray_constraint_positive(surface)?;
2286    let problem = DerivedRootProblem {
2287        constraint,
2288        polynomial: Some(
2289            polynomial
2290                .try_clone()
2291                .map_err(calculus_polynomial_failure)?,
2292        ),
2293        domain: Some(domain),
2294    };
2295    let candidates = enumerate_root_candidates(&problem, policy)?;
2296    let isolation = build_root_isolation(&problem, candidates, policy)?;
2297    let mut hits = Vec::new();
2298    let mut reason = None;
2299    for parameter in exact_positive_integer_roots(&polynomial)? {
2300        if !range.contains_exact(&parameter)? {
2301            continue;
2302        }
2303        let (multiplicity, contribution) = implicit_root_multiplicity(&polynomial, &parameter)?;
2304        let point = evaluate_ray_point(ray, &parameter)?;
2305        let normal = implicit_hit_normal(surface, &point)?;
2306        hits.push(RayCrossingHit::new(
2307            RayCrossingTargetId(id.0.clone()),
2308            parameter,
2309            point,
2310            RayCrossingLocation::Interior,
2311            multiplicity,
2312            contribution,
2313            normal,
2314        ));
2315    }
2316    for bracket in isolation.brackets() {
2317        let parameter = match bracket.evidence() {
2318            RootEvidence::EvenMultiplicityTouch { point, .. }
2319            | RootEvidence::HigherOrder { point, .. }
2320            | RootEvidence::SimpleRoot { point, .. } => point.try_clone()?,
2321            RootEvidence::SignChange { .. } | RootEvidence::Undetermined { .. } => {
2322                if bracket_overlaps_positive(bracket)?
2323                    && !hits.iter().any(|hit| {
2324                        hit.parameter
2325                            .compare(bracket.lower())
2326                            .is_ok_and(|ordering| ordering != Ordering::Less)
2327                            && hit
2328                                .parameter
2329                                .compare(bracket.upper())
2330                                .is_ok_and(|ordering| ordering != Ordering::Greater)
2331                    })
2332                {
2333                    reason.get_or_insert(RayCrossingUndeterminedReason::InvalidMultiplicity);
2334                }
2335                continue;
2336            }
2337        };
2338        if parameter.is_zero() || !range.contains_exact(&parameter)? {
2339            continue;
2340        }
2341        if hits.iter().any(|hit| {
2342            hit.parameter
2343                .compare(&parameter)
2344                .is_ok_and(|ordering| ordering == Ordering::Equal)
2345        }) {
2346            continue;
2347        }
2348        let point = evaluate_ray_point(ray, &parameter)?;
2349        let (multiplicity, contribution) = match bracket.evidence() {
2350            RootEvidence::SimpleRoot { .. } => {
2351                (CrossingMultiplicity::Simple, CrossingContribution::Toggle)
2352            }
2353            RootEvidence::HigherOrder { order, .. } if order % 2 == 1 => (
2354                CrossingMultiplicity::Odd(*order),
2355                CrossingContribution::Toggle,
2356            ),
2357            RootEvidence::EvenMultiplicityTouch { order, .. }
2358            | RootEvidence::HigherOrder { order, .. } => (
2359                CrossingMultiplicity::Even(*order),
2360                CrossingContribution::NoToggle,
2361            ),
2362            _ => (
2363                CrossingMultiplicity::Undetermined,
2364                CrossingContribution::Undetermined,
2365            ),
2366        };
2367        let normal = implicit_hit_normal(surface, &point)?;
2368        hits.push(RayCrossingHit::new(
2369            RayCrossingTargetId(id.0.clone()),
2370            parameter,
2371            point,
2372            RayCrossingLocation::Interior,
2373            multiplicity,
2374            contribution,
2375            normal,
2376        ));
2377    }
2378    if hits.is_empty()
2379        && matches!(
2380            isolation.completeness().status(),
2381            WitnessStatus::Undetermined { .. }
2382        )
2383    {
2384        reason.get_or_insert(RayCrossingUndeterminedReason::InvalidMultiplicity);
2385    }
2386    Ok(ExactImplicitCrossing {
2387        origin_contact: RayOriginContact::None,
2388        hits,
2389        reason,
2390    })
2391}
2392
2393fn combine_origin_contact(left: RayOriginContact, right: RayOriginContact) -> RayOriginContact {
2394    match (left, right) {
2395        (RayOriginContact::Boundary, _) | (_, RayOriginContact::Boundary) => {
2396            RayOriginContact::Boundary
2397        }
2398        (RayOriginContact::Interior, _) | (_, RayOriginContact::Interior) => {
2399            RayOriginContact::Interior
2400        }
2401        _ => RayOriginContact::None,
2402    }
2403}
2404
2405fn cross_exact_trimmed_surface(
2406    ray: &Ray3,
2407    id: &RayCrossingTargetId,
2408    candidate: &SurfaceCrossingCandidate,
2409    range: &crate::types::PositiveRayParameterRange,
2410) -> Result<ExactTriangleCrossing, GeometryFailure> {
2411    let Some(chart) = affine_chart(candidate.declaration().chart().surface())? else {
2412        return Ok(ExactTriangleCrossing {
2413            origin_contact: RayOriginContact::None,
2414            hit: None,
2415            reason: Some(RayCrossingUndeterminedReason::InvalidMultiplicity),
2416        });
2417    };
2418    let normal = cross_vector(&chart.du, &chart.dv)?;
2419    if vector_is_zero(&normal)? {
2420        return Ok(ExactTriangleCrossing {
2421            origin_contact: RayOriginContact::None,
2422            hit: None,
2423            reason: Some(RayCrossingUndeterminedReason::InvalidMultiplicity),
2424        });
2425    }
2426    let origin_offset = Vector3 {
2427        x: chart.origin.x.sub(&ray.origin().x)?,
2428        y: chart.origin.y.sub(&ray.origin().y)?,
2429        z: chart.origin.z.sub(&ray.origin().z)?,
2430    };
2431    let denominator = dot_vector(&normal, ray.direction().vector())?;
2432    let numerator = dot_vector(&normal, &origin_offset)?;
2433    if denominator.is_zero() {
2434        if !numerator.is_zero() {
2435            return Ok(ExactTriangleCrossing {
2436                origin_contact: RayOriginContact::None,
2437                hit: None,
2438                reason: None,
2439            });
2440        }
2441        let Some((u, v)) = plane_parameters(&chart, ray.origin())? else {
2442            return Ok(ExactTriangleCrossing {
2443                origin_contact: RayOriginContact::None,
2444                hit: None,
2445                reason: Some(RayCrossingUndeterminedReason::Coincident),
2446            });
2447        };
2448        let (origin_contact, reason) = surface_origin_classification(candidate, &u, &v)?;
2449        return Ok(ExactTriangleCrossing {
2450            origin_contact,
2451            hit: None,
2452            reason: reason.or(Some(RayCrossingUndeterminedReason::Coincident)),
2453        });
2454    }
2455    let parameter = numerator.div(&denominator)?;
2456    let point_on_ray = evaluate_ray_point(ray, &parameter)?;
2457    let Some((u, v)) = plane_parameters(&chart, &point_on_ray)? else {
2458        return Ok(ExactTriangleCrossing {
2459            origin_contact: RayOriginContact::None,
2460            hit: None,
2461            reason: Some(RayCrossingUndeterminedReason::InvalidMultiplicity),
2462        });
2463    };
2464    let (origin_contact, origin_reason) = if parameter.is_zero() {
2465        surface_origin_classification(candidate, &u, &v)?
2466    } else {
2467        (RayOriginContact::None, None)
2468    };
2469    if !range.contains_exact(&parameter)? {
2470        return Ok(ExactTriangleCrossing {
2471            origin_contact,
2472            hit: None,
2473            reason: origin_reason,
2474        });
2475    }
2476    if !candidate.domain().contains(&u, &v)? {
2477        return Ok(ExactTriangleCrossing {
2478            origin_contact,
2479            hit: None,
2480            reason: origin_reason,
2481        });
2482    }
2483    let (location, hit_reason) = surface_hit_classification(candidate, &u, &v)?;
2484    let Some(location) = location else {
2485        return Ok(ExactTriangleCrossing {
2486            origin_contact,
2487            hit: None,
2488            reason: origin_reason,
2489        });
2490    };
2491    let reason = origin_reason.or(hit_reason);
2492    let contribution = if reason.is_some() {
2493        CrossingContribution::Undetermined
2494    } else {
2495        CrossingContribution::Toggle
2496    };
2497    let witness = evaluate_surface_witness_exact(
2498        candidate.declaration().chart(),
2499        candidate.domain(),
2500        &u,
2501        &v,
2502    )?;
2503    let point = match witness {
2504        SurfaceEvaluationWitness::Exact { point, .. } => point,
2505        SurfaceEvaluationWitness::Certified { .. } => {
2506            return Ok(ExactTriangleCrossing {
2507                origin_contact,
2508                hit: None,
2509                reason: Some(RayCrossingUndeterminedReason::InvalidMultiplicity),
2510            });
2511        }
2512    };
2513    Ok(ExactTriangleCrossing {
2514        origin_contact,
2515        hit: Some(RayCrossingHit::new(
2516            RayCrossingTargetId(id.0.clone()),
2517            parameter,
2518            point,
2519            location,
2520            CrossingMultiplicity::Simple,
2521            contribution,
2522            ray_normal_from_vector(normal)?,
2523        )),
2524        reason,
2525    })
2526}
2527
2528struct AffineSurfaceChart {
2529    origin: Point3,
2530    du: Vector3,
2531    dv: Vector3,
2532}
2533
2534fn affine_chart(
2535    surface: &neco_calculus::RationalSurfacePolynomials,
2536) -> Result<Option<AffineSurfaceChart>, GeometryFailure> {
2537    let Some([origin_x, du_x, dv_x]) = affine_form(&surface.x)? else {
2538        return Ok(None);
2539    };
2540    let Some([origin_y, du_y, dv_y]) = affine_form(&surface.y)? else {
2541        return Ok(None);
2542    };
2543    let Some([origin_z, du_z, dv_z]) = affine_form(&surface.z)? else {
2544        return Ok(None);
2545    };
2546    Ok(Some(AffineSurfaceChart {
2547        origin: Point3 {
2548            x: origin_x,
2549            y: origin_y,
2550            z: origin_z,
2551        },
2552        du: Vector3 {
2553            x: du_x,
2554            y: du_y,
2555            z: du_z,
2556        },
2557        dv: Vector3 {
2558            x: dv_x,
2559            y: dv_y,
2560            z: dv_z,
2561        },
2562    }))
2563}
2564
2565fn affine_form(
2566    polynomial: &SurfacePolynomial,
2567) -> Result<Option<[RealAlgebraic; 3]>, GeometryFailure> {
2568    let mut constant = real_zero()?;
2569    let mut du = real_zero()?;
2570    let mut dv = real_zero()?;
2571    for term in polynomial.terms() {
2572        if term.exponent_u > 1 || term.exponent_v > 1 || term.exponent_u + term.exponent_v > 1 {
2573            return Ok(None);
2574        }
2575        let coefficient = RealAlgebraic::from_reduced_rational(&term.coefficient)
2576            .map_err(GeometryFailure::AlgebraFailure)?;
2577        match (term.exponent_u, term.exponent_v) {
2578            (0, 0) => constant = coefficient,
2579            (1, 0) => du = coefficient,
2580            (0, 1) => dv = coefficient,
2581            _ => return Ok(None),
2582        }
2583    }
2584    Ok(Some([constant, du, dv]))
2585}
2586
2587fn plane_parameters(
2588    chart: &AffineSurfaceChart,
2589    point: &Point3,
2590) -> Result<Option<(RealAlgebraic, RealAlgebraic)>, GeometryFailure> {
2591    let offset = Vector3 {
2592        x: point.x.sub(&chart.origin.x)?,
2593        y: point.y.sub(&chart.origin.y)?,
2594        z: point.z.sub(&chart.origin.z)?,
2595    };
2596    let pairs = [
2597        (&chart.du.x, &chart.dv.x, &offset.x),
2598        (&chart.du.y, &chart.dv.y, &offset.y),
2599        (&chart.du.z, &chart.dv.z, &offset.z),
2600    ];
2601    for first in 0..3 {
2602        for second in (first + 1)..3 {
2603            if let Some(values) = solve_2x2(
2604                [pairs[first].0, pairs[first].1, pairs[first].2],
2605                [pairs[second].0, pairs[second].1, pairs[second].2],
2606            )? {
2607                return Ok(Some(values));
2608            }
2609        }
2610    }
2611    Ok(None)
2612}
2613
2614fn solve_2x2(
2615    first: [&RealAlgebraic; 3],
2616    second: [&RealAlgebraic; 3],
2617) -> Result<Option<(RealAlgebraic, RealAlgebraic)>, GeometryFailure> {
2618    let det = first[0].mul(second[1])?.sub(&first[1].mul(second[0])?)?;
2619    if det.is_zero() {
2620        return Ok(None);
2621    }
2622    let u = first[2]
2623        .mul(second[1])?
2624        .sub(&first[1].mul(second[2])?)?
2625        .div(&det)?;
2626    let v = first[0]
2627        .mul(second[2])?
2628        .sub(&first[2].mul(second[0])?)?
2629        .div(&det)?;
2630    Ok(Some((u, v)))
2631}
2632
2633fn surface_origin_classification(
2634    candidate: &SurfaceCrossingCandidate,
2635    u: &RealAlgebraic,
2636    v: &RealAlgebraic,
2637) -> Result<(RayOriginContact, Option<RayCrossingUndeterminedReason>), GeometryFailure> {
2638    if !candidate.domain().contains(u, v)? {
2639        return Ok((RayOriginContact::None, None));
2640    }
2641    let (location, reason) = surface_hit_classification(candidate, u, v)?;
2642    Ok(match location {
2643        Some(RayCrossingLocation::Interior) => (RayOriginContact::Interior, reason),
2644        Some(_) => (
2645            RayOriginContact::Boundary,
2646            reason.or(Some(RayCrossingUndeterminedReason::TrimBoundary)),
2647        ),
2648        None => (RayOriginContact::None, None),
2649    })
2650}
2651
2652fn surface_hit_classification(
2653    candidate: &SurfaceCrossingCandidate,
2654    u: &RealAlgebraic,
2655    v: &RealAlgebraic,
2656) -> Result<
2657    (
2658        Option<RayCrossingLocation>,
2659        Option<RayCrossingUndeterminedReason>,
2660    ),
2661    GeometryFailure,
2662> {
2663    if let Some(reason) = unresolved_seam_reason(candidate.declaration(), u, v)? {
2664        return Ok((Some(RayCrossingLocation::Seam), Some(reason)));
2665    }
2666    if paired_seam_contains(candidate.declaration(), u, v)? {
2667        return Ok((Some(RayCrossingLocation::Interior), None));
2668    }
2669    match candidate.classify(u, v)? {
2670        TrimClassification::Outer => Ok((Some(RayCrossingLocation::Interior), None)),
2671        TrimClassification::Hole | TrimClassification::TrimExterior => Ok((None, None)),
2672        TrimClassification::TrimBoundary => {
2673            if hole_boundary_contains(candidate.declaration(), u, v)? {
2674                Ok((
2675                    Some(RayCrossingLocation::HoleBoundary),
2676                    Some(RayCrossingUndeterminedReason::HoleBoundary),
2677                ))
2678            } else {
2679                Ok((
2680                    Some(RayCrossingLocation::TrimBoundary),
2681                    Some(RayCrossingUndeterminedReason::TrimBoundary),
2682                ))
2683            }
2684        }
2685    }
2686}
2687
2688fn unresolved_seam_reason(
2689    declaration: &crate::types::TrimmedSurfaceDeclaration,
2690    u: &RealAlgebraic,
2691    v: &RealAlgebraic,
2692) -> Result<Option<RayCrossingUndeterminedReason>, GeometryFailure> {
2693    for seam in declaration.seams() {
2694        if let SeamContact::Undetermined { first, second } = seam {
2695            if parameter_equals(first.parameter(), u, v)?
2696                || parameter_equals(second.parameter(), u, v)?
2697            {
2698                return Ok(Some(RayCrossingUndeterminedReason::UnresolvedSeam));
2699            }
2700        }
2701    }
2702    Ok(None)
2703}
2704
2705fn paired_seam_contains(
2706    declaration: &crate::types::TrimmedSurfaceDeclaration,
2707    u: &RealAlgebraic,
2708    v: &RealAlgebraic,
2709) -> Result<bool, GeometryFailure> {
2710    for seam in declaration.seams() {
2711        if let SeamContact::Paired(paired) = seam {
2712            if parameter_equals(paired.first().parameter(), u, v)?
2713                || parameter_equals(paired.second().parameter(), u, v)?
2714            {
2715                return Ok(true);
2716            }
2717        }
2718    }
2719    Ok(false)
2720}
2721
2722fn hole_boundary_contains(
2723    declaration: &crate::types::TrimmedSurfaceDeclaration,
2724    u: &RealAlgebraic,
2725    v: &RealAlgebraic,
2726) -> Result<bool, GeometryFailure> {
2727    for hole in declaration.holes() {
2728        if point_on_loop(u, v, hole.vertices())? {
2729            return Ok(true);
2730        }
2731    }
2732    Ok(false)
2733}
2734
2735fn parameter_equals(
2736    point: &SurfaceParameterPoint,
2737    u: &RealAlgebraic,
2738    v: &RealAlgebraic,
2739) -> Result<bool, GeometryFailure> {
2740    Ok(point.u().compare(u)? == Ordering::Equal && point.v().compare(v)? == Ordering::Equal)
2741}
2742
2743fn vector_is_zero(vector: &Vector3) -> Result<bool, GeometryFailure> {
2744    Ok(vector.x.is_zero() && vector.y.is_zero() && vector.z.is_zero())
2745}
2746
2747fn real_zero() -> Result<RealAlgebraic, GeometryFailure> {
2748    RealAlgebraic::from_integer(BigInt::zero()).map_err(GeometryFailure::AlgebraFailure)
2749}
2750
2751fn real_abs(value: &RealAlgebraic) -> Result<RealAlgebraic, GeometryFailure> {
2752    let zero = real_zero()?;
2753    if value.compare(&zero)? == Ordering::Less {
2754        zero.sub(value).map_err(GeometryFailure::AlgebraFailure)
2755    } else {
2756        value.try_clone().map_err(GeometryFailure::AlgebraFailure)
2757    }
2758}
2759
2760fn exact_positive_integer_roots(
2761    polynomial: &Polynomial,
2762) -> Result<Vec<RealAlgebraic>, GeometryFailure> {
2763    let mut roots = Vec::new();
2764    for value in 1..=32 {
2765        let parameter =
2766            RealAlgebraic::from_integer(BigInt::try_from(value).map_err(map_bigint_failure)?)?;
2767        if polynomial
2768            .evaluate(&parameter)
2769            .map_err(calculus_polynomial_failure)?
2770            .is_zero()
2771        {
2772            roots.push(parameter);
2773        }
2774    }
2775    Ok(roots)
2776}
2777
2778fn implicit_root_multiplicity(
2779    polynomial: &Polynomial,
2780    parameter: &RealAlgebraic,
2781) -> Result<(CrossingMultiplicity, CrossingContribution), GeometryFailure> {
2782    let mut order = 1_usize;
2783    let mut current = polynomial
2784        .try_clone()
2785        .map_err(calculus_polynomial_failure)?;
2786    loop {
2787        let derivative = current
2788            .derivative(DerivativeOrder::new(1))
2789            .map_err(calculus_polynomial_failure)?;
2790        if !derivative
2791            .evaluate(parameter)
2792            .map_err(calculus_polynomial_failure)?
2793            .is_zero()
2794        {
2795            break;
2796        }
2797        order += 1;
2798        if order > 16 {
2799            return Ok((
2800                CrossingMultiplicity::Undetermined,
2801                CrossingContribution::Undetermined,
2802            ));
2803        }
2804        current = derivative;
2805    }
2806    Ok(match order {
2807        1 => (CrossingMultiplicity::Simple, CrossingContribution::Toggle),
2808        order if order % 2 == 1 => (
2809            CrossingMultiplicity::Odd(order),
2810            CrossingContribution::Toggle,
2811        ),
2812        order => (
2813            CrossingMultiplicity::Even(order),
2814            CrossingContribution::NoToggle,
2815        ),
2816    })
2817}
2818
2819fn bracket_overlaps_positive(bracket: &RootBracket) -> Result<bool, GeometryFailure> {
2820    Ok(bracket.upper().compare(&real_zero()?)? == Ordering::Greater)
2821}
2822
2823fn isolation_bound(polynomial: &Polynomial) -> Result<Dyadic, GeometryFailure> {
2824    let fallback = Dyadic::new(BigInt::try_from(1024_i32).map_err(map_bigint_failure)?, 0);
2825    let coefficients = polynomial.coefficients();
2826    let Some(degree) = coefficients.iter().rposition(|value| !value.is_zero()) else {
2827        return Ok(fallback);
2828    };
2829    let leading = real_abs(&coefficients[degree])?;
2830    if leading.is_zero() {
2831        return Ok(fallback);
2832    }
2833    let mut max_ratio = real_zero()?;
2834    for coefficient in &coefficients[..degree] {
2835        let ratio = real_abs(coefficient)?.div(&leading)?;
2836        if ratio.compare(&max_ratio)? == Ordering::Greater {
2837            max_ratio = ratio;
2838        }
2839    }
2840    let bound =
2841        RealAlgebraic::from_integer(BigInt::one().map_err(map_bigint_failure)?)?.add(&max_ratio)?;
2842    Ok(real_to_dyadic(&bound).unwrap_or(fallback))
2843}
2844
2845fn checked_undetermined_result(
2846    targets: &CheckedRayCrossingTargetSet,
2847    reason: RayCrossingUndeterminedReason,
2848) -> CheckedRayCrossingResult {
2849    let target_ids = targets
2850        .targets()
2851        .iter()
2852        .map(checked_target_id)
2853        .map(|id| RayCrossingTargetId(id.0.clone()))
2854        .collect();
2855    CheckedRayCrossingResult::Undetermined {
2856        reason,
2857        origin_contact: RayOriginContact::None,
2858        hits: Vec::new(),
2859        witness: CheckedRayCrossingWitness::new(target_ids, CrossingParity::Undetermined),
2860    }
2861}
2862
2863fn exact_ray_from_checked(ray: &CheckedRay3) -> Option<Ray3> {
2864    let origin = Point3 {
2865        x: f64_to_real(ray.origin()[0])?,
2866        y: f64_to_real(ray.origin()[1])?,
2867        z: f64_to_real(ray.origin()[2])?,
2868    };
2869    let direction = Vector3 {
2870        x: f64_to_real(ray.direction()[0])?,
2871        y: f64_to_real(ray.direction()[1])?,
2872        z: f64_to_real(ray.direction()[2])?,
2873    };
2874    Some(Ray3::new(
2875        origin,
2876        neco_geometry_foundation::Direction3::try_from_vector(direction).ok()?,
2877    ))
2878}
2879
2880fn exact_triangle_from_checked(triangle: &CheckedTriangleTarget) -> Option<ExactTriangleTarget> {
2881    ExactTriangleTarget::new(
2882        RayCrossingTargetId(triangle.id.0.clone()),
2883        Point3 {
2884            x: f64_to_real(triangle.vertices[0][0])?,
2885            y: f64_to_real(triangle.vertices[0][1])?,
2886            z: f64_to_real(triangle.vertices[0][2])?,
2887        },
2888        Point3 {
2889            x: f64_to_real(triangle.vertices[1][0])?,
2890            y: f64_to_real(triangle.vertices[1][1])?,
2891            z: f64_to_real(triangle.vertices[1][2])?,
2892        },
2893        Point3 {
2894            x: f64_to_real(triangle.vertices[2][0])?,
2895            y: f64_to_real(triangle.vertices[2][1])?,
2896            z: f64_to_real(triangle.vertices[2][2])?,
2897        },
2898    )
2899    .ok()
2900}
2901
2902fn f64_to_real(value: f64) -> Option<RealAlgebraic> {
2903    if !value.is_finite() {
2904        return None;
2905    }
2906    let integer = i32::try_from(value as i64).ok()?;
2907    if value != f64::from(integer) {
2908        return None;
2909    }
2910    RealAlgebraic::from_integer(BigInt::try_from(integer).ok()?).ok()
2911}
2912
2913fn checked_hit_from_exact(
2914    hit: RayCrossingHit,
2915    owner: OwnerId,
2916    requirement: ExactExpressionRequirement,
2917    source: NecoImplementationSource,
2918) -> Result<CheckedRayCrossingHit, GeometryFailure> {
2919    Ok(CheckedRayCrossingHit::from_exact_hit(
2920        RayCrossingTargetId(hit.target_id.0.clone()),
2921        real_to_enclosure(hit.parameter())?,
2922        CoordinateEnclosure3 {
2923            x: real_to_enclosure(&hit.point().x)?,
2924            y: real_to_enclosure(&hit.point().y)?,
2925            z: real_to_enclosure(&hit.point().z)?,
2926        },
2927        CheckedHitGeometry {
2928            location: hit.location(),
2929            multiplicity: hit.multiplicity(),
2930            contribution: hit.contribution(),
2931            owner,
2932            requirement,
2933            source,
2934            normal: hit.normal,
2935        },
2936    ))
2937}
2938
2939fn checked_surface_hit(
2940    hit: RayCrossingHit,
2941    surface: &CheckedTrimmedParametricSurfaceTarget,
2942) -> Result<CheckedRayCrossingHit, GeometryFailure> {
2943    let parameter = real_to_enclosure(hit.parameter())?;
2944    let point = match recover_checked_surface_point(&hit, surface)? {
2945        Some(point) => point,
2946        None => CoordinateEnclosure3 {
2947            x: real_to_enclosure(&hit.point().x)?,
2948            y: real_to_enclosure(&hit.point().y)?,
2949            z: real_to_enclosure(&hit.point().z)?,
2950        },
2951    };
2952    Ok(CheckedRayCrossingHit::from_exact_hit(
2953        RayCrossingTargetId(hit.target_id.0.clone()),
2954        parameter,
2955        point,
2956        CheckedHitGeometry {
2957            location: hit.location(),
2958            multiplicity: hit.multiplicity(),
2959            contribution: hit.contribution(),
2960            owner: surface.owner(),
2961            requirement: clone_requirement(surface.requirement())?,
2962            source: surface.source(),
2963            normal: hit.normal,
2964        },
2965    ))
2966}
2967
2968fn recover_checked_surface_point(
2969    hit: &RayCrossingHit,
2970    surface: &CheckedTrimmedParametricSurfaceTarget,
2971) -> Result<Option<CoordinateEnclosure3>, GeometryFailure> {
2972    let Some(chart) = affine_chart(surface.candidate().declaration().chart().surface())? else {
2973        return Ok(None);
2974    };
2975    let Some((u, v)) = plane_parameters(&chart, hit.point())? else {
2976        return Ok(None);
2977    };
2978    let u_enclosure = real_to_enclosure(&u)?;
2979    let v_enclosure = real_to_enclosure(&v)?;
2980    match evaluate_surface_witness_checked(
2981        surface.candidate().declaration().chart(),
2982        surface.candidate().domain(),
2983        &u_enclosure,
2984        &v_enclosure,
2985        surface.owner(),
2986        clone_requirement(surface.requirement())?,
2987        surface.source(),
2988    ) {
2989        Ok(SurfaceEvaluationWitness::Certified { x, y, z, .. }) => {
2990            Ok(Some(CoordinateEnclosure3 { x, y, z: *z }))
2991        }
2992        _ => Ok(None),
2993    }
2994}
2995
2996fn real_to_enclosure(value: &RealAlgebraic) -> Result<Enclosure, GeometryFailure> {
2997    let dyadic = real_to_dyadic(value)?;
2998    Enclosure::new(dyadic.try_clone().map_err(map_bigint_failure)?, dyadic).map_err(|error| {
2999        GeometryFailure::CalculusFailure {
3000            error: CalculusFailure::Interval(error),
3001        }
3002    })
3003}
3004
3005fn compare_enclosures(left: &Enclosure, right: &Enclosure) -> Result<Ordering, GeometryFailure> {
3006    dyadic_to_real(left.lower())?
3007        .compare(&dyadic_to_real(right.lower())?)
3008        .map_err(GeometryFailure::AlgebraFailure)
3009}
3010
3011fn enclosures_overlap(left: &Enclosure, right: &Enclosure) -> Result<bool, GeometryFailure> {
3012    let left_lower = dyadic_to_real(left.lower())?;
3013    let left_upper = dyadic_to_real(left.upper())?;
3014    let right_lower = dyadic_to_real(right.lower())?;
3015    let right_upper = dyadic_to_real(right.upper())?;
3016    Ok(left_lower.compare(&right_upper)? != Ordering::Greater
3017        && right_lower.compare(&left_upper)? != Ordering::Greater)
3018}
3019
3020fn cross_exact_triangle(
3021    ray: &Ray3,
3022    triangle: &ExactTriangleTarget,
3023    range: &crate::types::PositiveRayParameterRange,
3024) -> Result<ExactTriangleCrossing, GeometryFailure> {
3025    let ab = subtract_point(&triangle.b, &triangle.a)?;
3026    let ac = subtract_point(&triangle.c, &triangle.a)?;
3027    let normal = cross_vector(&ab, &ac)?;
3028    let origin_offset = subtract_point(&triangle.a, ray.origin())?;
3029    let denominator = dot_vector(&normal, ray.direction().vector())?;
3030    let numerator = dot_vector(&normal, &origin_offset)?;
3031    if denominator.is_zero() {
3032        return Ok(ExactTriangleCrossing {
3033            origin_contact: RayOriginContact::None,
3034            hit: None,
3035            reason: if numerator.is_zero() {
3036                Some(RayCrossingUndeterminedReason::CoplanarOverlap)
3037            } else {
3038                None
3039            },
3040        });
3041    }
3042    let parameter = numerator.div(&denominator)?;
3043    let point = evaluate_ray_point(ray, &parameter)?;
3044    let location = triangle_location(&point, triangle, &normal)?;
3045    let origin_location = if numerator.is_zero() {
3046        triangle_location(ray.origin(), triangle, &normal)?
3047    } else {
3048        None
3049    };
3050    let origin_contact = match origin_location {
3051        Some(RayCrossingLocation::Interior) => RayOriginContact::Interior,
3052        Some(_) => RayOriginContact::Boundary,
3053        None => RayOriginContact::None,
3054    };
3055    if !range.contains_exact(&parameter)? {
3056        return Ok(ExactTriangleCrossing {
3057            origin_contact,
3058            hit: None,
3059            reason: match origin_location {
3060                Some(RayCrossingLocation::Edge) => Some(RayCrossingUndeterminedReason::Edge),
3061                Some(RayCrossingLocation::Vertex) => Some(RayCrossingUndeterminedReason::Vertex),
3062                _ => None,
3063            },
3064        });
3065    }
3066    let Some(location) = location else {
3067        return Ok(ExactTriangleCrossing {
3068            origin_contact,
3069            hit: None,
3070            reason: match origin_location {
3071                Some(RayCrossingLocation::Edge) => Some(RayCrossingUndeterminedReason::Edge),
3072                Some(RayCrossingLocation::Vertex) => Some(RayCrossingUndeterminedReason::Vertex),
3073                _ => None,
3074            },
3075        });
3076    };
3077    let reason = match location {
3078        RayCrossingLocation::Interior => None,
3079        RayCrossingLocation::Edge => Some(RayCrossingUndeterminedReason::Edge),
3080        RayCrossingLocation::Vertex => Some(RayCrossingUndeterminedReason::Vertex),
3081        _ => Some(RayCrossingUndeterminedReason::InvalidMultiplicity),
3082    };
3083    let contribution = if reason.is_some() {
3084        CrossingContribution::Undetermined
3085    } else {
3086        CrossingContribution::Toggle
3087    };
3088    Ok(ExactTriangleCrossing {
3089        origin_contact,
3090        hit: Some(RayCrossingHit::new(
3091            RayCrossingTargetId(triangle.id.0.clone()),
3092            parameter,
3093            point,
3094            location,
3095            CrossingMultiplicity::Simple,
3096            contribution,
3097            ray_normal_from_vector(normal)?,
3098        )),
3099        reason,
3100    })
3101}
3102
3103fn ray_normal_from_vector(vector: Vector3) -> Result<RayNormal, GeometryFailure> {
3104    match Direction3::try_from_vector(vector) {
3105        Ok(direction) => Ok(RayNormal::Regular(direction)),
3106        Err(neco_geometry_foundation::GeometryFailure::ZeroDirection) => {
3107            Ok(RayNormal::Undetermined)
3108        }
3109        Err(error) => Err(GeometryFailure::FoundationFailure { error }),
3110    }
3111}
3112
3113fn implicit_hit_normal(
3114    surface: &ImplicitSurfaceDeclaration,
3115    point: &Point3,
3116) -> Result<RayNormal, GeometryFailure> {
3117    ray_normal_from_vector(implicit_gradient(surface, point)?)
3118}
3119
3120fn implicit_gradient(
3121    surface: &ImplicitSurfaceDeclaration,
3122    point: &Point3,
3123) -> Result<Vector3, GeometryFailure> {
3124    let mut components = [
3125        RealAlgebraic::from_integer(BigInt::zero())?,
3126        RealAlgebraic::from_integer(BigInt::zero())?,
3127        RealAlgebraic::from_integer(BigInt::zero())?,
3128    ];
3129    for term in surface.equation().terms() {
3130        let values = [&point.x, &point.y, &point.z];
3131        let exponents = [term.exponent_x(), term.exponent_y(), term.exponent_z()];
3132        for component in 0..3 {
3133            if exponents[component] == 0 {
3134                continue;
3135            }
3136            let mut value = term.coefficient().try_clone()?;
3137            value = value.mul(&RealAlgebraic::from_integer(
3138                BigInt::try_from(exponents[component]).map_err(map_bigint_failure)?,
3139            )?)?;
3140            for axis in 0..3 {
3141                let power = if axis == component {
3142                    exponents[axis] - 1
3143                } else {
3144                    exponents[axis]
3145                };
3146                for _ in 0..power {
3147                    value = value.mul(values[axis])?;
3148                }
3149            }
3150            components[component] = components[component].add(&value)?;
3151        }
3152    }
3153    Ok(Vector3 {
3154        x: components[0].try_clone()?,
3155        y: components[1].try_clone()?,
3156        z: components[2].try_clone()?,
3157    })
3158}
3159
3160fn subtract_point(left: &Point3, right: &Point3) -> Result<Vector3, GeometryFailure> {
3161    Ok(Vector3 {
3162        x: left.x.sub(&right.x)?,
3163        y: left.y.sub(&right.y)?,
3164        z: left.z.sub(&right.z)?,
3165    })
3166}
3167
3168fn cross_vector(left: &Vector3, right: &Vector3) -> Result<Vector3, GeometryFailure> {
3169    Ok(Vector3 {
3170        x: left.y.mul(&right.z)?.sub(&left.z.mul(&right.y)?)?,
3171        y: left.z.mul(&right.x)?.sub(&left.x.mul(&right.z)?)?,
3172        z: left.x.mul(&right.y)?.sub(&left.y.mul(&right.x)?)?,
3173    })
3174}
3175
3176fn dot_vector(left: &Vector3, right: &Vector3) -> Result<RealAlgebraic, GeometryFailure> {
3177    Ok(left
3178        .x
3179        .mul(&right.x)?
3180        .add(&left.y.mul(&right.y)?)?
3181        .add(&left.z.mul(&right.z)?)?)
3182}
3183
3184fn triangle_location(
3185    point: &Point3,
3186    triangle: &ExactTriangleTarget,
3187    normal: &Vector3,
3188) -> Result<Option<RayCrossingLocation>, GeometryFailure> {
3189    let pa = subtract_point(&triangle.a, point)?;
3190    let pb = subtract_point(&triangle.b, point)?;
3191    let pc = subtract_point(&triangle.c, point)?;
3192    let a = dot_vector(normal, &cross_vector(&pb, &pc)?)?;
3193    let b = dot_vector(normal, &cross_vector(&pc, &pa)?)?;
3194    let c = dot_vector(normal, &cross_vector(&pa, &pb)?)?;
3195    let signs = [a, b, c];
3196    let zero = real_zero()?;
3197    let positive = signs
3198        .iter()
3199        .filter(|value| value.compare(&zero).is_ok_and(|v| v == Ordering::Greater))
3200        .count();
3201    let negative = signs
3202        .iter()
3203        .filter(|value| value.compare(&zero).is_ok_and(|v| v == Ordering::Less))
3204        .count();
3205    if positive != 0 && negative != 0 {
3206        return Ok(None);
3207    }
3208    let zeroes = signs.iter().filter(|value| value.is_zero()).count();
3209    Ok(Some(match zeroes {
3210        0 => RayCrossingLocation::Interior,
3211        1 => RayCrossingLocation::Edge,
3212        _ => RayCrossingLocation::Vertex,
3213    }))
3214}
3215
3216fn ray_polynomial(
3217    ray: &Ray3,
3218    surface: &ImplicitSurfaceDeclaration,
3219) -> Result<Polynomial, GeometryFailure> {
3220    let mut result = Polynomial::zero().map_err(calculus_polynomial_failure)?;
3221    for term in surface.equation().terms() {
3222        let x = affine_polynomial(
3223            &ray.origin().x,
3224            &ray.direction().vector().x,
3225            term.exponent_x(),
3226        )?;
3227        let y = affine_polynomial(
3228            &ray.origin().y,
3229            &ray.direction().vector().y,
3230            term.exponent_y(),
3231        )?;
3232        let z = affine_polynomial(
3233            &ray.origin().z,
3234            &ray.direction().vector().z,
3235            term.exponent_z(),
3236        )?;
3237        let term_polynomial = polynomial_mul(&polynomial_mul(&x, &y)?, &z)?;
3238        let coefficient = term.coefficient().try_clone()?;
3239        let scaled = term_polynomial
3240            .coefficients()
3241            .iter()
3242            .map(|value| {
3243                value
3244                    .mul(&coefficient)
3245                    .map_err(GeometryFailure::AlgebraFailure)
3246            })
3247            .collect::<Result<Vec<_>, _>>()?;
3248        result = polynomial_add(
3249            &result,
3250            &Polynomial::from_coefficients(scaled).map_err(calculus_polynomial_failure)?,
3251        )?;
3252    }
3253    Ok(result)
3254}
3255
3256fn polynomial_add(left: &Polynomial, right: &Polynomial) -> Result<Polynomial, GeometryFailure> {
3257    let length = left.coefficients().len().max(right.coefficients().len());
3258    let zero = RealAlgebraic::from_integer(BigInt::zero())?;
3259    let mut coefficients = Vec::with_capacity(length);
3260    for index in 0..length {
3261        let lhs = left.coefficients().get(index).unwrap_or(&zero);
3262        let rhs = right.coefficients().get(index).unwrap_or(&zero);
3263        coefficients.push(lhs.add(rhs)?);
3264    }
3265    Polynomial::from_coefficients(coefficients).map_err(calculus_polynomial_failure)
3266}
3267
3268fn polynomial_mul(left: &Polynomial, right: &Polynomial) -> Result<Polynomial, GeometryFailure> {
3269    let mut coefficients = Vec::with_capacity(left.degree() + right.degree() + 1);
3270    for _ in 0..=left.degree() + right.degree() {
3271        coefficients.push(RealAlgebraic::from_integer(BigInt::zero())?);
3272    }
3273    for (left_index, lhs) in left.coefficients().iter().enumerate() {
3274        for (right_index, rhs) in right.coefficients().iter().enumerate() {
3275            let product = lhs.mul(rhs)?;
3276            coefficients[left_index + right_index] =
3277                coefficients[left_index + right_index].add(&product)?;
3278        }
3279    }
3280    Polynomial::from_coefficients(coefficients).map_err(calculus_polynomial_failure)
3281}
3282
3283fn affine_polynomial(
3284    origin: &RealAlgebraic,
3285    direction: &RealAlgebraic,
3286    exponent: u32,
3287) -> Result<Polynomial, GeometryFailure> {
3288    let mut result = Polynomial::constant(RealAlgebraic::from_integer(
3289        BigInt::one().map_err(map_bigint_failure)?,
3290    )?)
3291    .map_err(calculus_polynomial_failure)?;
3292    let affine =
3293        Polynomial::from_coefficients(alloc::vec![origin.try_clone()?, direction.try_clone()?])
3294            .map_err(calculus_polynomial_failure)?;
3295    for _ in 0..exponent {
3296        result = polynomial_mul(&result, &affine)?;
3297    }
3298    Ok(result)
3299}
3300
3301fn ray_constraint_positive(
3302    surface: &ImplicitSurfaceDeclaration,
3303) -> Result<IntersectionConstraint, GeometryFailure> {
3304    let declaration = ShapeDeclaration::ImplicitSurface(ImplicitSurfaceDeclaration::new(
3305        clone_polynomial3(surface.equation())?,
3306    ));
3307    let left = clone_declaration(&declaration)?;
3308    Ok(IntersectionConstraint::new(
3309        IntersectionOperand::Declaration(left),
3310        IntersectionOperand::Declaration(declaration),
3311        ResidualFunction::new(String::from("ray implicit"), String::from("0")),
3312        IntersectionDomain::new(
3313            String::from("ray-parameter"),
3314            String::from("0 < t < +infinity"),
3315            String::from("ray"),
3316        ),
3317        SupportRelation::Finite {
3318            evidence: SupportEvidence::ImplicitSupportPair,
3319        },
3320        RankEvidence::Sufficient { rank: 0 },
3321    ))
3322}
3323
3324fn evaluate_ray_point(ray: &Ray3, parameter: &RealAlgebraic) -> Result<Point3, GeometryFailure> {
3325    Ok(Point3 {
3326        x: ray
3327            .origin()
3328            .x
3329            .add(&ray.direction().vector().x.mul(parameter)?)?,
3330        y: ray
3331            .origin()
3332            .y
3333            .add(&ray.direction().vector().y.mul(parameter)?)?,
3334        z: ray
3335            .origin()
3336            .z
3337            .add(&ray.direction().vector().z.mul(parameter)?)?,
3338    })
3339}
3340
3341pub fn construct_intersection(
3342    request: IntersectionConstructionRequest,
3343) -> Result<IntersectionSet, GeometryFailure> {
3344    let body = request.into_body();
3345    let IntersectionConstructionRequestBody {
3346        left_operand,
3347        right_operand,
3348        root_isolation_policy,
3349    } = body;
3350    validate_policy(&root_isolation_policy)?;
3351
3352    let left_descriptor = resolve_operand(&left_operand)?;
3353    let right_descriptor = resolve_operand(&right_operand)?;
3354    let problem = derive_intersection_constraint(
3355        left_operand,
3356        right_operand,
3357        left_descriptor,
3358        right_descriptor,
3359    )?;
3360    let candidates = enumerate_root_candidates(&problem, &root_isolation_policy)?;
3361    let isolation = build_root_isolation(&problem, candidates, &root_isolation_policy)?;
3362    classify_constraint(problem, &isolation)
3363}
3364
3365fn validate_policy(policy: &RootIsolationPolicy) -> Result<(), GeometryFailure> {
3366    if policy.max_iterations == 0 || policy.max_cells == 0 {
3367        return Err(GeometryFailure::RootIsolationPolicyInvalid);
3368    }
3369    if policy.max_iterations > MAX_ROOT_PARTITION_DEPTH {
3370        return Err(GeometryFailure::RootIsolationResourceLimit {
3371            requested_depth: policy.max_iterations,
3372            maximum_depth: MAX_ROOT_PARTITION_DEPTH,
3373        });
3374    }
3375    if policy.max_cells > MAX_ROOT_PARTITION_CELLS {
3376        return Err(GeometryFailure::RootPartitionCellLimit {
3377            requested_cells: policy.max_cells,
3378            maximum_cells: MAX_ROOT_PARTITION_CELLS,
3379        });
3380    }
3381    Ok(())
3382}
3383
3384fn resolve_operand(operand: &IntersectionOperand) -> Result<OperandDescriptor, GeometryFailure> {
3385    match operand {
3386        IntersectionOperand::Declaration(declaration) => {
3387            let evaluation = evaluate_declaration_capability(declaration)?;
3388            descriptor_from_declaration(declaration, evaluation)
3389        }
3390        IntersectionOperand::Evaluated(evaluation) => descriptor_from_evaluation(evaluation),
3391    }
3392}
3393
3394fn derive_intersection_constraint(
3395    left_operand: IntersectionOperand,
3396    right_operand: IntersectionOperand,
3397    left: OperandDescriptor,
3398    right: OperandDescriptor,
3399) -> Result<DerivedRootProblem, GeometryFailure> {
3400    let residual_function =
3401        ResidualFunction::new(left.expression.clone(), right.expression.clone());
3402    let support = derive_support_relation(&left, &right);
3403    let rank = derive_rank_evidence(&left, &right, &support);
3404    let domain = IntersectionDomain::new(
3405        format!("{} x {}", left.chart_id, right.chart_id),
3406        format!("{} ∩ {}", left.domain, right.domain),
3407        format!("{} <> {}", left.support_id, right.support_id),
3408    );
3409    let polynomial = derive_residual_polynomial(&left, &right)?;
3410    let numeric_domain = derive_numeric_domain(&left, &right)?;
3411    let constraint = IntersectionConstraint::new(
3412        left_operand,
3413        right_operand,
3414        residual_function,
3415        domain,
3416        support,
3417        rank,
3418    );
3419    Ok(DerivedRootProblem {
3420        constraint,
3421        polynomial,
3422        domain: numeric_domain,
3423    })
3424}
3425
3426fn enumerate_root_candidates(
3427    problem: &DerivedRootProblem,
3428    policy: &RootIsolationPolicy,
3429) -> Result<RootCandidateSet, GeometryFailure> {
3430    let Some(polynomial) = problem.polynomial.as_ref() else {
3431        return Ok(RootEnumeration::incomplete(problem.domain.as_ref()));
3432    };
3433    let Some(domain) = problem.domain.as_ref() else {
3434        return Ok(RootEnumeration::incomplete(None));
3435    };
3436
3437    if polynomial.coefficients().iter().all(RealAlgebraic::is_zero)
3438        && matches!(
3439            problem.constraint.support_relation(),
3440            SupportRelation::Coincident { .. }
3441        )
3442    {
3443        return Ok(RootEnumeration {
3444            candidates: Vec::new(),
3445            cells: vec![PartitionCell {
3446                id: 0,
3447                depth: 0,
3448                enclosure: clone_enclosure(domain)?,
3449                disposition: CellDisposition::Coincident,
3450            }],
3451        });
3452    }
3453
3454    let source = problem.constraint.residual_function().combined_expression();
3455    let order_bound = DerivativeOrder::new(policy.max_iterations.max(2));
3456    let derivative = polynomial
3457        .derivative(DerivativeOrder::new(1))
3458        .map_err(calculus_polynomial_failure)?;
3459    let mut pending = vec![PendingPartitionCell {
3460        id: 0,
3461        depth: 0,
3462        enclosure: clone_enclosure(domain)?,
3463        suppressed_exact_endpoints: Vec::new(),
3464    }];
3465    let mut next_cell_id = 1;
3466    let mut cells = Vec::new();
3467    let mut candidates = Vec::new();
3468
3469    while let Some(PendingPartitionCell {
3470        id: cell_id,
3471        depth,
3472        enclosure,
3473        suppressed_exact_endpoints,
3474    }) = pending.pop()
3475    {
3476        match assess_partition_cell(
3477            polynomial,
3478            &derivative,
3479            &enclosure,
3480            cell_id,
3481            &order_bound,
3482            source,
3483            &suppressed_exact_endpoints,
3484        )? {
3485            CellAssessment::ExactTouch { candidate, pivot } => {
3486                cells.push(PartitionCell {
3487                    id: cell_id,
3488                    depth,
3489                    enclosure: clone_enclosure(&enclosure)?,
3490                    disposition: CellDisposition::Candidate,
3491                });
3492                let pivot_exhausts_polynomial =
3493                    exact_touch_exhausts_polynomial(&candidate, polynomial);
3494                let pivot_is_unresolved =
3495                    matches!(&candidate.bracket, RootCandidateBracket::Unresolved { .. });
3496                candidates.push(*candidate);
3497                if pivot_exhausts_polynomial || pivot_is_unresolved {
3498                    continue;
3499                }
3500
3501                let has_lower_child = pivot != *enclosure.lower();
3502                let has_upper_child = pivot != *enclosure.upper();
3503                ensure_partition_cell_capacity(
3504                    cells.len(),
3505                    pending.len(),
3506                    usize::from(has_lower_child) + usize::from(has_upper_child),
3507                    policy.max_cells,
3508                )?;
3509                if has_lower_child {
3510                    let lower = Enclosure::new(
3511                        enclosure.lower().try_clone().map_err(map_bigint_failure)?,
3512                        pivot.try_clone().map_err(map_bigint_failure)?,
3513                    )
3514                    .map_err(|error| GeometryFailure::CalculusFailure {
3515                        error: CalculusFailure::Interval(error),
3516                    })?;
3517                    let lower_id = take_partition_cell_id(&mut next_cell_id)?;
3518                    pending.push(PendingPartitionCell {
3519                        id: lower_id,
3520                        depth: depth + 1,
3521                        suppressed_exact_endpoints: suppressed_endpoints_for_child(
3522                            &suppressed_exact_endpoints,
3523                            lower.lower(),
3524                            lower.upper(),
3525                            &pivot,
3526                        )?,
3527                        enclosure: lower,
3528                    });
3529                }
3530                if has_upper_child {
3531                    let upper = Enclosure::new(
3532                        pivot.try_clone().map_err(map_bigint_failure)?,
3533                        enclosure.upper().try_clone().map_err(map_bigint_failure)?,
3534                    )
3535                    .map_err(|error| GeometryFailure::CalculusFailure {
3536                        error: CalculusFailure::Interval(error),
3537                    })?;
3538                    let upper_id = take_partition_cell_id(&mut next_cell_id)?;
3539                    pending.push(PendingPartitionCell {
3540                        id: upper_id,
3541                        depth: depth + 1,
3542                        suppressed_exact_endpoints: suppressed_endpoints_for_child(
3543                            &suppressed_exact_endpoints,
3544                            upper.lower(),
3545                            upper.upper(),
3546                            &pivot,
3547                        )?,
3548                        enclosure: upper,
3549                    });
3550                }
3551            }
3552            CellAssessment::Candidate(cell_candidates) => {
3553                cells.push(PartitionCell {
3554                    id: cell_id,
3555                    depth,
3556                    enclosure,
3557                    disposition: CellDisposition::Candidate,
3558                });
3559                candidates.extend(cell_candidates);
3560            }
3561            CellAssessment::RootFree => cells.push(PartitionCell {
3562                id: cell_id,
3563                depth,
3564                enclosure,
3565                disposition: CellDisposition::RootFree,
3566            }),
3567            CellAssessment::Unresolved(reason) if depth < policy.max_iterations => {
3568                let midpoint =
3569                    enclosure
3570                        .midpoint()
3571                        .map_err(|error| GeometryFailure::CalculusFailure {
3572                            error: CalculusFailure::Interval(error),
3573                        })?;
3574                if midpoint == *enclosure.lower() || midpoint == *enclosure.upper() {
3575                    cells.push(PartitionCell {
3576                        id: cell_id,
3577                        depth,
3578                        enclosure,
3579                        disposition: CellDisposition::Unresolved { reason },
3580                    });
3581                    continue;
3582                }
3583                ensure_partition_cell_capacity(cells.len(), pending.len(), 2, policy.max_cells)?;
3584                let lower_id = take_partition_cell_id(&mut next_cell_id)?;
3585                let upper_id = take_partition_cell_id(&mut next_cell_id)?;
3586                let lower = Enclosure::new(
3587                    enclosure.lower().try_clone().map_err(map_bigint_failure)?,
3588                    midpoint.try_clone().map_err(map_bigint_failure)?,
3589                )
3590                .map_err(|error| GeometryFailure::CalculusFailure {
3591                    error: CalculusFailure::Interval(error),
3592                })?;
3593                let upper = Enclosure::new(
3594                    midpoint,
3595                    enclosure.upper().try_clone().map_err(map_bigint_failure)?,
3596                )
3597                .map_err(|error| GeometryFailure::CalculusFailure {
3598                    error: CalculusFailure::Interval(error),
3599                })?;
3600                let lower_suppressed = inherited_suppressed_endpoints(
3601                    &suppressed_exact_endpoints,
3602                    lower.lower(),
3603                    lower.upper(),
3604                )?;
3605                let upper_suppressed = inherited_suppressed_endpoints(
3606                    &suppressed_exact_endpoints,
3607                    upper.lower(),
3608                    upper.upper(),
3609                )?;
3610                pending.push(PendingPartitionCell {
3611                    id: upper_id,
3612                    depth: depth + 1,
3613                    enclosure: upper,
3614                    suppressed_exact_endpoints: upper_suppressed,
3615                });
3616                pending.push(PendingPartitionCell {
3617                    id: lower_id,
3618                    depth: depth + 1,
3619                    enclosure: lower,
3620                    suppressed_exact_endpoints: lower_suppressed,
3621                });
3622            }
3623            CellAssessment::Unresolved(reason) => cells.push(PartitionCell {
3624                id: cell_id,
3625                depth,
3626                enclosure,
3627                disposition: CellDisposition::Unresolved { reason },
3628            }),
3629        }
3630    }
3631
3632    Ok(RootEnumeration { candidates, cells })
3633}
3634
3635fn exact_touch_exhausts_polynomial(candidate: &RootCandidate, polynomial: &Polynomial) -> bool {
3636    let order = match candidate.evidence {
3637        RootEvidence::EvenMultiplicityTouch { order, .. }
3638        | RootEvidence::HigherOrder { order, .. } => order,
3639        RootEvidence::SignChange { .. }
3640        | RootEvidence::SimpleRoot { .. }
3641        | RootEvidence::Undetermined { .. } => return false,
3642    };
3643    order >= polynomial.coefficients().len().saturating_sub(1)
3644}
3645
3646fn inherited_suppressed_endpoints(
3647    inherited: &[Dyadic],
3648    lower: &Dyadic,
3649    upper: &Dyadic,
3650) -> Result<Vec<Dyadic>, GeometryFailure> {
3651    inherited
3652        .iter()
3653        .filter(|point| *point == lower || *point == upper)
3654        .map(|point| point.try_clone().map_err(map_bigint_failure))
3655        .collect()
3656}
3657
3658fn suppressed_endpoints_for_child(
3659    inherited: &[Dyadic],
3660    lower: &Dyadic,
3661    upper: &Dyadic,
3662    pivot: &Dyadic,
3663) -> Result<Vec<Dyadic>, GeometryFailure> {
3664    let mut endpoints = inherited_suppressed_endpoints(inherited, lower, upper)?;
3665    if !endpoints.iter().any(|point| point == pivot) {
3666        endpoints.push(pivot.try_clone().map_err(map_bigint_failure)?);
3667    }
3668    Ok(endpoints)
3669}
3670
3671fn assess_partition_cell(
3672    polynomial: &Polynomial,
3673    derivative: &Polynomial,
3674    enclosure: &Enclosure,
3675    cell_id: PartitionCellId,
3676    order_bound: &DerivativeOrder,
3677    source: &str,
3678    suppressed_exact_endpoints: &[Dyadic],
3679) -> Result<CellAssessment, GeometryFailure> {
3680    let lower_sign = polynomial
3681        .evaluate(&dyadic_to_real(enclosure.lower())?)
3682        .map_err(calculus_polynomial_failure)?
3683        .sign()
3684        .map_err(GeometryFailure::AlgebraFailure)?;
3685    let upper_sign = polynomial
3686        .evaluate(&dyadic_to_real(enclosure.upper())?)
3687        .map_err(calculus_polynomial_failure)?
3688        .sign()
3689        .map_err(GeometryFailure::AlgebraFailure)?;
3690    let midpoint = enclosure
3691        .midpoint()
3692        .map_err(|error| GeometryFailure::CalculusFailure {
3693            error: CalculusFailure::Interval(error),
3694        })?;
3695    let midpoint_sign = polynomial
3696        .evaluate(&dyadic_to_real(&midpoint)?)
3697        .map_err(calculus_polynomial_failure)?
3698        .sign()
3699        .map_err(GeometryFailure::AlgebraFailure)?;
3700
3701    let mut exact_points = Vec::new();
3702    if lower_sign == Sign::Zero
3703        && !suppressed_exact_endpoints
3704            .iter()
3705            .any(|point| point == enclosure.lower())
3706    {
3707        exact_points.push(enclosure.lower().try_clone().map_err(map_bigint_failure)?);
3708    }
3709    if upper_sign == Sign::Zero
3710        && enclosure.upper() != enclosure.lower()
3711        && !suppressed_exact_endpoints
3712            .iter()
3713            .any(|point| point == enclosure.upper())
3714    {
3715        exact_points.push(enclosure.upper().try_clone().map_err(map_bigint_failure)?);
3716    }
3717    if midpoint_sign == Sign::Zero && !exact_points.iter().any(|point| point == &midpoint) {
3718        exact_points.push(midpoint.try_clone().map_err(map_bigint_failure)?);
3719    }
3720
3721    if exact_points.len() > 1 {
3722        return Ok(CellAssessment::Unresolved(
3723            PartitionUnresolvedReason::MultipleExactDyadicRoots,
3724        ));
3725    }
3726    if let Some(pivot) = exact_points.into_iter().next() {
3727        let candidate = exact_touch_candidate(
3728            polynomial,
3729            enclosure,
3730            pivot.try_clone().map_err(map_bigint_failure)?,
3731            cell_id,
3732            order_bound,
3733            source,
3734        )?;
3735        return Ok(CellAssessment::ExactTouch {
3736            candidate: Box::new(candidate),
3737            pivot,
3738        });
3739    }
3740
3741    if opposite_nonzero(lower_sign, upper_sign) {
3742        let derivative_enclosure = derivative
3743            .evaluate_enclosure(enclosure, ROOT_INTERVAL_PRECISION_BITS)
3744            .map_err(calculus_polynomial_failure)?;
3745        if derivative_enclosure.contains_zero() {
3746            return Ok(CellAssessment::Unresolved(
3747                PartitionUnresolvedReason::SignChangeUniqueness,
3748            ));
3749        }
3750        let calculus_bracket = CalculusRootBracket::sign_change(
3751            polynomial
3752                .try_clone()
3753                .map_err(calculus_polynomial_failure)?,
3754            clone_enclosure(enclosure)?,
3755        )
3756        .map_err(|error| GeometryFailure::CalculusFailure {
3757            error: CalculusFailure::Root(error),
3758        })?;
3759        return Ok(CellAssessment::Candidate(vec![RootCandidate {
3760            bracket: RootCandidateBracket::Certified(calculus_bracket),
3761            evidence: RootEvidence::SignChange {
3762                lower_sign: root_sign(lower_sign),
3763                upper_sign: root_sign(upper_sign),
3764                derivative_enclosure,
3765                source: ResidualSourceId::new(source),
3766            },
3767            source_cell: cell_id,
3768        }]));
3769    }
3770
3771    let value_enclosure = polynomial
3772        .evaluate_enclosure(enclosure, ROOT_INTERVAL_PRECISION_BITS)
3773        .map_err(calculus_polynomial_failure)?;
3774    if !value_enclosure.contains_zero() {
3775        return Ok(CellAssessment::RootFree);
3776    }
3777    Ok(CellAssessment::Unresolved(
3778        PartitionUnresolvedReason::UncertifiedRoot,
3779    ))
3780}
3781
3782fn exact_touch_candidate(
3783    polynomial: &Polynomial,
3784    enclosure: &Enclosure,
3785    point: Dyadic,
3786    cell_id: PartitionCellId,
3787    order_bound: &DerivativeOrder,
3788    source: &str,
3789) -> Result<RootCandidate, GeometryFailure> {
3790    let multiplicity = match neco_calculus::classify_multiplicity(polynomial, &point, *order_bound)
3791    {
3792        Ok(multiplicity) => multiplicity,
3793        Err(error) if root_failure_is_undetermined(&error) => {
3794            return Ok(RootCandidate {
3795                bracket: RootCandidateBracket::Unresolved {
3796                    enclosure: clone_enclosure(enclosure)?,
3797                },
3798                evidence: RootEvidence::Undetermined {
3799                    reason: RootUndeterminedReason::ExactMultiplicityUnavailable,
3800                    source: ResidualSourceId::new(source),
3801                },
3802                source_cell: cell_id,
3803            });
3804        }
3805        Err(error) => {
3806            return Err(GeometryFailure::CalculusFailure {
3807                error: CalculusFailure::Root(error),
3808            });
3809        }
3810    };
3811    let point = dyadic_to_real(&point)?;
3812    let order = match multiplicity {
3813        RootMultiplicity::Multiple(value) => value.get(),
3814        RootMultiplicity::Simple => 1,
3815    };
3816    let evidence = if order == 1 {
3817        RootEvidence::SimpleRoot {
3818            point: point.try_clone()?,
3819            source: ResidualSourceId::new(source),
3820        }
3821    } else if order > 2 {
3822        RootEvidence::HigherOrder {
3823            order,
3824            point: point.try_clone()?,
3825            source: ResidualSourceId::new(source),
3826        }
3827    } else {
3828        RootEvidence::EvenMultiplicityTouch {
3829            order,
3830            point: point.try_clone()?,
3831            source: ResidualSourceId::new(source),
3832        }
3833    };
3834    Ok(RootCandidate {
3835        bracket: RootCandidateBracket::Exact { parameter: point },
3836        evidence,
3837        source_cell: cell_id,
3838    })
3839}
3840
3841fn root_failure_is_undetermined(error: &neco_calculus::RootFailure) -> bool {
3842    matches!(
3843        error,
3844        neco_calculus::RootFailure::NoRootAtPoint
3845            | neco_calculus::RootFailure::NoEvenMultiplicityTouch
3846            | neco_calculus::RootFailure::MultiplicityUndetermined
3847            | neco_calculus::RootFailure::PointOutsideEnclosure
3848    )
3849}
3850
3851fn build_root_isolation(
3852    problem: &DerivedRootProblem,
3853    candidates: RootCandidateSet,
3854    policy: &RootIsolationPolicy,
3855) -> Result<RootIsolation, GeometryFailure> {
3856    let RootEnumeration { candidates, cells } = candidates;
3857    let mut candidate_brackets = Vec::new();
3858    let mut unresolved_candidate = false;
3859    for candidate in candidates {
3860        let source_cell = candidate.source_cell;
3861        let bracket = match candidate.bracket {
3862            RootCandidateBracket::Exact { parameter } => {
3863                RootBracket::from_exact(parameter, candidate.evidence, policy)?
3864            }
3865            RootCandidateBracket::Certified(calculus_bracket) => {
3866                let calculus_isolation = refine_root(&calculus_bracket, policy)?;
3867                RootBracket::from_calculus(
3868                    &calculus_bracket,
3869                    &calculus_isolation,
3870                    candidate.evidence,
3871                )?
3872            }
3873            RootCandidateBracket::Unresolved { enclosure } => {
3874                unresolved_candidate = true;
3875                RootBracket::from_unresolved(&enclosure, candidate.evidence, policy)?
3876            }
3877        };
3878        candidate_brackets.push((source_cell, bracket));
3879    }
3880    let candidate_cell_ids: Vec<_> = cells
3881        .iter()
3882        .filter(|cell| matches!(cell.disposition, CellDisposition::Candidate))
3883        .map(|cell| cell.id)
3884        .collect();
3885    let candidate_source_cells: Vec<_> = candidate_brackets
3886        .iter()
3887        .map(|(source_cell, _)| *source_cell)
3888        .collect();
3889    let candidate_brackets_match = candidate_cell_ids.len() == candidate_brackets.len()
3890        && candidate_cell_ids.iter().all(|cell_id| {
3891            candidate_source_cells
3892                .iter()
3893                .filter(|source_cell| **source_cell == *cell_id)
3894                .count()
3895                == 1
3896        })
3897        && candidate_source_cells.iter().all(|source_cell| {
3898            candidate_cell_ids
3899                .iter()
3900                .any(|cell_id| cell_id == source_cell)
3901        });
3902    let duplicate_candidate = candidate_source_cells
3903        .iter()
3904        .enumerate()
3905        .any(|(index, cell_id)| {
3906            candidate_source_cells[..index]
3907                .iter()
3908                .any(|previous| previous == cell_id)
3909        });
3910    let mut ordering_failed = false;
3911    candidate_brackets.sort_by(
3912        |(_, left), (_, right)| match left.lower().compare(right.lower()) {
3913            Ok(ordering) => ordering,
3914            Err(_) => {
3915                ordering_failed = true;
3916                Ordering::Equal
3917            }
3918        },
3919    );
3920
3921    let mut overlap = false;
3922    let mut outside_domain = false;
3923    let brackets: Vec<_> = candidate_brackets
3924        .into_iter()
3925        .map(|(_, bracket)| bracket)
3926        .collect();
3927    if let Some(domain) = problem.domain.as_ref() {
3928        for bracket in &brackets {
3929            let lower_inside = bracket.lower().compare(&dyadic_to_real(domain.lower())?);
3930            let upper_inside = bracket.upper().compare(&dyadic_to_real(domain.upper())?);
3931            match (lower_inside, upper_inside) {
3932                (Ok(lower), Ok(upper)) if lower != Ordering::Less && upper != Ordering::Greater => {
3933                }
3934                (Ok(_), Ok(_)) => outside_domain = true,
3935                _ => ordering_failed = true,
3936            }
3937        }
3938    } else {
3939        outside_domain = true;
3940    }
3941    for pair in brackets.windows(2) {
3942        match pair[0].lower().compare(pair[1].lower()) {
3943            Ok(Ordering::Equal) => overlap = true,
3944            Ok(_) => {}
3945            Err(_) => ordering_failed = true,
3946        }
3947        match pair[0].upper().compare(pair[1].lower()) {
3948            Ok(Ordering::Greater) => overlap = true,
3949            Ok(_) => {}
3950            Err(_) => ordering_failed = true,
3951        }
3952    }
3953
3954    let partition_complete = !cells.is_empty()
3955        && cells.iter().all(|cell| {
3956            matches!(
3957                cell.disposition,
3958                CellDisposition::Candidate
3959                    | CellDisposition::Coincident
3960                    | CellDisposition::RootFree
3961            )
3962        });
3963    let structural_complete = partition_complete
3964        && candidate_brackets_match
3965        && !unresolved_candidate
3966        && !duplicate_candidate
3967        && !overlap
3968        && !outside_domain
3969        && !ordering_failed;
3970    let source_domain = clone_domain(problem.constraint.domain());
3971    let source_function = clone_residual_function(problem.constraint.residual_function());
3972    let completeness_status = if structural_complete {
3973        WitnessStatus::Proved
3974    } else {
3975        WitnessStatus::Undetermined {
3976            reason: WitnessUndeterminedReason::PartitionOrCandidatesIncomplete,
3977        }
3978    };
3979    let non_overlap_status =
3980        if !duplicate_candidate && !overlap && !outside_domain && !ordering_failed {
3981            WitnessStatus::Proved
3982        } else {
3983            WitnessStatus::Undetermined {
3984                reason: WitnessUndeterminedReason::BracketSetInvalid,
3985            }
3986        };
3987    let completeness = ExistenceWitness::new(
3988        ExistenceEvidence::CompleteCandidatePartition,
3989        WitnessMethod::DeterministicDyadicCandidatePartition,
3990        completeness_status,
3991    );
3992    let non_overlap = UniquenessWitness::new(
3993        UniquenessEvidence::PairwiseNonOverlappingBrackets,
3994        WitnessMethod::CanonicalLowerEndpointOrdering,
3995        non_overlap_status,
3996    );
3997    Ok(RootIsolation::new(
3998        brackets,
3999        completeness,
4000        policy.method,
4001        source_domain,
4002        source_function,
4003        non_overlap,
4004    ))
4005}
4006
4007fn classify_constraint(
4008    problem: DerivedRootProblem,
4009    isolation: &RootIsolation,
4010) -> Result<IntersectionSet, GeometryFailure> {
4011    let residual = residual_from_constraint(&problem.constraint)?;
4012    let root_witness = IntersectionWitness::from_isolation_and_constraint(
4013        clone_isolation(isolation)?,
4014        problem.constraint,
4015    );
4016    let constraint = root_witness.constraint();
4017    if constraint.rank_is_undetermined() {
4018        return Ok(undetermined_with(
4019            IntersectionUndeterminedReason::EvaluationUndetermined,
4020            residual,
4021            root_witness,
4022        ));
4023    }
4024    let unresolved_isolation = !matches!(
4025        root_witness.root_isolation().completeness().status(),
4026        WitnessStatus::Proved
4027    ) || !matches!(
4028        root_witness.root_isolation().non_overlap().status(),
4029        WitnessStatus::Proved
4030    );
4031    if unresolved_isolation {
4032        return Ok(undetermined_with(
4033            IntersectionUndeterminedReason::RootIsolationIncomplete,
4034            residual,
4035            root_witness,
4036        ));
4037    }
4038    match constraint.support_relation() {
4039        SupportRelation::Coincident { .. } => {
4040            let Ok((left, right)) = declaration_pair(constraint) else {
4041                return Ok(undetermined_with(
4042                    IntersectionUndeterminedReason::CoincidenceUndetermined,
4043                    residual,
4044                    root_witness,
4045                ));
4046            };
4047            IntersectionSet::from_components(
4048                IntersectionKind::Coincident,
4049                clone_residual(&residual)?,
4050                clone_witness(&root_witness)?,
4051                vec![OwnedIntersectionEvidence::Coincident(Box::new(
4052                    CoincidentSupport::new(
4053                        left,
4054                        clone_residual(&residual)?,
4055                        right,
4056                        clone_witness(&root_witness)?,
4057                    ),
4058                ))],
4059            )
4060        }
4061        SupportRelation::Disjoint { .. } => Ok(IntersectionSet::empty(residual, root_witness)),
4062        SupportRelation::Finite { .. } => {
4063            let points = derive_points(constraint, isolation, &residual, &root_witness)?;
4064            match points.len() {
4065                0 => Ok(IntersectionSet::empty(residual, root_witness)),
4066                1 => {
4067                    let point = points.into_iter().next().ok_or({
4068                        GeometryFailure::CalculusFailure {
4069                            error: CalculusFailure::Polynomial(
4070                                PolynomialFailure::EmptyCoefficients,
4071                            ),
4072                        }
4073                    })?;
4074                    IntersectionSet::from_components(
4075                        IntersectionKind::Point,
4076                        residual,
4077                        root_witness,
4078                        vec![OwnedIntersectionEvidence::Point(Box::new(point))],
4079                    )
4080                }
4081                _ => IntersectionSet::from_components(
4082                    IntersectionKind::FinitePoints,
4083                    residual,
4084                    root_witness,
4085                    points
4086                        .into_iter()
4087                        .map(|point| OwnedIntersectionEvidence::Point(Box::new(point)))
4088                        .collect(),
4089                ),
4090            }
4091        }
4092        SupportRelation::Curve { .. } => {
4093            let identities = derive_branch_identities(constraint, isolation)?;
4094            if identities.is_empty() {
4095                return Ok(undetermined_with(
4096                    IntersectionUndeterminedReason::BranchIdentityUndetermined,
4097                    residual,
4098                    root_witness,
4099                ));
4100            }
4101            if identities.len() != isolation.brackets().len() {
4102                return Ok(undetermined_with(
4103                    IntersectionUndeterminedReason::BranchIdentityUndetermined,
4104                    residual,
4105                    root_witness,
4106                ));
4107            }
4108            let mut branches = Vec::new();
4109            for (ordinal, identity) in identities.into_iter().enumerate() {
4110                let Some(bracket) = isolation.brackets().get(ordinal) else {
4111                    return Ok(undetermined_with(
4112                        IntersectionUndeterminedReason::BranchIdentityUndetermined,
4113                        residual,
4114                        root_witness,
4115                    ));
4116                };
4117                branches.push(CurveBranch::new(
4118                    identity,
4119                    bracket.contact_order().clone(),
4120                    clone_residual(&residual)?,
4121                    clone_witness(&root_witness)?,
4122                ));
4123            }
4124            if branches.len() == 1 {
4125                let branch = branches.into_iter().next().ok_or({
4126                    GeometryFailure::CalculusFailure {
4127                        error: CalculusFailure::Polynomial(PolynomialFailure::EmptyCoefficients),
4128                    }
4129                })?;
4130                let identity = clone_identity(branch.branch_identity())?;
4131                let curve = IntersectionCurve::new(
4132                    identity,
4133                    branch.contact_order().clone(),
4134                    branch.residual().clone_for_operation()?,
4135                    constraint_support_id(constraint),
4136                    clone_witness(&root_witness)?,
4137                );
4138                IntersectionSet::from_components(
4139                    IntersectionKind::Curve,
4140                    residual,
4141                    root_witness,
4142                    vec![OwnedIntersectionEvidence::Curve(Box::new(curve))],
4143                )
4144            } else {
4145                IntersectionSet::from_components(
4146                    IntersectionKind::CurveBranches,
4147                    residual,
4148                    root_witness,
4149                    branches
4150                        .into_iter()
4151                        .map(|branch| OwnedIntersectionEvidence::CurveBranch(Box::new(branch)))
4152                        .collect(),
4153                )
4154            }
4155        }
4156        SupportRelation::Undetermined { .. } => Ok(undetermined_with(
4157            IntersectionUndeterminedReason::CoincidenceUndetermined,
4158            residual,
4159            root_witness,
4160        )),
4161    }
4162}
4163
4164fn derive_support_relation(left: &OperandDescriptor, right: &OperandDescriptor) -> SupportRelation {
4165    if left.support_id == right.support_id && left.chart_id == right.chart_id {
4166        return SupportRelation::Coincident {
4167            evidence: SupportEvidence::CanonicalSupportAndChart,
4168        };
4169    }
4170    let left_evaluated = matches!(left.source, OperandSource::Evaluated);
4171    let right_evaluated = matches!(right.source, OperandSource::Evaluated);
4172    if (left_evaluated && left.exact_point.is_some())
4173        || (right_evaluated && right.exact_point.is_some())
4174    {
4175        return SupportRelation::Finite {
4176            evidence: SupportEvidence::EvaluatedSpatialCoordinates,
4177        };
4178    }
4179    if left_evaluated && right_evaluated {
4180        if let (Some(left), Some(right)) = (&left.exact_scalar, &right.exact_scalar) {
4181            return if left == right {
4182                SupportRelation::Coincident {
4183                    evidence: SupportEvidence::EqualEvaluatedScalars,
4184                }
4185            } else {
4186                SupportRelation::Disjoint {
4187                    evidence: SupportEvidence::DistinctEvaluatedScalars,
4188                }
4189            };
4190        }
4191        if left.exact_scalar.is_some() || right.exact_scalar.is_some() {
4192            return SupportRelation::Undetermined {
4193                reason: SupportUndeterminedReason::IncompleteEvaluatedScalar,
4194            };
4195        }
4196    }
4197    if matches!(left.source, OperandSource::Declaration)
4198        && matches!(right.source, OperandSource::Declaration)
4199    {
4200        return match (left.family, right.family) {
4201            (
4202                crate::types::ShapeFamily::ParametricCurve,
4203                crate::types::ShapeFamily::ParametricCurve,
4204            )
4205            | (
4206                crate::types::ShapeFamily::ParametricSurface,
4207                crate::types::ShapeFamily::ParametricSurface,
4208            ) => SupportRelation::Curve {
4209                evidence: SupportEvidence::CompatibleParametricSupports,
4210            },
4211            (
4212                crate::types::ShapeFamily::ImplicitSurface,
4213                crate::types::ShapeFamily::ImplicitSurface,
4214            ) => SupportRelation::Curve {
4215                evidence: SupportEvidence::ImplicitSupportPair,
4216            },
4217            _ => SupportRelation::Undetermined {
4218                reason: SupportUndeterminedReason::NoCommonParameterization,
4219            },
4220        };
4221    }
4222    SupportRelation::Undetermined {
4223        reason: SupportUndeterminedReason::UnclassifiedEvidence,
4224    }
4225}
4226
4227fn derive_rank_evidence(
4228    left: &OperandDescriptor,
4229    right: &OperandDescriptor,
4230    support: &SupportRelation,
4231) -> RankEvidence {
4232    if matches!(support, SupportRelation::Undetermined { .. }) {
4233        return RankEvidence::Undetermined {
4234            reason: RankUndeterminedReason::SupportRelationUnresolved,
4235        };
4236    }
4237    if left.family == right.family {
4238        RankEvidence::Sufficient { rank: 1 }
4239    } else if (matches!(left.source, OperandSource::Evaluated) && left.exact_point.is_some())
4240        || (matches!(right.source, OperandSource::Evaluated) && right.exact_point.is_some())
4241    {
4242        RankEvidence::Sufficient { rank: 0 }
4243    } else {
4244        RankEvidence::Degenerate {
4245            reason: RankDegeneracyReason::InsufficientCommonRank,
4246        }
4247    }
4248}
4249
4250fn derive_residual_polynomial(
4251    left: &OperandDescriptor,
4252    right: &OperandDescriptor,
4253) -> Result<Option<Polynomial>, GeometryFailure> {
4254    match (left.source, right.source) {
4255        (OperandSource::Evaluated, OperandSource::Evaluated) => {
4256            if let (Some(left), Some(right)) = (&left.exact_scalar, &right.exact_scalar) {
4257                return Ok(Some(
4258                    Polynomial::constant(left.sub(right).map_err(GeometryFailure::AlgebraFailure)?)
4259                        .map_err(calculus_polynomial_failure)?,
4260                ));
4261            }
4262            if let (Some(left), Some(right)) = (&left.exact_point, &right.exact_point) {
4263                return Ok(Some(
4264                    Polynomial::constant(
4265                        left.x
4266                            .sub(&right.x)
4267                            .map_err(GeometryFailure::AlgebraFailure)?,
4268                    )
4269                    .map_err(calculus_polynomial_failure)?,
4270                ));
4271            }
4272            Ok(None)
4273        }
4274        (OperandSource::Evaluated, OperandSource::Declaration) => {
4275            let Some(polynomial) = right.polynomial.as_ref() else {
4276                return Ok(None);
4277            };
4278            if let Some(point) = left.exact_point.as_ref() {
4279                return negate_polynomial_plus_constant(polynomial, &point.x);
4280            }
4281            if let Some(value) = left.exact_scalar.as_ref() {
4282                return negate_polynomial_plus_constant(polynomial, value);
4283            }
4284            Ok(None)
4285        }
4286        (OperandSource::Declaration, OperandSource::Evaluated) => {
4287            let Some(polynomial) = left.polynomial.as_ref() else {
4288                return Ok(None);
4289            };
4290            if let Some(point) = right.exact_point.as_ref() {
4291                return subtract_constant_from_polynomial(polynomial, &point.x);
4292            }
4293            if let Some(value) = right.exact_scalar.as_ref() {
4294                return subtract_constant_from_polynomial(polynomial, value);
4295            }
4296            Ok(None)
4297        }
4298        (OperandSource::Declaration, OperandSource::Declaration) => {
4299            match (&left.polynomial, &right.polynomial) {
4300                (Some(left), Some(right)) => {
4301                    let max = left.degree().max(right.degree());
4302                    let mut coefficients = Vec::with_capacity(max + 1);
4303                    for index in 0..=max {
4304                        let left_value = left
4305                            .coefficients()
4306                            .get(index)
4307                            .map(RealAlgebraic::try_clone)
4308                            .transpose()?;
4309                        let right_value = right
4310                            .coefficients()
4311                            .get(index)
4312                            .map(RealAlgebraic::try_clone)
4313                            .transpose()?;
4314                        let zero = RealAlgebraic::from_integer(BigInt::zero())?;
4315                        let left_value = left_value.unwrap_or(zero.try_clone()?);
4316                        let right_value = right_value.unwrap_or(zero);
4317                        coefficients.push(
4318                            left_value
4319                                .sub(&right_value)
4320                                .map_err(GeometryFailure::AlgebraFailure)?,
4321                        );
4322                    }
4323                    Ok(Some(
4324                        Polynomial::from_coefficients(coefficients)
4325                            .map_err(calculus_polynomial_failure)?,
4326                    ))
4327                }
4328                _ => Ok(None),
4329            }
4330        }
4331    }
4332}
4333
4334fn subtract_constant_from_polynomial(
4335    polynomial: &Polynomial,
4336    value: &RealAlgebraic,
4337) -> Result<Option<Polynomial>, GeometryFailure> {
4338    let mut coefficients = Vec::with_capacity(polynomial.coefficients().len());
4339    for (index, coefficient) in polynomial.coefficients().iter().enumerate() {
4340        let adjusted = if index == 0 {
4341            coefficient
4342                .sub(value)
4343                .map_err(GeometryFailure::AlgebraFailure)?
4344        } else {
4345            coefficient.try_clone()?
4346        };
4347        coefficients.push(adjusted);
4348    }
4349    Ok(Some(
4350        Polynomial::from_coefficients(coefficients).map_err(calculus_polynomial_failure)?,
4351    ))
4352}
4353
4354fn negate_polynomial_plus_constant(
4355    polynomial: &Polynomial,
4356    value: &RealAlgebraic,
4357) -> Result<Option<Polynomial>, GeometryFailure> {
4358    let mut coefficients = Vec::with_capacity(polynomial.coefficients().len());
4359    for (index, coefficient) in polynomial.coefficients().iter().enumerate() {
4360        let negated = RealAlgebraic::from_integer(BigInt::zero())?
4361            .sub(coefficient)
4362            .map_err(GeometryFailure::AlgebraFailure)?;
4363        let adjusted = if index == 0 {
4364            value
4365                .sub(coefficient)
4366                .map_err(GeometryFailure::AlgebraFailure)?
4367        } else {
4368            negated
4369        };
4370        coefficients.push(adjusted);
4371    }
4372    Ok(Some(
4373        Polynomial::from_coefficients(coefficients).map_err(calculus_polynomial_failure)?,
4374    ))
4375}
4376
4377fn derive_numeric_domain(
4378    left: &OperandDescriptor,
4379    right: &OperandDescriptor,
4380) -> Result<Option<Enclosure>, GeometryFailure> {
4381    match (&left.parameter_bounds, &right.parameter_bounds) {
4382        (Some((left_lower, left_upper)), Some((right_lower, right_upper))) => {
4383            let lower = if left_lower.compare(right_lower)? == Ordering::Greater {
4384                left_lower
4385            } else {
4386                right_lower
4387            };
4388            let upper = if left_upper.compare(right_upper)? == Ordering::Less {
4389                left_upper
4390            } else {
4391                right_upper
4392            };
4393            if lower.compare(upper)? == Ordering::Greater {
4394                return Err(GeometryFailure::ParameterOutsideDomain);
4395            }
4396            let lower = real_to_dyadic(lower)?;
4397            let upper = real_to_dyadic(upper)?;
4398            Ok(Some(Enclosure::new(lower, upper).map_err(|error| {
4399                GeometryFailure::CalculusFailure {
4400                    error: CalculusFailure::Interval(error),
4401                }
4402            })?))
4403        }
4404        (Some((lower, upper)), None) | (None, Some((lower, upper))) => {
4405            let lower = real_to_dyadic(lower)?;
4406            let upper = real_to_dyadic(upper)?;
4407            Ok(Some(Enclosure::new(lower, upper).map_err(|error| {
4408                GeometryFailure::CalculusFailure {
4409                    error: CalculusFailure::Interval(error),
4410                }
4411            })?))
4412        }
4413        (None, None) if left.exact_scalar.is_some() && right.exact_scalar.is_some() => Ok(Some(
4414            Enclosure::new(
4415                Dyadic::new(BigInt::zero(), 0),
4416                Dyadic::new(BigInt::zero(), 0),
4417            )
4418            .map_err(|error| GeometryFailure::CalculusFailure {
4419                error: CalculusFailure::Interval(error),
4420            })?,
4421        )),
4422        (None, None) => Ok(None),
4423    }
4424}
4425
4426fn descriptor_from_declaration(
4427    declaration: &ShapeDeclaration,
4428    evaluation: ShapeEvaluation,
4429) -> Result<OperandDescriptor, GeometryFailure> {
4430    let family = declaration.family();
4431    let (support_id, chart_id, domain, parameter_bounds, expression, polynomial) = match declaration
4432    {
4433        ShapeDeclaration::ParametricCurve(value) => {
4434            let chart_id = match value.chart() {
4435                crate::types::CurveChart::Chart2(_) => String::from("chart-2"),
4436                crate::types::CurveChart::Chart3(_) => String::from("chart-3"),
4437            };
4438            let expression = curve_expression(value);
4439            let polynomial = curve_polynomial(value)?;
4440            (
4441                format!("curve:{}", expression),
4442                chart_id,
4443                String::from(value.chart_domain()),
4444                interval_bounds(value.domain()),
4445                expression,
4446                polynomial,
4447            )
4448        }
4449        ShapeDeclaration::ParametricSurface(value) => {
4450            let expression = surface_expression(value);
4451            (
4452                format!("surface:{}", expression),
4453                String::from("surface-chart"),
4454                String::from(value.chart().identity().domain_id().as_str()),
4455                None,
4456                expression,
4457                None,
4458            )
4459        }
4460        ShapeDeclaration::ImplicitSurface(value) => {
4461            let expression = implicit_expression(value);
4462            (
4463                format!("implicit:{}", expression),
4464                String::from("implicit-chart"),
4465                String::from("support-domain"),
4466                None,
4467                expression,
4468                implicit_polynomial(value)?,
4469            )
4470        }
4471    };
4472    let (exact_scalar, exact_point, certified_scalar) = evaluation_evidence(&evaluation)?;
4473    Ok(OperandDescriptor {
4474        source: OperandSource::Declaration,
4475        family,
4476        support_id,
4477        chart_id,
4478        domain,
4479        parameter_bounds,
4480        expression,
4481        polynomial,
4482        exact_scalar,
4483        exact_point,
4484        certified_scalar,
4485    })
4486}
4487
4488fn descriptor_from_evaluation(
4489    evaluation: &ShapeEvaluation,
4490) -> Result<OperandDescriptor, GeometryFailure> {
4491    let family = match evaluation {
4492        ShapeEvaluation::Exact(ExactShapeEvaluation::ParametricCurve { .. })
4493        | ShapeEvaluation::CertifiedEnclosure(CertifiedShapeEvaluation::ParametricCurve {
4494            ..
4495        }) => crate::types::ShapeFamily::ParametricCurve,
4496        ShapeEvaluation::Exact(ExactShapeEvaluation::ParametricSurface { .. })
4497        | ShapeEvaluation::CertifiedEnclosure(CertifiedShapeEvaluation::ParametricSurface {
4498            ..
4499        }) => crate::types::ShapeFamily::ParametricSurface,
4500        ShapeEvaluation::Exact(ExactShapeEvaluation::ImplicitSurface { .. })
4501        | ShapeEvaluation::CertifiedEnclosure(CertifiedShapeEvaluation::ImplicitSurface {
4502            ..
4503        }) => crate::types::ShapeFamily::ImplicitSurface,
4504        ShapeEvaluation::Undetermined { family } => *family,
4505    };
4506    let (exact_scalar, exact_point, certified_scalar) = evaluation_evidence(evaluation)?;
4507    let expression = format!("evaluated:{family:?}:{evaluation:?}");
4508    Ok(OperandDescriptor {
4509        source: OperandSource::Evaluated,
4510        family,
4511        support_id: expression.clone(),
4512        chart_id: format!("evaluated-{family:?}"),
4513        domain: String::from("evaluated-domain"),
4514        parameter_bounds: None,
4515        expression,
4516        polynomial: None,
4517        exact_scalar,
4518        exact_point,
4519        certified_scalar,
4520    })
4521}
4522
4523type EvaluationEvidence = (
4524    Option<RealAlgebraic>,
4525    Option<Point3>,
4526    Option<(
4527        Enclosure,
4528        OwnerId,
4529        ExactExpressionRequirement,
4530        NecoImplementationSource,
4531    )>,
4532);
4533
4534fn evaluation_evidence(
4535    evaluation: &ShapeEvaluation,
4536) -> Result<EvaluationEvidence, GeometryFailure> {
4537    match evaluation {
4538        ShapeEvaluation::Exact(ExactShapeEvaluation::ImplicitSurface { scalar }) => {
4539            Ok((Some(scalar.try_clone()?), None, None))
4540        }
4541        ShapeEvaluation::Exact(ExactShapeEvaluation::ParametricCurve { coordinate }) => {
4542            let point = match coordinate {
4543                ShapeCoordinate::Spatial(point) => clone_point(point)?,
4544                ShapeCoordinate::Planar(point) => Point3 {
4545                    x: point.x.try_clone()?,
4546                    y: point.y.try_clone()?,
4547                    z: RealAlgebraic::from_integer(BigInt::zero())?,
4548                },
4549            };
4550            Ok((None, Some(point), None))
4551        }
4552        ShapeEvaluation::Exact(ExactShapeEvaluation::ParametricSurface { coordinate }) => {
4553            Ok((None, Some(clone_point(coordinate)?), None))
4554        }
4555        ShapeEvaluation::CertifiedEnclosure(CertifiedShapeEvaluation::ImplicitSurface {
4556            scalar,
4557            owner,
4558            requirement,
4559            source,
4560        }) => Ok((
4561            None,
4562            None,
4563            Some((
4564                clone_enclosure(scalar)?,
4565                *owner,
4566                clone_requirement(requirement)?,
4567                *source,
4568            )),
4569        )),
4570        ShapeEvaluation::CertifiedEnclosure(_) | ShapeEvaluation::Undetermined { .. } => {
4571            Ok((None, None, None))
4572        }
4573    }
4574}
4575
4576fn derive_points(
4577    constraint: &IntersectionConstraint,
4578    isolation: &RootIsolation,
4579    residual: &IntersectionResidual,
4580    witness: &IntersectionWitness,
4581) -> Result<IntersectionPointSet, GeometryFailure> {
4582    let Some(point) = operand_point(constraint.left_operand())
4583        .or_else(|| operand_point(constraint.right_operand()))
4584    else {
4585        return Ok(Vec::new());
4586    };
4587    isolation
4588        .brackets()
4589        .iter()
4590        .enumerate()
4591        .map(|(ordinal, bracket)| {
4592            Ok(IntersectionPoint::new(
4593                Some(derive_branch_identity(constraint, ordinal)),
4594                bracket.contact_order().clone(),
4595                clone_point(&point)?,
4596                clone_residual(residual)?,
4597                clone_witness(witness)?,
4598            ))
4599        })
4600        .collect()
4601}
4602
4603fn derive_branch_identities(
4604    constraint: &IntersectionConstraint,
4605    isolation: &RootIsolation,
4606) -> Result<BranchIdentitySet, GeometryFailure> {
4607    if constraint.support_relation().is_undetermined() {
4608        return Ok(Vec::new());
4609    }
4610    let count = isolation.brackets().len();
4611    Ok((0..count)
4612        .map(|ordinal| derive_branch_identity(constraint, ordinal))
4613        .collect())
4614}
4615
4616fn derive_branch_identity(constraint: &IntersectionConstraint, ordinal: usize) -> BranchIdentity {
4617    let support_id = constraint_support_id(constraint);
4618    let chart_id = constraint_chart_id(constraint);
4619    BranchIdentity::new(
4620        format!("{support_id}|{chart_id}|candidate-{ordinal}"),
4621        chart_id,
4622        support_id,
4623    )
4624}
4625
4626fn declaration_pair(
4627    constraint: &IntersectionConstraint,
4628) -> Result<(ShapeDeclaration, ShapeDeclaration), GeometryFailure> {
4629    match (constraint.left_operand(), constraint.right_operand()) {
4630        (IntersectionOperand::Declaration(left), IntersectionOperand::Declaration(right)) => {
4631            Ok((clone_declaration(left)?, clone_declaration(right)?))
4632        }
4633        _ => Err(GeometryFailure::EvaluationIndeterminacy {
4634            family: crate::types::ShapeFamily::ImplicitSurface,
4635            reason: crate::types::ShapeEvaluationIndeterminacy::DomainValidity,
4636        }),
4637    }
4638}
4639
4640fn operand_point(operand: &IntersectionOperand) -> Option<Point3> {
4641    match operand {
4642        IntersectionOperand::Evaluated(ShapeEvaluation::Exact(
4643            ExactShapeEvaluation::ParametricSurface { coordinate },
4644        )) => Some(clone_point(coordinate).ok()?),
4645        IntersectionOperand::Evaluated(ShapeEvaluation::Exact(
4646            ExactShapeEvaluation::ParametricCurve {
4647                coordinate: ShapeCoordinate::Spatial(coordinate),
4648            },
4649        )) => Some(clone_point(coordinate).ok()?),
4650        _ => None,
4651    }
4652}
4653
4654fn residual_from_constraint(
4655    constraint: &IntersectionConstraint,
4656) -> Result<IntersectionResidual, GeometryFailure> {
4657    let left = operand_residual_value(constraint.left_operand())?;
4658    let right = operand_residual_value(constraint.right_operand())?;
4659    let combined = match (&left, &right) {
4660        (ResidualValue::Exact { value: left }, ResidualValue::Exact { value: right }) => {
4661            ResidualValue::Exact {
4662                value: left.sub(right).map_err(GeometryFailure::AlgebraFailure)?,
4663            }
4664        }
4665        (
4666            ResidualValue::Certified {
4667                owner: left_owner,
4668                requirement: left_requirement,
4669                source: left_source,
4670                value: left,
4671            },
4672            ResidualValue::Certified { value: right, .. },
4673        ) => ResidualValue::Certified {
4674            owner: *left_owner,
4675            requirement: clone_requirement(left_requirement)?,
4676            source: *left_source,
4677            value: subtract_enclosures(left, right)?,
4678        },
4679        _ => ResidualValue::Undetermined {
4680            reason: ResidualUndeterminedReason::OperandEvidenceUnresolved,
4681        },
4682    };
4683    Ok(IntersectionResidual::new(combined, left, right))
4684}
4685
4686fn operand_residual_value(operand: &IntersectionOperand) -> Result<ResidualValue, GeometryFailure> {
4687    match operand {
4688        IntersectionOperand::Evaluated(ShapeEvaluation::Exact(
4689            ExactShapeEvaluation::ImplicitSurface { scalar },
4690        )) => Ok(ResidualValue::Exact {
4691            value: scalar.try_clone()?,
4692        }),
4693        IntersectionOperand::Evaluated(ShapeEvaluation::CertifiedEnclosure(
4694            CertifiedShapeEvaluation::ImplicitSurface {
4695                scalar,
4696                owner,
4697                requirement,
4698                source,
4699            },
4700        )) => Ok(ResidualValue::Certified {
4701            owner: *owner,
4702            requirement: clone_requirement(requirement)?,
4703            source: *source,
4704            value: clone_enclosure(scalar)?,
4705        }),
4706        _ => Ok(ResidualValue::Undetermined {
4707            reason: ResidualUndeterminedReason::ScalarResidualUnavailable,
4708        }),
4709    }
4710}
4711
4712fn undetermined_with(
4713    reason: IntersectionUndeterminedReason,
4714    residual: IntersectionResidual,
4715    witness: IntersectionWitness,
4716) -> IntersectionSet {
4717    IntersectionSet::undetermined(reason, residual, witness)
4718}
4719
4720fn refine_root(
4721    bracket: &CalculusRootBracket,
4722    policy: &RootIsolationPolicy,
4723) -> Result<CalculusRootIsolation, GeometryFailure> {
4724    match policy.method {
4725        RootRefinementMethod::Bisection => {
4726            neco_calculus::refine_root_bisection(bracket, policy.max_iterations)
4727                .map_err(map_calculus_failure)
4728        }
4729        RootRefinementMethod::NewtonBisection => {
4730            neco_calculus::refine_root_newton_bisection(bracket, policy.max_iterations, 32)
4731                .map_err(map_calculus_failure)
4732        }
4733    }
4734}
4735
4736fn contact_order_from_evidence(evidence: &RootEvidence) -> ContactOrder {
4737    match evidence {
4738        RootEvidence::SignChange { .. } | RootEvidence::SimpleRoot { .. } => {
4739            ContactOrder::new(ContactOrderKind::Transverse, 1)
4740        }
4741        RootEvidence::EvenMultiplicityTouch { order, .. } => {
4742            if *order == 2 {
4743                ContactOrder::new(ContactOrderKind::Tangent, 2)
4744            } else if *order > 2 {
4745                ContactOrder::new(ContactOrderKind::HigherOrder, *order)
4746            } else {
4747                ContactOrder::new(ContactOrderKind::Undetermined, 0)
4748            }
4749        }
4750        RootEvidence::HigherOrder { order, .. } => {
4751            ContactOrder::new(ContactOrderKind::HigherOrder, *order)
4752        }
4753        RootEvidence::Undetermined { .. } => ContactOrder::new(ContactOrderKind::Undetermined, 0),
4754    }
4755}
4756
4757fn clone_isolation(isolation: &RootIsolation) -> Result<RootIsolation, GeometryFailure> {
4758    let brackets = isolation
4759        .brackets
4760        .iter()
4761        .map(clone_bracket)
4762        .collect::<Result<Vec<_>, _>>()?;
4763    Ok(RootIsolation::new(
4764        brackets,
4765        clone_existence(&isolation.completeness),
4766        isolation.method,
4767        clone_domain(&isolation.source_domain),
4768        clone_residual_function(&isolation.source_function),
4769        clone_uniqueness(&isolation.non_overlap),
4770    ))
4771}
4772
4773fn clone_bracket(bracket: &RootBracket) -> Result<RootBracket, GeometryFailure> {
4774    Ok(RootBracket {
4775        contact_order: bracket.contact_order.clone(),
4776        convergence: ConvergenceWitness::new(
4777            bracket.convergence.final_lower.try_clone()?,
4778            bracket.convergence.final_upper.try_clone()?,
4779            bracket.convergence.initial_lower.try_clone()?,
4780            bracket.convergence.initial_upper.try_clone()?,
4781            bracket.convergence.iterations,
4782            bracket.convergence.method,
4783            bracket.convergence.status,
4784        ),
4785        lower: bracket.lower.try_clone()?,
4786        sign_change: bracket.sign_change,
4787        upper: bracket.upper.try_clone()?,
4788        evidence: clone_root_evidence(&bracket.evidence)?,
4789        exact_parameter: bracket
4790            .exact_parameter
4791            .as_ref()
4792            .map(|parameter| parameter.try_clone())
4793            .transpose()?,
4794    })
4795}
4796
4797pub(crate) fn clone_root_evidence(
4798    evidence: &RootEvidence,
4799) -> Result<RootEvidence, GeometryFailure> {
4800    Ok(match evidence {
4801        RootEvidence::SignChange {
4802            lower_sign,
4803            upper_sign,
4804            derivative_enclosure,
4805            source,
4806        } => RootEvidence::SignChange {
4807            lower_sign: *lower_sign,
4808            upper_sign: *upper_sign,
4809            derivative_enclosure: clone_enclosure(derivative_enclosure)?,
4810            source: source.clone(),
4811        },
4812        RootEvidence::EvenMultiplicityTouch {
4813            order,
4814            point,
4815            source,
4816        } => RootEvidence::EvenMultiplicityTouch {
4817            order: *order,
4818            point: point.try_clone()?,
4819            source: source.clone(),
4820        },
4821        RootEvidence::HigherOrder {
4822            order,
4823            point,
4824            source,
4825        } => RootEvidence::HigherOrder {
4826            order: *order,
4827            point: point.try_clone()?,
4828            source: source.clone(),
4829        },
4830        RootEvidence::SimpleRoot { point, source } => RootEvidence::SimpleRoot {
4831            point: point.try_clone()?,
4832            source: source.clone(),
4833        },
4834        RootEvidence::Undetermined { reason, source } => RootEvidence::Undetermined {
4835            reason: *reason,
4836            source: source.clone(),
4837        },
4838    })
4839}
4840
4841fn clone_existence(value: &ExistenceWitness) -> ExistenceWitness {
4842    ExistenceWitness::new(
4843        value.evidence,
4844        value.method,
4845        clone_witness_status(&value.status),
4846    )
4847}
4848
4849fn clone_uniqueness(value: &UniquenessWitness) -> UniquenessWitness {
4850    UniquenessWitness::new(
4851        value.evidence,
4852        value.method,
4853        clone_witness_status(&value.status),
4854    )
4855}
4856
4857fn clone_witness_status(status: &WitnessStatus) -> WitnessStatus {
4858    match status {
4859        WitnessStatus::Proved => WitnessStatus::Proved,
4860        WitnessStatus::Undetermined { reason } => WitnessStatus::Undetermined { reason: *reason },
4861    }
4862}
4863
4864fn clone_witness(value: &IntersectionWitness) -> Result<IntersectionWitness, GeometryFailure> {
4865    Ok(IntersectionWitness {
4866        existence: clone_existence(&value.existence),
4867        uniqueness: clone_uniqueness(&value.uniqueness),
4868        root_isolation: clone_isolation(&value.root_isolation)?,
4869        constraint: clone_constraint(&value.constraint)?,
4870    })
4871}
4872
4873fn clone_constraint(
4874    value: &IntersectionConstraint,
4875) -> Result<IntersectionConstraint, GeometryFailure> {
4876    Ok(IntersectionConstraint::new(
4877        clone_operand(value.left_operand())?,
4878        clone_operand(value.right_operand())?,
4879        clone_residual_function(value.residual_function()),
4880        clone_domain(value.domain()),
4881        clone_support_relation(value.support_relation()),
4882        clone_rank_evidence(value.rank_evidence()),
4883    ))
4884}
4885
4886fn clone_operand(value: &IntersectionOperand) -> Result<IntersectionOperand, GeometryFailure> {
4887    match value {
4888        IntersectionOperand::Declaration(declaration) => Ok(IntersectionOperand::Declaration(
4889            clone_declaration(declaration)?,
4890        )),
4891        IntersectionOperand::Evaluated(evaluation) => Ok(IntersectionOperand::Evaluated(
4892            clone_evaluation(evaluation)?,
4893        )),
4894    }
4895}
4896
4897fn clone_evaluation(value: &ShapeEvaluation) -> Result<ShapeEvaluation, GeometryFailure> {
4898    Ok(match value {
4899        ShapeEvaluation::Exact(evaluation) => ShapeEvaluation::Exact(match evaluation {
4900            ExactShapeEvaluation::ParametricCurve { coordinate } => {
4901                ExactShapeEvaluation::ParametricCurve {
4902                    coordinate: clone_shape_coordinate(coordinate)?,
4903                }
4904            }
4905            ExactShapeEvaluation::ParametricSurface { coordinate } => {
4906                ExactShapeEvaluation::ParametricSurface {
4907                    coordinate: clone_point(coordinate)?,
4908                }
4909            }
4910            ExactShapeEvaluation::ImplicitSurface { scalar } => {
4911                ExactShapeEvaluation::ImplicitSurface {
4912                    scalar: scalar.try_clone()?,
4913                }
4914            }
4915        }),
4916        ShapeEvaluation::CertifiedEnclosure(evaluation) => {
4917            ShapeEvaluation::CertifiedEnclosure(match evaluation {
4918                CertifiedShapeEvaluation::ParametricCurve {
4919                    coordinate,
4920                    owner,
4921                    requirement,
4922                    source,
4923                } => CertifiedShapeEvaluation::ParametricCurve {
4924                    coordinate: clone_shape_coordinate_enclosure(coordinate)?,
4925                    owner: *owner,
4926                    requirement: clone_requirement(requirement)?,
4927                    source: *source,
4928                },
4929                CertifiedShapeEvaluation::ParametricSurface {
4930                    coordinate,
4931                    owner,
4932                    requirement,
4933                    source,
4934                } => CertifiedShapeEvaluation::ParametricSurface {
4935                    coordinate: Box::new(clone_coordinate_enclosure3(coordinate)?),
4936                    owner: *owner,
4937                    requirement: clone_requirement(requirement)?,
4938                    source: *source,
4939                },
4940                CertifiedShapeEvaluation::ImplicitSurface {
4941                    scalar,
4942                    owner,
4943                    requirement,
4944                    source,
4945                } => CertifiedShapeEvaluation::ImplicitSurface {
4946                    scalar: clone_enclosure(scalar)?,
4947                    owner: *owner,
4948                    requirement: clone_requirement(requirement)?,
4949                    source: *source,
4950                },
4951            })
4952        }
4953        ShapeEvaluation::Undetermined { family } => {
4954            ShapeEvaluation::Undetermined { family: *family }
4955        }
4956    })
4957}
4958
4959fn clone_shape_coordinate(value: &ShapeCoordinate) -> Result<ShapeCoordinate, GeometryFailure> {
4960    Ok(match value {
4961        ShapeCoordinate::Planar(point) => ShapeCoordinate::Planar(Point2 {
4962            x: point.x.try_clone()?,
4963            y: point.y.try_clone()?,
4964        }),
4965        ShapeCoordinate::Spatial(point) => ShapeCoordinate::Spatial(clone_point(point)?),
4966    })
4967}
4968
4969fn clone_shape_coordinate_enclosure(
4970    value: &crate::types::ShapeCoordinateEnclosure,
4971) -> Result<crate::types::ShapeCoordinateEnclosure, GeometryFailure> {
4972    Ok(match value {
4973        crate::types::ShapeCoordinateEnclosure::Planar(coordinate) => {
4974            crate::types::ShapeCoordinateEnclosure::Planar(crate::types::CoordinateEnclosure2 {
4975                x: clone_enclosure(&coordinate.x)?,
4976                y: clone_enclosure(&coordinate.y)?,
4977            })
4978        }
4979        crate::types::ShapeCoordinateEnclosure::Spatial(coordinate) => {
4980            crate::types::ShapeCoordinateEnclosure::Spatial(Box::new(clone_coordinate_enclosure3(
4981                coordinate,
4982            )?))
4983        }
4984    })
4985}
4986
4987fn clone_coordinate_enclosure3(
4988    value: &crate::types::CoordinateEnclosure3,
4989) -> Result<crate::types::CoordinateEnclosure3, GeometryFailure> {
4990    Ok(crate::types::CoordinateEnclosure3 {
4991        x: clone_enclosure(&value.x)?,
4992        y: clone_enclosure(&value.y)?,
4993        z: clone_enclosure(&value.z)?,
4994    })
4995}
4996
4997pub(crate) fn clone_support_relation(value: &SupportRelation) -> SupportRelation {
4998    match value {
4999        SupportRelation::Coincident { evidence } => SupportRelation::Coincident {
5000            evidence: *evidence,
5001        },
5002        SupportRelation::Curve { evidence } => SupportRelation::Curve {
5003            evidence: *evidence,
5004        },
5005        SupportRelation::Disjoint { evidence } => SupportRelation::Disjoint {
5006            evidence: *evidence,
5007        },
5008        SupportRelation::Finite { evidence } => SupportRelation::Finite {
5009            evidence: *evidence,
5010        },
5011        SupportRelation::Undetermined { reason } => {
5012            SupportRelation::Undetermined { reason: *reason }
5013        }
5014    }
5015}
5016
5017pub(crate) fn clone_rank_evidence(value: &RankEvidence) -> RankEvidence {
5018    match value {
5019        RankEvidence::Sufficient { rank } => RankEvidence::Sufficient { rank: *rank },
5020        RankEvidence::Degenerate { reason } => RankEvidence::Degenerate { reason: *reason },
5021        RankEvidence::Undetermined { reason } => RankEvidence::Undetermined { reason: *reason },
5022    }
5023}
5024
5025fn clone_residual(value: &IntersectionResidual) -> Result<IntersectionResidual, GeometryFailure> {
5026    Ok(IntersectionResidual::new(
5027        clone_residual_value(&value.combined)?,
5028        clone_residual_value(&value.left)?,
5029        clone_residual_value(&value.right)?,
5030    ))
5031}
5032
5033impl IntersectionResidual {
5034    fn clone_for_operation(&self) -> Result<Self, GeometryFailure> {
5035        clone_residual(self)
5036    }
5037}
5038
5039fn clone_residual_value(value: &ResidualValue) -> Result<ResidualValue, GeometryFailure> {
5040    Ok(match value {
5041        ResidualValue::Certified {
5042            owner,
5043            requirement,
5044            source,
5045            value,
5046        } => ResidualValue::Certified {
5047            owner: *owner,
5048            requirement: clone_requirement(requirement)?,
5049            source: *source,
5050            value: clone_enclosure(value)?,
5051        },
5052        ResidualValue::Exact { value } => ResidualValue::Exact {
5053            value: value.try_clone()?,
5054        },
5055        ResidualValue::Undetermined { reason } => ResidualValue::Undetermined { reason: *reason },
5056    })
5057}
5058
5059fn clone_domain(value: &IntersectionDomain) -> IntersectionDomain {
5060    IntersectionDomain::new(
5061        value.parameterization.clone(),
5062        value.restriction.clone(),
5063        value.support.clone(),
5064    )
5065}
5066
5067pub(crate) fn clone_residual_function(value: &ResidualFunction) -> ResidualFunction {
5068    ResidualFunction::new(
5069        value.left_expression.clone(),
5070        value.right_expression.clone(),
5071    )
5072}
5073
5074fn clone_identity(value: &BranchIdentity) -> Result<BranchIdentity, GeometryFailure> {
5075    Ok(BranchIdentity::new(
5076        value.branch_id.clone(),
5077        value.chart_id.clone(),
5078        value.support_id.clone(),
5079    ))
5080}
5081
5082fn clone_point(value: &Point3) -> Result<Point3, GeometryFailure> {
5083    Ok(Point3 {
5084        x: value.x.try_clone()?,
5085        y: value.y.try_clone()?,
5086        z: value.z.try_clone()?,
5087    })
5088}
5089
5090fn clone_enclosure(value: &Enclosure) -> Result<Enclosure, GeometryFailure> {
5091    Enclosure::new(
5092        value
5093            .lower()
5094            .try_clone()
5095            .map_err(|error| GeometryFailure::CalculusFailure {
5096                error: CalculusFailure::Polynomial(PolynomialFailure::Arithmetic(error)),
5097            })?,
5098        value
5099            .upper()
5100            .try_clone()
5101            .map_err(|error| GeometryFailure::CalculusFailure {
5102                error: CalculusFailure::Polynomial(PolynomialFailure::Arithmetic(error)),
5103            })?,
5104    )
5105    .map_err(|error| GeometryFailure::CalculusFailure {
5106        error: CalculusFailure::Interval(error),
5107    })
5108}
5109
5110fn clone_requirement(
5111    requirement: &ExactExpressionRequirement,
5112) -> Result<ExactExpressionRequirement, GeometryFailure> {
5113    ExactExpressionRequirement::new(
5114        requirement.consumer_id(),
5115        requirement.expressions(),
5116        requirement.decision(),
5117        requirement.precision(),
5118    )
5119    .map_err(|_| GeometryFailure::EvaluationIndeterminacy {
5120        family: crate::types::ShapeFamily::ImplicitSurface,
5121        reason: crate::types::ShapeEvaluationIndeterminacy::CalculusResult,
5122    })
5123}
5124
5125fn subtract_enclosures(left: &Enclosure, right: &Enclosure) -> Result<Enclosure, GeometryFailure> {
5126    Enclosure::new(
5127        left.lower()
5128            .sub(right.upper())
5129            .map_err(map_bigint_failure)?,
5130        left.upper()
5131            .sub(right.lower())
5132            .map_err(map_bigint_failure)?,
5133    )
5134    .map_err(|error| GeometryFailure::CalculusFailure {
5135        error: CalculusFailure::Interval(error),
5136    })
5137}
5138
5139pub(crate) fn dyadic_to_real(value: &Dyadic) -> Result<RealAlgebraic, GeometryFailure> {
5140    if value.is_zero() {
5141        return Ok(RealAlgebraic::from_integer(BigInt::zero())?);
5142    }
5143    let denominator = BigUint::one()
5144        .map_err(map_bigint_failure)?
5145        .shl_bits(value.exponent() as usize)
5146        .map_err(map_bigint_failure)?;
5147    let rational = RawRational::new(
5148        value.integer().try_clone().map_err(map_bigint_failure)?,
5149        denominator,
5150    )
5151    .reduce()
5152    .map_err(map_bigint_failure)?
5153    .into_reduced();
5154    RealAlgebraic::from_reduced_rational(&rational).map_err(GeometryFailure::AlgebraFailure)
5155}
5156
5157fn real_to_dyadic(value: &RealAlgebraic) -> Result<Dyadic, GeometryFailure> {
5158    let minimal = value.minimal_polynomial().polynomial();
5159    if minimal.degree() == Some(1) {
5160        let coefficients = minimal.coefficients();
5161        let mut numerator = coefficients[0].negated().map_err(map_bigint_failure)?;
5162        let leading = &coefficients[1];
5163        if matches!(leading.sign(), Sign::Negative) {
5164            numerator = numerator.negated().map_err(map_bigint_failure)?;
5165        }
5166        let denominator = leading.magnitude();
5167        let bit_len = denominator.bit_len();
5168        if bit_len > 0 && (0..bit_len - 1).all(|bit| !denominator.bit(bit)) {
5169            return Ok(Dyadic::new(numerator, (bit_len - 1) as u32));
5170        }
5171    }
5172    if value.is_zero() {
5173        return Ok(Dyadic::new(BigInt::zero(), 0));
5174    }
5175    if value.is_one() {
5176        return Ok(Dyadic::new(BigInt::one().map_err(map_bigint_failure)?, 0));
5177    }
5178    let sign = value.sign().map_err(GeometryFailure::AlgebraFailure)?;
5179    if matches!(sign, Sign::Negative) {
5180        let negative_one = BigInt::zero()
5181            .sub(&BigInt::one().map_err(map_bigint_failure)?)
5182            .map_err(map_bigint_failure)?;
5183        let magnitude = value.mul(&RealAlgebraic::from_integer(negative_one)?)?;
5184        let mut dyadic = real_to_dyadic(&magnitude)?;
5185        dyadic = Dyadic::new(
5186            dyadic.integer().negated().map_err(map_bigint_failure)?,
5187            dyadic.exponent(),
5188        );
5189        return Ok(dyadic);
5190    }
5191    let enclosure = value
5192        .enclose(0)
5193        .map_err(GeometryFailure::AlgebraFailure)?
5194        .enclosure()
5195        .try_clone()
5196        .map_err(map_bigint_failure)?;
5197    if enclosure.lower() == enclosure.upper() {
5198        return enclosure.lower().try_clone().map_err(map_bigint_failure);
5199    }
5200    Err(GeometryFailure::EvaluationIndeterminacy {
5201        family: crate::types::ShapeFamily::ParametricCurve,
5202        reason: crate::types::ShapeEvaluationIndeterminacy::DomainValidity,
5203    })
5204}
5205
5206fn map_bigint_failure(error: BigintError) -> GeometryFailure {
5207    GeometryFailure::CalculusFailure {
5208        error: CalculusFailure::Polynomial(PolynomialFailure::Arithmetic(error)),
5209    }
5210}
5211
5212fn map_calculus_failure(error: CalculusFailure) -> GeometryFailure {
5213    GeometryFailure::CalculusFailure { error }
5214}
5215
5216fn calculus_polynomial_failure(error: PolynomialFailure) -> GeometryFailure {
5217    GeometryFailure::CalculusFailure {
5218        error: CalculusFailure::Polynomial(error),
5219    }
5220}
5221
5222fn opposite_nonzero(left: Sign, right: Sign) -> bool {
5223    matches!(
5224        (left, right),
5225        (Sign::Negative, Sign::Positive) | (Sign::Positive, Sign::Negative)
5226    )
5227}
5228
5229fn root_sign(sign: Sign) -> RootSign {
5230    match sign {
5231        Sign::Negative => RootSign::Negative,
5232        Sign::Positive => RootSign::Positive,
5233        Sign::Zero => RootSign::Zero,
5234    }
5235}
5236
5237fn constraint_support_id(constraint: &IntersectionConstraint) -> String {
5238    format!(
5239        "{}|{}",
5240        operand_support_id(constraint.left_operand()),
5241        operand_support_id(constraint.right_operand())
5242    )
5243}
5244
5245fn constraint_chart_id(constraint: &IntersectionConstraint) -> String {
5246    format!(
5247        "{}|{}",
5248        operand_chart_id(constraint.left_operand()),
5249        operand_chart_id(constraint.right_operand())
5250    )
5251}
5252
5253fn operand_support_id(operand: &IntersectionOperand) -> String {
5254    match operand {
5255        IntersectionOperand::Declaration(value) => format!("declaration-{:?}", value.family()),
5256        IntersectionOperand::Evaluated(value) => format!("evaluated-{:?}", value),
5257    }
5258}
5259
5260fn operand_chart_id(operand: &IntersectionOperand) -> String {
5261    match operand {
5262        IntersectionOperand::Declaration(value) => format!("chart-{:?}", value.family()),
5263        IntersectionOperand::Evaluated(value) => format!("evaluation-{:?}", value),
5264    }
5265}
5266
5267fn curve_expression(value: &crate::types::ParametricCurveDeclaration) -> String {
5268    format!("curve-domain:{}", value.chart_domain())
5269}
5270
5271fn surface_expression(value: &crate::types::ParametricSurfaceDeclaration) -> String {
5272    format!("surface-domain:{}", value.chart().display_name().as_str())
5273}
5274
5275fn implicit_expression(value: &crate::types::ImplicitSurfaceDeclaration) -> String {
5276    format!("implicit-terms:{}", value.equation().terms().len())
5277}
5278
5279fn interval_bounds(
5280    interval: &crate::types::ParameterInterval,
5281) -> Option<(RealAlgebraic, RealAlgebraic)> {
5282    Some((
5283        interval.lower().try_clone().ok()?,
5284        interval.upper().try_clone().ok()?,
5285    ))
5286}
5287
5288fn curve_polynomial(
5289    value: &crate::types::ParametricCurveDeclaration,
5290) -> Result<Option<Polynomial>, GeometryFailure> {
5291    let chart = match value.chart() {
5292        crate::types::CurveChart::Chart2(chart) => chart.numerator_x(),
5293        crate::types::CurveChart::Chart3(chart) => chart.numerator_x(),
5294    };
5295    let coefficients = chart
5296        .to_real_algebraic_coefficients()
5297        .map_err(|error| GeometryFailure::CalculusFailure {
5298            error: CalculusFailure::Polynomial(PolynomialFailure::Algebra(error)),
5299        })?
5300        .into_coefficients();
5301    if coefficients.is_empty() {
5302        return Ok(Some(
5303            Polynomial::zero().map_err(calculus_polynomial_failure)?,
5304        ));
5305    }
5306    Ok(Some(
5307        Polynomial::from_coefficients(coefficients).map_err(calculus_polynomial_failure)?,
5308    ))
5309}
5310
5311fn implicit_polynomial(
5312    value: &crate::types::ImplicitSurfaceDeclaration,
5313) -> Result<Option<Polynomial>, GeometryFailure> {
5314    let mut coefficients = Vec::new();
5315    for term in value.equation().terms() {
5316        if term.exponent_y() != 0 || term.exponent_z() != 0 {
5317            return Ok(None);
5318        }
5319        while coefficients.len() <= term.exponent_x() as usize {
5320            coefficients.push(RealAlgebraic::from_integer(BigInt::zero())?);
5321        }
5322        coefficients[term.exponent_x() as usize] = term.coefficient().try_clone()?;
5323    }
5324    if coefficients.is_empty() {
5325        return Ok(Some(
5326            Polynomial::zero().map_err(calculus_polynomial_failure)?,
5327        ));
5328    }
5329    Ok(Some(
5330        Polynomial::from_coefficients(coefficients).map_err(calculus_polynomial_failure)?,
5331    ))
5332}
5333
5334fn clone_declaration(value: &ShapeDeclaration) -> Result<ShapeDeclaration, GeometryFailure> {
5335    match value {
5336        ShapeDeclaration::ParametricCurve(value) => Ok(ShapeDeclaration::ParametricCurve(
5337            crate::types::ParametricCurveDeclaration::new(
5338                clone_curve_chart(value.chart())?,
5339                crate::types::ParameterInterval::new(
5340                    value.domain().lower().try_clone()?,
5341                    value.domain().upper().try_clone()?,
5342                    value.domain().lower_closed(),
5343                    value.domain().upper_closed(),
5344                )?,
5345            ),
5346        )),
5347        ShapeDeclaration::ParametricSurface(value) => Ok(ShapeDeclaration::ParametricSurface(
5348            crate::types::ParametricSurfaceDeclaration::new(
5349                clone_surface_chart(value.chart())?,
5350                crate::types::SurfaceParameterDomain::new(
5351                    clone_interval(value.domain().u())?,
5352                    clone_interval(value.domain().v())?,
5353                ),
5354            ),
5355        )),
5356        ShapeDeclaration::ImplicitSurface(value) => Ok(ShapeDeclaration::ImplicitSurface(
5357            crate::types::ImplicitSurfaceDeclaration::new(clone_polynomial3(value.equation())?),
5358        )),
5359    }
5360}
5361
5362fn clone_curve_chart(
5363    value: &crate::types::CurveChart,
5364) -> Result<crate::types::CurveChart, GeometryFailure> {
5365    match value {
5366        crate::types::CurveChart::Chart2(chart) => Ok(crate::types::CurveChart::Chart2(
5367            neco_geometry_foundation::ChartDefinition2::new(
5368                chart.domain_id().try_clone()?,
5369                chart.display_name().try_clone()?,
5370                chart.coefficients().try_clone()?,
5371                chart.numerator_x().try_clone()?,
5372                chart.numerator_y().try_clone()?,
5373                chart.denominator().try_clone()?,
5374            )?,
5375        )),
5376        crate::types::CurveChart::Chart3(chart) => {
5377            Ok(crate::types::CurveChart::Chart3(clone_chart3(chart)?))
5378        }
5379    }
5380}
5381
5382fn clone_surface_chart(
5383    chart: &crate::types::ParametricSurfaceChart2,
5384) -> Result<crate::types::ParametricSurfaceChart2, GeometryFailure> {
5385    crate::types::ParametricSurfaceChart2::try_new(
5386        chart.identity().domain_id().try_clone()?,
5387        chart.display_name().try_clone()?,
5388        chart.identity().version(),
5389        chart.orientation(),
5390        crate::evaluation::clone_rational_surface(chart.surface())?,
5391    )
5392}
5393
5394fn clone_chart3(
5395    chart: &neco_geometry_foundation::ChartDefinition3,
5396) -> Result<neco_geometry_foundation::ChartDefinition3, GeometryFailure> {
5397    Ok(neco_geometry_foundation::ChartDefinition3::new(
5398        chart.domain_id().try_clone()?,
5399        chart.display_name().try_clone()?,
5400        chart.coefficients().try_clone()?,
5401        chart.numerator_x().try_clone()?,
5402        chart.numerator_y().try_clone()?,
5403        chart.numerator_z().try_clone()?,
5404        chart.denominator().try_clone()?,
5405    )?)
5406}
5407
5408fn clone_interval(
5409    value: &crate::types::ParameterInterval,
5410) -> Result<crate::types::ParameterInterval, GeometryFailure> {
5411    crate::types::ParameterInterval::new(
5412        value.lower().try_clone()?,
5413        value.upper().try_clone()?,
5414        value.lower_closed(),
5415        value.upper_closed(),
5416    )
5417}
5418
5419fn clone_polynomial3(
5420    value: &crate::types::MultivariatePolynomial3,
5421) -> Result<crate::types::MultivariatePolynomial3, GeometryFailure> {
5422    let terms = value
5423        .terms()
5424        .iter()
5425        .map(|term| {
5426            crate::types::PolynomialTerm3::new(
5427                term.coefficient().try_clone()?,
5428                term.exponent_x(),
5429                term.exponent_y(),
5430                term.exponent_z(),
5431            )
5432        })
5433        .collect::<Result<Vec<_>, _>>()?;
5434    crate::types::MultivariatePolynomial3::try_from_terms(terms)
5435}
5436
5437fn evaluate_declaration_capability(
5438    declaration: &ShapeDeclaration,
5439) -> Result<ShapeEvaluation, GeometryFailure> {
5440    match evaluate_shape(declaration_probe_request(declaration)?) {
5441        Ok(evaluation) => Ok(evaluation),
5442        Err(GeometryFailure::CalculusFailure {
5443            error: CalculusFailure::Polynomial(PolynomialFailure::EmptyCoefficients),
5444        }) => Ok(ShapeEvaluation::Undetermined {
5445            family: declaration.family(),
5446        }),
5447        Err(error) => Err(error),
5448    }
5449}
5450
5451fn declaration_probe_request(
5452    declaration: &ShapeDeclaration,
5453) -> Result<ShapeEvaluationRequest, GeometryFailure> {
5454    match declaration {
5455        ShapeDeclaration::ParametricCurve(value) => Ok(ShapeEvaluationRequest::new(
5456            clone_declaration(declaration)?,
5457            match value.chart() {
5458                crate::types::CurveChart::Chart2(_) | crate::types::CurveChart::Chart3(_) => {
5459                    crate::types::ShapeEvaluationInput::ParametricCurve {
5460                        parameter: value.domain().lower().try_clone()?,
5461                    }
5462                }
5463            },
5464        )),
5465        ShapeDeclaration::ParametricSurface(value) => Ok(ShapeEvaluationRequest::new(
5466            clone_declaration(declaration)?,
5467            crate::types::ShapeEvaluationInput::ParametricSurface {
5468                u: value.domain().u().lower().try_clone()?,
5469                v: value.domain().v().lower().try_clone()?,
5470            },
5471        )),
5472        ShapeDeclaration::ImplicitSurface(_) => Ok(ShapeEvaluationRequest::new(
5473            clone_declaration(declaration)?,
5474            crate::types::ShapeEvaluationInput::ImplicitSurface {
5475                point: Point3 {
5476                    x: RealAlgebraic::from_integer(BigInt::zero())?,
5477                    y: RealAlgebraic::from_integer(BigInt::zero())?,
5478                    z: RealAlgebraic::from_integer(BigInt::zero())?,
5479                },
5480            },
5481        )),
5482    }
5483}
5484
5485trait ChartDomain {
5486    fn chart_domain(&self) -> &str;
5487}
5488
5489impl ChartDomain for crate::types::ParametricCurveDeclaration {
5490    fn chart_domain(&self) -> &str {
5491        match self.chart() {
5492            crate::types::CurveChart::Chart2(chart) => chart.domain_id().as_str(),
5493            crate::types::CurveChart::Chart3(chart) => chart.domain_id().as_str(),
5494        }
5495    }
5496}
5497
5498trait SupportRelationExt {
5499    fn is_undetermined(&self) -> bool;
5500}
5501
5502impl SupportRelationExt for SupportRelation {
5503    fn is_undetermined(&self) -> bool {
5504        matches!(self, SupportRelation::Undetermined { .. })
5505    }
5506}
5507
5508#[cfg(test)]
5509mod tests {
5510    use super::*;
5511
5512    fn algebraic(value: i32) -> RealAlgebraic {
5513        RealAlgebraic::from_integer(BigInt::try_from(value).unwrap()).unwrap()
5514    }
5515
5516    fn unit_enclosure() -> Enclosure {
5517        Enclosure::new(
5518            Dyadic::new(BigInt::zero(), 0),
5519            Dyadic::new(BigInt::one().unwrap(), 0),
5520        )
5521        .unwrap()
5522    }
5523
5524    fn polynomial(coefficients: &[i32]) -> Polynomial {
5525        Polynomial::from_coefficients(coefficients.iter().map(|value| algebraic(*value)).collect())
5526            .unwrap()
5527    }
5528
5529    fn problem(polynomial: Polynomial) -> DerivedRootProblem {
5530        let operand = IntersectionOperand::Evaluated(ShapeEvaluation::Undetermined {
5531            family: crate::types::ShapeFamily::ParametricCurve,
5532        });
5533        DerivedRootProblem {
5534            constraint: IntersectionConstraint::new(
5535                operand,
5536                IntersectionOperand::Evaluated(ShapeEvaluation::Undetermined {
5537                    family: crate::types::ShapeFamily::ImplicitSurface,
5538                }),
5539                ResidualFunction::new(String::from("left"), String::from("right")),
5540                IntersectionDomain::new(
5541                    String::from("chart"),
5542                    String::from("domain"),
5543                    String::from("support"),
5544                ),
5545                SupportRelation::Finite {
5546                    evidence: SupportEvidence::EvaluatedSpatialCoordinates,
5547                },
5548                RankEvidence::Sufficient { rank: 1 },
5549            ),
5550            polynomial: Some(polynomial),
5551            domain: Some(unit_enclosure()),
5552        }
5553    }
5554
5555    fn policy(max_iterations: usize) -> RootIsolationPolicy {
5556        RootIsolationPolicy::new(
5557            max_iterations,
5558            RootRefinementMethod::Bisection,
5559            unit_enclosure(),
5560        )
5561        .unwrap()
5562    }
5563
5564    #[test]
5565    fn sign_change_with_derivative_zero_is_unresolved() {
5566        let polynomial = polynomial(&[-1, 36, -96, 64]);
5567        let enclosure = unit_enclosure();
5568        let derivative = polynomial.derivative(DerivativeOrder::new(1)).unwrap();
5569        assert!(derivative
5570            .evaluate_enclosure(&enclosure, ROOT_INTERVAL_PRECISION_BITS)
5571            .unwrap()
5572            .contains_zero());
5573        assert!(matches!(
5574            assess_partition_cell(
5575                &polynomial,
5576                &derivative,
5577                &enclosure,
5578                0,
5579                &DerivativeOrder::new(2),
5580                "test",
5581                &[],
5582            )
5583            .unwrap(),
5584            CellAssessment::Unresolved(PartitionUnresolvedReason::SignChangeUniqueness)
5585        ));
5586    }
5587
5588    #[test]
5589    fn exact_touch_pivot_keeps_distinct_root_region_pending() {
5590        let polynomial = polynomial(&[-3, 22, -52, 40]);
5591        let enclosure = unit_enclosure();
5592        let derivative = polynomial.derivative(DerivativeOrder::new(1)).unwrap();
5593        let assessment = assess_partition_cell(
5594            &polynomial,
5595            &derivative,
5596            &enclosure,
5597            0,
5598            &DerivativeOrder::new(8),
5599            "test",
5600            &[],
5601        )
5602        .unwrap();
5603        let pivot = match assessment {
5604            CellAssessment::ExactTouch { candidate, pivot } => {
5605                assert!(matches!(
5606                    candidate.evidence,
5607                    RootEvidence::EvenMultiplicityTouch { .. }
5608                ));
5609                pivot
5610            }
5611            _ => panic!("expected the exact touch pivot"),
5612        };
5613        let lower = Enclosure::new(
5614            enclosure.lower().try_clone().unwrap(),
5615            pivot.try_clone().unwrap(),
5616        )
5617        .unwrap();
5618        assert!(!matches!(
5619            assess_partition_cell(
5620                &polynomial,
5621                &derivative,
5622                &lower,
5623                1,
5624                &DerivativeOrder::new(8),
5625                "test",
5626                &[pivot],
5627            )
5628            .unwrap(),
5629            CellAssessment::RootFree
5630        ));
5631
5632        let root_problem = problem(polynomial);
5633        let candidates = enumerate_root_candidates(&root_problem, &policy(2)).unwrap();
5634        let isolation = build_root_isolation(&root_problem, candidates, &policy(2)).unwrap();
5635        assert!(
5636            isolation.brackets().len() >= 2
5637                || matches!(
5638                    isolation.completeness().status(),
5639                    WitnessStatus::Undetermined { .. }
5640                )
5641        );
5642    }
5643
5644    #[test]
5645    fn suppressed_exact_endpoint_is_not_repeated_as_candidate() {
5646        let root_problem = problem(polynomial(&[0, 0, 1]));
5647        let enumeration = enumerate_root_candidates(&root_problem, &policy(4)).unwrap();
5648        assert_eq!(enumeration.candidates.len(), 1);
5649        assert!(matches!(
5650            enumeration.candidates[0].evidence,
5651            RootEvidence::EvenMultiplicityTouch { .. }
5652        ));
5653    }
5654}