ifc_lite_geometry/
union_find.rs

1// This Source Code Form is subject to the terms of the Mozilla Public
2// License, v. 2.0. If a copy of the MPL was not distributed with this
3// file, You can obtain one at https://mozilla.org/MPL/2.0/.
4
5//! Minimal union-find with path halving, shared by mesh cavity removal and
6//! scan plane merging (`ifc_lite_processing::scan_segmentation`).
7//!
8//! `union(a, b)` always re-parents `b`'s root under `a`'s root, so the root of
9//! a set depends only on the sequence of unions, never on hashing or memory
10//! layout: callers that union in a deterministic order get deterministic roots.
11
12/// Disjoint sets over `0..n`.
13pub struct UnionFind {
14    parent: Vec<u32>,
15}
16
17impl UnionFind {
18    /// `n` singleton sets.
19    pub fn new(n: usize) -> Self {
20        Self {
21            parent: (0..n as u32).collect(),
22        }
23    }
24
25    /// Representative of `x`'s set (halves the path as it walks; the walk is
26    /// iterative and bounded by the set size).
27    pub fn find(&mut self, mut x: u32) -> u32 {
28        while self.parent[x as usize] != x {
29            let grand = self.parent[self.parent[x as usize] as usize];
30            self.parent[x as usize] = grand;
31            x = grand;
32        }
33        x
34    }
35
36    /// Merge the sets of `a` and `b`; `b`'s root is re-parented under `a`'s.
37    /// Returns whether two distinct sets were joined.
38    pub fn union(&mut self, a: u32, b: u32) -> bool {
39        let (ra, rb) = (self.find(a), self.find(b));
40        if ra != rb {
41            self.parent[rb as usize] = ra;
42        }
43        ra != rb
44    }
45}
ifc_lite_geometry/union_find.rs

ifc_lite_geometry/
union_find.rs
