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(®ion)?;
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| ®ion.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(®ion, 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(®ion, 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}