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}