1use super::math::solve_cubic;
2use cgmath::prelude::*;
3use cgmath::{dot, Point2, Vector2};
4use std::f32::MAX;
5use std::ops::Sub;
6
7#[derive(Debug, Clone, Copy)]
8pub struct SignedDistance {
9 pub real_dist: f32,
10 pub real_pos: f32,
11 pub extended_dist: f32,
12 pub extended_pos: f32,
13 pub orthogonality: f32,
14 pub sign: f32,
15}
16
17#[derive(Debug, Clone, Copy)]
18pub struct Rect<T> {
19 pub min: Point2<T>,
20 pub max: Point2<T>,
21}
22
23impl<T: Sub<Output = T> + Copy> Rect<T> {
24 pub fn new(min_x: T, min_y: T, max_x: T, max_y: T) -> Self {
25 Rect {
26 min: Point2::new(min_x, min_y),
27 max: Point2::new(max_x, max_y),
28 }
29 }
30
31 pub fn width(&self) -> T {
32 self.max.x - self.min.x
33 }
34
35 pub fn height(&self) -> T {
36 self.max.y - self.min.y
37 }
38}
39
40#[derive(Debug, Clone, Copy)]
41pub struct Line {
42 pub p0: Point2<f32>,
43 pub p1: Point2<f32>,
44}
45
46impl Line {
47 pub fn new(p0: Point2<f32>, p1: Point2<f32>) -> Self {
48 Line { p0, p1 }
49 }
50
51 pub fn bounding_box(&self) -> Rect<f32> {
52 let (a, b) = (self.p0, self.p1);
53 let (min_x, max_x) = if a.x < b.x { (a.x, b.x) } else { (b.x, a.x) };
54 let (min_y, max_y) = if a.y < b.y { (a.y, b.y) } else { (b.y, a.y) };
55 Rect {
56 min: Point2 { x: min_x, y: min_y },
57 max: Point2 { x: max_x, y: max_y },
58 }
59 }
60
61 pub fn point(&self, t: f32) -> Point2<f32> {
62 return Point2::from_vec((1.0 - t) * self.p0.to_vec() + t * self.p1.to_vec());
63 }
64
65 pub fn area(&self) -> f32 {
66 (self.p0.x * self.p1.y - self.p1.x * self.p0.y) / 2.0
67 }
68
69 pub fn signed_distance(&self, p: Point2<f32>) -> SignedDistance {
70 let p1_p0 = self.p1 - self.p0;
71 let p_p0 = p - self.p0;
72
73 let extended_pos = dot(p_p0, p1_p0) / dot(p1_p0, p1_p0);
74 let real_pos = extended_pos.max(0.0).min(1.0);
75
76 let extended_dist = (extended_pos * p1_p0 - p_p0).magnitude();
77 let real_dist = (real_pos * p1_p0 - p_p0).magnitude();
78
79 let pt = self.p0 + real_pos * p1_p0;
80 let p_pt = p - pt;
81
82 let orthogonality = if p_pt.x == 0.0 && p_pt.y == 0.0 {
83 0.0
84 } else {
85 p1_p0.normalize().perp_dot(p_pt.normalize())
86 };
87
88 let sign = orthogonality.signum();
89 let orthogonality = orthogonality.abs();
90
91 SignedDistance {
92 real_dist,
93 real_pos,
94 extended_dist,
95 extended_pos,
96 orthogonality,
97 sign,
98 }
99 }
100}
101
102#[derive(Debug, Clone, Copy)]
103pub struct Curve {
104 pub p0: Point2<f32>,
105 pub p1: Point2<f32>,
106 pub p2: Point2<f32>,
107}
108
109impl Curve {
110 pub fn new(p0: Point2<f32>, p1: Point2<f32>, p2: Point2<f32>) -> Self {
111 Curve { p0, p1, p2 }
112 }
113
114 pub fn bounding_box(&self) -> Rect<f32> {
115 let p0 = self.p0;
116 let p1 = self.p1;
117 let p2 = self.p2;
118
119 let (min_x, max_x) = if p0.x <= p1.x && p1.x <= p2.x {
120 (p0.x, p2.x)
121 } else if p0.x >= p1.x && p1.x >= p2.x {
122 (p2.x, p0.x)
123 } else {
124 let t = (p0.x - p1.x) / (p0.x - 2.0 * p1.x + p2.x);
125 let _1mt = 1.0 - t;
126 let inflection = _1mt * _1mt * p0.x + 2.0 * _1mt * t * p1.x + t * t * p2.x;
127 if p1.x < p0.x {
128 (inflection, p0.x.max(p2.x))
129 } else {
130 (p0.x.min(p2.x), inflection)
131 }
132 };
133
134 let (min_y, max_y) = if p0.y <= p1.y && p1.y <= p2.y {
135 (p0.y, p2.y)
136 } else if p0.y >= p1.y && p1.y >= p2.y {
137 (p2.y, p0.y)
138 } else {
139 let t = (p0.y - p1.y) / (p0.y - 2.0 * p1.y + p2.y);
140 let _1mt = 1.0 - t;
141 let inflection = _1mt * _1mt * p0.y + 2.0 * _1mt * t * p1.y + t * t * p2.y;
142 if p1.y < p0.y {
143 (inflection, p0.y.max(p2.y))
144 } else {
145 (p0.y.min(p2.y), inflection)
146 }
147 };
148
149 Rect {
150 min: Point2 { x: min_x, y: min_y },
151 max: Point2 { x: max_x, y: max_y },
152 }
153 }
154
155 pub fn point(&self, t: f32) -> Point2<f32> {
156 let nt = 1.0 - t;
157 return Point2::from_vec(
158 (nt * nt) * self.p0.to_vec()
159 + (2.0 * t * nt) * self.p1.to_vec()
160 + (t * t) * self.p2.to_vec(),
161 );
162 }
163
164 pub fn area(&self) -> f32 {
165 (self.p2.x * (-self.p0.y - 2.0 * self.p1.y)
166 + 2.0 * self.p1.x * (self.p2.y - self.p0.y)
167 + self.p0.x * (2.0 * self.p1.y + self.p2.y))
168 / 6.0
169 }
170
171 #[allow(clippy::many_single_char_names)]
172 pub fn signed_distance(&self, p: Point2<f32>) -> SignedDistance {
173 let p = p.to_vec();
174 let p0 = self.p0.to_vec();
175 let p1 = self.p1.to_vec();
176 let p2 = self.p2.to_vec();
177
178 let v = p - p0;
179 let v1 = p1 - p0;
180 let v2 = p2 - 2.0 * p1 + p0;
181
182 let a = v2.dot(v2);
183 let b = 3.0 * v1.dot(v2);
184 let c = 2.0 * v1.dot(v1) - v2.dot(v);
185 let d = -v1.dot(v);
186
187 let (t1, t2, t3) = solve_cubic(a, b, c, d);
188
189 struct DistResult {
190 dist2: f32,
191 t: f32,
192 pt: Vector2<f32>,
193 };
194
195 let mut dist_result = DistResult {
196 dist2: MAX,
197 pt: Vector2::new(0.0, 0.0),
198 t: 0.0,
199 };
200
201 {
202 let mut update_closest_t = |root: Option<f32>| {
203 if let Some(t) = root {
204 let ct = t.max(0.0).min(1.0);
205 let pt = ct * ct * v2 + 2.0 * ct * v1 + p0;
206 let dist2 = (p - pt).magnitude2();
207 if dist2 < dist_result.dist2 {
208 dist_result = DistResult { dist2, pt, t }
209 }
210 }
211 };
212
213 update_closest_t(t1);
214 update_closest_t(t2);
215 update_closest_t(t3);
216 }
217
218 let extended_pos = dist_result.t;
219 let real_pos = extended_pos.max(0.0).min(1.0);
220
221 let dir = 2.0 * real_pos * v2 + 2.0 * v1;
222 let p_pt = p - dist_result.pt;
223 let orthogonality = if p_pt.is_zero() || dir.is_zero() {
224 0.0
225 } else {
226 dir.normalize().perp_dot(p_pt.normalize())
227 };
228
229 let sign = orthogonality.signum();
230 let orthogonality = orthogonality.abs();
231
232 let real_dist = dist_result.dist2.sqrt();
233 let extended_dist =
234 (extended_pos * extended_pos * v2 + 2.0 * extended_pos * v1 - v).magnitude();
235
236 SignedDistance {
237 real_dist,
238 real_pos,
239 extended_dist,
240 extended_pos,
241 orthogonality,
242 sign,
243 }
244 }
245}