ternary_contours/contour/
paths.rs1use 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 pub points: Vec<TernaryCoordinate>,
15 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}