Another project
1use serde::Serialize;
2
3use crate::layout::{LayoutPos, LayoutPx, LayoutRect, LayoutSize};
4
5pub const MAX_CONVEX_VERTS: usize = 8;
6
7pub const MAX_PATH_POINTS: usize = 8;
8
9const GEOMETRY_EPSILON: f32 = 1.0e-4;
10
11#[derive(Clone, Debug, PartialEq, Serialize)]
12pub struct ConvexPoly {
13 verts: Vec<LayoutPos>,
14}
15
16impl ConvexPoly {
17 #[must_use]
18 pub fn new(verts: Vec<LayoutPos>) -> Option<Self> {
19 if !(3..=MAX_CONVEX_VERTS).contains(&verts.len()) {
20 return None;
21 }
22 let n = verts.len();
23 let edges_nondegenerate =
24 (0..n).all(|i| edge_length(verts[i], verts[(i + 1) % n]) > GEOMETRY_EPSILON);
25 if !edges_nondegenerate {
26 return None;
27 }
28 is_convex(&verts).then_some(Self { verts })
29 }
30
31 #[must_use]
32 pub fn verts(&self) -> &[LayoutPos] {
33 &self.verts
34 }
35
36 #[must_use]
37 pub fn bounds(&self) -> LayoutRect {
38 bounds_of(&self.verts)
39 }
40
41 #[must_use]
42 pub fn edge_planes(&self) -> Vec<[f32; 3]> {
43 let center = centroid(&self.verts);
44 let n = self.verts.len();
45 (0..n)
46 .map(|i| outward_plane(self.verts[i], self.verts[(i + 1) % n], center))
47 .collect()
48 }
49}
50
51#[derive(Clone, Debug, PartialEq, Serialize)]
52pub struct PolyPath {
53 points: Vec<LayoutPos>,
54 closed: bool,
55}
56
57impl PolyPath {
58 #[must_use]
59 pub fn new(points: Vec<LayoutPos>, closed: bool) -> Option<Self> {
60 (2..=MAX_PATH_POINTS)
61 .contains(&points.len())
62 .then_some(Self { points, closed })
63 }
64
65 #[must_use]
66 pub fn open(points: Vec<LayoutPos>) -> Option<Self> {
67 Self::new(points, false)
68 }
69
70 #[must_use]
71 pub fn closed_loop(points: Vec<LayoutPos>) -> Option<Self> {
72 Self::new(points, true)
73 }
74
75 #[must_use]
76 pub fn points(&self) -> &[LayoutPos] {
77 &self.points
78 }
79
80 #[must_use]
81 pub fn is_closed(&self) -> bool {
82 self.closed
83 }
84
85 pub fn segments(&self) -> impl Iterator<Item = (LayoutPos, LayoutPos)> + '_ {
86 let n = self.points.len();
87 let count = if self.closed { n } else { n - 1 };
88 (0..count).map(move |i| (self.points[i], self.points[(i + 1) % n]))
89 }
90
91 #[must_use]
92 pub fn bounds(&self) -> LayoutRect {
93 bounds_of(&self.points)
94 }
95}
96
97fn edge_length(a: LayoutPos, b: LayoutPos) -> f32 {
98 (b.x.value() - a.x.value()).hypot(b.y.value() - a.y.value())
99}
100
101fn is_convex(verts: &[LayoutPos]) -> bool {
102 let n = verts.len();
103 let crosses = (0..n).map(|i| turn_cross(verts[i], verts[(i + 1) % n], verts[(i + 2) % n]));
104 let signs = crosses.fold((false, false, false), |(pos, neg, any), c| {
105 (
106 pos || c > GEOMETRY_EPSILON,
107 neg || c < -GEOMETRY_EPSILON,
108 any || c.abs() > GEOMETRY_EPSILON,
109 )
110 });
111 let (positive, negative, any_nonzero) = signs;
112 any_nonzero && !(positive && negative)
113}
114
115fn turn_cross(a: LayoutPos, b: LayoutPos, c: LayoutPos) -> f32 {
116 let (abx, aby) = (b.x.value() - a.x.value(), b.y.value() - a.y.value());
117 let (bcx, bcy) = (c.x.value() - b.x.value(), c.y.value() - b.y.value());
118 abx * bcy - aby * bcx
119}
120
121fn centroid(verts: &[LayoutPos]) -> (f32, f32) {
122 let sum = verts.iter().fold((0.0, 0.0), |(sx, sy), p| {
123 (sx + p.x.value(), sy + p.y.value())
124 });
125 let count = lossless_count(verts.len());
126 (sum.0 / count, sum.1 / count)
127}
128
129fn outward_plane(a: LayoutPos, b: LayoutPos, center: (f32, f32)) -> [f32; 3] {
130 let (dx, dy) = (b.x.value() - a.x.value(), b.y.value() - a.y.value());
131 let len = dx.hypot(dy).max(GEOMETRY_EPSILON);
132 let (mut nx, mut ny) = (dy / len, -dx / len);
133 let d = nx * a.x.value() + ny * a.y.value();
134 if nx * center.0 + ny * center.1 - d > 0.0 {
135 nx = -nx;
136 ny = -ny;
137 }
138 [nx, ny, nx * a.x.value() + ny * a.y.value()]
139}
140
141fn bounds_of(points: &[LayoutPos]) -> LayoutRect {
142 let fold_minmax = |pick: fn(LayoutPos) -> f32| {
143 points
144 .iter()
145 .fold((f32::INFINITY, f32::NEG_INFINITY), |(lo, hi), p| {
146 (lo.min(pick(*p)), hi.max(pick(*p)))
147 })
148 };
149 let (min_x, max_x) = fold_minmax(|p| p.x.value());
150 let (min_y, max_y) = fold_minmax(|p| p.y.value());
151 LayoutRect::new(
152 LayoutPos::new(LayoutPx::saturating(min_x), LayoutPx::saturating(min_y)),
153 LayoutSize::new(
154 LayoutPx::saturating_nonneg(max_x - min_x),
155 LayoutPx::saturating_nonneg(max_y - min_y),
156 ),
157 )
158}
159
160#[allow(
161 clippy::cast_precision_loss,
162 reason = "vertex counts stay far below the f32 mantissa limit"
163)]
164fn lossless_count(len: usize) -> f32 {
165 len as f32
166}
167
168#[cfg(test)]
169mod tests {
170 use super::*;
171
172 fn pos(x: f32, y: f32) -> LayoutPos {
173 LayoutPos::new(LayoutPx::new(x), LayoutPx::new(y))
174 }
175
176 #[test]
177 fn a_square_is_convex() {
178 assert!(
179 ConvexPoly::new(vec![
180 pos(0.0, 0.0),
181 pos(4.0, 0.0),
182 pos(4.0, 4.0),
183 pos(0.0, 4.0)
184 ])
185 .is_some()
186 );
187 }
188
189 #[test]
190 fn a_dart_is_rejected_as_concave() {
191 let dart = vec![pos(0.0, 0.0), pos(4.0, 2.0), pos(0.0, 4.0), pos(1.0, 2.0)];
192 assert!(ConvexPoly::new(dart).is_none());
193 }
194
195 #[test]
196 fn fewer_than_three_vertices_is_rejected() {
197 assert!(ConvexPoly::new(vec![pos(0.0, 0.0), pos(1.0, 1.0)]).is_none());
198 }
199
200 #[test]
201 fn more_than_the_cap_is_rejected() {
202 let many = (0..=MAX_CONVEX_VERTS)
203 .map(|i| pos(lossless_count(i), 0.0))
204 .collect();
205 assert!(ConvexPoly::new(many).is_none());
206 }
207
208 #[test]
209 fn collinear_points_are_rejected() {
210 assert!(ConvexPoly::new(vec![pos(0.0, 0.0), pos(1.0, 0.0), pos(2.0, 0.0)]).is_none());
211 }
212
213 #[test]
214 fn coincident_vertices_are_rejected() {
215 assert!(ConvexPoly::new(vec![pos(0.0, 0.0), pos(0.0, 0.0), pos(4.0, 4.0)]).is_none());
216 }
217
218 #[test]
219 fn edge_planes_face_outward_from_every_edge() {
220 let Some(poly) = ConvexPoly::new(vec![
221 pos(0.0, 0.0),
222 pos(4.0, 0.0),
223 pos(4.0, 4.0),
224 pos(0.0, 4.0),
225 ]) else {
226 panic!("the unit square is convex");
227 };
228 let center = (2.0, 2.0);
229 poly.edge_planes().into_iter().for_each(|[nx, ny, d]| {
230 assert!(
231 nx * center.0 + ny * center.1 - d < 0.0,
232 "the centroid sits inside every edge half-plane",
233 );
234 assert!(
235 (nx.hypot(ny) - 1.0).abs() < 1.0e-5,
236 "edge normals are unit length"
237 );
238 });
239 }
240
241 #[test]
242 fn an_open_path_has_one_fewer_segment_than_a_closed_loop() {
243 let pts = vec![pos(0.0, 0.0), pos(1.0, 0.0), pos(1.0, 1.0)];
244 let Some(open) = PolyPath::open(pts.clone()) else {
245 panic!("three points form a path");
246 };
247 let Some(closed) = PolyPath::closed_loop(pts) else {
248 panic!("three points form a loop");
249 };
250 assert_eq!(open.segments().count(), 2);
251 assert_eq!(closed.segments().count(), 3);
252 }
253
254 #[test]
255 fn a_single_point_is_not_a_path() {
256 assert!(PolyPath::new(vec![pos(0.0, 0.0)], false).is_none());
257 }
258
259 #[test]
260 fn more_points_than_the_cap_is_not_a_path() {
261 let many = (0..=MAX_PATH_POINTS)
262 .map(|i| pos(lossless_count(i), 0.0))
263 .collect();
264 assert!(PolyPath::new(many, false).is_none());
265 }
266}