1use super::{Error, TernaryCartesian, TernaryViewport, Tolerance};
2
3#[derive(Clone, Copy, Debug, PartialEq)]
8pub struct CartesianSegment {
9 pub start: TernaryCartesian,
10 pub end: TernaryCartesian,
11}
12
13impl CartesianSegment {
14 pub const fn new(start: TernaryCartesian, end: TernaryCartesian) -> Self {
15 Self { start, end }
16 }
17
18 pub fn point_at(self, parameter: f64) -> TernaryCartesian {
20 TernaryCartesian::new(
21 self.start.x + (self.end.x - self.start.x) * parameter,
22 self.start.y + (self.end.y - self.start.y) * parameter,
23 )
24 }
25}
26
27#[derive(Clone, Copy, Debug, PartialEq)]
29pub struct ClippedSegment {
30 pub segment: CartesianSegment,
31 pub parameter_start: f64,
32 pub parameter_end: f64,
33}
34
35pub fn clip_segment(
41 segment: CartesianSegment,
42 viewport: TernaryViewport,
43 tolerance: Tolerance,
44) -> Result<Option<CartesianSegment>, Error> {
45 Ok(clip_segment_with_parameters(segment, viewport, tolerance)?.map(|clipped| clipped.segment))
46}
47
48pub fn clip_segment_with_parameters(
50 segment: CartesianSegment,
51 viewport: TernaryViewport,
52 tolerance: Tolerance,
53) -> Result<Option<ClippedSegment>, Error> {
54 tolerance.validate()?;
55 validate_segment(segment)?;
56
57 let start_visible = viewport.contains(segment.start, tolerance)?;
58 let end_visible = viewport.contains(segment.end, tolerance)?;
59 if start_visible && end_visible {
60 return Ok(Some(ClippedSegment {
61 segment,
62 parameter_start: 0.0,
63 parameter_end: 1.0,
64 }));
65 }
66
67 if segment.start == segment.end {
68 return Ok(None);
69 }
70
71 let delta_x = segment.end.x - segment.start.x;
72 let delta_y = segment.end.y - segment.start.y;
73 let constraints = [
74 (-delta_x, segment.start.x - viewport.x_min()),
75 (delta_x, viewport.x_max() - segment.start.x),
76 (-delta_y, segment.start.y - viewport.y_min()),
77 (delta_y, viewport.y_max() - segment.start.y),
78 ];
79
80 let mut parameter_start: f64 = 0.0;
81 let mut parameter_end: f64 = 1.0;
82 for (direction, distance) in constraints {
83 if direction == 0.0 {
84 if distance < 0.0 && !tolerance.is_close(distance, 0.0) {
85 return Ok(None);
86 }
87 continue;
88 }
89
90 let parameter = distance / direction;
91 if direction < 0.0 {
92 parameter_start = parameter_start.max(parameter);
93 } else {
94 parameter_end = parameter_end.min(parameter);
95 }
96
97 if parameter_start > parameter_end {
98 if tolerance.is_close(parameter_start, parameter_end) {
99 let tangent = (parameter_start + parameter_end) / 2.0;
100 parameter_start = tangent;
101 parameter_end = tangent;
102 } else {
103 return Ok(None);
104 }
105 }
106 }
107
108 parameter_start = parameter_start.clamp(0.0, 1.0);
109 parameter_end = parameter_end.clamp(0.0, 1.0);
110 Ok(Some(ClippedSegment {
111 segment: CartesianSegment::new(
112 segment.point_at(parameter_start),
113 segment.point_at(parameter_end),
114 ),
115 parameter_start,
116 parameter_end,
117 }))
118}
119
120fn validate_segment(segment: CartesianSegment) -> Result<(), Error> {
121 if !segment.start.x.is_finite()
122 || !segment.start.y.is_finite()
123 || !segment.end.x.is_finite()
124 || !segment.end.y.is_finite()
125 {
126 return Err(Error::NonFiniteSegment {
127 start_x: segment.start.x,
128 start_y: segment.start.y,
129 end_x: segment.end.x,
130 end_y: segment.end.y,
131 });
132 }
133 Ok(())
134}
135
136#[cfg(test)]
137mod tests {
138 use super::*;
139 use proptest::prelude::*;
140
141 const TOLERANCE: Tolerance = Tolerance {
142 absolute: 1.0e-9,
143 relative: 1.0e-9,
144 };
145 const EPSILON: f64 = 1.0e-9;
146
147 fn viewport() -> TernaryViewport {
148 TernaryViewport::new(0.0, 1.0, 0.0, 1.0).unwrap()
149 }
150
151 fn point(x: f64, y: f64) -> TernaryCartesian {
152 TernaryCartesian::new(x, y)
153 }
154
155 fn segment(start: (f64, f64), end: (f64, f64)) -> CartesianSegment {
156 CartesianSegment::new(point(start.0, start.1), point(end.0, end.1))
157 }
158
159 fn assert_segment_close(actual: CartesianSegment, expected: CartesianSegment) {
160 for (actual, expected) in [
161 (actual.start.x, expected.start.x),
162 (actual.start.y, expected.start.y),
163 (actual.end.x, expected.end.x),
164 (actual.end.y, expected.end.y),
165 ] {
166 assert!(
167 (actual - expected).abs() < EPSILON,
168 "{actual} != {expected}"
169 );
170 }
171 }
172
173 #[test]
174 fn fully_inside_and_outside_segments_are_distinguished() {
175 let inside = segment((0.2, 0.3), (0.8, 0.7));
176 assert_eq!(
177 clip_segment(inside, viewport(), TOLERANCE).unwrap(),
178 Some(inside)
179 );
180
181 for outside in [
182 segment((-2.0, 0.2), (-1.0, 0.8)),
183 segment((2.0, 0.2), (3.0, 0.8)),
184 segment((0.2, 2.0), (0.8, 3.0)),
185 segment((0.2, -2.0), (0.8, -1.0)),
186 segment((-2.0, 2.0), (-1.0, 3.0)),
187 ] {
188 assert_eq!(clip_segment(outside, viewport(), TOLERANCE).unwrap(), None);
189 }
190 }
191
192 #[test]
193 fn crossings_cover_every_side_opposites_adjacent_and_both_endpoints_outside() {
194 let cases = [
195 (
196 segment((-1.0, 0.5), (0.5, 0.5)),
197 segment((0.0, 0.5), (0.5, 0.5)),
198 ),
199 (
200 segment((0.5, 0.5), (2.0, 0.5)),
201 segment((0.5, 0.5), (1.0, 0.5)),
202 ),
203 (
204 segment((0.5, -1.0), (0.5, 0.5)),
205 segment((0.5, 0.0), (0.5, 0.5)),
206 ),
207 (
208 segment((0.5, 0.5), (0.5, 2.0)),
209 segment((0.5, 0.5), (0.5, 1.0)),
210 ),
211 (
212 segment((-1.0, 0.5), (2.0, 0.5)),
213 segment((0.0, 0.5), (1.0, 0.5)),
214 ),
215 (
216 segment((0.5, -1.0), (0.5, 2.0)),
217 segment((0.5, 0.0), (0.5, 1.0)),
218 ),
219 (
220 segment((-1.0, 0.2), (0.8, 1.2)),
221 segment((0.0, 0.755_555_555_555_555_5), (0.44, 1.0)),
222 ),
223 (
224 segment((-1.0, -1.0), (2.0, 2.0)),
225 segment((0.0, 0.0), (1.0, 1.0)),
226 ),
227 ];
228 for (source, expected) in cases {
229 assert_segment_close(
230 clip_segment(source, viewport(), TOLERANCE)
231 .unwrap()
232 .unwrap(),
233 expected,
234 );
235 }
236 }
237
238 #[test]
239 fn reversed_direction_horizontal_vertical_and_diagonal_are_preserved() {
240 for source in [
241 segment((-1.0, 0.5), (2.0, 0.5)),
242 segment((0.5, -1.0), (0.5, 2.0)),
243 segment((-1.0, -1.0), (2.0, 2.0)),
244 ] {
245 let forward = clip_segment(source, viewport(), TOLERANCE)
246 .unwrap()
247 .unwrap();
248 let reversed_source = CartesianSegment::new(source.end, source.start);
249 let reversed = clip_segment(reversed_source, viewport(), TOLERANCE)
250 .unwrap()
251 .unwrap();
252 assert_segment_close(reversed, CartesianSegment::new(forward.end, forward.start));
253 }
254 }
255
256 #[test]
257 fn degenerate_boundary_coincident_and_corner_tangent_segments_are_explicit() {
258 let zero_inside = segment((0.5, 0.5), (0.5, 0.5));
259 assert_eq!(
260 clip_segment(zero_inside, viewport(), TOLERANCE).unwrap(),
261 Some(zero_inside)
262 );
263 assert_eq!(
264 clip_segment(segment((2.0, 2.0), (2.0, 2.0)), viewport(), TOLERANCE).unwrap(),
265 None
266 );
267
268 let boundary = segment((0.0, -1.0), (0.0, 2.0));
269 assert_segment_close(
270 clip_segment(boundary, viewport(), TOLERANCE)
271 .unwrap()
272 .unwrap(),
273 segment((0.0, 0.0), (0.0, 1.0)),
274 );
275 let tangent = clip_segment(segment((-1.0, 0.0), (0.0, 1.0)), viewport(), TOLERANCE)
276 .unwrap()
277 .unwrap();
278 assert_segment_close(tangent, segment((0.0, 1.0), (0.0, 1.0)));
279 }
280
281 #[test]
282 fn non_finite_endpoints_are_rejected() {
283 for source in [
284 segment((f64::NAN, 0.0), (1.0, 1.0)),
285 segment((0.0, f64::INFINITY), (1.0, 1.0)),
286 segment((0.0, 0.0), (f64::NEG_INFINITY, 1.0)),
287 ] {
288 assert!(matches!(
289 clip_segment(source, viewport(), TOLERANCE),
290 Err(Error::NonFiniteSegment { .. })
291 ));
292 }
293 }
294
295 proptest! {
296 #[test]
297 fn clipped_endpoints_are_visible_and_lie_on_the_source(
298 x0 in -5.0_f64..5.0,
299 y0 in -5.0_f64..5.0,
300 x1 in -5.0_f64..5.0,
301 y1 in -5.0_f64..5.0,
302 ) {
303 let source = segment((x0, y0), (x1, y1));
304 if let Some(clipped) = clip_segment_with_parameters(source, viewport(), TOLERANCE).unwrap() {
305 prop_assert!(viewport().contains(clipped.segment.start, TOLERANCE).unwrap());
306 prop_assert!(viewport().contains(clipped.segment.end, TOLERANCE).unwrap());
307 let expected_start = source.point_at(clipped.parameter_start);
308 let expected_end = source.point_at(clipped.parameter_end);
309 prop_assert!((expected_start.x - clipped.segment.start.x).abs() < EPSILON);
310 prop_assert!((expected_start.y - clipped.segment.start.y).abs() < EPSILON);
311 prop_assert!((expected_end.x - clipped.segment.end.x).abs() < EPSILON);
312 prop_assert!((expected_end.y - clipped.segment.end.y).abs() < EPSILON);
313 prop_assert!(clipped.parameter_start >= 0.0);
314 prop_assert!(clipped.parameter_end <= 1.0);
315 prop_assert!(clipped.parameter_start <= clipped.parameter_end + EPSILON);
316 }
317 }
318
319 #[test]
320 fn reversing_a_source_reverses_its_clipped_result(
321 x0 in -5.0_f64..5.0,
322 y0 in -5.0_f64..5.0,
323 x1 in -5.0_f64..5.0,
324 y1 in -5.0_f64..5.0,
325 ) {
326 let source = segment((x0, y0), (x1, y1));
327 let reverse = CartesianSegment::new(source.end, source.start);
328 let forward_result = clip_segment(source, viewport(), TOLERANCE).unwrap();
329 let reverse_result = clip_segment(reverse, viewport(), TOLERANCE).unwrap();
330 prop_assert_eq!(forward_result.is_some(), reverse_result.is_some());
331 if let (Some(forward), Some(reversed)) = (forward_result, reverse_result) {
332 prop_assert!((forward.start.x - reversed.end.x).abs() < EPSILON);
333 prop_assert!((forward.start.y - reversed.end.y).abs() < EPSILON);
334 prop_assert!((forward.end.x - reversed.start.x).abs() < EPSILON);
335 prop_assert!((forward.end.y - reversed.start.y).abs() < EPSILON);
336 }
337 }
338
339 #[test]
340 fn fully_contained_segments_are_unchanged(
341 x0 in 0.0_f64..1.0,
342 y0 in 0.0_f64..1.0,
343 x1 in 0.0_f64..1.0,
344 y1 in 0.0_f64..1.0,
345 ) {
346 let source = segment((x0, y0), (x1, y1));
347 prop_assert_eq!(clip_segment(source, viewport(), TOLERANCE).unwrap(), Some(source));
348 }
349 }
350}