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

geop_core_math/disjoint_set/
mod.rs
