Skip to main content

neco_geometry/
boundary.rs

1use alloc::{format, string::String, vec, vec::Vec};
2use core::cmp::Ordering;
3
4use neco_algnum::RealAlgebraic;
5use neco_bigint::{BigInt, BigUint, BigintError, Dyadic, RawRational};
6use neco_calculus::{
7    expose_membership_transitions, expose_region_sign, CalculusFailure, DerivativeOrder, Enclosure,
8    MembershipJudgmentRequest as CalculusMembershipJudgmentRequest, MembershipTransitionReport,
9    Polynomial, PolynomialFailure, RegionSign, RegionSignJudgment,
10};
11use neco_geometry_foundation::{Point2, Point3};
12
13use crate::intersection::{
14    clone_rank_evidence, clone_residual_function, clone_root_evidence, clone_support_relation,
15};
16use crate::{
17    AlgebraicRegion, BoundaryResource, CanonicalAtom, ContactOrderKind, GeometryFailure,
18    IntersectionSet, MembershipClassification, RankEvidence, RegionFunction,
19    RegionMembershipRequest, RegionPoint, RegionPolynomial3, ResidualFunction, RootEvidence,
20    SignRelation, SupportRelation,
21};
22
23pub const MAX_BOUNDARY_CANDIDATE_LOCI: usize = 64;
24pub const MAX_BOUNDARY_CANDIDATE_PARAMETERS: usize = 4_096;
25pub const MAX_BOUNDARY_SIDE_SAMPLES: usize = 4_096;
26pub const MAX_BOUNDARY_INTERSECTIONS: usize = 16;
27pub const BOUNDARY_ZERO_EXCLUSION_PRECISION_BITS: u32 = 64;
28
29#[derive(Debug, Eq, PartialEq)]
30pub struct BoundaryTypes {
31    algebraic_boundary: AlgebraicBoundary,
32    stratification: BoundaryStratification,
33}
34impl BoundaryTypes {
35    pub fn algebraic_boundary(&self) -> &AlgebraicBoundary {
36        &self.algebraic_boundary
37    }
38    pub fn stratification(&self) -> &BoundaryStratification {
39        &self.stratification
40    }
41    pub fn into_parts(self) -> (AlgebraicBoundary, BoundaryStratification) {
42        (self.algebraic_boundary, self.stratification)
43    }
44}
45#[derive(Debug, Eq, PartialEq)]
46pub struct BoundaryAtomLocus {
47    atom_id: String,
48    zero_relation: SignRelation,
49    ambient_dimension: i64,
50}
51impl BoundaryAtomLocus {
52    pub fn atom_id(&self) -> &str {
53        &self.atom_id
54    }
55    pub fn zero_relation(&self) -> SignRelation {
56        self.zero_relation
57    }
58    pub fn ambient_dimension(&self) -> i64 {
59        self.ambient_dimension
60    }
61}
62#[derive(Debug, Eq, PartialEq)]
63pub enum BoundaryEvidenceStatus {
64    Proved,
65    Undetermined { reason: BoundaryUndeterminedReason },
66}
67#[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd)]
68pub enum BoundaryUndeterminedReason {
69    RestrictedRationalDenominatorNotProvedNonzero,
70    FormulaSensitiveTransitionNotProved,
71    FormulaInsensitiveCandidatesOmitted,
72    StrataEvidenceLocal,
73    DisjointnessNotEstablished,
74    IntersectionEvidenceUnresolved,
75    ActiveAtomDimensionEvidenceInsufficient,
76}
77#[derive(Clone, Copy, Debug, Eq, PartialEq)]
78pub enum BoundaryEvidenceSource {
79    ExactChartLocalCalculusAndRegionMembership,
80}
81#[derive(Debug, Eq, PartialEq)]
82pub struct BoundaryTransitionWitness {
83    atom_id: String,
84    candidate_count: usize,
85    inside_side_observed: bool,
86    outside_side_observed: bool,
87    evidence_source: BoundaryEvidenceSource,
88}
89impl BoundaryTransitionWitness {
90    pub fn atom_id(&self) -> &str {
91        &self.atom_id
92    }
93    pub fn candidate_count(&self) -> usize {
94        self.candidate_count
95    }
96    pub fn inside_side_observed(&self) -> bool {
97        self.inside_side_observed
98    }
99    pub fn outside_side_observed(&self) -> bool {
100        self.outside_side_observed
101    }
102    pub fn evidence_source(&self) -> BoundaryEvidenceSource {
103        self.evidence_source
104    }
105}
106#[derive(Debug, Eq, PartialEq)]
107pub enum BoundaryLocalEvidence {
108    Proved {
109        sign_judgment: RegionSignJudgment,
110        transition_report: MembershipTransitionReport,
111        witness: BoundaryTransitionWitness,
112    },
113    Undetermined {
114        reason: BoundaryUndeterminedReason,
115        sign_judgment: Option<RegionSignJudgment>,
116        transition_report: Option<MembershipTransitionReport>,
117    },
118}
119#[derive(Debug, Eq, PartialEq, Ord, PartialOrd)]
120pub enum BoundaryStratumDimension {
121    Dimension(i64),
122    UndeterminedDimension { reason: BoundaryUndeterminedReason },
123}
124#[derive(Clone, Copy, Debug, Eq, PartialEq)]
125pub enum IntersectionEvidenceKind {
126    Empty,
127    Point,
128    FinitePoints,
129    Curve,
130    CurveBranches,
131    Coincident,
132    Undetermined,
133}
134#[derive(Debug, Eq, PartialEq)]
135pub struct BoundaryBranchEvidence {
136    branch_id: String,
137    chart_id: String,
138    support_id: String,
139    contact_order: usize,
140    contact_kind: ContactOrderKind,
141}
142impl BoundaryBranchEvidence {
143    pub fn branch_id(&self) -> &str {
144        &self.branch_id
145    }
146    pub fn chart_id(&self) -> &str {
147        &self.chart_id
148    }
149    pub fn support_id(&self) -> &str {
150        &self.support_id
151    }
152    pub fn contact_order(&self) -> usize {
153        self.contact_order
154    }
155    pub fn contact_kind(&self) -> ContactOrderKind {
156        self.contact_kind
157    }
158}
159#[derive(Debug, Eq, PartialEq)]
160pub struct BoundaryRootEvidence {
161    lower: RealAlgebraic,
162    upper: RealAlgebraic,
163    sign_change: bool,
164    contact_order: usize,
165    contact_kind: ContactOrderKind,
166    evidence: RootEvidence,
167}
168impl BoundaryRootEvidence {
169    pub fn lower(&self) -> &RealAlgebraic {
170        &self.lower
171    }
172    pub fn upper(&self) -> &RealAlgebraic {
173        &self.upper
174    }
175    pub fn sign_change(&self) -> bool {
176        self.sign_change
177    }
178    pub fn contact_order(&self) -> usize {
179        self.contact_order
180    }
181    pub fn contact_kind(&self) -> ContactOrderKind {
182        self.contact_kind
183    }
184    pub fn evidence(&self) -> &RootEvidence {
185        &self.evidence
186    }
187}
188#[derive(Debug, Eq, PartialEq)]
189pub struct IntersectionEvidenceRef {
190    source_index: usize,
191    kind: IntersectionEvidenceKind,
192    branch_evidence: Vec<BoundaryBranchEvidence>,
193    root_evidence: Vec<BoundaryRootEvidence>,
194    support_relation: SupportRelation,
195    rank_evidence: RankEvidence,
196    residual_function: ResidualFunction,
197}
198impl IntersectionEvidenceRef {
199    pub fn source_index(&self) -> usize {
200        self.source_index
201    }
202    pub fn kind(&self) -> IntersectionEvidenceKind {
203        self.kind
204    }
205    pub fn branch_evidence(&self) -> &[BoundaryBranchEvidence] {
206        &self.branch_evidence
207    }
208    pub fn root_evidence(&self) -> &[BoundaryRootEvidence] {
209        &self.root_evidence
210    }
211    pub fn support_relation(&self) -> &SupportRelation {
212        &self.support_relation
213    }
214    pub fn rank_evidence(&self) -> &RankEvidence {
215        &self.rank_evidence
216    }
217    pub fn residual_function(&self) -> &ResidualFunction {
218        &self.residual_function
219    }
220}
221pub type BoundaryCandidateSet = Vec<BoundaryCandidate>;
222pub type BoundaryStratumSet = Vec<BoundaryStratum>;
223pub type StringSet = Vec<String>;
224pub type IntersectionEvidenceSet = Vec<IntersectionEvidenceRef>;
225#[derive(Debug, Eq, PartialEq)]
226pub struct BoundaryCandidate {
227    locus: BoundaryAtomLocus,
228    active_atom_ids: StringSet,
229    local_evidence: BoundaryLocalEvidence,
230    intersection_evidence: Option<IntersectionEvidenceRef>,
231}
232impl BoundaryCandidate {
233    pub fn locus(&self) -> &BoundaryAtomLocus {
234        &self.locus
235    }
236    pub fn active_atom_ids(&self) -> &[String] {
237        &self.active_atom_ids
238    }
239    pub fn local_evidence(&self) -> &BoundaryLocalEvidence {
240        &self.local_evidence
241    }
242    pub fn intersection_evidence(&self) -> Option<&IntersectionEvidenceRef> {
243        self.intersection_evidence.as_ref()
244    }
245}
246#[derive(Debug, Eq, PartialEq)]
247pub struct BoundaryCoverageEvidence {
248    supplied_candidate_count: usize,
249    retained_candidate_count: usize,
250    omitted_candidate_count: usize,
251    status: BoundaryEvidenceStatus,
252}
253impl BoundaryCoverageEvidence {
254    pub fn supplied_candidate_count(&self) -> usize {
255        self.supplied_candidate_count
256    }
257    pub fn retained_candidate_count(&self) -> usize {
258        self.retained_candidate_count
259    }
260    pub fn omitted_candidate_count(&self) -> usize {
261        self.omitted_candidate_count
262    }
263    pub fn status(&self) -> &BoundaryEvidenceStatus {
264        &self.status
265    }
266}
267#[derive(Debug, Eq, PartialEq)]
268pub struct AlgebraicBoundary {
269    ambient_dimension: i64,
270    source_region: AlgebraicRegion,
271    candidate_loci: BoundaryCandidateSet,
272    retained_loci: BoundaryCandidateSet,
273    coverage_evidence: BoundaryCoverageEvidence,
274}
275impl AlgebraicBoundary {
276    pub fn ambient_dimension(&self) -> i64 {
277        self.ambient_dimension
278    }
279    pub fn source_region(&self) -> &AlgebraicRegion {
280        &self.source_region
281    }
282    pub fn candidate_loci(&self) -> &[BoundaryCandidate] {
283        &self.candidate_loci
284    }
285    pub fn retained_loci(&self) -> &[BoundaryCandidate] {
286        &self.retained_loci
287    }
288    pub fn coverage_evidence(&self) -> &BoundaryCoverageEvidence {
289        &self.coverage_evidence
290    }
291}
292#[derive(Debug, Eq, PartialEq)]
293pub struct StratificationEvidence {
294    dimension_partition_status: BoundaryEvidenceStatus,
295    disjointness_status: BoundaryEvidenceStatus,
296    source_evidence_count: usize,
297}
298impl StratificationEvidence {
299    pub fn dimension_partition_status(&self) -> &BoundaryEvidenceStatus {
300        &self.dimension_partition_status
301    }
302    pub fn disjointness_status(&self) -> &BoundaryEvidenceStatus {
303        &self.disjointness_status
304    }
305    pub fn source_evidence_count(&self) -> usize {
306        self.source_evidence_count
307    }
308}
309#[derive(Debug, Eq, PartialEq)]
310pub struct BoundaryStratum {
311    stratum_id: String,
312    dimension: BoundaryStratumDimension,
313    active_atom_ids: StringSet,
314    candidates: BoundaryCandidateSet,
315    local_evidence: BoundaryLocalEvidence,
316    source_intersections: IntersectionEvidenceSet,
317}
318impl BoundaryStratum {
319    pub fn stratum_id(&self) -> &str {
320        &self.stratum_id
321    }
322    pub fn dimension(&self) -> &BoundaryStratumDimension {
323        &self.dimension
324    }
325    pub fn active_atom_ids(&self) -> &[String] {
326        &self.active_atom_ids
327    }
328    pub fn candidates(&self) -> &[BoundaryCandidate] {
329        &self.candidates
330    }
331    pub fn local_evidence(&self) -> &BoundaryLocalEvidence {
332        &self.local_evidence
333    }
334    pub fn source_intersections(&self) -> &[IntersectionEvidenceRef] {
335        &self.source_intersections
336    }
337}
338#[derive(Debug, Eq, PartialEq)]
339#[must_use]
340pub struct BoundaryStratification {
341    ambient_dimension: i64,
342    boundary: AlgebraicBoundary,
343    strata: BoundaryStratumSet,
344    stratification_evidence: StratificationEvidence,
345}
346impl BoundaryStratification {
347    pub fn ambient_dimension(&self) -> i64 {
348        self.ambient_dimension
349    }
350    pub fn boundary(&self) -> &AlgebraicBoundary {
351        &self.boundary
352    }
353    pub fn strata(&self) -> &[BoundaryStratum] {
354        &self.strata
355    }
356    pub fn stratification_evidence(&self) -> &StratificationEvidence {
357        &self.stratification_evidence
358    }
359}
360#[derive(Debug, Eq, PartialEq)]
361pub struct BoundaryRestrictionChart {
362    chart_id: String,
363    parameter_enclosure: Enclosure,
364    coordinate_x: Polynomial,
365    coordinate_y: Polynomial,
366    coordinate_z: Polynomial,
367}
368impl BoundaryRestrictionChart {
369    pub fn try_new(
370        chart_id: impl Into<String>,
371        parameter_enclosure: Enclosure,
372        coordinate_x: Polynomial,
373        coordinate_y: Polynomial,
374        coordinate_z: Polynomial,
375    ) -> Result<Self, GeometryFailure> {
376        let chart_id = chart_id.into();
377        if chart_id.is_empty() {
378            return Err(GeometryFailure::MalformedRegionFormula);
379        }
380        Ok(Self {
381            chart_id,
382            parameter_enclosure,
383            coordinate_x,
384            coordinate_y,
385            coordinate_z,
386        })
387    }
388    pub fn chart_id(&self) -> &str {
389        &self.chart_id
390    }
391    pub fn parameter_enclosure(&self) -> &Enclosure {
392        &self.parameter_enclosure
393    }
394    pub fn coordinate_x(&self) -> &Polynomial {
395        &self.coordinate_x
396    }
397    pub fn coordinate_y(&self) -> &Polynomial {
398        &self.coordinate_y
399    }
400    pub fn coordinate_z(&self) -> &Polynomial {
401        &self.coordinate_z
402    }
403}
404#[derive(Debug, Eq, PartialEq)]
405pub struct BoundarySideSample {
406    parameter: Dyadic,
407}
408impl BoundarySideSample {
409    pub fn new(parameter: Dyadic) -> Self {
410        Self { parameter }
411    }
412    pub fn parameter(&self) -> &Dyadic {
413        &self.parameter
414    }
415}
416#[derive(Debug, Eq, PartialEq)]
417pub struct BoundaryIntersectionSelector {
418    intersection_index: usize,
419    branch_id: Option<String>,
420}
421impl BoundaryIntersectionSelector {
422    pub fn try_new(
423        intersection_index: usize,
424        branch_id: Option<String>,
425    ) -> Result<Self, GeometryFailure> {
426        if branch_id.as_ref().is_some_and(String::is_empty) {
427            return Err(GeometryFailure::MalformedRegionFormula);
428        }
429        Ok(Self {
430            intersection_index,
431            branch_id,
432        })
433    }
434    pub fn intersection_index(&self) -> usize {
435        self.intersection_index
436    }
437    pub fn branch_id(&self) -> Option<&str> {
438        self.branch_id.as_deref()
439    }
440}
441#[derive(Debug, Eq, PartialEq)]
442pub struct BoundaryCandidateSeed {
443    atom_id: String,
444    chart: BoundaryRestrictionChart,
445    candidate_parameters: Vec<Dyadic>,
446    side_samples: Vec<BoundarySideSample>,
447    intersection: Option<BoundaryIntersectionSelector>,
448}
449impl BoundaryCandidateSeed {
450    pub fn try_new(
451        atom_id: impl Into<String>,
452        chart: BoundaryRestrictionChart,
453        mut candidate_parameters: Vec<Dyadic>,
454        mut side_samples: Vec<BoundarySideSample>,
455        intersection: Option<BoundaryIntersectionSelector>,
456    ) -> Result<Self, GeometryFailure> {
457        let atom_id = atom_id.into();
458        if candidate_parameters.len() > MAX_BOUNDARY_CANDIDATE_PARAMETERS {
459            return Err(GeometryFailure::BoundaryResourceLimit {
460                resource: BoundaryResource::CandidateParameters,
461                requested: candidate_parameters.len(),
462                maximum: MAX_BOUNDARY_CANDIDATE_PARAMETERS,
463            });
464        }
465        if side_samples.len() > MAX_BOUNDARY_SIDE_SAMPLES {
466            return Err(GeometryFailure::BoundaryResourceLimit {
467                resource: BoundaryResource::SideSamples,
468                requested: side_samples.len(),
469                maximum: MAX_BOUNDARY_SIDE_SAMPLES,
470            });
471        }
472        if atom_id.is_empty()
473            || candidate_parameters.is_empty()
474            || candidate_parameters
475                .iter()
476                .any(|p| !chart.parameter_enclosure.contains(p))
477            || side_samples
478                .iter()
479                .any(|p| !chart.parameter_enclosure.contains(&p.parameter))
480        {
481            return Err(GeometryFailure::MalformedRegionFormula);
482        }
483        candidate_parameters.sort();
484        side_samples.sort_by(|left, right| left.parameter.cmp(&right.parameter));
485        if candidate_parameters
486            .windows(2)
487            .any(|pair| pair[0] == pair[1])
488            || side_samples
489                .windows(2)
490                .any(|pair| pair[0].parameter == pair[1].parameter)
491        {
492            return Err(GeometryFailure::MalformedRegionFormula);
493        }
494        Ok(Self {
495            atom_id,
496            chart,
497            candidate_parameters,
498            side_samples,
499            intersection,
500        })
501    }
502    pub fn atom_id(&self) -> &str {
503        &self.atom_id
504    }
505    pub fn chart(&self) -> &BoundaryRestrictionChart {
506        &self.chart
507    }
508    pub fn candidate_parameters(&self) -> &[Dyadic] {
509        &self.candidate_parameters
510    }
511    pub fn side_samples(&self) -> &[BoundarySideSample] {
512        &self.side_samples
513    }
514    pub fn intersection(&self) -> Option<&BoundaryIntersectionSelector> {
515        self.intersection.as_ref()
516    }
517}
518
519fn compare_candidate_seeds(
520    left: &BoundaryCandidateSeed,
521    right: &BoundaryCandidateSeed,
522) -> Ordering {
523    left.atom_id
524        .cmp(&right.atom_id)
525        .then_with(|| left.chart.chart_id.cmp(&right.chart.chart_id))
526        .then_with(|| left.candidate_parameters.cmp(&right.candidate_parameters))
527        .then_with(|| {
528            left.side_samples
529                .iter()
530                .map(|sample| &sample.parameter)
531                .cmp(right.side_samples.iter().map(|sample| &sample.parameter))
532        })
533        .then_with(|| match (&left.intersection, &right.intersection) {
534            (Some(left), Some(right)) => left
535                .intersection_index
536                .cmp(&right.intersection_index)
537                .then_with(|| left.branch_id.cmp(&right.branch_id)),
538            (None, Some(_)) => Ordering::Less,
539            (Some(_), None) => Ordering::Greater,
540            (None, None) => Ordering::Equal,
541        })
542}
543#[derive(Debug, Eq, PartialEq)]
544pub struct BoundaryDerivationRequest {
545    pub region: AlgebraicRegion,
546    pub intersections: Vec<IntersectionSet>,
547    pub candidate_loci: Vec<BoundaryCandidateSeed>,
548    pub max_order: DerivativeOrder,
549}
550
551struct RestrictedAtomFunction {
552    numerator: Polynomial,
553    denominator: Option<Polynomial>,
554}
555
556pub fn derive_boundary(
557    request: BoundaryDerivationRequest,
558) -> Result<BoundaryTypes, GeometryFailure> {
559    let BoundaryDerivationRequest {
560        region,
561        intersections,
562        mut candidate_loci,
563        max_order,
564    } = request;
565    if candidate_loci.len() > MAX_BOUNDARY_CANDIDATE_LOCI {
566        return Err(GeometryFailure::BoundaryResourceLimit {
567            resource: BoundaryResource::CandidateLoci,
568            requested: candidate_loci.len(),
569            maximum: MAX_BOUNDARY_CANDIDATE_LOCI,
570        });
571    }
572    if intersections.len() > MAX_BOUNDARY_INTERSECTIONS {
573        return Err(GeometryFailure::BoundaryResourceLimit {
574            resource: BoundaryResource::Intersections,
575            requested: intersections.len(),
576            maximum: MAX_BOUNDARY_INTERSECTIONS,
577        });
578    }
579    candidate_loci.sort_by(compare_candidate_seeds);
580    let ambient = region.ambient_dimension();
581    let source = clone_region(&region)?;
582    let mut all = Vec::with_capacity(candidate_loci.len());
583    let mut retained = Vec::with_capacity(candidate_loci.len());
584    for seed in candidate_loci {
585        let atom = region
586            .canonical_atoms()
587            .binary_search_by(|atom| atom.atom_id().cmp(seed.atom_id()))
588            .map(|index| &region.canonical_atoms()[index])
589            .map_err(|_| GeometryFailure::MalformedRegionFormula)?;
590        let evidence = match seed.intersection() {
591            Some(selector) => Some(snapshot_selector(&intersections, selector)?),
592            None => None,
593        };
594        let restricted = restrict_atom_to_chart(atom, seed.chart())?;
595        let sign_request = make_calculus_judgment_request(
596            restricted.numerator,
597            seed.chart(),
598            seed.candidate_parameters(),
599            max_order,
600        )?;
601        let sign = expose_region_sign(&sign_request).map_err(calculus_failure)?;
602        let report = expose_membership_transitions(&sign_request).map_err(calculus_failure)?;
603        let denominator_valid = if let Some(denominator) = restricted.denominator {
604            let request = make_calculus_judgment_request(
605                denominator,
606                seed.chart(),
607                seed.candidate_parameters(),
608                max_order,
609            )?;
610            matches!(
611                expose_region_sign(&request)
612                    .map_err(calculus_failure)?
613                    .sign(),
614                RegionSign::ConstantPositive | RegionSign::ConstantNegative
615            )
616        } else {
617            true
618        };
619        let mut candidates_zero = true;
620        let mut active = Vec::new();
621        for parameter in seed.candidate_parameters() {
622            let result = membership_at(&region, seed.chart(), parameter)?;
623            let selected = atom_relation(&result.atom_signs, seed.atom_id())?;
624            candidates_zero &= selected == SignRelation::Zero;
625            for value in result.atom_signs {
626                if value.relation == SignRelation::Zero {
627                    active.push(value.atom_id)
628                }
629            }
630        }
631        active.sort();
632        active.dedup();
633        let mut inside = None;
634        let mut outside = None;
635        for sample in seed.side_samples() {
636            let result = membership_at(&region, seed.chart(), sample.parameter())?;
637            let relation = atom_relation(&result.atom_signs, seed.atom_id())?;
638            match result.classification {
639                MembershipClassification::Inside => {
640                    if inside.is_none() {
641                        inside = Some(relation)
642                    }
643                }
644                MembershipClassification::Outside => {
645                    if outside.is_none() {
646                        outside = Some(relation)
647                    }
648                }
649                MembershipClassification::Boundary => {}
650            }
651        }
652        let opposite = matches!(
653            (inside, outside),
654            (Some(SignRelation::Positive), Some(SignRelation::Negative))
655                | (Some(SignRelation::Negative), Some(SignRelation::Positive))
656        );
657        let transitioned = report
658            .loci()
659            .iter()
660            .any(|l| matches!(l.kind(), neco_calculus::MembershipLocusKind::Transition));
661        let proved = candidates_zero
662            && denominator_valid
663            && inside.is_some()
664            && outside.is_some()
665            && opposite
666            && transitioned
667            && intersection_proves(evidence.as_ref());
668        let local = if proved {
669            BoundaryLocalEvidence::Proved {
670                sign_judgment: sign,
671                transition_report: report,
672                witness: BoundaryTransitionWitness {
673                    atom_id: String::from(seed.atom_id()),
674                    candidate_count: seed.candidate_parameters().len(),
675                    inside_side_observed: inside.is_some(),
676                    outside_side_observed: outside.is_some(),
677                    evidence_source:
678                        BoundaryEvidenceSource::ExactChartLocalCalculusAndRegionMembership,
679                },
680            }
681        } else {
682            let reason = if !denominator_valid {
683                BoundaryUndeterminedReason::RestrictedRationalDenominatorNotProvedNonzero
684            } else {
685                BoundaryUndeterminedReason::FormulaSensitiveTransitionNotProved
686            };
687            BoundaryLocalEvidence::Undetermined {
688                reason,
689                sign_judgment: Some(sign),
690                transition_report: Some(report),
691            }
692        };
693        let candidate = BoundaryCandidate {
694            locus: BoundaryAtomLocus {
695                atom_id: String::from(seed.atom_id()),
696                zero_relation: SignRelation::Zero,
697                ambient_dimension: ambient,
698            },
699            active_atom_ids: active,
700            local_evidence: local,
701            intersection_evidence: evidence,
702        };
703        let keep = !matches!(
704            candidate.local_evidence,
705            BoundaryLocalEvidence::Undetermined { .. }
706        ) || candidates_zero;
707        if keep {
708            retained.push(clone_candidate(&candidate)?)
709        }
710        all.push(candidate);
711    }
712    let coverage = BoundaryCoverageEvidence {
713        supplied_candidate_count: all.len(),
714        retained_candidate_count: retained.len(),
715        omitted_candidate_count: all.len() - retained.len(),
716        status: if all.len() == retained.len() {
717            BoundaryEvidenceStatus::Proved
718        } else {
719            BoundaryEvidenceStatus::Undetermined {
720                reason: BoundaryUndeterminedReason::FormulaInsensitiveCandidatesOmitted,
721            }
722        },
723    };
724    let boundary = AlgebraicBoundary {
725        ambient_dimension: ambient,
726        source_region: source,
727        candidate_loci: all,
728        retained_loci: retained,
729        coverage_evidence: coverage,
730    };
731    let strata = make_strata(&boundary)?;
732    let strat_boundary = clone_boundary(&boundary)?;
733    Ok(BoundaryTypes {
734        algebraic_boundary: boundary,
735        stratification: BoundaryStratification {
736            ambient_dimension: ambient,
737            boundary: strat_boundary,
738            strata,
739            stratification_evidence: StratificationEvidence {
740                dimension_partition_status: BoundaryEvidenceStatus::Undetermined {
741                    reason: BoundaryUndeterminedReason::StrataEvidenceLocal,
742                },
743                disjointness_status: BoundaryEvidenceStatus::Undetermined {
744                    reason: BoundaryUndeterminedReason::DisjointnessNotEstablished,
745                },
746                source_evidence_count: intersections.len(),
747            },
748        },
749    })
750}
751
752fn restrict_atom_to_chart(
753    atom: &CanonicalAtom,
754    chart: &BoundaryRestrictionChart,
755) -> Result<RestrictedAtomFunction, GeometryFailure> {
756    match atom.function() {
757        RegionFunction::Polynomial(p) => Ok(RestrictedAtomFunction {
758            numerator: compose(p, chart)?,
759            denominator: None,
760        }),
761        RegionFunction::RationalFunction(r) => Ok(RestrictedAtomFunction {
762            numerator: compose(r.numerator(), chart)?,
763            denominator: Some(compose(r.denominator(), chart)?),
764        }),
765    }
766}
767fn make_calculus_judgment_request(
768    target: Polynomial,
769    chart: &BoundaryRestrictionChart,
770    candidates: &[Dyadic],
771    max_order: DerivativeOrder,
772) -> Result<CalculusMembershipJudgmentRequest, GeometryFailure> {
773    CalculusMembershipJudgmentRequest::new(
774        target,
775        clone_enclosure(chart.parameter_enclosure())?,
776        clone_dyadics(candidates)?,
777        max_order,
778        BOUNDARY_ZERO_EXCLUSION_PRECISION_BITS,
779    )
780    .map_err(|error| calculus_failure(CalculusFailure::Root(error)))
781}
782fn compose(
783    p: &RegionPolynomial3,
784    chart: &BoundaryRestrictionChart,
785) -> Result<Polynomial, GeometryFailure> {
786    let mut acc = zero_poly()?;
787    for term in p.terms() {
788        let mut value = constant(term.coefficient())?;
789        value = mul_poly(&value, &power(chart.coordinate_x(), term.exponent_x())?)?;
790        value = mul_poly(&value, &power(chart.coordinate_y(), term.exponent_y())?)?;
791        value = mul_poly(&value, &power(chart.coordinate_z(), term.exponent_z())?)?;
792        acc = add_poly(&acc, &value)?;
793    }
794    Ok(acc)
795}
796fn zero_poly() -> Result<Polynomial, GeometryFailure> {
797    Polynomial::zero().map_err(poly_failure)
798}
799fn constant(v: &RealAlgebraic) -> Result<Polynomial, GeometryFailure> {
800    Polynomial::constant(v.try_clone().map_err(GeometryFailure::AlgebraFailure)?)
801        .map_err(poly_failure)
802}
803fn add_poly(a: &Polynomial, b: &Polynomial) -> Result<Polynomial, GeometryFailure> {
804    let n = a.coefficients().len().max(b.coefficients().len());
805    let mut out = Vec::with_capacity(n);
806    for i in 0..n {
807        let x = coefficient(a, i)?;
808        let y = coefficient(b, i)?;
809        out.push(x.add(&y).map_err(GeometryFailure::AlgebraFailure)?)
810    }
811    Polynomial::from_coefficients(out).map_err(poly_failure)
812}
813fn mul_poly(a: &Polynomial, b: &Polynomial) -> Result<Polynomial, GeometryFailure> {
814    let mut out = Vec::with_capacity(a.coefficients().len() + b.coefficients().len() - 1);
815    for _ in 0..a.coefficients().len() + b.coefficients().len() - 1 {
816        out.push(zero_algebraic()?)
817    }
818    for (i, x) in a.coefficients().iter().enumerate() {
819        for (j, y) in b.coefficients().iter().enumerate() {
820            let product = x.mul(y).map_err(GeometryFailure::AlgebraFailure)?;
821            out[i + j] = out[i + j]
822                .add(&product)
823                .map_err(GeometryFailure::AlgebraFailure)?;
824        }
825    }
826    Polynomial::from_coefficients(out).map_err(poly_failure)
827}
828fn power(p: &Polynomial, exponent: u32) -> Result<Polynomial, GeometryFailure> {
829    let mut base = clone_polynomial(p)?;
830    let mut result = constant_one()?;
831    let mut n = exponent;
832    while n > 0 {
833        if n & 1 == 1 {
834            result = mul_poly(&result, &base)?
835        }
836        n >>= 1;
837        if n > 0 {
838            base = mul_poly(&base, &base)?
839        }
840    }
841    Ok(result)
842}
843fn coefficient(p: &Polynomial, index: usize) -> Result<RealAlgebraic, GeometryFailure> {
844    match p.coefficients().get(index) {
845        Some(x) => x.try_clone().map_err(GeometryFailure::AlgebraFailure),
846        None => zero_algebraic(),
847    }
848}
849fn zero_algebraic() -> Result<RealAlgebraic, GeometryFailure> {
850    RealAlgebraic::from_integer(BigInt::zero()).map_err(GeometryFailure::AlgebraFailure)
851}
852fn constant_one() -> Result<Polynomial, GeometryFailure> {
853    Polynomial::constant(
854        RealAlgebraic::from_integer(BigInt::one().map_err(bigint_failure)?)
855            .map_err(GeometryFailure::AlgebraFailure)?,
856    )
857    .map_err(poly_failure)
858}
859fn membership_at(
860    region: &AlgebraicRegion,
861    chart: &BoundaryRestrictionChart,
862    p: &Dyadic,
863) -> Result<crate::RegionMembershipResult, GeometryFailure> {
864    let t = dyadic_to_real(p)?;
865    let x = chart.coordinate_x().evaluate(&t).map_err(poly_failure)?;
866    let y = chart.coordinate_y().evaluate(&t).map_err(poly_failure)?;
867    let point = if region.ambient_dimension() == 2 {
868        RegionPoint::Planar(Point2 { x, y })
869    } else {
870        RegionPoint::Spatial(Point3 {
871            x,
872            y,
873            z: chart.coordinate_z().evaluate(&t).map_err(poly_failure)?,
874        })
875    };
876    region.membership(RegionMembershipRequest {
877        region: clone_region(region)?,
878        point,
879    })
880}
881fn atom_relation(
882    values: &[crate::AtomSignResult],
883    id: &str,
884) -> Result<SignRelation, GeometryFailure> {
885    values
886        .iter()
887        .find(|v| v.atom_id == id)
888        .map(|v| v.relation)
889        .ok_or(GeometryFailure::MalformedRegionFormula)
890}
891fn snapshot_selector(
892    sets: &[IntersectionSet],
893    selector: &BoundaryIntersectionSelector,
894) -> Result<IntersectionEvidenceRef, GeometryFailure> {
895    let set = sets
896        .get(selector.intersection_index())
897        .ok_or(GeometryFailure::MalformedRegionFormula)?;
898    if let Some(id) = selector.branch_id() {
899        let matches = match set.component_view() {
900            crate::IntersectionComponentView::Components(mut entries) => entries.any(|entry| {
901                entry
902                    .evidence()
903                    .branch_identity()
904                    .is_some_and(|identity| identity.branch_id() == id)
905            }),
906            _ => false,
907        };
908        if !matches {
909            return Err(GeometryFailure::MalformedRegionFormula);
910        }
911    }
912    snapshot(set, selector.intersection_index())
913}
914fn snapshot(
915    set: &IntersectionSet,
916    index: usize,
917) -> Result<IntersectionEvidenceRef, GeometryFailure> {
918    let kind = match set.kind() {
919        crate::IntersectionKind::Empty => IntersectionEvidenceKind::Empty,
920        crate::IntersectionKind::Point => IntersectionEvidenceKind::Point,
921        crate::IntersectionKind::FinitePoints => IntersectionEvidenceKind::FinitePoints,
922        crate::IntersectionKind::Curve => IntersectionEvidenceKind::Curve,
923        crate::IntersectionKind::CurveBranches => IntersectionEvidenceKind::CurveBranches,
924        crate::IntersectionKind::Coincident => IntersectionEvidenceKind::Coincident,
925        crate::IntersectionKind::Undetermined => IntersectionEvidenceKind::Undetermined,
926    };
927    let witness = set.witness();
928    let branches = match set.component_view() {
929        crate::IntersectionComponentView::Components(entries) => entries
930            .filter_map(|entry| {
931                let evidence = entry.evidence();
932                Some(branch(
933                    evidence.branch_identity()?,
934                    evidence.contact_order()?,
935                ))
936            })
937            .collect(),
938        _ => Vec::new(),
939    };
940    let roots = witness
941        .root_isolation()
942        .brackets()
943        .iter()
944        .map(|b| {
945            Ok::<BoundaryRootEvidence, GeometryFailure>(BoundaryRootEvidence {
946                lower: b
947                    .lower()
948                    .try_clone()
949                    .map_err(GeometryFailure::AlgebraFailure)?,
950                upper: b
951                    .upper()
952                    .try_clone()
953                    .map_err(GeometryFailure::AlgebraFailure)?,
954                sign_change: b.sign_change(),
955                contact_order: b.contact_order().order(),
956                contact_kind: b.contact_order().kind(),
957                evidence: clone_root_evidence(b.evidence())?,
958            })
959        })
960        .collect::<Result<Vec<_>, _>>()?;
961    let c = witness.constraint();
962    Ok(IntersectionEvidenceRef {
963        source_index: index,
964        kind,
965        branch_evidence: branches,
966        root_evidence: roots,
967        support_relation: clone_support_relation(c.support_relation()),
968        rank_evidence: clone_rank_evidence(c.rank_evidence()),
969        residual_function: clone_residual_function(c.residual_function()),
970    })
971}
972fn branch(b: &crate::BranchIdentity, contact: &crate::ContactOrder) -> BoundaryBranchEvidence {
973    BoundaryBranchEvidence {
974        branch_id: String::from(b.branch_id()),
975        chart_id: String::from(b.chart_id()),
976        support_id: String::from(b.support_id()),
977        contact_order: contact.order(),
978        contact_kind: contact.kind(),
979    }
980}
981fn intersection_proves(evidence: Option<&IntersectionEvidenceRef>) -> bool {
982    !matches!(
983        evidence.map(IntersectionEvidenceRef::kind),
984        Some(IntersectionEvidenceKind::Coincident | IntersectionEvidenceKind::Undetermined)
985    )
986}
987fn dimension(c: &BoundaryCandidate) -> BoundaryStratumDimension {
988    match c
989        .intersection_evidence
990        .as_ref()
991        .map(IntersectionEvidenceRef::kind)
992    {
993        Some(IntersectionEvidenceKind::Point | IntersectionEvidenceKind::FinitePoints) => {
994            BoundaryStratumDimension::Dimension(0)
995        }
996        Some(IntersectionEvidenceKind::Curve | IntersectionEvidenceKind::CurveBranches) => {
997            BoundaryStratumDimension::Dimension(1)
998        }
999        Some(IntersectionEvidenceKind::Coincident | IntersectionEvidenceKind::Undetermined) => {
1000            BoundaryStratumDimension::UndeterminedDimension {
1001                reason: BoundaryUndeterminedReason::IntersectionEvidenceUnresolved,
1002            }
1003        }
1004        Some(IntersectionEvidenceKind::Empty) | None => {
1005            if c.active_atom_ids.len() == 1 {
1006                BoundaryStratumDimension::Dimension(c.locus.ambient_dimension - 1)
1007            } else {
1008                BoundaryStratumDimension::UndeterminedDimension {
1009                    reason: BoundaryUndeterminedReason::ActiveAtomDimensionEvidenceInsufficient,
1010                }
1011            }
1012        }
1013    }
1014}
1015fn make_strata(boundary: &AlgebraicBoundary) -> Result<Vec<BoundaryStratum>, GeometryFailure> {
1016    let mut strata = Vec::new();
1017    for (i, c) in boundary.retained_loci.iter().enumerate() {
1018        strata.push(BoundaryStratum {
1019            stratum_id: format!("boundary-stratum-{i}"),
1020            dimension: dimension(c),
1021            active_atom_ids: c.active_atom_ids.clone(),
1022            candidates: vec![clone_candidate(c)?],
1023            local_evidence: clone_local(&c.local_evidence)?,
1024            source_intersections: c
1025                .intersection_evidence
1026                .as_ref()
1027                .map(clone_intersection)
1028                .transpose()?
1029                .into_iter()
1030                .collect(),
1031        })
1032    }
1033    Ok(strata)
1034}
1035fn clone_region(r: &AlgebraicRegion) -> Result<AlgebraicRegion, GeometryFailure> {
1036    let atoms = r
1037        .canonical_atoms()
1038        .iter()
1039        .map(clone_atom)
1040        .collect::<Result<Vec<_>, _>>()?;
1041    AlgebraicRegion::try_new(
1042        r.ambient_dimension(),
1043        atoms,
1044        r.normalized_region_formula().clone(),
1045        r.region_kind(),
1046    )
1047}
1048fn clone_atom(a: &CanonicalAtom) -> Result<CanonicalAtom, GeometryFailure> {
1049    CanonicalAtom::try_new(a.atom_id(), a.function().try_clone()?, a.relation())
1050}
1051fn clone_candidate(c: &BoundaryCandidate) -> Result<BoundaryCandidate, GeometryFailure> {
1052    Ok(BoundaryCandidate {
1053        locus: BoundaryAtomLocus {
1054            atom_id: c.locus.atom_id.clone(),
1055            zero_relation: c.locus.zero_relation,
1056            ambient_dimension: c.locus.ambient_dimension,
1057        },
1058        active_atom_ids: c.active_atom_ids.clone(),
1059        local_evidence: clone_local(&c.local_evidence)?,
1060        intersection_evidence: c
1061            .intersection_evidence
1062            .as_ref()
1063            .map(clone_intersection)
1064            .transpose()?,
1065    })
1066}
1067fn clone_local(e: &BoundaryLocalEvidence) -> Result<BoundaryLocalEvidence, GeometryFailure> {
1068    Ok(match e {
1069        BoundaryLocalEvidence::Proved {
1070            sign_judgment,
1071            transition_report,
1072            witness,
1073        } => BoundaryLocalEvidence::Proved {
1074            sign_judgment: sign_judgment.clone(),
1075            transition_report: clone_report(transition_report),
1076            witness: BoundaryTransitionWitness {
1077                atom_id: witness.atom_id.clone(),
1078                candidate_count: witness.candidate_count,
1079                inside_side_observed: witness.inside_side_observed,
1080                outside_side_observed: witness.outside_side_observed,
1081                evidence_source: witness.evidence_source,
1082            },
1083        },
1084        BoundaryLocalEvidence::Undetermined {
1085            reason,
1086            sign_judgment,
1087            transition_report,
1088        } => BoundaryLocalEvidence::Undetermined {
1089            reason: *reason,
1090            sign_judgment: sign_judgment.clone(),
1091            transition_report: transition_report.as_ref().map(clone_report),
1092        },
1093    })
1094}
1095fn clone_report(r: &MembershipTransitionReport) -> MembershipTransitionReport {
1096    r.clone()
1097}
1098fn clone_intersection(
1099    e: &IntersectionEvidenceRef,
1100) -> Result<IntersectionEvidenceRef, GeometryFailure> {
1101    Ok(IntersectionEvidenceRef {
1102        source_index: e.source_index,
1103        kind: e.kind,
1104        branch_evidence: e
1105            .branch_evidence
1106            .iter()
1107            .map(|b| BoundaryBranchEvidence {
1108                branch_id: b.branch_id.clone(),
1109                chart_id: b.chart_id.clone(),
1110                support_id: b.support_id.clone(),
1111                contact_order: b.contact_order,
1112                contact_kind: b.contact_kind,
1113            })
1114            .collect(),
1115        root_evidence: e
1116            .root_evidence
1117            .iter()
1118            .map(|r| {
1119                Ok::<BoundaryRootEvidence, GeometryFailure>(BoundaryRootEvidence {
1120                    lower: r
1121                        .lower
1122                        .try_clone()
1123                        .map_err(GeometryFailure::AlgebraFailure)?,
1124                    upper: r
1125                        .upper
1126                        .try_clone()
1127                        .map_err(GeometryFailure::AlgebraFailure)?,
1128                    sign_change: r.sign_change,
1129                    contact_order: r.contact_order,
1130                    contact_kind: r.contact_kind,
1131                    evidence: clone_root_evidence(&r.evidence)?,
1132                })
1133            })
1134            .collect::<Result<Vec<_>, _>>()?,
1135        support_relation: clone_support_relation(&e.support_relation),
1136        rank_evidence: clone_rank_evidence(&e.rank_evidence),
1137        residual_function: clone_residual_function(&e.residual_function),
1138    })
1139}
1140fn clone_boundary(b: &AlgebraicBoundary) -> Result<AlgebraicBoundary, GeometryFailure> {
1141    Ok(AlgebraicBoundary {
1142        ambient_dimension: b.ambient_dimension,
1143        source_region: clone_region(&b.source_region)?,
1144        candidate_loci: b
1145            .candidate_loci
1146            .iter()
1147            .map(clone_candidate)
1148            .collect::<Result<Vec<_>, _>>()?,
1149        retained_loci: b
1150            .retained_loci
1151            .iter()
1152            .map(clone_candidate)
1153            .collect::<Result<Vec<_>, _>>()?,
1154        coverage_evidence: BoundaryCoverageEvidence {
1155            supplied_candidate_count: b.coverage_evidence.supplied_candidate_count,
1156            retained_candidate_count: b.coverage_evidence.retained_candidate_count,
1157            omitted_candidate_count: b.coverage_evidence.omitted_candidate_count,
1158            status: match &b.coverage_evidence.status {
1159                BoundaryEvidenceStatus::Proved => BoundaryEvidenceStatus::Proved,
1160                BoundaryEvidenceStatus::Undetermined { reason } => {
1161                    BoundaryEvidenceStatus::Undetermined { reason: *reason }
1162                }
1163            },
1164        },
1165    })
1166}
1167fn clone_enclosure(e: &Enclosure) -> Result<Enclosure, GeometryFailure> {
1168    Enclosure::new(
1169        e.lower().try_clone().map_err(bigint_failure)?,
1170        e.upper().try_clone().map_err(bigint_failure)?,
1171    )
1172    .map_err(|x| GeometryFailure::CalculusFailure {
1173        error: CalculusFailure::Interval(x),
1174    })
1175}
1176fn clone_dyadics(v: &[Dyadic]) -> Result<Vec<Dyadic>, GeometryFailure> {
1177    v.iter()
1178        .map(|x| x.try_clone().map_err(bigint_failure))
1179        .collect()
1180}
1181fn clone_polynomial(p: &Polynomial) -> Result<Polynomial, GeometryFailure> {
1182    p.try_clone().map_err(poly_failure)
1183}
1184fn dyadic_to_real(v: &Dyadic) -> Result<RealAlgebraic, GeometryFailure> {
1185    if v.is_zero() {
1186        return zero_algebraic();
1187    }
1188    let denominator = BigUint::one()
1189        .map_err(bigint_failure)?
1190        .shl_bits(v.exponent() as usize)
1191        .map_err(bigint_failure)?;
1192    let rational = RawRational::new(
1193        v.integer().try_clone().map_err(bigint_failure)?,
1194        denominator,
1195    )
1196    .reduce()
1197    .map_err(bigint_failure)?
1198    .into_reduced();
1199    RealAlgebraic::from_reduced_rational(&rational).map_err(GeometryFailure::AlgebraFailure)
1200}
1201fn calculus_failure(error: CalculusFailure) -> GeometryFailure {
1202    GeometryFailure::CalculusFailure { error }
1203}
1204fn poly_failure(error: PolynomialFailure) -> GeometryFailure {
1205    GeometryFailure::CalculusFailure {
1206        error: CalculusFailure::Polynomial(error),
1207    }
1208}
1209fn bigint_failure(error: BigintError) -> GeometryFailure {
1210    GeometryFailure::CalculusFailure {
1211        error: CalculusFailure::Polynomial(PolynomialFailure::Arithmetic(error)),
1212    }
1213}