Skip to main content

plotters_ternary/coord/
clipping.rs

1use super::{Error, TernaryCartesian, TernaryViewport, Tolerance};
2
3/// A directed segment in the logical ternary Cartesian plane.
4///
5/// Zero-length segments are valid. Clipping retains one when its point lies
6/// inside or on the viewport and rejects it otherwise.
7#[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    /// Evaluate the directed segment at a parameter, normally in `[0, 1]`.
19    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/// A clipped segment together with its parameter range on the source segment.
28#[derive(Clone, Copy, Debug, PartialEq)]
29pub struct ClippedSegment {
30    pub segment: CartesianSegment,
31    pub parameter_start: f64,
32    pub parameter_end: f64,
33}
34
35/// Clip a directed segment against a logical viewport using Liang-Barsky.
36///
37/// The returned direction always matches the source direction. Parallel
38/// segments within tolerance of a viewport side are treated as coincident;
39/// materially external parallel segments return `None`.
40pub 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
48/// Clip a segment and retain its original directed parameter interval.
49pub 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}