axioval_engine/
free_space.rs

1//! Source-neutral free-area and clearance host-service contracts.
2//!
3//! Geometry algorithms and native shapes remain in Axiolid or another trusted
4//! backend. This module carries canonical metric requests and reviewable evidence.
5
6use crate::circulation::{CirculationMap, CirculationRequest};
7use crate::door_leaves::{SweptDoor, tidy_swept};
8use crate::services::reviewable_exact_evidence;
9use crate::{MetricPoint, MobilityProfile, ThresholdVerdict};
10use axioval_ir::{Evidence, ObjectId};
11use std::sync::Arc;
12use thiserror::Error;
13
14#[derive(Clone, Debug, Error, PartialEq, Eq)]
15pub enum FreeSpaceError {
16    #[error("free-area interval is invalid")]
17    InvalidAreaInterval,
18    #[error("metric direction is zero or non-finite")]
19    InvalidMetricDirection,
20    #[error("metric frame axes are not mutually perpendicular")]
21    InvalidMetricFrame,
22    #[error("clearance shape dimensions must be positive and finite")]
23    InvalidClearanceShape,
24    #[error("placement offset interval is non-finite or reversed")]
25    InvalidOffsetInterval,
26    #[error("placement support gap must be finite and non-negative")]
27    InvalidSupportGap,
28    #[error("clearance evidence is incomplete")]
29    IncompleteClearanceEvidence,
30    #[error("obstruction evidence has no blocking objects")]
31    EmptyObstructionEvidence,
32    #[error("obstruction evidence names an object outside the request candidate set")]
33    UnexpectedObstacleEvidence,
34    #[error("obstruction provenance is not exact and reviewable")]
35    InexactObstructionEvidence,
36    #[error("free-area evidence is not exact and reviewable")]
37    InexactAreaEvidence,
38    #[error("placement evidence is not exact and reviewable")]
39    InexactPlacementEvidence,
40    #[error("support evidence is not exact and reviewable")]
41    InexactSupportEvidence,
42    #[error("supported placement has no complete support evidence")]
43    MissingSupportEvidence,
44    #[error("support evidence does not match the requested support or found frame")]
45    SupportEvidenceMismatch,
46    #[error("placement frame is not grounded in the requested scope")]
47    PlacementScopeMismatch,
48    #[error("placement witness falls outside its requested search domain")]
49    PlacementDomainMismatch,
50    #[error("placement witness does not follow the requested orientation")]
51    PlacementOrientationMismatch,
52    #[error("frame-offset placement of a box needs a fixed orientation along the anchor axes")]
53    OrientationDomainConflict,
54    #[error("placement elevation band must be finite, start at or above the floor and be ordered")]
55    InvalidElevationBand,
56    #[error("a merged scope is the search scope itself or one of its obstacles")]
57    MergedScopeConflict,
58    /// One door is given twice with different swept sectors.
59    #[error("a swept door is given twice with different sectors")]
60    ConflictingSweptDoors,
61    #[error("free-space backend returned evidence for another request")]
62    ResponseRequestMismatch,
63    #[error("free-space geometry is unavailable for `{0}`")]
64    MissingGeometry(Box<ObjectId>),
65    #[error("free-space query unavailable: {0}")]
66    Unavailable(String),
67}
68
69#[derive(Clone, Copy, Debug, PartialEq)]
70pub struct AreaInterval {
71    lower_square_metres: f64,
72    upper_square_metres: f64,
73}
74impl AreaInterval {
75    pub fn try_new(lower: f64, upper: f64) -> Result<Self, FreeSpaceError> {
76        if !valid_non_negative(lower) || !valid_non_negative(upper) || lower > upper {
77            return Err(FreeSpaceError::InvalidAreaInterval);
78        }
79        Ok(Self {
80            lower_square_metres: lower,
81            upper_square_metres: upper,
82        })
83    }
84    pub fn exact(square_metres: f64) -> Result<Self, FreeSpaceError> {
85        Self::try_new(square_metres, square_metres)
86    }
87    pub fn lower_square_metres(&self) -> f64 {
88        self.lower_square_metres
89    }
90    pub fn upper_square_metres(&self) -> f64 {
91        self.upper_square_metres
92    }
93    pub fn compare_minimum(&self, minimum: f64) -> Result<ThresholdVerdict, FreeSpaceError> {
94        if !valid_non_negative(minimum) {
95            return Err(FreeSpaceError::InvalidAreaInterval);
96        }
97        if self.lower_square_metres >= minimum {
98            Ok(ThresholdVerdict::Satisfied)
99        } else if self.upper_square_metres < minimum {
100            Ok(ThresholdVerdict::Violated)
101        } else {
102            Ok(ThresholdVerdict::Indeterminate)
103        }
104    }
105}
106
107#[derive(Clone, Copy, Debug, PartialEq)]
108pub struct MetricDirection([f64; 3]);
109impl MetricDirection {
110    pub fn try_new(vector: [f64; 3]) -> Result<Self, FreeSpaceError> {
111        if !vector.iter().all(|v| v.is_finite()) {
112            return Err(FreeSpaceError::InvalidMetricDirection);
113        }
114        let norm = vector.iter().map(|v| v * v).sum::<f64>().sqrt();
115        if norm <= f64::EPSILON {
116            return Err(FreeSpaceError::InvalidMetricDirection);
117        }
118        Ok(Self([vector[0] / norm, vector[1] / norm, vector[2] / norm]))
119    }
120    pub fn components(&self) -> [f64; 3] {
121        self.0
122    }
123    fn dot(self, other: Self) -> f64 {
124        self.0[0] * other.0[0] + self.0[1] * other.0[1] + self.0[2] * other.0[2]
125    }
126}
127
128#[derive(Clone, Debug, PartialEq)]
129pub struct MetricFrame {
130    origin: MetricPoint,
131    right: MetricDirection,
132    forward: MetricDirection,
133    up: MetricDirection,
134}
135impl MetricFrame {
136    pub fn try_new(
137        origin: MetricPoint,
138        right: MetricDirection,
139        forward: MetricDirection,
140        up: MetricDirection,
141    ) -> Result<Self, FreeSpaceError> {
142        const ORTHOGONAL_TOLERANCE: f64 = 1.0e-9;
143        let [rx, ry, rz] = right.components();
144        let [fx, fy, fz] = forward.components();
145        let [ux, uy, uz] = up.components();
146        let handedness =
147            (ry * fz - rz * fy) * ux + (rz * fx - rx * fz) * uy + (rx * fy - ry * fx) * uz;
148        if right.dot(forward).abs() > ORTHOGONAL_TOLERANCE
149            || right.dot(up).abs() > ORTHOGONAL_TOLERANCE
150            || forward.dot(up).abs() > ORTHOGONAL_TOLERANCE
151            || handedness < 1.0 - ORTHOGONAL_TOLERANCE
152        {
153            return Err(FreeSpaceError::InvalidMetricFrame);
154        }
155        Ok(Self {
156            origin,
157            right,
158            forward,
159            up,
160        })
161    }
162    pub fn origin(&self) -> &MetricPoint {
163        &self.origin
164    }
165    pub fn right(&self) -> MetricDirection {
166        self.right
167    }
168    pub fn forward(&self) -> MetricDirection {
169        self.forward
170    }
171    pub fn up(&self) -> MetricDirection {
172        self.up
173    }
174}
175
176#[derive(Clone, Copy, Debug, PartialEq)]
177pub struct BoxClearance {
178    width: f64,
179    depth: f64,
180    height: f64,
181}
182impl BoxClearance {
183    pub fn try_new(width: f64, depth: f64, height: f64) -> Result<Self, FreeSpaceError> {
184        if !valid_positive(width) || !valid_positive(depth) || !valid_positive(height) {
185            return Err(FreeSpaceError::InvalidClearanceShape);
186        }
187        Ok(Self {
188            width,
189            depth,
190            height,
191        })
192    }
193    pub fn width_metres(&self) -> f64 {
194        self.width
195    }
196    pub fn depth_metres(&self) -> f64 {
197        self.depth
198    }
199    pub fn height_metres(&self) -> f64 {
200        self.height
201    }
202}
203
204#[derive(Clone, Copy, Debug, PartialEq)]
205pub struct CylinderClearance {
206    radius: f64,
207    height: f64,
208}
209impl CylinderClearance {
210    pub fn try_new(radius: f64, height: f64) -> Result<Self, FreeSpaceError> {
211        if !valid_positive(radius) || !valid_positive(height) {
212            return Err(FreeSpaceError::InvalidClearanceShape);
213        }
214        Ok(Self { radius, height })
215    }
216    pub fn radius_metres(&self) -> f64 {
217        self.radius
218    }
219    pub fn height_metres(&self) -> f64 {
220        self.height
221    }
222}
223
224#[derive(Clone, Copy, Debug, PartialEq)]
225pub enum ClearanceShape {
226    Box(BoxClearance),
227    Cylinder(CylinderClearance),
228}
229
230#[derive(Clone, Debug, PartialEq)]
231pub struct ClearanceRequest {
232    frame: MetricFrame,
233    shape: ClearanceShape,
234    obstacles: Vec<ObjectId>,
235}
236impl ClearanceRequest {
237    pub fn new(frame: MetricFrame, shape: ClearanceShape, mut obstacles: Vec<ObjectId>) -> Self {
238        obstacles.sort();
239        obstacles.dedup();
240        Self {
241            frame,
242            shape,
243            obstacles,
244        }
245    }
246    pub fn frame(&self) -> &MetricFrame {
247        &self.frame
248    }
249    pub fn shape(&self) -> ClearanceShape {
250        self.shape
251    }
252    pub fn obstacles(&self) -> &[ObjectId] {
253        &self.obstacles
254    }
255}
256
257#[derive(Clone, Debug, PartialEq)]
258pub struct FreeAreaRequest {
259    scope: ObjectId,
260    mobility: MobilityProfile,
261    obstacles: Vec<ObjectId>,
262}
263impl FreeAreaRequest {
264    pub fn new(scope: ObjectId, mobility: MobilityProfile, mut obstacles: Vec<ObjectId>) -> Self {
265        obstacles.sort();
266        obstacles.dedup();
267        Self {
268            scope,
269            mobility,
270            obstacles,
271        }
272    }
273    pub fn scope(&self) -> &ObjectId {
274        &self.scope
275    }
276    pub fn mobility(&self) -> MobilityProfile {
277        self.mobility
278    }
279    pub fn obstacles(&self) -> &[ObjectId] {
280        &self.obstacles
281    }
282}
283
284/// Inclusive signed offset bounds in canonical metres.
285#[derive(Clone, Copy, Debug, PartialEq)]
286pub struct SignedDistanceInterval {
287    lower_metres: f64,
288    upper_metres: f64,
289}
290impl SignedDistanceInterval {
291    pub fn try_new(lower_metres: f64, upper_metres: f64) -> Result<Self, FreeSpaceError> {
292        if !lower_metres.is_finite() || !upper_metres.is_finite() || lower_metres > upper_metres {
293            return Err(FreeSpaceError::InvalidOffsetInterval);
294        }
295        Ok(Self {
296            lower_metres,
297            upper_metres,
298        })
299    }
300    pub fn exact(metres: f64) -> Result<Self, FreeSpaceError> {
301        Self::try_new(metres, metres)
302    }
303    pub fn lower_metres(&self) -> f64 {
304        self.lower_metres
305    }
306    pub fn upper_metres(&self) -> f64 {
307        self.upper_metres
308    }
309    fn contains(self, value: f64) -> bool {
310        value >= self.lower_metres && value <= self.upper_metres
311    }
312}
313
314/// Requires the entire placement base to lie on an object's support surface.
315#[derive(Clone, Debug, PartialEq)]
316pub struct SupportedPlacement {
317    support: ObjectId,
318    maximum_gap_metres: f64,
319}
320impl SupportedPlacement {
321    pub fn try_new(support: ObjectId, maximum_gap_metres: f64) -> Result<Self, FreeSpaceError> {
322        if !valid_non_negative(maximum_gap_metres) {
323            return Err(FreeSpaceError::InvalidSupportGap);
324        }
325        Ok(Self {
326            support,
327            maximum_gap_metres,
328        })
329    }
330    pub fn support(&self) -> &ObjectId {
331        &self.support
332    }
333    pub fn maximum_gap_metres(&self) -> f64 {
334        self.maximum_gap_metres
335    }
336}
337
338/// Restricts candidate-frame origins to offsets in an anchor frame.
339#[derive(Clone, Debug, PartialEq)]
340pub struct FrameOffsetPlacement {
341    anchor: MetricFrame,
342    right: SignedDistanceInterval,
343    forward: SignedDistanceInterval,
344    up: SignedDistanceInterval,
345}
346impl FrameOffsetPlacement {
347    pub fn new(
348        anchor: MetricFrame,
349        right: SignedDistanceInterval,
350        forward: SignedDistanceInterval,
351        up: SignedDistanceInterval,
352    ) -> Self {
353        Self {
354            anchor,
355            right,
356            forward,
357            up,
358        }
359    }
360    pub fn anchor(&self) -> &MetricFrame {
361        &self.anchor
362    }
363    pub fn right(&self) -> SignedDistanceInterval {
364        self.right
365    }
366    pub fn forward(&self) -> SignedDistanceInterval {
367        self.forward
368    }
369    pub fn up(&self) -> SignedDistanceInterval {
370        self.up
371    }
372    /// Whether a found frame keeps the anchor's axes and lies within the
373    /// offsets. Placement evidence is validated with exactly this test, so a
374    /// backend may filter its witnesses with it.
375    pub fn contains_frame(&self, frame: &MetricFrame) -> bool {
376        let aligned = self.anchor.right() == frame.right()
377            && self.anchor.forward() == frame.forward()
378            && self.anchor.up() == frame.up();
379        if !aligned {
380            return false;
381        }
382        let anchor = self.anchor.origin().coordinates_metres();
383        let found = frame.origin().coordinates_metres();
384        let delta = [
385            found[0] - anchor[0],
386            found[1] - anchor[1],
387            found[2] - anchor[2],
388        ];
389        let project = |axis: MetricDirection| {
390            axis.components()
391                .into_iter()
392                .zip(delta)
393                .map(|(a, b)| a * b)
394                .sum()
395        };
396        self.right.contains(project(self.anchor.right()))
397            && self.forward.contains(project(self.anchor.forward()))
398            && self.up.contains(project(self.anchor.up()))
399    }
400}
401
402/// Geometric predicate limiting where a backend may search for placements.
403#[derive(Clone, Debug, PartialEq)]
404pub enum PlacementDomain {
405    Unconstrained,
406    Supported(SupportedPlacement),
407    FrameOffsets(FrameOffsetPlacement),
408    SupportedFrameOffsets {
409        support: SupportedPlacement,
410        offsets: FrameOffsetPlacement,
411    },
412}
413
414fn requested_support(domain: &PlacementDomain) -> Option<&SupportedPlacement> {
415    match domain {
416        PlacementDomain::Supported(support)
417        | PlacementDomain::SupportedFrameOffsets { support, .. } => Some(support),
418        _ => None,
419    }
420}
421
422/// Which rotations of a box placement count as a fit.
423///
424/// Answers differ by orientation: a box that fits only diagonally has no
425/// placement along a fixed frame but has one at some angle. Evidence for a
426/// fixed orientation says nothing about other angles.
427#[derive(Clone, Debug, PartialEq)]
428pub enum PlacementOrientation {
429    /// The box width follows the frame's right axis and its depth the forward
430    /// axis. Only the axes are binding; the frame origin is not a location.
431    Fixed(MetricFrame),
432    /// Every rotation about the vertical axis counts.
433    Any,
434}
435
436/// The elevations, relative to the scope's floor, in which obstacles count.
437///
438/// Only the part of an obstacle's solid inside the open band blocks a
439/// placement. Without a band, the band runs from the floor up by the shape's
440/// height.
441#[derive(Clone, Copy, Debug, PartialEq)]
442pub struct ElevationBand {
443    from_metres: f64,
444    to_metres: f64,
445}
446impl ElevationBand {
447    pub fn try_new(from_metres: f64, to_metres: f64) -> Result<Self, FreeSpaceError> {
448        if !from_metres.is_finite()
449            || !to_metres.is_finite()
450            || from_metres < 0.0
451            || from_metres >= to_metres
452        {
453            return Err(FreeSpaceError::InvalidElevationBand);
454        }
455        Ok(Self {
456            from_metres,
457            to_metres,
458        })
459    }
460    /// Bottom of the band above the floor.
461    pub fn from_metres(&self) -> f64 {
462        self.from_metres
463    }
464    /// Top of the band above the floor.
465    pub fn to_metres(&self) -> f64 {
466        self.to_metres
467    }
468}
469
470/// A clearance shape together with the rotations a placement may use.
471///
472/// A box carries an explicit orientation so that a request cannot leave open
473/// which question it asks. A cylinder is rotation-invariant and carries none.
474#[derive(Clone, Debug, PartialEq)]
475pub enum PlacementShape {
476    Box {
477        shape: BoxClearance,
478        orientation: PlacementOrientation,
479    },
480    Cylinder(CylinderClearance),
481}
482impl PlacementShape {
483    pub fn clearance(&self) -> ClearanceShape {
484        match self {
485            Self::Box { shape, .. } => ClearanceShape::Box(*shape),
486            Self::Cylinder(shape) => ClearanceShape::Cylinder(*shape),
487        }
488    }
489    pub fn orientation(&self) -> Option<&PlacementOrientation> {
490        match self {
491            Self::Box { orientation, .. } => Some(orientation),
492            Self::Cylinder(_) => None,
493        }
494    }
495}
496
497fn same_axes(a: &MetricFrame, b: &MetricFrame) -> bool {
498    a.right() == b.right() && a.forward() == b.forward() && a.up() == b.up()
499}
500
501/// The entrances a placement must be reached from, by a path of a width.
502///
503/// A placement is reached when its shape meets a piece of the free area
504/// eroded by half the path's width that comes within half the width plus
505/// the tolerance of an entrance's plan footprint, as a
506/// [`crate::CirculationMap`] proves a contact: a path that wide runs from
507/// the entrance into the shape. The path is free in the placement's band,
508/// clear of the same obstacles and swept doors; the entrances themselves
509/// are walked through, so they and their swings are never obstacles.
510#[derive(Clone, Debug, PartialEq)]
511pub struct EntranceReach {
512    entrances: Vec<ObjectId>,
513    width_metres: f64,
514    tolerance_metres: f64,
515}
516
517impl EntranceReach {
518    /// A path `width_metres` wide from one of `entrances`, which it comes
519    /// within half its width plus `tolerance_metres` of. Without entrances
520    /// nothing is reached.
521    ///
522    /// # Errors
523    ///
524    /// [`FreeSpaceError::InvalidClearanceShape`] for a width that is not
525    /// positive and finite or a tolerance that is negative or not finite.
526    pub fn try_new(
527        mut entrances: Vec<ObjectId>,
528        width_metres: f64,
529        tolerance_metres: f64,
530    ) -> Result<Self, FreeSpaceError> {
531        if !(width_metres.is_finite()
532            && width_metres > 0.0
533            && tolerance_metres.is_finite()
534            && tolerance_metres >= 0.0)
535        {
536            return Err(FreeSpaceError::InvalidClearanceShape);
537        }
538        entrances.sort();
539        entrances.dedup();
540        Ok(Self {
541            entrances,
542            width_metres,
543            tolerance_metres,
544        })
545    }
546
547    /// The entrances, sorted.
548    #[must_use]
549    pub fn entrances(&self) -> &[ObjectId] {
550        &self.entrances
551    }
552
553    /// The path's width.
554    #[must_use]
555    pub fn width_metres(&self) -> f64 {
556        self.width_metres
557    }
558
559    /// How much farther than half the width an entrance may be from the
560    /// path and still be reached.
561    #[must_use]
562    pub fn tolerance_metres(&self) -> f64 {
563        self.tolerance_metres
564    }
565}
566
567/// Searches an object-grounded scope for any placement of a clearance shape.
568#[derive(Clone, Debug, PartialEq)]
569pub struct PlacementRequest {
570    scope: ObjectId,
571    shape: PlacementShape,
572    obstacles: Vec<ObjectId>,
573    domain: PlacementDomain,
574    band: Option<ElevationBand>,
575    merged: Vec<ObjectId>,
576    swept: Vec<SweptDoor>,
577    reach: Option<EntranceReach>,
578}
579impl PlacementRequest {
580    pub fn new(scope: ObjectId, shape: PlacementShape, mut obstacles: Vec<ObjectId>) -> Self {
581        obstacles.sort();
582        obstacles.dedup();
583        Self {
584            scope,
585            shape,
586            obstacles,
587            domain: PlacementDomain::Unconstrained,
588            band: None,
589            merged: Vec::new(),
590            swept: Vec::new(),
591            reach: None,
592        }
593    }
594    pub fn new_in_domain(
595        scope: ObjectId,
596        shape: PlacementShape,
597        mut obstacles: Vec<ObjectId>,
598        domain: PlacementDomain,
599    ) -> Result<Self, FreeSpaceError> {
600        let offsets = match &domain {
601            PlacementDomain::FrameOffsets(offsets)
602            | PlacementDomain::SupportedFrameOffsets { offsets, .. } => Some(offsets),
603            _ => None,
604        };
605        // The anchor may be grounded on another object, such as a door or a
606        // fixture in front of which the shape must fit; the witness is still
607        // grounded on the scope.
608        // Offset witnesses must align with the anchor, so a box searched there
609        // can only be asked about the anchor's own orientation.
610        if let (Some(offsets), Some(orientation)) = (offsets, shape.orientation()) {
611            match orientation {
612                PlacementOrientation::Fixed(frame) if same_axes(frame, offsets.anchor()) => {}
613                _ => return Err(FreeSpaceError::OrientationDomainConflict),
614            }
615        }
616        obstacles.sort();
617        obstacles.dedup();
618        Ok(Self {
619            scope,
620            shape,
621            obstacles,
622            domain,
623            band: None,
624            merged: Vec::new(),
625            swept: Vec::new(),
626            reach: None,
627        })
628    }
629    /// Counts obstacles only inside `band` above the scope's floor.
630    #[must_use]
631    pub fn with_band(mut self, band: ElevationBand) -> Self {
632        self.band = Some(band);
633        self
634    }
635    /// Searches the union of the scope and `merged` scopes, such as the
636    /// spaces of one group. The witness stays grounded on the scope. A merged
637    /// scope must be neither the scope nor an obstacle.
638    pub fn with_merged_scopes(mut self, mut merged: Vec<ObjectId>) -> Result<Self, FreeSpaceError> {
639        merged.sort();
640        merged.dedup();
641        if merged
642            .iter()
643            .any(|id| id == &self.scope || self.obstacles.binary_search(id).is_ok())
644        {
645            return Err(FreeSpaceError::MergedScopeConflict);
646        }
647        self.merged = merged;
648        Ok(self)
649    }
650    /// Counts the sectors `swept` doors sweep as obstacles (see
651    /// [`SweptDoor`]): a witness must stay clear of their circumscribed
652    /// polygons, a proof of absence holds against their inscribed ones.
653    ///
654    /// # Errors
655    ///
656    /// [`FreeSpaceError::ConflictingSweptDoors`] when one door is given
657    /// twice with different sectors.
658    pub fn with_swept_doors(mut self, swept: Vec<SweptDoor>) -> Result<Self, FreeSpaceError> {
659        let mut swept = tidy_swept(swept).ok_or(FreeSpaceError::ConflictingSweptDoors)?;
660        if let Some(reach) = &self.reach {
661            swept.retain(|door| reach.entrances.binary_search(door.door()).is_err());
662        }
663        self.swept = swept;
664        Ok(self)
665    }
666    /// Requires the placement to be reached from `reach`'s entrances (see
667    /// [`EntranceReach`]). The entrances are walked through: they leave the
668    /// obstacles, and their swings the swept doors.
669    #[must_use]
670    pub fn with_entrance_reach(mut self, reach: EntranceReach) -> Self {
671        self.obstacles
672            .retain(|object| reach.entrances.binary_search(object).is_err());
673        self.swept
674            .retain(|door| reach.entrances.binary_search(door.door()).is_err());
675        self.reach = Some(reach);
676        self
677    }
678    /// The entrances the placement must be reached from, if any.
679    pub fn entrance_reach(&self) -> Option<&EntranceReach> {
680        self.reach.as_ref()
681    }
682    /// The doors whose swept sectors are obstacles, sorted by door.
683    pub fn swept_doors(&self) -> &[SweptDoor] {
684        &self.swept
685    }
686    pub fn scope(&self) -> &ObjectId {
687        &self.scope
688    }
689    pub fn shape(&self) -> &PlacementShape {
690        &self.shape
691    }
692    pub fn obstacles(&self) -> &[ObjectId] {
693        &self.obstacles
694    }
695    pub fn domain(&self) -> &PlacementDomain {
696        &self.domain
697    }
698    /// The band the request states, if any.
699    pub fn band(&self) -> Option<ElevationBand> {
700        self.band
701    }
702    /// The band obstacles count in: the stated one, or from the floor up by
703    /// the shape's height.
704    pub fn effective_band(&self) -> ElevationBand {
705        self.band.unwrap_or(ElevationBand {
706            from_metres: 0.0,
707            to_metres: match &self.shape {
708                PlacementShape::Box { shape, .. } => shape.height_metres(),
709                PlacementShape::Cylinder(shape) => shape.height_metres(),
710            },
711        })
712    }
713    /// Scopes searched together with the scope, sorted.
714    pub fn merged_scopes(&self) -> &[ObjectId] {
715        &self.merged
716    }
717}
718
719/// Exact proof that the entire candidate base is supported at a found frame.
720#[derive(Clone, Debug, PartialEq)]
721pub struct CompleteSupportEvidence {
722    support: ObjectId,
723    frame: MetricFrame,
724    maximum_gap_metres: f64,
725    evidence: Evidence,
726}
727
728impl CompleteSupportEvidence {
729    pub fn try_new(
730        support: ObjectId,
731        frame: MetricFrame,
732        maximum_gap_metres: f64,
733        evidence: Evidence,
734    ) -> Result<Self, FreeSpaceError> {
735        if !valid_non_negative(maximum_gap_metres) {
736            return Err(FreeSpaceError::InvalidSupportGap);
737        }
738        if !reviewable_exact_evidence(&evidence) {
739            return Err(FreeSpaceError::InexactSupportEvidence);
740        }
741        Ok(Self {
742            support,
743            frame,
744            maximum_gap_metres,
745            evidence,
746        })
747    }
748    pub fn support(&self) -> &ObjectId {
749        &self.support
750    }
751    pub fn frame(&self) -> &MetricFrame {
752        &self.frame
753    }
754    pub fn maximum_gap_metres(&self) -> f64 {
755        self.maximum_gap_metres
756    }
757    pub fn evidence(&self) -> &Evidence {
758        &self.evidence
759    }
760}
761
762#[derive(Clone, Debug, PartialEq)]
763pub struct CompleteClearanceEvidence {
764    request: ClearanceRequest,
765    evidence: Evidence,
766}
767impl CompleteClearanceEvidence {
768    pub fn try_new(request: ClearanceRequest, evidence: Evidence) -> Result<Self, FreeSpaceError> {
769        if !reviewable_exact_evidence(&evidence) {
770            return Err(FreeSpaceError::IncompleteClearanceEvidence);
771        }
772        Ok(Self { request, evidence })
773    }
774    pub fn request(&self) -> &ClearanceRequest {
775        &self.request
776    }
777    pub fn evidence(&self) -> &Evidence {
778        &self.evidence
779    }
780}
781
782#[derive(Clone, Debug, PartialEq)]
783pub struct ObstructionEvidence {
784    request: ClearanceRequest,
785    blockers: Vec<ObjectId>,
786    evidence: Evidence,
787}
788impl ObstructionEvidence {
789    pub fn try_new(
790        request: ClearanceRequest,
791        mut blockers: Vec<ObjectId>,
792        evidence: Evidence,
793    ) -> Result<Self, FreeSpaceError> {
794        if blockers.is_empty() {
795            return Err(FreeSpaceError::EmptyObstructionEvidence);
796        }
797        if !reviewable_exact_evidence(&evidence) {
798            return Err(FreeSpaceError::InexactObstructionEvidence);
799        }
800        blockers.sort();
801        blockers.dedup();
802        if blockers
803            .iter()
804            .any(|blocker| request.obstacles().binary_search(blocker).is_err())
805        {
806            return Err(FreeSpaceError::UnexpectedObstacleEvidence);
807        }
808        Ok(Self {
809            request,
810            blockers,
811            evidence,
812        })
813    }
814    pub fn request(&self) -> &ClearanceRequest {
815        &self.request
816    }
817    pub fn blockers(&self) -> &[ObjectId] {
818        &self.blockers
819    }
820    pub fn evidence(&self) -> &Evidence {
821        &self.evidence
822    }
823}
824
825#[derive(Clone, Debug, PartialEq)]
826pub enum ClearanceOutcome {
827    Clear(CompleteClearanceEvidence),
828    Obstructed(ObstructionEvidence),
829}
830
831/// Asks whether a clearance volume's plan footprint lies inside the union of
832/// the plan footprints of `scopes`, such as the spaces a component stands in.
833///
834/// Only the plan is compared: the volume's height is carried so the request
835/// names the same volume a clearance request does, not to compare it with
836/// the scopes' heights. The scopes are the rule's selection, sorted and
837/// deduplicated; with none, nothing covers the footprint.
838#[derive(Clone, Debug, PartialEq)]
839pub struct ContainmentRequest {
840    frame: MetricFrame,
841    shape: ClearanceShape,
842    scopes: Vec<ObjectId>,
843}
844impl ContainmentRequest {
845    pub fn new(frame: MetricFrame, shape: ClearanceShape, mut scopes: Vec<ObjectId>) -> Self {
846        scopes.sort();
847        scopes.dedup();
848        Self {
849            frame,
850            shape,
851            scopes,
852        }
853    }
854    pub fn frame(&self) -> &MetricFrame {
855        &self.frame
856    }
857    pub fn shape(&self) -> ClearanceShape {
858        self.shape
859    }
860    pub fn scopes(&self) -> &[ObjectId] {
861        &self.scopes
862    }
863}
864
865/// Exact evidence for a containment answer, bound to its request.
866#[derive(Clone, Debug, PartialEq)]
867pub struct ContainmentEvidence {
868    request: ContainmentRequest,
869    evidence: Evidence,
870}
871impl ContainmentEvidence {
872    pub fn try_new(
873        request: ContainmentRequest,
874        evidence: Evidence,
875    ) -> Result<Self, FreeSpaceError> {
876        if !reviewable_exact_evidence(&evidence) {
877            return Err(FreeSpaceError::IncompleteClearanceEvidence);
878        }
879        Ok(Self { request, evidence })
880    }
881    pub fn request(&self) -> &ContainmentRequest {
882        &self.request
883    }
884    pub fn evidence(&self) -> &Evidence {
885        &self.evidence
886    }
887}
888
889/// Whether a clearance footprint lies inside its scopes.
890///
891/// Both answers are claims about the whole footprint: `Inside` that no part
892/// of positive area lies outside every scope, `Outside` that some part does.
893/// A backend that can only bound the footprint (a cylinder's disc) answers
894/// neither while the bounds disagree.
895#[derive(Clone, Debug, PartialEq)]
896pub enum ContainmentOutcome {
897    Inside(ContainmentEvidence),
898    Outside(ContainmentEvidence),
899}
900
901/// Asks whether the tops of `supports` hold a clearance footprint (the
902/// plan of `frame` and `shape`, as for [`ContainmentRequest`]): the
903/// upward-facing surfaces of the supports between `from` and `to` metres of
904/// elevation, such as a slab or landing near the floor under a door's clear
905/// area.
906///
907/// Only the plan and the elevation band are compared. The supports are the
908/// rule's selection, sorted and deduplicated; with none, nothing holds the
909/// footprint.
910#[derive(Clone, Debug, PartialEq)]
911pub struct SupportCoverageRequest {
912    frame: MetricFrame,
913    shape: ClearanceShape,
914    supports: Vec<ObjectId>,
915    from: f64,
916    to: f64,
917}
918impl SupportCoverageRequest {
919    /// Refuses a band that is not finite or whose ends are reversed.
920    pub fn try_new(
921        frame: MetricFrame,
922        shape: ClearanceShape,
923        mut supports: Vec<ObjectId>,
924        from_metres: f64,
925        to_metres: f64,
926    ) -> Result<Self, FreeSpaceError> {
927        if !(from_metres.is_finite() && to_metres.is_finite() && from_metres <= to_metres) {
928            return Err(FreeSpaceError::InvalidElevationBand);
929        }
930        supports.sort();
931        supports.dedup();
932        Ok(Self {
933            frame,
934            shape,
935            supports,
936            from: from_metres,
937            to: to_metres,
938        })
939    }
940    pub fn frame(&self) -> &MetricFrame {
941        &self.frame
942    }
943    pub fn shape(&self) -> ClearanceShape {
944        self.shape
945    }
946    pub fn supports(&self) -> &[ObjectId] {
947        &self.supports
948    }
949    /// The lowest elevation a top may lie at, in metres.
950    pub fn from_metres(&self) -> f64 {
951        self.from
952    }
953    /// The highest elevation a top may lie at, in metres.
954    pub fn to_metres(&self) -> f64 {
955        self.to
956    }
957}
958
959/// Exact evidence for a support-coverage answer, bound to its request.
960#[derive(Clone, Debug, PartialEq)]
961pub struct SupportCoverageEvidence {
962    request: SupportCoverageRequest,
963    evidence: Evidence,
964}
965impl SupportCoverageEvidence {
966    pub fn try_new(
967        request: SupportCoverageRequest,
968        evidence: Evidence,
969    ) -> Result<Self, FreeSpaceError> {
970        if !reviewable_exact_evidence(&evidence) {
971            return Err(FreeSpaceError::InexactSupportEvidence);
972        }
973        Ok(Self { request, evidence })
974    }
975    pub fn request(&self) -> &SupportCoverageRequest {
976        &self.request
977    }
978    pub fn evidence(&self) -> &Evidence {
979        &self.evidence
980    }
981}
982
983/// Whether the supports' tops hold a clearance footprint.
984///
985/// Both answers are whole-footprint claims: `Supported` that no part of
986/// positive area lies outside the tops within the band, `Unsupported` that
987/// some part does. A backend that can only bound the footprint (a
988/// cylinder's disc) answers neither while the bounds disagree.
989#[derive(Clone, Debug, PartialEq)]
990pub enum SupportCoverageOutcome {
991    Supported(SupportCoverageEvidence),
992    Unsupported(SupportCoverageEvidence),
993}
994
995/// One exact placement witness. It does not claim exhaustive search coverage.
996#[derive(Clone, Debug, PartialEq)]
997pub struct ClearancePlacementEvidence {
998    request: PlacementRequest,
999    frame: MetricFrame,
1000    support_evidence: Option<Box<CompleteSupportEvidence>>,
1001    evidence: Evidence,
1002}
1003fn validate_placement_witness(
1004    request: &PlacementRequest,
1005    frame: &MetricFrame,
1006    evidence: &Evidence,
1007) -> Result<(), FreeSpaceError> {
1008    if frame.origin().subject() != request.scope() {
1009        return Err(FreeSpaceError::PlacementScopeMismatch);
1010    }
1011    let offsets = match request.domain() {
1012        PlacementDomain::FrameOffsets(offsets)
1013        | PlacementDomain::SupportedFrameOffsets { offsets, .. } => Some(offsets),
1014        _ => None,
1015    };
1016    if offsets.is_some_and(|offsets| !offsets.contains_frame(frame)) {
1017        return Err(FreeSpaceError::PlacementDomainMismatch);
1018    }
1019    if let Some(PlacementOrientation::Fixed(fixed)) = request.shape().orientation() {
1020        if !same_axes(fixed, frame) {
1021            return Err(FreeSpaceError::PlacementOrientationMismatch);
1022        }
1023    }
1024    if !reviewable_exact_evidence(evidence) {
1025        return Err(FreeSpaceError::InexactPlacementEvidence);
1026    }
1027    Ok(())
1028}
1029
1030impl ClearancePlacementEvidence {
1031    pub fn try_new(
1032        request: PlacementRequest,
1033        frame: MetricFrame,
1034        evidence: Evidence,
1035    ) -> Result<Self, FreeSpaceError> {
1036        if requested_support(request.domain()).is_some() {
1037            return Err(FreeSpaceError::MissingSupportEvidence);
1038        }
1039        validate_placement_witness(&request, &frame, &evidence)?;
1040        Ok(Self {
1041            request,
1042            frame,
1043            support_evidence: None,
1044            evidence,
1045        })
1046    }
1047    pub fn try_new_supported(
1048        request: PlacementRequest,
1049        frame: MetricFrame,
1050        support_evidence: CompleteSupportEvidence,
1051        evidence: Evidence,
1052    ) -> Result<Self, FreeSpaceError> {
1053        validate_placement_witness(&request, &frame, &evidence)?;
1054        let required =
1055            requested_support(request.domain()).ok_or(FreeSpaceError::SupportEvidenceMismatch)?;
1056        if support_evidence.support() != required.support()
1057            || support_evidence.frame() != &frame
1058            || support_evidence.maximum_gap_metres() > required.maximum_gap_metres()
1059        {
1060            return Err(FreeSpaceError::SupportEvidenceMismatch);
1061        }
1062        Ok(Self {
1063            request,
1064            frame,
1065            support_evidence: Some(Box::new(support_evidence)),
1066            evidence,
1067        })
1068    }
1069    pub fn request(&self) -> &PlacementRequest {
1070        &self.request
1071    }
1072    pub fn frame(&self) -> &MetricFrame {
1073        &self.frame
1074    }
1075    pub fn support_evidence(&self) -> Option<&CompleteSupportEvidence> {
1076        self.support_evidence.as_deref()
1077    }
1078    pub fn evidence(&self) -> &Evidence {
1079        &self.evidence
1080    }
1081}
1082
1083/// Exact, complete evidence that no valid placement exists.
1084#[derive(Clone, Debug, PartialEq)]
1085pub struct CompletePlacementEvidence {
1086    request: PlacementRequest,
1087    evidence: Evidence,
1088}
1089impl CompletePlacementEvidence {
1090    pub fn try_new(request: PlacementRequest, evidence: Evidence) -> Result<Self, FreeSpaceError> {
1091        if !reviewable_exact_evidence(&evidence) {
1092            return Err(FreeSpaceError::IncompleteClearanceEvidence);
1093        }
1094        Ok(Self { request, evidence })
1095    }
1096    pub fn request(&self) -> &PlacementRequest {
1097        &self.request
1098    }
1099    pub fn evidence(&self) -> &Evidence {
1100        &self.evidence
1101    }
1102}
1103
1104#[derive(Clone, Debug, PartialEq)]
1105pub enum PlacementOutcome {
1106    Found(ClearancePlacementEvidence),
1107    NoPlacement(CompletePlacementEvidence),
1108}
1109
1110#[derive(Clone, Debug, PartialEq)]
1111pub struct FreeAreaEvidence {
1112    request: FreeAreaRequest,
1113    available_area: AreaInterval,
1114    evidence: Evidence,
1115}
1116impl FreeAreaEvidence {
1117    pub fn try_new(
1118        request: FreeAreaRequest,
1119        available_area: AreaInterval,
1120        evidence: Evidence,
1121    ) -> Result<Self, FreeSpaceError> {
1122        if !reviewable_exact_evidence(&evidence) {
1123            return Err(FreeSpaceError::InexactAreaEvidence);
1124        }
1125        Ok(Self {
1126            request,
1127            available_area,
1128            evidence,
1129        })
1130    }
1131    pub fn request(&self) -> &FreeAreaRequest {
1132        &self.request
1133    }
1134    pub fn available_area(&self) -> &AreaInterval {
1135        &self.available_area
1136    }
1137    pub fn evidence(&self) -> &Evidence {
1138        &self.evidence
1139    }
1140}
1141
1142pub trait FreeSpaceService: Send + Sync + 'static {
1143    fn assess_clearance(
1144        &self,
1145        request: &ClearanceRequest,
1146    ) -> Result<ClearanceOutcome, FreeSpaceError>;
1147    fn find_placement(
1148        &self,
1149        request: &PlacementRequest,
1150    ) -> Result<PlacementOutcome, FreeSpaceError>;
1151    fn measure_free_area(
1152        &self,
1153        request: &FreeAreaRequest,
1154    ) -> Result<FreeAreaEvidence, FreeSpaceError>;
1155    /// Whether a clearance footprint lies inside its scopes. A service that
1156    /// does not compare footprints refuses, never answering either way.
1157    fn assess_containment(
1158        &self,
1159        request: &ContainmentRequest,
1160    ) -> Result<ContainmentOutcome, FreeSpaceError> {
1161        let _ = request;
1162        Err(FreeSpaceError::Unavailable(
1163            "this free-space service does not compare clearance footprints with scopes".into(),
1164        ))
1165    }
1166    /// Whether the tops of the request's supports hold a clearance
1167    /// footprint. A service that does not compare footprints with supports
1168    /// refuses, never answering either way.
1169    fn assess_support_coverage(
1170        &self,
1171        request: &SupportCoverageRequest,
1172    ) -> Result<SupportCoverageOutcome, FreeSpaceError> {
1173        let _ = request;
1174        Err(FreeSpaceError::Unavailable(
1175            "this free-space service does not compare clearance footprints with supports".into(),
1176        ))
1177    }
1178    /// Where a path of the request's width can run in its space, and which
1179    /// entrances and components it comes near (see [`CirculationMap`]). A
1180    /// service that does not map circulation refuses.
1181    fn map_circulation(
1182        &self,
1183        request: &CirculationRequest,
1184    ) -> Result<CirculationMap, FreeSpaceError> {
1185        let _ = request;
1186        Err(FreeSpaceError::Unavailable(
1187            "this free-space service does not map circulation".into(),
1188        ))
1189    }
1190}
1191
1192#[derive(Clone)]
1193pub struct FreeSpaceServiceHandle(Arc<dyn FreeSpaceService>);
1194impl FreeSpaceServiceHandle {
1195    pub fn new(service: Arc<dyn FreeSpaceService>) -> Self {
1196        Self(service)
1197    }
1198    pub fn assess_clearance(
1199        &self,
1200        request: &ClearanceRequest,
1201    ) -> Result<ClearanceOutcome, FreeSpaceError> {
1202        let outcome = self.0.assess_clearance(request)?;
1203        let actual = match &outcome {
1204            ClearanceOutcome::Clear(value) => value.request(),
1205            ClearanceOutcome::Obstructed(value) => value.request(),
1206        };
1207        if actual != request {
1208            return Err(FreeSpaceError::ResponseRequestMismatch);
1209        }
1210        Ok(outcome)
1211    }
1212    pub fn find_placement(
1213        &self,
1214        request: &PlacementRequest,
1215    ) -> Result<PlacementOutcome, FreeSpaceError> {
1216        let outcome = self.0.find_placement(request)?;
1217        let actual = match &outcome {
1218            PlacementOutcome::Found(value) => value.request(),
1219            PlacementOutcome::NoPlacement(value) => value.request(),
1220        };
1221        if actual != request {
1222            return Err(FreeSpaceError::ResponseRequestMismatch);
1223        }
1224        Ok(outcome)
1225    }
1226    pub fn measure_free_area(
1227        &self,
1228        request: &FreeAreaRequest,
1229    ) -> Result<FreeAreaEvidence, FreeSpaceError> {
1230        let evidence = self.0.measure_free_area(request)?;
1231        if evidence.request() != request {
1232            return Err(FreeSpaceError::ResponseRequestMismatch);
1233        }
1234        Ok(evidence)
1235    }
1236    pub fn assess_containment(
1237        &self,
1238        request: &ContainmentRequest,
1239    ) -> Result<ContainmentOutcome, FreeSpaceError> {
1240        let outcome = self.0.assess_containment(request)?;
1241        let actual = match &outcome {
1242            ContainmentOutcome::Inside(value) | ContainmentOutcome::Outside(value) => {
1243                value.request()
1244            }
1245        };
1246        if actual != request {
1247            return Err(FreeSpaceError::ResponseRequestMismatch);
1248        }
1249        Ok(outcome)
1250    }
1251}
1252
1253impl FreeSpaceServiceHandle {
1254    /// Whether the supports' tops hold the footprint; an answer to another
1255    /// request is refused.
1256    ///
1257    /// # Errors
1258    ///
1259    /// The backend's refusal, or [`FreeSpaceError::ResponseRequestMismatch`].
1260    pub fn assess_support_coverage(
1261        &self,
1262        request: &SupportCoverageRequest,
1263    ) -> Result<SupportCoverageOutcome, FreeSpaceError> {
1264        let outcome = self.0.assess_support_coverage(request)?;
1265        let actual = match &outcome {
1266            SupportCoverageOutcome::Supported(value)
1267            | SupportCoverageOutcome::Unsupported(value) => value.request(),
1268        };
1269        if actual != request {
1270            return Err(FreeSpaceError::ResponseRequestMismatch);
1271        }
1272        Ok(outcome)
1273    }
1274
1275    /// Maps circulation and checks that the map answers `request`.
1276    ///
1277    /// # Errors
1278    ///
1279    /// The backend's refusal, or [`FreeSpaceError::ResponseRequestMismatch`]
1280    /// for a map of another request.
1281    pub fn map_circulation(
1282        &self,
1283        request: &CirculationRequest,
1284    ) -> Result<CirculationMap, FreeSpaceError> {
1285        let map = self.0.map_circulation(request)?;
1286        if map.request() != request {
1287            return Err(FreeSpaceError::ResponseRequestMismatch);
1288        }
1289        Ok(map)
1290    }
1291}
1292
1293fn valid_non_negative(value: f64) -> bool {
1294    value.is_finite() && value >= 0.0
1295}
1296fn valid_positive(value: f64) -> bool {
1297    value.is_finite() && value > 0.0
1298}
axioval_engine/free_space.rs

axioval_engine/
free_space.rs
