geop_core_math/disjoint_set/
mod.rs

1//! Accumulate candidate values found during a subdivision search into a
2//! minimal set of merged, mutually-disjoint solutions.
3//!
4//! A geometric subdivision search (curve/curve, curve/surface, or a plain
5//! point projection) converges on many small candidate values near each
6//! genuine solution, not just one — [`DisjointSet::insert`] folds each new
7//! candidate into whichever existing entries it `could_be_equal`,
8//! transitively (a candidate can bridge two previously-separate entries
9//! into one), so the result never contains two entries describing the same
10//! physical solution.
11
12use crate::{scalars::Scalar, vector::Vector};
13
14/// A value that can be tested for approximate equality against another of
15/// the same type and combined into the smallest value definitely
16/// containing both — the building block [`DisjointSet`] merges on.
17pub trait Mergeable: Copy {
18    fn could_be_equal(&self, other: &Self) -> bool;
19    fn union(&self, other: &Self) -> Self;
20}
21
22impl Mergeable for Scalar {
23    fn could_be_equal(&self, other: &Self) -> bool {
24        Scalar::could_be_equal(*self, *other)
25    }
26    fn union(&self, other: &Self) -> Self {
27        Scalar::union(*self, *other)
28    }
29}
30
31impl<const N: usize> Mergeable for Vector<N> {
32    fn could_be_equal(&self, other: &Self) -> bool {
33        Vector::could_be_equal(self, other)
34    }
35    fn union(&self, other: &Self) -> Self {
36        Vector::union(self, other)
37    }
38}
39
40impl<A: Mergeable, B: Mergeable> Mergeable for (A, B) {
41    fn could_be_equal(&self, other: &Self) -> bool {
42        self.0.could_be_equal(&other.0) && self.1.could_be_equal(&other.1)
43    }
44    fn union(&self, other: &Self) -> Self {
45        (self.0.union(&other.0), self.1.union(&other.1))
46    }
47}
48
49/// A set of mutually-disjoint (no two `could_be_equal`) merged values,
50/// built up one candidate at a time via [`DisjointSet::insert`].
51#[derive(Clone, Debug)]
52pub struct DisjointSet<T: Mergeable> {
53    items: Vec<T>,
54}
55
56impl<T: Mergeable> DisjointSet<T> {
57    pub fn new() -> Self {
58        Self { items: Vec::new() }
59    }
60
61    /// The current number of disjoint entries.
62    pub fn len(&self) -> usize {
63        self.items.len()
64    }
65
66    pub fn is_empty(&self) -> bool {
67        self.items.is_empty()
68    }
69
70    pub fn iter(&self) -> impl Iterator<Item = &T> {
71        self.items.iter()
72    }
73
74    /// Fold `candidate` into this set: absorb every existing entry it
75    /// `could_be_equal` (via `union`), repeating — not just once — since
76    /// absorbing one entry can widen the merged result enough to now also
77    /// `could_be_equal` a *different*, previously-distinct entry (e.g. a
78    /// third candidate bridging two already-found ones, which a
79    /// single non-repeating pass would leave as two separate entries
80    /// instead of joining them into one). The fully-merged result takes the
81    /// place of the earliest entry it absorbed (or is appended), so entries
82    /// keep the order in which they were first found.
83    pub fn insert(&mut self, mut candidate: T) {
84        let mut at: Option<usize> = None;
85        while let Some(i) = self
86            .items
87            .iter()
88            .position(|item| item.could_be_equal(&candidate))
89        {
90            candidate = candidate.union(&self.items.remove(i));
91            at = Some(at.map_or(i, |a| a.min(i)));
92        }
93        match at {
94            Some(i) => self.items.insert(i, candidate),
95            None => self.items.push(candidate),
96        }
97    }
98
99    pub fn into_vec(self) -> Vec<T> {
100        self.items
101    }
102}
103
104impl<T: Mergeable> Default for DisjointSet<T> {
105    fn default() -> Self {
106        Self::new()
107    }
108}
109
110#[cfg(test)]
111mod tests {
112    use super::DisjointSet;
113    use crate::scalars::Scalar;
114
115    #[test]
116    fn disjoint_scalars_stay_separate() {
117        let mut set = DisjointSet::new();
118        set.insert(Scalar::from_f64(0.1));
119        set.insert(Scalar::from_f64(0.9));
120        assert_eq!(set.len(), 2);
121    }
122
123    #[test]
124    fn overlapping_scalars_merge() {
125        let mut set = DisjointSet::new();
126        set.insert(Scalar::from_f64(0.5));
127        set.insert(Scalar::from_f64(0.5));
128        assert_eq!(set.len(), 1);
129    }
130
131    /// A third candidate bridging two previously-separate entries must
132    /// merge all three into one, not just absorb into whichever entry it
133    /// happened to match first.
134    #[test]
135    fn bridging_candidate_joins_two_solutions() {
136        let mut set = DisjointSet::new();
137        set.insert(Scalar::from_f64(0.0));
138        set.insert(Scalar::from_f64(1.0));
139        assert_eq!(set.len(), 2);
140
141        // A very wide candidate spanning both — built as the union of two
142        // points straddling each existing entry — should absorb both.
143        let bridge = Scalar::from_f64(-0.5).union(Scalar::from_f64(1.5));
144        set.insert(bridge);
145        assert_eq!(
146            set.len(),
147            1,
148            "a candidate overlapping both existing entries should merge them into one"
149        );
150    }
151}
geop_core_math/disjoint_set/mod.rs

geop_core_math/disjoint_set/
mod.rs
