Skip to main content

neco_geometry/
region.rs

1use alloc::{boxed::Box, string::String, vec, vec::Vec};
2use core::cmp::Ordering;
3
4use neco_algnum::{AlgnumError, RealAlgebraic};
5use neco_bigint::{BigInt, BigintError, Sign};
6use neco_calculus::{CalculusFailure, PolynomialFailure, RationalFailure};
7use neco_geometry_foundation::{Point2, Point3};
8
9use crate::types::GeometryFailure;
10
11pub const MAX_REGION_CANONICAL_ATOMS: usize = 256;
12pub const MAX_REGION_POLYNOMIAL_TERMS: usize = 256;
13pub const MAX_REGION_EXPONENT_OPERATIONS: usize = 4_096;
14
15#[derive(Debug, Eq, PartialEq)]
16pub struct RegionPolynomialTerm {
17    coefficient: RealAlgebraic,
18    exponent_x: u32,
19    exponent_y: u32,
20    exponent_z: u32,
21}
22
23impl RegionPolynomialTerm {
24    pub fn try_new(
25        coefficient: RealAlgebraic,
26        exponent_x: u32,
27        exponent_y: u32,
28        exponent_z: u32,
29    ) -> Result<Self, GeometryFailure> {
30        Ok(Self {
31            coefficient,
32            exponent_x,
33            exponent_y,
34            exponent_z,
35        })
36    }
37
38    pub fn coefficient(&self) -> &RealAlgebraic {
39        &self.coefficient
40    }
41
42    pub fn exponent_x(&self) -> u32 {
43        self.exponent_x
44    }
45
46    pub fn exponent_y(&self) -> u32 {
47        self.exponent_y
48    }
49
50    pub fn exponent_z(&self) -> u32 {
51        self.exponent_z
52    }
53
54    fn try_clone(&self) -> Result<Self, GeometryFailure> {
55        Ok(Self {
56            coefficient: self
57                .coefficient
58                .try_clone()
59                .map_err(GeometryFailure::AlgebraFailure)?,
60            exponent_x: self.exponent_x,
61            exponent_y: self.exponent_y,
62            exponent_z: self.exponent_z,
63        })
64    }
65}
66
67pub type RegionPolynomialTermSet = Vec<RegionPolynomialTerm>;
68
69#[derive(Debug, Eq, PartialEq)]
70pub struct RegionPolynomial3 {
71    terms: RegionPolynomialTermSet,
72}
73
74impl RegionPolynomial3 {
75    pub fn try_from_terms(mut terms: RegionPolynomialTermSet) -> Result<Self, GeometryFailure> {
76        terms.sort_unstable_by_key(|term| (term.exponent_x, term.exponent_y, term.exponent_z));
77        let mut normalized: Vec<RegionPolynomialTerm> = Vec::with_capacity(terms.len());
78        for term in terms {
79            if term.coefficient.is_zero() {
80                continue;
81            }
82            if let Some(previous) = normalized.last_mut() {
83                if (
84                    previous.exponent_x,
85                    previous.exponent_y,
86                    previous.exponent_z,
87                ) == (term.exponent_x, term.exponent_y, term.exponent_z)
88                {
89                    previous.coefficient = previous
90                        .coefficient
91                        .add(&term.coefficient)
92                        .map_err(GeometryFailure::AlgebraFailure)?;
93                    if previous.coefficient.is_zero() {
94                        normalized.pop();
95                    }
96                    continue;
97                }
98            }
99            normalized.push(term);
100        }
101        if normalized.len() > MAX_REGION_POLYNOMIAL_TERMS {
102            return Err(GeometryFailure::RegionPolynomialTermLimit {
103                requested_terms: normalized.len(),
104                maximum_terms: MAX_REGION_POLYNOMIAL_TERMS,
105            });
106        }
107        Ok(Self { terms: normalized })
108    }
109
110    pub fn zero() -> Self {
111        Self { terms: Vec::new() }
112    }
113
114    pub fn terms(&self) -> &[RegionPolynomialTerm] {
115        &self.terms
116    }
117
118    fn is_zero(&self) -> bool {
119        self.terms.iter().all(|term| term.coefficient.is_zero())
120    }
121
122    pub fn try_clone(&self) -> Result<Self, GeometryFailure> {
123        Ok(Self {
124            terms: self
125                .terms
126                .iter()
127                .map(RegionPolynomialTerm::try_clone)
128                .collect::<Result<Vec<_>, _>>()?,
129        })
130    }
131
132    pub fn try_add(&self, other: &Self) -> Result<Self, GeometryFailure> {
133        let mut terms = Vec::with_capacity(self.terms.len() + other.terms.len());
134        for term in &self.terms {
135            terms.push(term.try_clone()?);
136        }
137        for term in &other.terms {
138            terms.push(term.try_clone()?);
139        }
140        Self::try_from_terms(terms)
141    }
142
143    pub fn try_scale(&self, scalar: &RealAlgebraic) -> Result<Self, GeometryFailure> {
144        let mut terms = Vec::with_capacity(self.terms.len());
145        for term in &self.terms {
146            terms.push(RegionPolynomialTerm {
147                coefficient: term
148                    .coefficient
149                    .mul(scalar)
150                    .map_err(GeometryFailure::AlgebraFailure)?,
151                exponent_x: term.exponent_x,
152                exponent_y: term.exponent_y,
153                exponent_z: term.exponent_z,
154            });
155        }
156        Self::try_from_terms(terms)
157    }
158
159    pub fn try_multiply(&self, other: &Self) -> Result<Self, GeometryFailure> {
160        let mut operations = 0;
161        self.try_multiply_counted(other, &mut operations)
162    }
163
164    pub fn try_affine_substitute(&self, map: &RegionAffineMap3) -> Result<Self, GeometryFailure> {
165        let mut operations = 0;
166        let mut result = Self::zero();
167        for term in &self.terms {
168            let powered_x = map.x.try_pow(term.exponent_x, &mut operations)?;
169            let powered_y = map.y.try_pow(term.exponent_y, &mut operations)?;
170            let powered_z = map.z.try_pow(term.exponent_z, &mut operations)?;
171            let mut substituted = powered_x.try_multiply_counted(&powered_y, &mut operations)?;
172            substituted = substituted.try_multiply_counted(&powered_z, &mut operations)?;
173            substituted = substituted.try_scale(&term.coefficient)?;
174            result = result.try_add(&substituted)?;
175        }
176        Ok(result)
177    }
178
179    fn try_multiply_counted(
180        &self,
181        other: &Self,
182        operations: &mut usize,
183    ) -> Result<Self, GeometryFailure> {
184        if self.is_zero() || other.is_zero() {
185            return Ok(Self::zero());
186        }
187        let mut terms = Vec::new();
188        for left in &self.terms {
189            for right in &other.terms {
190                let exponent_x = add_exponents(left.exponent_x, right.exponent_x, operations)?;
191                let exponent_y = add_exponents(left.exponent_y, right.exponent_y, operations)?;
192                let exponent_z = add_exponents(left.exponent_z, right.exponent_z, operations)?;
193                let coefficient = left
194                    .coefficient
195                    .mul(&right.coefficient)
196                    .map_err(GeometryFailure::AlgebraFailure)?;
197                terms.push(RegionPolynomialTerm {
198                    coefficient,
199                    exponent_x,
200                    exponent_y,
201                    exponent_z,
202                });
203            }
204        }
205        Self::try_from_terms(terms)
206    }
207
208    fn try_pow(&self, exponent: u32, operations: &mut usize) -> Result<Self, GeometryFailure> {
209        if exponent == 0 {
210            return constant_one();
211        }
212        if exponent == 1 {
213            return self.try_clone();
214        }
215        if self.terms.len() == 1 {
216            return self.try_monomial_pow(exponent, operations);
217        }
218        let mut result = self.try_clone()?;
219        for _ in 1..exponent {
220            result = result.try_multiply_counted(self, operations)?;
221        }
222        Ok(result)
223    }
224
225    fn try_monomial_pow(
226        &self,
227        exponent: u32,
228        operations: &mut usize,
229    ) -> Result<Self, GeometryFailure> {
230        let term = &self.terms[0];
231        let exponent_x = multiply_exponents(term.exponent_x, exponent, operations)?;
232        let exponent_y = multiply_exponents(term.exponent_y, exponent, operations)?;
233        let exponent_z = multiply_exponents(term.exponent_z, exponent, operations)?;
234        let power = BigInt::try_from(exponent).map_err(calculus_from_bigint)?;
235        Self::try_from_terms(vec![RegionPolynomialTerm {
236            coefficient: algebraic_power(&term.coefficient, &power)?,
237            exponent_x,
238            exponent_y,
239            exponent_z,
240        }])
241    }
242
243    fn evaluate(
244        &self,
245        x: &RealAlgebraic,
246        y: &RealAlgebraic,
247        z: &RealAlgebraic,
248    ) -> Result<RealAlgebraic, GeometryFailure> {
249        let zero = BigInt::zero();
250        let mut result =
251            RealAlgebraic::from_integer(zero).map_err(GeometryFailure::AlgebraFailure)?;
252        for term in &self.terms {
253            let exponent_x = BigInt::try_from(term.exponent_x).map_err(calculus_from_bigint)?;
254            let exponent_y = BigInt::try_from(term.exponent_y).map_err(calculus_from_bigint)?;
255            let exponent_z = BigInt::try_from(term.exponent_z).map_err(calculus_from_bigint)?;
256            let value = algebraic_power(x, &exponent_x)?
257                .mul(&algebraic_power(y, &exponent_y)?)
258                .map_err(GeometryFailure::AlgebraFailure)?
259                .mul(&algebraic_power(z, &exponent_z)?)
260                .map_err(GeometryFailure::AlgebraFailure)?
261                .mul(&term.coefficient)
262                .map_err(GeometryFailure::AlgebraFailure)?;
263            result = result
264                .add(&value)
265                .map_err(GeometryFailure::AlgebraFailure)?;
266        }
267        Ok(result)
268    }
269}
270
271#[derive(Debug, Eq, PartialEq)]
272pub struct RegionAffineMap3 {
273    x: RegionPolynomial3,
274    y: RegionPolynomial3,
275    z: RegionPolynomial3,
276}
277
278impl RegionAffineMap3 {
279    pub fn try_new(
280        x: RegionPolynomial3,
281        y: RegionPolynomial3,
282        z: RegionPolynomial3,
283    ) -> Result<Self, GeometryFailure> {
284        validate_affine_coordinate(&x)?;
285        validate_affine_coordinate(&y)?;
286        validate_affine_coordinate(&z)?;
287        Ok(Self { x, y, z })
288    }
289
290    pub fn x(&self) -> &RegionPolynomial3 {
291        &self.x
292    }
293
294    pub fn y(&self) -> &RegionPolynomial3 {
295        &self.y
296    }
297
298    pub fn z(&self) -> &RegionPolynomial3 {
299        &self.z
300    }
301}
302
303#[derive(Debug, Eq, PartialEq)]
304pub struct RationalFunctionDomain3 {
305    non_zero_denominator: RegionPolynomial3,
306}
307
308impl RationalFunctionDomain3 {
309    pub fn try_new(non_zero_denominator: RegionPolynomial3) -> Result<Self, GeometryFailure> {
310        if non_zero_denominator.is_zero() {
311            return Err(GeometryFailure::MalformedRegionFormula);
312        }
313        Ok(Self {
314            non_zero_denominator,
315        })
316    }
317
318    pub fn non_zero_denominator(&self) -> &RegionPolynomial3 {
319        &self.non_zero_denominator
320    }
321
322    fn try_clone(&self) -> Result<Self, GeometryFailure> {
323        Ok(Self {
324            non_zero_denominator: self.non_zero_denominator.try_clone()?,
325        })
326    }
327}
328
329#[derive(Debug, Eq, PartialEq)]
330pub struct RationalFunction3 {
331    numerator: RegionPolynomial3,
332    denominator: RegionPolynomial3,
333    domain: RationalFunctionDomain3,
334}
335
336impl RationalFunction3 {
337    pub fn try_new(
338        numerator: RegionPolynomial3,
339        denominator: RegionPolynomial3,
340        domain: RationalFunctionDomain3,
341    ) -> Result<Self, GeometryFailure> {
342        if denominator != *domain.non_zero_denominator() {
343            return Err(GeometryFailure::MalformedRegionFormula);
344        }
345        Ok(Self {
346            numerator,
347            denominator,
348            domain,
349        })
350    }
351
352    pub fn numerator(&self) -> &RegionPolynomial3 {
353        &self.numerator
354    }
355
356    pub fn denominator(&self) -> &RegionPolynomial3 {
357        &self.denominator
358    }
359
360    pub fn domain(&self) -> &RationalFunctionDomain3 {
361        &self.domain
362    }
363
364    pub fn try_clone(&self) -> Result<Self, GeometryFailure> {
365        Ok(Self {
366            numerator: self.numerator.try_clone()?,
367            denominator: self.denominator.try_clone()?,
368            domain: self.domain.try_clone()?,
369        })
370    }
371
372    pub fn try_affine_substitute(&self, map: &RegionAffineMap3) -> Result<Self, GeometryFailure> {
373        let numerator = self.numerator.try_affine_substitute(map)?;
374        let denominator = self.denominator.try_affine_substitute(map)?;
375        let domain = RationalFunctionDomain3::try_new(denominator.try_clone()?)?;
376        Self::try_new(numerator, denominator, domain)
377    }
378
379    fn evaluate(
380        &self,
381        x: &RealAlgebraic,
382        y: &RealAlgebraic,
383        z: &RealAlgebraic,
384    ) -> Result<RealAlgebraic, GeometryFailure> {
385        let denominator = self.domain.non_zero_denominator.evaluate(x, y, z)?;
386        if denominator.is_zero() {
387            return Err(GeometryFailure::CalculusFailure {
388                error: CalculusFailure::Rational(RationalFailure::UndefinedDomain),
389            });
390        }
391        let numerator = self.numerator.evaluate(x, y, z)?;
392        numerator.div(&denominator).map_err(|error| match error {
393            AlgnumError::DivisionByZero => GeometryFailure::CalculusFailure {
394                error: CalculusFailure::Polynomial(PolynomialFailure::Algebra(error)),
395            },
396            error => GeometryFailure::AlgebraFailure(error),
397        })
398    }
399}
400
401#[derive(Debug, Eq, PartialEq)]
402pub enum RegionFunction {
403    Polynomial(RegionPolynomial3),
404    RationalFunction(RationalFunction3),
405}
406
407impl RegionFunction {
408    pub fn try_clone(&self) -> Result<Self, GeometryFailure> {
409        match self {
410            Self::Polynomial(polynomial) => Ok(Self::Polynomial(polynomial.try_clone()?)),
411            Self::RationalFunction(function) => Ok(Self::RationalFunction(function.try_clone()?)),
412        }
413    }
414
415    pub fn try_affine_substitute(&self, map: &RegionAffineMap3) -> Result<Self, GeometryFailure> {
416        match self {
417            Self::Polynomial(polynomial) => {
418                Ok(Self::Polynomial(polynomial.try_affine_substitute(map)?))
419            }
420            Self::RationalFunction(function) => {
421                Ok(Self::RationalFunction(function.try_affine_substitute(map)?))
422            }
423        }
424    }
425
426    fn evaluate(
427        &self,
428        x: &RealAlgebraic,
429        y: &RealAlgebraic,
430        z: &RealAlgebraic,
431    ) -> Result<RealAlgebraic, GeometryFailure> {
432        match self {
433            Self::Polynomial(polynomial) => polynomial.evaluate(x, y, z),
434            Self::RationalFunction(function) => function.evaluate(x, y, z),
435        }
436    }
437
438    fn compatible_with_dimension(&self, ambient_dimension: i64) -> bool {
439        if ambient_dimension == 3 {
440            return true;
441        }
442        let has_z = |polynomial: &RegionPolynomial3| {
443            polynomial.terms().iter().any(|term| term.exponent_z != 0)
444        };
445        match self {
446            Self::Polynomial(polynomial) => !has_z(polynomial),
447            Self::RationalFunction(function) => {
448                !has_z(function.numerator()) && !has_z(function.denominator())
449            }
450        }
451    }
452}
453
454#[derive(Clone, Copy, Debug, Eq, PartialEq)]
455pub enum SignRelation {
456    Negative,
457    Zero,
458    Positive,
459}
460
461#[derive(Debug, Eq, PartialEq)]
462pub struct CanonicalAtom {
463    atom_id: String,
464    function: RegionFunction,
465    relation: SignRelation,
466}
467
468impl CanonicalAtom {
469    pub fn try_new(
470        atom_id: impl Into<String>,
471        function: RegionFunction,
472        relation: SignRelation,
473    ) -> Result<Self, GeometryFailure> {
474        let atom_id = atom_id.into();
475        if atom_id.is_empty() {
476            return Err(GeometryFailure::MalformedRegionFormula);
477        }
478        Ok(Self {
479            atom_id,
480            function,
481            relation,
482        })
483    }
484
485    pub fn atom_id(&self) -> &str {
486        &self.atom_id
487    }
488
489    pub fn function(&self) -> &RegionFunction {
490        &self.function
491    }
492
493    pub fn relation(&self) -> SignRelation {
494        self.relation
495    }
496
497    pub fn try_clone(&self) -> Result<Self, GeometryFailure> {
498        Ok(Self {
499            atom_id: self.atom_id.clone(),
500            function: self.function.try_clone()?,
501            relation: self.relation,
502        })
503    }
504}
505
506pub type CanonicalAtomSet = Vec<CanonicalAtom>;
507
508#[derive(Clone, Debug, Eq, PartialEq)]
509pub enum NormalizedRegionFormula {
510    Atom(String),
511    Not(Box<NormalizedRegionFormula>),
512    And(NormalizedRegionFormulaSet),
513    Or(NormalizedRegionFormulaSet),
514    True,
515    False,
516}
517
518pub type NormalizedRegionFormulaSet = Vec<NormalizedRegionFormula>;
519
520impl NormalizedRegionFormula {
521    pub fn normalize(self) -> Result<Self, GeometryFailure> {
522        match self {
523            Self::Atom(atom_id) if atom_id.is_empty() => {
524                Err(GeometryFailure::MalformedRegionFormula)
525            }
526            Self::Atom(atom_id) => Ok(Self::Atom(atom_id)),
527            Self::Not(formula) => match formula.normalize()? {
528                Self::True => Ok(Self::False),
529                Self::False => Ok(Self::True),
530                Self::Not(inner) => Ok(*inner),
531                normalized => Ok(Self::Not(Box::new(normalized))),
532            },
533            Self::And(operands) => normalize_operands(operands, true),
534            Self::Or(operands) => normalize_operands(operands, false),
535            Self::True => Ok(Self::True),
536            Self::False => Ok(Self::False),
537        }
538    }
539}
540
541fn normalize_operands(
542    operands: NormalizedRegionFormulaSet,
543    is_and: bool,
544) -> Result<NormalizedRegionFormula, GeometryFailure> {
545    if operands.is_empty() {
546        return Err(GeometryFailure::MalformedRegionFormula);
547    }
548    let mut normalized = Vec::new();
549    for operand in operands {
550        let operand = operand.normalize()?;
551        if (is_and && operand == NormalizedRegionFormula::False)
552            || (!is_and && operand == NormalizedRegionFormula::True)
553        {
554            return Ok(if is_and {
555                NormalizedRegionFormula::False
556            } else {
557                NormalizedRegionFormula::True
558            });
559        }
560        if (is_and && operand == NormalizedRegionFormula::True)
561            || (!is_and && operand == NormalizedRegionFormula::False)
562        {
563            continue;
564        }
565        normalized.push(operand);
566    }
567    normalized.sort_by(compare_formulas);
568    normalized.dedup();
569    match normalized.len() {
570        0 => Ok(if is_and {
571            NormalizedRegionFormula::True
572        } else {
573            NormalizedRegionFormula::False
574        }),
575        1 => Ok(normalized.remove(0)),
576        _ if is_and => Ok(NormalizedRegionFormula::And(normalized)),
577        _ => Ok(NormalizedRegionFormula::Or(normalized)),
578    }
579}
580
581fn compare_formulas(left: &NormalizedRegionFormula, right: &NormalizedRegionFormula) -> Ordering {
582    let rank = |formula: &NormalizedRegionFormula| match formula {
583        NormalizedRegionFormula::Atom(_) => 0,
584        NormalizedRegionFormula::Not(_) => 1,
585        NormalizedRegionFormula::And(_) => 2,
586        NormalizedRegionFormula::Or(_) => 3,
587        NormalizedRegionFormula::True => 4,
588        NormalizedRegionFormula::False => 5,
589    };
590    match rank(left).cmp(&rank(right)) {
591        Ordering::Equal => match (left, right) {
592            (NormalizedRegionFormula::Atom(left), NormalizedRegionFormula::Atom(right)) => {
593                left.cmp(right)
594            }
595            (NormalizedRegionFormula::Not(left), NormalizedRegionFormula::Not(right)) => {
596                compare_formulas(left, right)
597            }
598            (NormalizedRegionFormula::And(left), NormalizedRegionFormula::And(right))
599            | (NormalizedRegionFormula::Or(left), NormalizedRegionFormula::Or(right)) => {
600                compare_formula_sets(left, right)
601            }
602            _ => Ordering::Equal,
603        },
604        ordering => ordering,
605    }
606}
607
608fn compare_formula_sets(
609    left: &NormalizedRegionFormulaSet,
610    right: &NormalizedRegionFormulaSet,
611) -> Ordering {
612    for (left, right) in left.iter().zip(right) {
613        match compare_formulas(left, right) {
614            Ordering::Equal => {}
615            ordering => return ordering,
616        }
617    }
618    left.len().cmp(&right.len())
619}
620
621#[derive(Clone, Copy, Debug, Eq, PartialEq)]
622pub enum RegionKind {
623    RegularClosedVolume,
624    GeneralSemiAlgebraicSet,
625    LowerDimensionalSet,
626}
627
628#[derive(Debug, Eq, PartialEq)]
629#[must_use]
630pub struct AlgebraicRegion {
631    ambient_dimension: i64,
632    canonical_atoms: CanonicalAtomSet,
633    normalized_region_formula: NormalizedRegionFormula,
634    region_kind: RegionKind,
635}
636
637impl AlgebraicRegion {
638    pub fn try_new(
639        ambient_dimension: i64,
640        mut canonical_atoms: CanonicalAtomSet,
641        normalized_region_formula: NormalizedRegionFormula,
642        region_kind: RegionKind,
643    ) -> Result<Self, GeometryFailure> {
644        if ambient_dimension != 2 && ambient_dimension != 3 {
645            return Err(GeometryFailure::RegionAmbientDimensionMismatch);
646        }
647        if canonical_atoms.len() > MAX_REGION_CANONICAL_ATOMS {
648            return Err(GeometryFailure::RegionCanonicalAtomLimit {
649                requested_atoms: canonical_atoms.len(),
650                maximum_atoms: MAX_REGION_CANONICAL_ATOMS,
651            });
652        }
653        canonical_atoms.sort_unstable_by(|left, right| left.atom_id.cmp(&right.atom_id));
654        for pair in canonical_atoms.windows(2) {
655            if pair[0].atom_id == pair[1].atom_id {
656                return Err(GeometryFailure::DuplicateRegionAtom);
657            }
658        }
659        if canonical_atoms.iter().enumerate().any(|(index, atom)| {
660            canonical_atoms[index + 1..]
661                .iter()
662                .any(|other| atom.function == other.function && atom.relation == other.relation)
663        }) {
664            return Err(GeometryFailure::DuplicateRegionCanonicalKey);
665        }
666        if canonical_atoms
667            .iter()
668            .any(|atom| !atom.function.compatible_with_dimension(ambient_dimension))
669        {
670            return Err(GeometryFailure::RegionAmbientDimensionMismatch);
671        }
672        let normalized_region_formula = normalized_region_formula.normalize()?;
673        if !formula_references_known_atoms(&normalized_region_formula, &canonical_atoms) {
674            return Err(GeometryFailure::MalformedRegionFormula);
675        }
676        Ok(Self {
677            ambient_dimension,
678            canonical_atoms,
679            normalized_region_formula,
680            region_kind,
681        })
682    }
683
684    pub fn ambient_dimension(&self) -> i64 {
685        self.ambient_dimension
686    }
687
688    pub fn canonical_atoms(&self) -> &[CanonicalAtom] {
689        &self.canonical_atoms
690    }
691
692    pub fn normalized_region_formula(&self) -> &NormalizedRegionFormula {
693        &self.normalized_region_formula
694    }
695
696    pub fn region_kind(&self) -> RegionKind {
697        self.region_kind
698    }
699
700    pub fn membership(
701        &self,
702        request: RegionMembershipRequest,
703    ) -> Result<RegionMembershipResult, GeometryFailure> {
704        self.membership_at(&request.point)
705    }
706
707    pub fn membership_judgment(
708        &self,
709        request: MembershipJudgmentRequest,
710    ) -> Result<MembershipJudgmentResult, GeometryFailure> {
711        let mut candidate_points = request.candidate_points.into_iter();
712        let mut judgment = None;
713        let mut mismatch = false;
714
715        for point in candidate_points.by_ref() {
716            let result = self.membership_at(&point)?;
717            if let Some(expected) = judgment.as_ref() {
718                if expected != &result {
719                    mismatch = true;
720                }
721            } else {
722                judgment = Some(result);
723            }
724        }
725
726        if mismatch {
727            return Err(GeometryFailure::MalformedRegionFormula);
728        }
729        match judgment {
730            Some(result) => Ok(result),
731            None => match self.normalized_region_formula {
732                NormalizedRegionFormula::True => Ok(RegionMembershipResult {
733                    classification: MembershipClassification::Inside,
734                    atom_signs: Vec::new(),
735                }),
736                NormalizedRegionFormula::False => Ok(RegionMembershipResult {
737                    classification: MembershipClassification::Outside,
738                    atom_signs: Vec::new(),
739                }),
740                _ => Err(GeometryFailure::MalformedRegionFormula),
741            },
742        }
743    }
744
745    pub fn set_boolean(
746        &self,
747        other: &Self,
748        formula: NormalizedRegionFormula,
749    ) -> Result<Self, GeometryFailure> {
750        if self.ambient_dimension != other.ambient_dimension {
751            return Err(GeometryFailure::RegionAmbientDimensionMismatch);
752        }
753        let mut atoms = Vec::new();
754        for atom in &self.canonical_atoms {
755            atoms.push(atom.try_clone()?);
756        }
757        for atom in &other.canonical_atoms {
758            atoms.push(atom.try_clone()?);
759        }
760        Self::try_new(
761            self.ambient_dimension,
762            atoms,
763            formula,
764            combined_region_kind(self.region_kind, other.region_kind),
765        )
766    }
767
768    pub fn solid_boolean(
769        &self,
770        other: &Self,
771        formula: NormalizedRegionFormula,
772    ) -> Result<Self, GeometryFailure> {
773        if self.region_kind != RegionKind::RegularClosedVolume
774            || other.region_kind != RegionKind::RegularClosedVolume
775        {
776            return Err(GeometryFailure::RegionKindMismatch);
777        }
778        let result = self.set_boolean(other, formula)?;
779        Self::try_new(
780            result.ambient_dimension,
781            result.canonical_atoms,
782            result.normalized_region_formula,
783            RegionKind::RegularClosedVolume,
784        )
785    }
786
787    fn membership_at(
788        &self,
789        point: &RegionPoint,
790    ) -> Result<RegionMembershipResult, GeometryFailure> {
791        if point.dimension() != self.ambient_dimension {
792            return Err(GeometryFailure::RegionPointDimensionMismatch);
793        }
794        let (x, y, z) = point.coordinates()?;
795        let mut atom_signs = Vec::new();
796        for atom in &self.canonical_atoms {
797            let relation = SignRelation::from_sign(
798                atom.function
799                    .evaluate(&x, &y, &z)?
800                    .sign()
801                    .map_err(GeometryFailure::AlgebraFailure)?,
802            );
803            atom_signs.push(AtomSignResult {
804                atom_id: atom.atom_id.clone(),
805                relation,
806            });
807        }
808        let formula_true = evaluate_formula(
809            &self.normalized_region_formula,
810            &atom_signs,
811            &self.canonical_atoms,
812        )?;
813        let classification = if atom_signs
814            .iter()
815            .any(|sign| sign.relation == SignRelation::Zero)
816        {
817            MembershipClassification::Boundary
818        } else if formula_true {
819            MembershipClassification::Inside
820        } else {
821            MembershipClassification::Outside
822        };
823        Ok(RegionMembershipResult {
824            classification,
825            atom_signs,
826        })
827    }
828}
829
830fn combined_region_kind(left: RegionKind, right: RegionKind) -> RegionKind {
831    if left == RegionKind::LowerDimensionalSet && right == RegionKind::LowerDimensionalSet {
832        RegionKind::LowerDimensionalSet
833    } else {
834        RegionKind::GeneralSemiAlgebraicSet
835    }
836}
837
838fn formula_references_known_atoms(
839    formula: &NormalizedRegionFormula,
840    atoms: &CanonicalAtomSet,
841) -> bool {
842    match formula {
843        NormalizedRegionFormula::Atom(atom_id) => atoms
844            .binary_search_by(|atom| atom.atom_id.as_str().cmp(atom_id.as_str()))
845            .is_ok(),
846        NormalizedRegionFormula::Not(inner) => formula_references_known_atoms(inner, atoms),
847        NormalizedRegionFormula::And(operands) | NormalizedRegionFormula::Or(operands) => operands
848            .iter()
849            .all(|operand| formula_references_known_atoms(operand, atoms)),
850        NormalizedRegionFormula::True | NormalizedRegionFormula::False => true,
851    }
852}
853
854fn evaluate_formula(
855    formula: &NormalizedRegionFormula,
856    atom_signs: &AtomSignResultSet,
857    atoms: &CanonicalAtomSet,
858) -> Result<bool, GeometryFailure> {
859    match formula {
860        NormalizedRegionFormula::Atom(atom_id) => {
861            let atom = atoms
862                .binary_search_by(|atom| atom.atom_id.as_str().cmp(atom_id.as_str()))
863                .map(|index| &atoms[index])
864                .map_err(|_| GeometryFailure::MalformedRegionFormula)?;
865            let sign = atom_signs
866                .binary_search_by(|sign| sign.atom_id.as_str().cmp(atom_id.as_str()))
867                .map(|index| &atom_signs[index])
868                .map_err(|_| GeometryFailure::MalformedRegionFormula)?;
869            Ok(atom.relation == sign.relation)
870        }
871        NormalizedRegionFormula::Not(inner) => Ok(!evaluate_formula(inner, atom_signs, atoms)?),
872        NormalizedRegionFormula::And(operands) => {
873            operands.iter().try_fold(true, |result, operand| {
874                Ok(result && evaluate_formula(operand, atom_signs, atoms)?)
875            })
876        }
877        NormalizedRegionFormula::Or(operands) => {
878            operands.iter().try_fold(false, |result, operand| {
879                Ok(result || evaluate_formula(operand, atom_signs, atoms)?)
880            })
881        }
882        NormalizedRegionFormula::True => Ok(true),
883        NormalizedRegionFormula::False => Ok(false),
884    }
885}
886
887#[derive(Debug, Eq, PartialEq)]
888pub enum RegionPoint {
889    Planar(Point2),
890    Spatial(Point3),
891}
892
893impl RegionPoint {
894    pub fn dimension(&self) -> i64 {
895        match self {
896            Self::Planar(_) => 2,
897            Self::Spatial(_) => 3,
898        }
899    }
900
901    fn coordinates(
902        &self,
903    ) -> Result<(RealAlgebraic, RealAlgebraic, RealAlgebraic), GeometryFailure> {
904        match self {
905            Self::Planar(point) => Ok((
906                point
907                    .x
908                    .try_clone()
909                    .map_err(GeometryFailure::AlgebraFailure)?,
910                point
911                    .y
912                    .try_clone()
913                    .map_err(GeometryFailure::AlgebraFailure)?,
914                RealAlgebraic::from_integer(BigInt::zero())
915                    .map_err(GeometryFailure::AlgebraFailure)?,
916            )),
917            Self::Spatial(point) => Ok((
918                point
919                    .x
920                    .try_clone()
921                    .map_err(GeometryFailure::AlgebraFailure)?,
922                point
923                    .y
924                    .try_clone()
925                    .map_err(GeometryFailure::AlgebraFailure)?,
926                point
927                    .z
928                    .try_clone()
929                    .map_err(GeometryFailure::AlgebraFailure)?,
930            )),
931        }
932    }
933}
934
935pub type RegionPointSet = Vec<RegionPoint>;
936
937#[derive(Debug, Eq, PartialEq)]
938pub struct RegionMembershipRequest {
939    pub region: AlgebraicRegion,
940    pub point: RegionPoint,
941}
942
943#[derive(Clone, Copy, Debug, Eq, PartialEq)]
944pub enum MembershipClassification {
945    Inside,
946    Boundary,
947    Outside,
948}
949
950#[derive(Debug, Eq, PartialEq)]
951pub struct AtomSignResult {
952    pub atom_id: String,
953    pub relation: SignRelation,
954}
955
956pub type AtomSignResultSet = Vec<AtomSignResult>;
957
958#[derive(Debug, Eq, PartialEq)]
959pub struct RegionMembershipResult {
960    pub classification: MembershipClassification,
961    pub atom_signs: AtomSignResultSet,
962}
963
964pub type MembershipJudgmentResult = RegionMembershipResult;
965
966#[derive(Debug, Eq, PartialEq)]
967pub struct MembershipJudgmentRequest {
968    pub region: AlgebraicRegion,
969    pub candidate_points: RegionPointSet,
970}
971
972#[derive(Debug, Eq, PartialEq)]
973pub struct RegionConstructionRequest {
974    pub ambient_dimension: i64,
975    pub canonical_atoms: CanonicalAtomSet,
976    pub normalized_region_formula: NormalizedRegionFormula,
977    pub region_kind: RegionKind,
978}
979
980#[derive(Debug, Eq, PartialEq)]
981pub struct RegionTypes {
982    region: AlgebraicRegion,
983}
984
985impl RegionTypes {
986    pub fn region(&self) -> &AlgebraicRegion {
987        &self.region
988    }
989
990    pub fn into_region(self) -> AlgebraicRegion {
991        self.region
992    }
993}
994
995pub fn construct_region_types(
996    request: RegionConstructionRequest,
997) -> Result<RegionTypes, GeometryFailure> {
998    Ok(RegionTypes {
999        region: AlgebraicRegion::try_new(
1000            request.ambient_dimension,
1001            request.canonical_atoms,
1002            request.normalized_region_formula,
1003            request.region_kind,
1004        )?,
1005    })
1006}
1007
1008fn validate_affine_coordinate(polynomial: &RegionPolynomial3) -> Result<(), GeometryFailure> {
1009    for term in polynomial.terms() {
1010        let plane = match term.exponent_x.checked_add(term.exponent_y) {
1011            Some(value) => value,
1012            None => return Err(GeometryFailure::InvalidRegionAffineMap),
1013        };
1014        let degree = match plane.checked_add(term.exponent_z) {
1015            Some(value) => value,
1016            None => return Err(GeometryFailure::InvalidRegionAffineMap),
1017        };
1018        if degree > 1 {
1019            return Err(GeometryFailure::InvalidRegionAffineMap);
1020        }
1021    }
1022    Ok(())
1023}
1024
1025fn constant_one() -> Result<RegionPolynomial3, GeometryFailure> {
1026    let one = BigInt::one().map_err(calculus_from_bigint)?;
1027    RegionPolynomial3::try_from_terms(vec![RegionPolynomialTerm::try_new(
1028        RealAlgebraic::from_integer(one).map_err(GeometryFailure::AlgebraFailure)?,
1029        0,
1030        0,
1031        0,
1032    )?])
1033}
1034
1035fn record_exponent_operation(operations: &mut usize) -> Result<(), GeometryFailure> {
1036    *operations = operations.saturating_add(1);
1037    if *operations > MAX_REGION_EXPONENT_OPERATIONS {
1038        return Err(GeometryFailure::RegionExponentOperationLimit {
1039            requested_operations: *operations,
1040            maximum_operations: MAX_REGION_EXPONENT_OPERATIONS,
1041        });
1042    }
1043    Ok(())
1044}
1045
1046fn add_exponents(left: u32, right: u32, operations: &mut usize) -> Result<u32, GeometryFailure> {
1047    record_exponent_operation(operations)?;
1048    left.checked_add(right)
1049        .ok_or(GeometryFailure::RegionExponentOverflow)
1050}
1051
1052fn multiply_exponents(
1053    left: u32,
1054    right: u32,
1055    operations: &mut usize,
1056) -> Result<u32, GeometryFailure> {
1057    record_exponent_operation(operations)?;
1058    left.checked_mul(right)
1059        .ok_or(GeometryFailure::RegionExponentOverflow)
1060}
1061
1062fn algebraic_power(
1063    value: &RealAlgebraic,
1064    exponent: &BigInt,
1065) -> Result<RealAlgebraic, GeometryFailure> {
1066    if exponent.is_zero() && value.is_zero() {
1067        return RealAlgebraic::from_integer(BigInt::one().map_err(calculus_from_bigint)?)
1068            .map_err(GeometryFailure::AlgebraFailure);
1069    }
1070    value
1071        .pow_integer(exponent)
1072        .map_err(GeometryFailure::AlgebraFailure)
1073}
1074
1075fn calculus_from_bigint(error: BigintError) -> GeometryFailure {
1076    GeometryFailure::CalculusFailure {
1077        error: CalculusFailure::from(error),
1078    }
1079}
1080
1081impl SignRelation {
1082    fn from_sign(sign: Sign) -> Self {
1083        match sign {
1084            Sign::Negative => Self::Negative,
1085            Sign::Zero => Self::Zero,
1086            Sign::Positive => Self::Positive,
1087        }
1088    }
1089}