Skip to main content

ternary_contours/contour/
paths.rs

1use crate::TernaryCoordinate;
2
3use super::ContourError;
4
5#[derive(Clone, Copy, Debug, PartialEq)]
6pub(crate) struct ContourSegment {
7    pub start: TernaryCoordinate,
8    pub end: TernaryCoordinate,
9}
10
11#[derive(Clone, Debug, PartialEq)]
12pub struct ContourPath {
13    /// Ordered semantic A/B/C coordinates with no duplicate closing endpoint.
14    pub points: Vec<TernaryCoordinate>,
15    /// Whether the final point connects periodically back to the first.
16    pub closed: bool,
17}
18
19pub(crate) fn join_segments(
20    segments: Vec<ContourSegment>,
21    tolerance: f64,
22) -> Result<Vec<ContourPath>, ContourError> {
23    let mut nodes: Vec<TernaryCoordinate> = Vec::new();
24    let mut edges: Vec<(usize, usize)> = Vec::new();
25    for segment in segments {
26        if close(segment.start, segment.end, tolerance) {
27            continue;
28        }
29        let start = node_for(&mut nodes, segment.start, tolerance);
30        let end = node_for(&mut nodes, segment.end, tolerance);
31        if start != end
32            && !edges
33                .iter()
34                .any(|&(a, b)| (a == start && b == end) || (a == end && b == start))
35        {
36            edges.push((start, end));
37        }
38    }
39    let mut adjacency = vec![Vec::<(usize, usize)>::new(); nodes.len()];
40    for (edge_index, &(left, right)) in edges.iter().enumerate() {
41        adjacency[left].push((right, edge_index));
42        adjacency[right].push((left, edge_index));
43    }
44    if let Some(degree) = adjacency.iter().map(Vec::len).find(|degree| *degree > 2) {
45        return Err(ContourError::BranchingTopology { degree });
46    }
47    let mut used = vec![false; edges.len()];
48    let mut paths = Vec::new();
49    let mut starts: Vec<_> = adjacency
50        .iter()
51        .enumerate()
52        .filter(|(_, edges)| edges.len() == 1)
53        .map(|(index, _)| index)
54        .collect();
55    starts.sort_by(|&a, &b| lex_cmp(nodes[a], nodes[b]));
56    for start in starts {
57        if adjacency[start].iter().all(|(_, edge)| used[*edge]) {
58            continue;
59        }
60        paths.push(walk(start, &nodes, &adjacency, &mut used, false)?);
61    }
62    while let Some(edge_index) = used.iter().position(|used| !*used) {
63        let (a, b) = edges[edge_index];
64        let start = if lex_cmp(nodes[a], nodes[b]).is_le() {
65            a
66        } else {
67            b
68        };
69        paths.push(walk(start, &nodes, &adjacency, &mut used, true)?);
70    }
71    paths.sort_by(|left, right| {
72        lex_cmp(left.points[0], right.points[0])
73            .then_with(|| left.points.len().cmp(&right.points.len()))
74    });
75    Ok(paths)
76}
77
78fn walk(
79    start: usize,
80    nodes: &[TernaryCoordinate],
81    adjacency: &[Vec<(usize, usize)>],
82    used: &mut [bool],
83    expect_closed: bool,
84) -> Result<ContourPath, ContourError> {
85    let mut points = vec![nodes[start]];
86    let mut current = start;
87    let mut previous = None;
88    loop {
89        let next = adjacency[current]
90            .iter()
91            .filter(|(_, edge)| !used[*edge])
92            .min_by(|(a, _), (b, _)| lex_cmp(nodes[*a], nodes[*b]))
93            .copied();
94        let Some((node, edge)) = next else { break };
95        used[edge] = true;
96        previous = Some(current);
97        current = node;
98        if current == start {
99            break;
100        }
101        points.push(nodes[current]);
102        if points.len() > used.len() + 1 {
103            return Err(ContourError::BranchingTopology {
104                degree: adjacency[current].len(),
105            });
106        }
107    }
108    let closed = current == start;
109    if expect_closed && !closed {
110        return Err(ContourError::InvalidClosedLoop);
111    }
112    if closed && points.len() < 3 {
113        return Err(ContourError::InvalidClosedLoop);
114    }
115    if points.len() < 2 {
116        return Err(ContourError::ZeroLengthPath);
117    }
118    let _ = previous;
119    if !closed && lex_cmp(*points.last().unwrap(), points[0]).is_lt() {
120        points.reverse();
121    }
122    if closed {
123        let minimum = (0..points.len())
124            .min_by(|&a, &b| lex_cmp(points[a], points[b]))
125            .unwrap();
126        points.rotate_left(minimum);
127        if points.len() > 2 && lex_cmp(points[points.len() - 1], points[1]).is_lt() {
128            points[1..].reverse();
129        }
130    }
131    Ok(ContourPath { points, closed })
132}
133fn node_for(nodes: &mut Vec<TernaryCoordinate>, point: TernaryCoordinate, tolerance: f64) -> usize {
134    if let Some(index) = nodes
135        .iter()
136        .position(|candidate| close(*candidate, point, tolerance))
137    {
138        index
139    } else {
140        nodes.push(point);
141        nodes.len() - 1
142    }
143}
144fn close(left: TernaryCoordinate, right: TernaryCoordinate, tolerance: f64) -> bool {
145    left.as_array()
146        .into_iter()
147        .zip(right.as_array())
148        .all(|(a, b)| (a - b).abs() <= tolerance)
149}
150fn lex_cmp(left: TernaryCoordinate, right: TernaryCoordinate) -> std::cmp::Ordering {
151    for (a, b) in left.as_array().into_iter().zip(right.as_array()) {
152        let order = a.total_cmp(&b);
153        if !order.is_eq() {
154            return order;
155        }
156    }
157    std::cmp::Ordering::Equal
158}
159
160#[cfg(test)]
161mod tests {
162    use super::*;
163    fn p(a: f64, b: f64) -> TernaryCoordinate {
164        TernaryCoordinate::new(a, b, 1.0 - a - b)
165    }
166    #[test]
167    fn open_and_closed_paths_join_deterministically() {
168        let open = join_segments(
169            vec![
170                ContourSegment {
171                    start: p(0.5, 0.4),
172                    end: p(0.3, 0.4),
173                },
174                ContourSegment {
175                    start: p(0.3, 0.4),
176                    end: p(0.1, 0.4),
177                },
178            ],
179            1e-9,
180        )
181        .unwrap();
182        assert_eq!(open.len(), 1);
183        assert!(!open[0].closed);
184        assert_eq!(open[0].points[0], p(0.1, 0.4));
185        let closed = join_segments(
186            vec![
187                ContourSegment {
188                    start: p(0.2, 0.2),
189                    end: p(0.5, 0.2),
190                },
191                ContourSegment {
192                    start: p(0.5, 0.2),
193                    end: p(0.3, 0.5),
194                },
195                ContourSegment {
196                    start: p(0.3, 0.5),
197                    end: p(0.2, 0.2),
198                },
199            ],
200            1e-9,
201        )
202        .unwrap();
203        assert_eq!(closed.len(), 1);
204        assert!(closed[0].closed);
205        assert_eq!(closed[0].points.len(), 3);
206    }
207    #[test]
208    fn branching_is_reported() {
209        let centre = p(0.3, 0.3);
210        let segments = [p(0.1, 0.3), p(0.5, 0.3), p(0.3, 0.5)]
211            .map(|end| ContourSegment { start: centre, end });
212        assert!(matches!(
213            join_segments(segments.to_vec(), 1e-9),
214            Err(ContourError::BranchingTopology { degree: 3 })
215        ));
216    }
217}