Skip to main content

spacelab_estimation/
screening.rs

1//! Finding the conjunctions that [`conjunction`](crate::conjunction) then puts a probability on.
2//!
3//! `conjunction.rs` starts from a relative state *at the time of closest approach*. Something has to
4//! produce that epoch, and this is it: the local minima of the separation, and the cheap filter that
5//! decides which pairs are worth looking for them in.
6//!
7//! # The minimum is a sign change, not a search over distances
8//!
9//! Minimising `|Δr|` directly means a one-dimensional optimisation with no bracket and no guarantee
10//! of which basin it lands in. Its derivative is better behaved: with `f(t) = ½|Δr|²`,
11//!
12//! ```text
13//! f'(t) = Δr · Δv
14//! ```
15//!
16//! so every closest approach is a zero of `Δr · Δv` where the sign goes **negative to positive** —
17//! approaching, then receding. A maximum is the same zero with the sign the other way, and it is
18//! discarded by the direction rather than by comparing distances afterwards. That turns the problem
19//! into a bracketed root find, which cannot converge to the wrong kind of stationary point and
20//! cannot fail to terminate.
21//!
22//! # Nothing here reports an empty sky by accident
23//!
24//! A screen has one failure mode that matters more than the rest: *no conjunctions found* is the
25//! answer a caller acts on by doing nothing. A malformed step or an ephemeris that runs out mid-span
26//! must therefore not be able to produce it, which is why [`closest_approaches`] returns
27//! [`ScreeningError`] rather than quietly returning with nothing emitted. Every rejected argument
28//! names itself and its value.
29//!
30//! # What the step size can and cannot promise
31//!
32//! The coarse scan sees a sign change only if the two samples straddle it. Two minima closer
33//! together than `step` are one bracket, and the search reports one approach where there were two.
34//! **This is not defended against, because it cannot be**: no sampled scan can bound what it did not
35//! sample. The step is the caller's, and it must be shorter than the interval between successive
36//! extrema of the separation — for two low-Earth orbits that is a few minutes, and for a co-orbiting
37//! pair with a slow relative drift it can be much longer. `a_step_too_coarse_to_resolve_two_minima_
38//! reports_one` pins the failure mode rather than pretending it is absent.
39
40/// One closest approach: when, how close, and how fast.
41#[derive(Clone, Copy, Debug, PartialEq)]
42pub struct CloseApproach {
43    /// Time of closest approach, in the caller's own timescale.
44    pub tca: f64,
45    /// Separation at `tca`, metres.
46    pub distance: f64,
47    /// Relative speed at `tca`, m/s — the short-encounter model's own validity depends on this
48    /// being large enough that the relative motion is rectilinear over the encounter.
49    pub relative_speed: f64,
50}
51
52/// Why a scan could not be run to the end of its span. Each variant names the argument that was
53/// wrong and its value, so that "nothing found" is never the report for a malformed request.
54#[derive(Clone, Copy, Debug, PartialEq)]
55pub enum ScreeningError {
56    /// The sample interval is not a positive, finite number of seconds.
57    Step(f64),
58    /// The span needs more samples at this step than one scan will take. The step is well formed and
59    /// the *pair* is not, which is why it is not [`ScreeningError::Step`].
60    TooManySamples {
61        /// The requested sample interval, seconds.
62        step: f64,
63        /// `ceil((end - start) / step)`, against a ceiling of [`MAX_SAMPLES`].
64        requested: f64,
65    },
66    /// The refinement tolerance is not a positive, finite number of seconds.
67    Tolerance(f64),
68    /// `end - start` is zero, negative or not finite — which also covers either endpoint being NaN
69    /// or infinite, since the difference is then never a finite positive number.
70    Span {
71        /// The requested start of the scan.
72        start: f64,
73        /// The requested end of the scan.
74        end: f64,
75    },
76    /// The relative state was not finite at this epoch: the ephemeris stopped covering the span.
77    /// Approaches already reported through `emit` before it stand; the span past it was not scanned.
78    Coverage(f64),
79}
80
81impl core::fmt::Display for ScreeningError {
82    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
83        match self {
84            Self::Step(step) => {
85                write!(f, "sample interval {step} is not positive and finite")
86            }
87            Self::TooManySamples { step, requested } => {
88                write!(
89                    f,
90                    "a {step} s step over this span is {requested} samples, past the {MAX_SAMPLES} a scan will take"
91                )
92            }
93            Self::Tolerance(tolerance) => {
94                write!(
95                    f,
96                    "refinement tolerance {tolerance} is not positive and finite"
97                )
98            }
99            Self::Span { start, end } => {
100                write!(
101                    f,
102                    "scan span [{start}, {end}] is empty, inverted or not finite"
103                )
104            }
105            Self::Coverage(epoch) => {
106                write!(f, "the relative state is not finite at epoch {epoch}")
107            }
108        }
109    }
110}
111
112impl core::error::Error for ScreeningError {}
113
114fn dot(a: &[f64; 3], b: &[f64; 3]) -> f64 {
115    a[0] * b[0] + a[1] * b[1] + a[2] * b[2]
116}
117
118fn norm(a: &[f64; 3]) -> f64 {
119    libm::sqrt(dot(a, a))
120}
121
122/// Report every closest approach of `relative` in `[start, end]`, in time order.
123///
124/// `relative` returns the relative position and velocity `(Δr, Δv)` — object 2 minus object 1, in
125/// one common inertial frame, the same convention [`ConjunctionGeometry`](crate::conjunction::ConjunctionGeometry)
126/// takes. The scan samples every `step` seconds and refines each bracket by bisection until it is
127/// narrower than `tolerance`; `emit` is called once per approach found.
128///
129/// Bisection rather than a secant or Brent step, deliberately: the bracket is the guarantee, and
130/// halving it a fixed number of times makes the cost `ceil(log2(step/tolerance))` evaluations per
131/// approach — 26 for a 60 s step refined to a microsecond — with no dependence on how the function
132/// behaves inside. A superlinear step would be fewer evaluations on a smooth pair and unbounded on a
133/// pathological one, and a screening run's cost has to be predictable.
134///
135/// # Errors
136///
137/// Returns [`ScreeningError`] for a step or tolerance that is not positive and finite, for a span
138/// that is not a finite positive interval, for a step too small to advance the clock at this epoch,
139/// and for a non-finite sample. The last of these ends the scan where the ephemeris did rather than
140/// propagating a NaN into a bracket: an ephemeris that stops covering the span is a fact about the
141/// input, and continuing past it would invent approaches out of comparisons against NaN. Whatever
142/// was emitted before that epoch is still the caller's to keep.
143pub fn closest_approaches<F>(
144    relative: F,
145    start: f64,
146    end: f64,
147    step: f64,
148    tolerance: f64,
149    emit: &mut dyn FnMut(CloseApproach),
150) -> Result<(), ScreeningError>
151where
152    F: Fn(f64) -> ([f64; 3], [f64; 3]),
153{
154    // Written against `is_finite` rather than as a negated comparison so that NaN is rejected by
155    // name: `!(step > 0.0)` and `step <= 0.0` agree on every value except NaN, which is exactly the
156    // argument a caller passes by accident.
157    if !step.is_finite() || step <= 0.0 {
158        return Err(ScreeningError::Step(step));
159    }
160    if !tolerance.is_finite() || tolerance <= 0.0 {
161        return Err(ScreeningError::Tolerance(tolerance));
162    }
163    // The span rather than the two endpoints: `end - start` is NaN or infinite whenever either of
164    // them is, so one test rejects an inverted span, an empty one, and every non-finite endpoint.
165    let span = end - start;
166    if !span.is_finite() || span <= 0.0 {
167        return Err(ScreeningError::Span { start, end });
168    }
169
170    // The scan is a counted number of samples, not an accumulation. Two reasons, and the second is
171    // the one that decides it. `t += step` drifts by an ulp per step — 2.9e6 steps in a day at 30 s
172    // — while `start + i·step` commits one rounding per sample; and at a large epoch `t + step` can
173    // round back to `t`, which makes the loop's termination depend on the same arithmetic it is
174    // scanning with. The count is *clamped* rather than checked, because a bound that a comparison
175    // can be mutated out of is not a bound; the comparison below only decides what to report.
176    let requested = libm::ceil(span / step);
177    #[expect(
178        clippy::cast_possible_truncation,
179        clippy::cast_sign_loss,
180        reason = "clamped to [1, MAX_SAMPLES] on the line above, so neither can happen"
181    )]
182    let count = requested.clamp(1.0, MAX_SAMPLES) as usize;
183    if requested > MAX_SAMPLES {
184        return Err(ScreeningError::TooManySamples { step, requested });
185    }
186
187    let rate = |t: f64| {
188        let (dr, dv) = relative(t);
189        dot(&dr, &dv)
190    };
191
192    let mut previous_t = start;
193    let mut previous = rate(start);
194    if !previous.is_finite() {
195        return Err(ScreeningError::Coverage(start));
196    }
197
198    for i in 1..=count {
199        #[expect(
200            clippy::cast_precision_loss,
201            reason = "i <= MAX_SAMPLES = 1e6, exactly representable in f64"
202        )]
203        let t = (start + i as f64 * step).min(end);
204        let current = rate(t);
205        if !current.is_finite() {
206            return Err(ScreeningError::Coverage(t));
207        }
208        // Negative to non-negative is a minimum; the other direction is a maximum and is skipped by
209        // this test rather than by measuring distances afterwards.
210        if previous < 0.0 && current >= 0.0 {
211            emit(refine(&relative, previous_t, t, tolerance));
212        }
213        previous_t = t;
214        previous = current;
215    }
216    Ok(())
217}
218
219/// The most samples one scan will take: eleven days at a one-second step, or a year at thirty
220/// seconds. Past any screening window, and past it the answer a caller wants is a coarser step
221/// rather than a longer wait.
222///
223/// Chosen low enough that its own boundary is reachable from a test. A ceiling no test can stand on
224/// is a ceiling nothing checks the sense of, and `>` against `>=` at the boundary is exactly the
225/// difference between refusing the largest legal scan and running it.
226pub const MAX_SAMPLES: f64 = 1.0e6;
227
228/// The most halvings any `f64` bracket can need. `f64::MAX` down to the smallest subnormal is 2 098
229/// doublings, so no interval outlives this count whatever its width — and the loop is counted rather
230/// than left to its own two exit tests, because a termination condition one wrong operator can
231/// disable is a hang rather than a wrong answer, and a wrong answer is the only kind a test can see.
232const MAX_BISECTIONS: usize = 2_100;
233
234/// Bisect `[a, b]`, where `Δr·Δv` is negative at `a` and non-negative at `b`, to `tolerance`.
235fn refine<F>(relative: &F, mut a: f64, mut b: f64, tolerance: f64) -> CloseApproach
236where
237    F: Fn(f64) -> ([f64; 3], [f64; 3]),
238{
239    for _ in 0..MAX_BISECTIONS {
240        if b - a <= tolerance {
241            break;
242        }
243        let mid = f64::midpoint(a, b);
244        // A midpoint that is not strictly inside is the interval exhausting `f64`, not a failure to
245        // converge; stopping there is the only honest answer and it terminates.
246        if mid <= a || mid >= b {
247            break;
248        }
249        let (dr, dv) = relative(mid);
250        if dot(&dr, &dv) < 0.0 {
251            a = mid;
252        } else {
253            b = mid;
254        }
255    }
256    let tca = f64::midpoint(a, b);
257    let (dr, dv) = relative(tca);
258    CloseApproach {
259        tca,
260        distance: norm(&dr),
261        relative_speed: norm(&dv),
262    }
263}
264
265/// Whether two orbits are far enough apart in radius that no conjunction is possible — the first and
266/// cheapest stage of an all-on-all screen (Hoots, Crawford & Roehrich 1984, filter 1).
267///
268/// All four arguments are geocentric distances in metres. The pair is separable when one object's
269/// perigee clears the other's apogee by more than `threshold`, because the two spherical shells the
270/// orbits are confined to do not then come within `threshold` of each other at any epoch, whatever
271/// the phasing or the plane. `threshold` is the screening distance — the miss distance below which a
272/// pair is worth propagating.
273///
274/// This is a *geometric certainty*, not a heuristic, which is what makes it safe to apply before any
275/// propagation: it discards pairs that cannot conjunct rather than pairs that probably will not. The
276/// converse does not hold and is not claimed — a pair that survives the filter usually still does not
277/// conjunct, and that is what the later stages are for.
278///
279/// Returns `false` for any non-finite input, so a corrupt element set is propagated and examined
280/// rather than silently dropped.
281#[must_use]
282pub fn radially_separated(
283    perigee_a: f64,
284    apogee_a: f64,
285    perigee_b: f64,
286    apogee_b: f64,
287    threshold: f64,
288) -> bool {
289    if !perigee_a.is_finite()
290        || !apogee_a.is_finite()
291        || !perigee_b.is_finite()
292        || !apogee_b.is_finite()
293        || !threshold.is_finite()
294    {
295        return false;
296    }
297    perigee_a - apogee_b > threshold || perigee_b - apogee_a > threshold
298}
299
300#[cfg(test)]
301mod tests {
302    #![allow(clippy::expect_used)]
303    // The dense-scan oracle indexes 200 000 samples; the counts are exact in `f64` a decade over.
304    #![allow(clippy::cast_precision_loss)]
305
306    use super::*;
307
308    /// The separation, computed without [`norm`] or [`dot`].
309    ///
310    /// `norm(a)` is `sqrt(dot(a, a))`, so an oracle built on it shares the inner product with the
311    /// search it is supposed to be checking — and a wrong `dot` would move both sides together. This
312    /// is the same arithmetic written out separately, which is what makes the comparison mean
313    /// something.
314    fn separation(d: &[f64; 3]) -> f64 {
315        libm::sqrt(d[0] * d[0] + d[1] * d[1] + d[2] * d[2])
316    }
317
318    /// Two objects passing on straight lines: the minimum is at a time with a closed form.
319    ///
320    /// Object 2 crosses object 1's track at `closest` metres, moving at `speed`. Then
321    /// `Δr(t) = (v t − offset, closest, 0)` and the minimum is at `t = offset / v`, exactly.
322    fn rectilinear(closest: f64, speed: f64, offset: f64) -> impl Fn(f64) -> ([f64; 3], [f64; 3]) {
323        move |t: f64| ([speed * t - offset, closest, 0.0], [speed, 0.0, 0.0])
324    }
325
326    fn collect<F>(
327        relative: F,
328        start: f64,
329        end: f64,
330        step: f64,
331        tolerance: f64,
332    ) -> Result<Vec<CloseApproach>, ScreeningError>
333    where
334        F: Fn(f64) -> ([f64; 3], [f64; 3]),
335    {
336        let mut out = Vec::new();
337        closest_approaches(relative, start, end, step, tolerance, &mut |c| out.push(c))?;
338        Ok(out)
339    }
340
341    /// A geometry with a closed-form answer, to the refinement tolerance and no worse.
342    #[test]
343    fn a_rectilinear_pass_is_found_where_the_closed_form_puts_it() {
344        let (closest, speed, offset) = (1_500.0, 12_000.0, 600_000.0);
345        let found = collect(rectilinear(closest, speed, offset), 0.0, 120.0, 5.0, 1e-9)
346            .expect("well-formed arguments");
347        assert_eq!(found.len(), 1, "{found:?}");
348        let expected = offset / speed;
349        assert!(
350            libm::fabs(found[0].tca - expected) < 1e-9,
351            "{} s against the closed-form {expected} s",
352            found[0].tca
353        );
354        assert!(
355            libm::fabs(found[0].distance - closest) < 1e-3,
356            "{} m against the {closest} m the geometry has",
357            found[0].distance
358        );
359        assert!(libm::fabs(found[0].relative_speed - speed) < 1e-9);
360    }
361
362    const MU: f64 = 3.986_004_418e14;
363
364    fn mean_motion(r: f64) -> f64 {
365        libm::sqrt(MU / (r * r * r))
366    }
367
368    /// Two circular co-planar orbits, the second started `phase` radians ahead.
369    ///
370    /// Their separation is `√(r₁² + r₂² − 2r₁r₂ cos Δφ)` with `Δφ = (n₂ − n₁)t + phase`, so the
371    /// minima are where the two align and the beat period is `2π/|n₂ − n₁|`. That period is what
372    /// makes the geometry usable or not: a 40 km altitude difference beats over **7.9 days**, and a
373    /// span short enough to scan at 30 s contains no minimum at all. The pair below is 500 km apart
374    /// for that reason and no other.
375    fn co_planar(r1: f64, r2: f64, phase: f64) -> impl Fn(f64) -> ([f64; 3], [f64; 3]) {
376        let (n1, n2) = (mean_motion(r1), mean_motion(r2));
377        move |t: f64| {
378            let (s1, c1) = (libm::sin(n1 * t), libm::cos(n1 * t));
379            let (s2, c2) = (libm::sin(n2 * t + phase), libm::cos(n2 * t + phase));
380            (
381                [r2 * c2 - r1 * c1, r2 * s2 - r1 * s1, 0.0],
382                [
383                    -r2 * n2 * s2 + r1 * n1 * s1,
384                    r2 * n2 * c2 - r1 * n1 * c1,
385                    0.0,
386                ],
387            )
388        }
389    }
390
391    /// The same pair with object 2's plane tilted by `inc`, so that `Δr` and `Δv` are genuinely
392    /// three-dimensional.
393    ///
394    /// Every other geometry here is planar, which leaves the third component of the inner product
395    /// multiplying zero by zero — unexercised, in a screen that will be handed real orbits, no two
396    /// of which share a plane.
397    fn inclined(r1: f64, r2: f64, inc: f64, phase: f64) -> impl Fn(f64) -> ([f64; 3], [f64; 3]) {
398        let (n1, n2) = (mean_motion(r1), mean_motion(r2));
399        let (si, ci) = (libm::sin(inc), libm::cos(inc));
400        move |t: f64| {
401            let (s1, c1) = (libm::sin(n1 * t), libm::cos(n1 * t));
402            let (s2, c2) = (libm::sin(n2 * t + phase), libm::cos(n2 * t + phase));
403            (
404                [r2 * c2 - r1 * c1, r2 * s2 * ci - r1 * s1, r2 * s2 * si],
405                [
406                    -r2 * n2 * s2 + r1 * n1 * s1,
407                    r2 * n2 * c2 * ci - r1 * n1 * c1,
408                    r2 * n2 * c2 * si,
409                ],
410            )
411        }
412    }
413
414    /// The beat period of the co-planar pair, seconds.
415    fn beat(r1: f64, r2: f64) -> f64 {
416        core::f64::consts::TAU / libm::fabs(mean_motion(r2) - mean_motion(r1))
417    }
418
419    /// Every local minimum of the separation in `[0, span]`, by dense sampling of `|Δr|` itself.
420    ///
421    /// The oracle shares nothing with the search: it samples the separation rather than its
422    /// derivative, and computes it with [`separation`] rather than [`norm`].
423    fn dense_minima<F>(motion: &F, span: f64, samples: usize) -> Vec<f64>
424    where
425        F: Fn(f64) -> ([f64; 3], [f64; 3]),
426    {
427        let at = |i: usize| separation(&motion(span * i as f64 / samples as f64).0);
428        let mut minima = Vec::new();
429        for i in 1..samples {
430            let (before, here, after) = (at(i - 1), at(i), at(i + 1));
431            if here < before && here <= after {
432                minima.push(span * i as f64 / samples as f64);
433            }
434        }
435        minima
436    }
437
438    const DENSE_SAMPLES: usize = 200_000;
439
440    /// Every minimum in the span is found, in order, and where a dense scan puts it.
441    #[test]
442    fn every_minimum_in_the_span_is_found_and_agrees_with_a_dense_scan() {
443        let (r1, r2) = (7_000_000.0_f64, 7_500_000.0_f64);
444        let motion = co_planar(r1, r2, 1.0);
445        // Two full beats, so there are two alignments to find and the phase offset puts neither on
446        // a boundary. The 500 km separation is what makes that span 118 000 s rather than 16 days.
447        let span = 2.0 * beat(r1, r2);
448
449        let found = collect(&motion, 0.0, span, 30.0, 1e-6).expect("well-formed arguments");
450        assert!(found.len() >= 2, "only {} minima found", found.len());
451
452        let minima = dense_minima(&motion, span, DENSE_SAMPLES);
453        assert_eq!(
454            found.len(),
455            minima.len(),
456            "search found {} minima, the dense scan {}",
457            found.len(),
458            minima.len()
459        );
460
461        // The dense scan resolves a time to half its own sample spacing, and no better.
462        let resolution = span / DENSE_SAMPLES as f64;
463        for (c, &t) in found.iter().zip(&minima) {
464            assert!(
465                libm::fabs(c.tca - t) <= resolution,
466                "{} s against the dense scan's {t} s, past its own {resolution} s resolution",
467                c.tca
468            );
469        }
470        // In time order, which the caller is entitled to assume.
471        for pair in found.windows(2) {
472            assert!(pair[0].tca < pair[1].tca, "{found:?} is not in time order");
473        }
474    }
475
476    /// The same agreement on a pair whose planes differ, where every component of `Δr · Δv` and of
477    /// the reported distance carries weight.
478    #[test]
479    fn an_inclined_pair_exercises_the_out_of_plane_component() {
480        let (r1, r2) = (7_000_000.0_f64, 7_500_000.0_f64);
481        let motion = inclined(r1, r2, 63.4_f64.to_radians(), 1.0);
482        // Four revolutions of the lower object: long enough for several encounters near the line of
483        // nodes, short enough that a 15 s step resolves each of them.
484        let span = 4.0 * core::f64::consts::TAU / mean_motion(r1);
485
486        // The geometry has to be three-dimensional for this test to mean anything at all.
487        let (dr, dv) = motion(0.3 * span);
488        assert!(
489            libm::fabs(dr[2]) > 1.0e5 && libm::fabs(dv[2]) > 1.0e2,
490            "the out-of-plane components are {} m and {} m/s, too small to exercise anything",
491            dr[2],
492            dv[2]
493        );
494
495        let found = collect(&motion, 0.0, span, 15.0, 1e-6).expect("well-formed arguments");
496        let minima = dense_minima(&motion, span, DENSE_SAMPLES);
497        assert_eq!(
498            found.len(),
499            minima.len(),
500            "search found {} minima, the dense scan {}",
501            found.len(),
502            minima.len()
503        );
504
505        let resolution = span / DENSE_SAMPLES as f64;
506        for (c, &t) in found.iter().zip(&minima) {
507            assert!(
508                libm::fabs(c.tca - t) <= resolution,
509                "{} s against the dense scan's {t} s, past its own {resolution} s resolution",
510                c.tca
511            );
512            // And the distance it reports is the separation at its own epoch, computed the other
513            // way — the check that the inner product behind `norm` is the right one.
514            let (dr, dv) = motion(c.tca);
515            assert!(
516                libm::fabs(c.distance - separation(&dr)) < 1e-6,
517                "reported {} m against {} m at the same epoch",
518                c.distance,
519                separation(&dr)
520            );
521            assert!(
522                libm::fabs(c.relative_speed - separation(&dv)) < 1e-6,
523                "reported {} m/s against {} m/s at the same epoch",
524                c.relative_speed,
525                separation(&dv)
526            );
527        }
528    }
529
530    /// A maximum of the separation is a zero of the same function with the other sign, and it must
531    /// not be reported. Starting the same geometry half a period later puts a maximum first.
532    #[test]
533    fn a_maximum_of_the_separation_is_not_reported_as_an_approach() {
534        let (closest, speed, offset) = (1_500.0, 12_000.0, 600_000.0);
535        // Receding throughout: the derivative is positive everywhere, so there is no bracket.
536        let found = collect(rectilinear(closest, speed, offset), 60.0, 120.0, 5.0, 1e-9)
537            .expect("well-formed arguments");
538        assert!(found.is_empty(), "{found:?}");
539        // And approaching throughout, where it is negative everywhere.
540        let found = collect(rectilinear(closest, speed, offset), 0.0, 40.0, 5.0, 1e-9)
541            .expect("well-formed arguments");
542        assert!(found.is_empty(), "{found:?}");
543    }
544
545    /// The documented failure mode, pinned: two minima closer together than the step are one bracket
546    /// and are reported as one approach. A scan cannot bound what it did not sample, and a test that
547    /// asserted otherwise would be asserting something false.
548    #[test]
549    fn a_step_too_coarse_to_resolve_two_minima_reports_one() {
550        let (r1, r2) = (7_000_000.0_f64, 7_500_000.0_f64);
551        let motion = co_planar(r1, r2, 1.0);
552        let span = 2.0 * beat(r1, r2);
553
554        let fine = collect(&motion, 0.0, span, 30.0, 1e-6).expect("well-formed arguments");
555        let coarse = collect(&motion, 0.0, span, 0.75 * span, 1e-6).expect("well-formed arguments");
556        assert!(
557            coarse.len() < fine.len(),
558            "a one-sample scan found {} of the {} minima, so this test no longer demonstrates the \
559             limitation it documents",
560            coarse.len(),
561            fine.len()
562        );
563    }
564
565    /// Every rejected argument names itself, and none of them is reported as an empty sky.
566    ///
567    /// The geometry is deliberately one that runs out of coverage at 40 s: under a *correct* guard
568    /// it is never called, because each row is rejected before the scan starts. It is there so that
569    /// a guard which stops rejecting cannot scan an unbounded span, and so that what it returns
570    /// instead is a different error rather than a hang.
571    #[test]
572    fn every_malformed_argument_is_reported_as_itself() {
573        let good = rectilinear(1_500.0, 12_000.0, 600_000.0);
574        let covers_40_s = |t: f64| {
575            if t > 40.0 {
576                ([f64::NAN; 3], [f64::NAN; 3])
577            } else {
578                good(t)
579            }
580        };
581        let cases = [
582            (0.0, 120.0, 0.0, 1e-9, ScreeningError::Step(0.0)),
583            (0.0, 120.0, -5.0, 1e-9, ScreeningError::Step(-5.0)),
584            (0.0, 120.0, f64::NAN, 1e-9, ScreeningError::Step(f64::NAN)),
585            (0.0, 120.0, 5.0, 0.0, ScreeningError::Tolerance(0.0)),
586            (0.0, 120.0, 5.0, -1e-9, ScreeningError::Tolerance(-1e-9)),
587            (
588                0.0,
589                120.0,
590                5.0,
591                f64::NAN,
592                ScreeningError::Tolerance(f64::NAN),
593            ),
594            (
595                0.0,
596                0.0,
597                5.0,
598                1e-9,
599                ScreeningError::Span {
600                    start: 0.0,
601                    end: 0.0,
602                },
603            ),
604            (
605                120.0,
606                0.0,
607                5.0,
608                1e-9,
609                ScreeningError::Span {
610                    start: 120.0,
611                    end: 0.0,
612                },
613            ),
614            (
615                0.0,
616                f64::NAN,
617                5.0,
618                1e-9,
619                ScreeningError::Span {
620                    start: 0.0,
621                    end: f64::NAN,
622                },
623            ),
624            (
625                f64::NAN,
626                120.0,
627                5.0,
628                1e-9,
629                ScreeningError::Span {
630                    start: f64::NAN,
631                    end: 120.0,
632                },
633            ),
634            (
635                0.0,
636                f64::INFINITY,
637                5.0,
638                1e-9,
639                ScreeningError::Span {
640                    start: 0.0,
641                    end: f64::INFINITY,
642                },
643            ),
644            (
645                f64::NEG_INFINITY,
646                120.0,
647                5.0,
648                1e-9,
649                ScreeningError::Span {
650                    start: f64::NEG_INFINITY,
651                    end: 120.0,
652                },
653            ),
654        ];
655        for (start, end, step, tolerance, expected) in cases {
656            let outcome = collect(covers_40_s, start, end, step, tolerance);
657            // NaN payloads are not equal to themselves, so the variant is compared by its debug
658            // form; the finite rows still pin the value.
659            assert_eq!(
660                format!("{outcome:?}"),
661                format!("{:?}", Err::<Vec<CloseApproach>, _>(expected)),
662                "({start}, {end}, {step}, {tolerance})"
663            );
664        }
665    }
666
667    /// A step below the epoch's own resolution still scans, because the samples are indexed rather
668    /// than accumulated.
669    ///
670    /// `ulp(1e16)` is 2 s, so `t += 1.0` at that epoch never moves at all and an accumulating scan
671    /// would sit on its first sample forever. `start + i·step` reaches every representable epoch in
672    /// the span, and the pass is still found — to the 2 s the type has left, which is the honest
673    /// answer rather than an error.
674    #[test]
675    fn a_step_below_the_epochs_resolution_still_advances_because_the_scan_is_indexed() {
676        let start = 1.0e16_f64;
677        assert_eq!(
678            (start + 1.0).to_bits(),
679            start.to_bits(),
680            "the epoch is not past f64's reach, so this test demonstrates nothing"
681        );
682
683        // A pass whose closest approach is 30 s into the span, expressed against `start` so that the
684        // geometry itself carries no cancellation.
685        let motion = move |t: f64| {
686            let dt = t - start;
687            (
688                [12_000.0 * dt - 360_000.0, 1_500.0, 0.0],
689                [12_000.0, 0.0, 0.0],
690            )
691        };
692        let found = collect(motion, start, start + 60.0, 1.0, 1e-9).expect("well-formed arguments");
693        assert_eq!(found.len(), 1, "{found:?}");
694        assert!(
695            libm::fabs(found[0].tca - (start + 30.0)) <= 2.0,
696            "{} s against {} s, past the 2 s ulp that is all the type has left",
697            found[0].tca,
698            start + 30.0
699        );
700    }
701
702    /// A step so fine that the span would take more samples than a scan will run is refused by
703    /// name, rather than started and abandoned.
704    #[test]
705    fn a_step_that_asks_for_more_samples_than_a_scan_will_take_is_refused() {
706        let outcome = collect(
707            rectilinear(1_500.0, 12_000.0, 600_000.0),
708            0.0,
709            60.0,
710            1e-9,
711            1e-12,
712        );
713        assert_eq!(
714            outcome,
715            Err(ScreeningError::TooManySamples {
716                step: 1e-9,
717                requested: 6.0e10
718            }),
719            "{outcome:?}"
720        );
721    }
722
723    /// The ceiling is a ceiling and not a fence one short of it: exactly [`MAX_SAMPLES`] runs, and
724    /// one more does not.
725    ///
726    /// The accepting half is the half worth paying for. Refusing the largest legal scan and running
727    /// it are the same code with one character changed, and nothing but a scan that actually reaches
728    /// the boundary separates them — which is the whole reason `MAX_SAMPLES` is a number a test can
729    /// stand on.
730    #[test]
731    fn the_sample_ceiling_admits_exactly_its_own_count_and_no_more() {
732        let evaluations = core::cell::Cell::new(0_usize);
733        let end = MAX_SAMPLES;
734        let at_the_ceiling = collect(counted_exact_pass(&evaluations), 0.0, end, 1.0, 1.0);
735        assert!(at_the_ceiling.is_ok(), "{at_the_ceiling:?}");
736        // One sample before the loop, then exactly `MAX_SAMPLES` of them; the pass at 3 s adds its
737        // own bisection on top, and only the leading term is the point.
738        #[expect(
739            clippy::cast_precision_loss,
740            reason = "the count is bounded by MAX_SAMPLES plus a bisection, well under 2^53"
741        )]
742        let taken = evaluations.get() as f64;
743        assert!(
744            taken > MAX_SAMPLES,
745            "{taken} evaluations, so the scan did not reach the ceiling"
746        );
747
748        let one_past = collect(
749            rectilinear(1_500.0, 12_000.0, 0.0),
750            0.0,
751            end + 1.0,
752            1.0,
753            1.0,
754        );
755        assert_eq!(
756            one_past,
757            Err(ScreeningError::TooManySamples {
758                step: 1.0,
759                requested: MAX_SAMPLES + 1.0
760            }),
761            "{one_past:?}"
762        );
763    }
764
765    /// An ephemeris that stops covering the span ends the scan there, naming the epoch, and does not
766    /// turn NaN comparisons into approaches. Both the first sample and a later one are checked,
767    /// because the first is guarded before the loop and the rest inside it.
768    #[test]
769    fn a_non_finite_sample_ends_the_scan_rather_than_inventing_an_approach() {
770        let good = rectilinear(1_500.0, 12_000.0, 600_000.0);
771        let stops_at_40 = |t: f64| {
772            if t > 40.0 {
773                ([f64::NAN; 3], [f64::NAN; 3])
774            } else {
775                good(t)
776            }
777        };
778        assert_eq!(
779            collect(stops_at_40, 0.0, 120.0, 5.0, 1e-9),
780            Err(ScreeningError::Coverage(45.0))
781        );
782
783        let bad_from_the_start = |_: f64| ([f64::NAN; 3], [f64::NAN; 3]);
784        assert_eq!(
785            collect(bad_from_the_start, 0.0, 120.0, 5.0, 1e-9),
786            Err(ScreeningError::Coverage(0.0))
787        );
788    }
789
790    /// Each error prints what it is, both directly and through `dyn Error`.
791    #[test]
792    fn every_error_names_its_own_argument() {
793        let messages = [
794            (
795                ScreeningError::Step(-5.0),
796                "sample interval -5 is not positive and finite",
797            ),
798            (
799                ScreeningError::TooManySamples {
800                    step: 1e-9,
801                    requested: 6.0e10,
802                },
803                "a 0.000000001 s step over this span is 60000000000 samples, past the 1000000 a scan will take",
804            ),
805            (
806                ScreeningError::Tolerance(0.0),
807                "refinement tolerance 0 is not positive and finite",
808            ),
809            (
810                ScreeningError::Span {
811                    start: 120.0,
812                    end: 0.0,
813                },
814                "scan span [120, 0] is empty, inverted or not finite",
815            ),
816            (
817                ScreeningError::Coverage(45.0),
818                "the relative state is not finite at epoch 45",
819            ),
820        ];
821        for (error, expected) in messages {
822            assert_eq!(format!("{error}"), expected);
823            let dynamic: &dyn core::error::Error = &error;
824            assert_eq!(format!("{dynamic}"), expected);
825        }
826    }
827
828    /// A geometry whose whole bisection is exact in `f64`: the TCA is at 3 s and every intermediate
829    /// midpoint is a power of two.
830    fn counted_exact_pass(
831        evaluations: &core::cell::Cell<usize>,
832    ) -> impl Fn(f64) -> ([f64; 3], [f64; 3]) {
833        move |t: f64| {
834            evaluations.set(evaluations.get() + 1);
835            ([1024.0 * t - 3072.0, 512.0, 0.0], [1024.0, 0.0, 0.0])
836        }
837    }
838
839    /// The refinement costs what the cost model says it costs, and stops where it says it stops.
840    ///
841    /// Bisection was chosen over a superlinear step *because* the cost is `ceil(log2(step/tolerance))`
842    /// evaluations and nothing else, so that claim is worth an assertion rather than a comment. The
843    /// bracket here is `[0, 8]` at a 1 s tolerance, so three halvings leave `[2, 3]` and the answer
844    /// at its centre — and both the epoch and the count are exact, which is what makes a loop that
845    /// halves once more, or one that halves until `f64` runs out, visible at all.
846    #[test]
847    fn the_refinement_costs_what_the_cost_model_says() {
848        let evaluations = core::cell::Cell::new(0_usize);
849        let found = collect(counted_exact_pass(&evaluations), 0.0, 8.0, 8.0, 1.0)
850            .expect("well-formed arguments");
851        assert_eq!(found.len(), 1, "{found:?}");
852        assert_eq!(
853            found[0].tca.to_bits(),
854            2.5_f64.to_bits(),
855            "{} s, where three exact halvings of [0, 8] put the bracket centre at 2.5",
856            found[0].tca
857        );
858        // Two samples for the scan, `ceil(log2(8/1)) = 3` midpoints, one final state at the answer.
859        assert_eq!(evaluations.get(), 6);
860    }
861
862    /// A tolerance finer than the type stops where the type stops, in a bounded number of steps.
863    ///
864    /// Asking for more digits than `f64` holds is a caller's mistake that the loop has to survive
865    /// rather than diagnose, and the midpoint test is what ends it. The count is asserted alongside
866    /// the answer because a midpoint test that stops working is not a wrong answer — it is a loop
867    /// that runs to `MAX_BISECTIONS`, and only the count says so.
868    #[test]
869    fn a_tolerance_finer_than_the_type_stops_at_the_types_own_resolution() {
870        let evaluations = core::cell::Cell::new(0_usize);
871        let found = collect(counted_exact_pass(&evaluations), 0.0, 8.0, 8.0, 1e-30)
872            .expect("well-formed arguments");
873        assert_eq!(found.len(), 1, "{found:?}");
874        assert!(
875            libm::fabs(found[0].tca - 3.0) <= 4.5e-16,
876            "{} s against the exact 3 s, further than one ulp",
877            found[0].tca
878        );
879        // 8 s halved down to ulp(3) is 54 steps; with the scan's two samples and the final state,
880        // 57. The bound is the assertion — an unbounded loop here would be 2 103.
881        assert!(
882            evaluations.get() < 64,
883            "{} evaluations to exhaust the bracket",
884            evaluations.get()
885        );
886    }
887
888    /// A sample landing exactly on the minimum is still a bracket. `Δr·Δv` is exactly zero there, so
889    /// the test that opens a bracket has to accept zero on the right — `previous < 0 && current >= 0`
890    /// and not `> 0`, which would step over its own answer.
891    #[test]
892    fn a_sample_exactly_at_the_minimum_still_opens_a_bracket() {
893        let (closest, speed, offset) = (1_500.0, 12_000.0, 600_000.0);
894        let exact = offset / speed;
895        // A step that lands on `exact` to the bit: it is a sample, not an interior point.
896        let found = collect(
897            rectilinear(closest, speed, offset),
898            0.0,
899            2.0 * exact,
900            exact,
901            1e-9,
902        )
903        .expect("well-formed arguments");
904        assert_eq!(found.len(), 1, "{found:?}");
905        assert!(libm::fabs(found[0].tca - exact) < 1e-9);
906    }
907
908    /// The radial filter discards only what it is entitled to, checked against the exact answer.
909    ///
910    /// For two concentric circular orbits the closest approach over *all* time is `|r₂ − r₁|`
911    /// exactly, reached whenever the two align. That closed form is the oracle here rather than a
912    /// scan, and deliberately: at a 1 km altitude difference the two beat against each other with a
913    /// period of 315 days, so a scan short enough to run would sample a fraction of one beat and
914    /// report whatever separation the pair happened to start at.
915    #[test]
916    fn the_radial_filter_never_drops_a_pair_that_could_conjunct() {
917        let threshold = 5_000.0;
918        let r1 = 7_000_000.0_f64;
919        for gap in [1.0_f64, 4_000.0, 4_999.0, 5_000.0, 5_001.0, 10_000.0, 5.0e5] {
920            let r2 = r1 + gap;
921            // Circular, so perigee and apogee are both the radius.
922            let separated = radially_separated(r1, r1, r2, r2, threshold);
923            assert_eq!(
924                separated,
925                gap > threshold,
926                "at a {gap} m gap the filter said {separated}, and the exact closest approach of \
927                 two concentric circles is the gap itself"
928            );
929        }
930
931        // And the closed form is the one the search agrees with, on the one pair whose beat period
932        // is short enough to scan: two alignments in the span, both at |r₂ − r₁|.
933        let r2 = r1 + 5.0e5;
934        let closest = collect(co_planar(r1, r2, 1.0), 0.0, 2.0 * beat(r1, r2), 30.0, 1e-6)
935            .expect("well-formed arguments")
936            .into_iter()
937            .map(|c| c.distance)
938            .fold(f64::INFINITY, f64::min);
939        assert!(
940            libm::fabs(closest - 5.0e5) < 1.0,
941            "the search's closest approach is {closest} m against the exact 500000 m"
942        );
943    }
944
945    /// The filter is symmetric in its two objects, needs *either* ordering to separate, and refuses
946    /// to act on a non-finite input.
947    #[test]
948    fn the_radial_filter_is_symmetric_and_refuses_non_finite_input() {
949        let (lo_p, lo_a, hi_p, hi_a) = (7.0e6, 7.1e6, 7.2e6, 7.3e6);
950        assert!(radially_separated(lo_p, lo_a, hi_p, hi_a, 50_000.0));
951        assert!(radially_separated(hi_p, hi_a, lo_p, lo_a, 50_000.0));
952        // Overlapping shells cannot be separated at any threshold.
953        assert!(!radially_separated(7.0e6, 7.3e6, 7.1e6, 7.2e6, 0.0));
954        // Exactly at the threshold is not past it: the comparison is strict.
955        assert!(!radially_separated(hi_p, hi_a, lo_p, lo_a, hi_p - lo_a));
956        assert!(radially_separated(
957            hi_p,
958            hi_a,
959            lo_p,
960            lo_a,
961            hi_p - lo_a - 1.0
962        ));
963        for bad in [f64::NAN, f64::INFINITY, f64::NEG_INFINITY] {
964            assert!(!radially_separated(bad, lo_a, hi_p, hi_a, 1.0));
965            assert!(!radially_separated(lo_p, bad, hi_p, hi_a, 1.0));
966            assert!(!radially_separated(lo_p, lo_a, bad, hi_a, 1.0));
967            assert!(!radially_separated(lo_p, lo_a, hi_p, bad, 1.0));
968            assert!(!radially_separated(lo_p, lo_a, hi_p, hi_a, bad));
969        }
970    }
971}