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}