line_clipping/
cohen_sutherland.rs

1use crate::{LineSegment, Point, Window};
2use bitflags::bitflags;
3
4/// Implements the Cohen-Sutherland line clipping algorithm.
5///
6/// Returns the clipped line if the original line intersects the clipping window, or `None` if the
7/// original line is completely outside the clipping window.
8///
9/// Reference: [Cohen-Sutherland algorithm](https://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland_algorithm)
10///
11/// The Cohen-Sutherland algorithm is a line clipping algorithm that divides the 2D plane into 9
12/// regions and then determines the region in which the line lies. If the line lies completely
13/// outside the clipping window, it is rejected. If the line lies completely inside the clipping
14/// window, it is accepted. If the line lies partially inside the clipping window, it is clipped.
15///
16/// The regions are defined as follows:
17///
18/// 1001 | 1000 | 1010
19/// -----|------|-----
20/// 0001 | 0000 | 0010
21/// -----|------|-----
22/// 0101 | 0100 | 0110
23///
24/// The algorithm works as follows:
25///
26/// 1. Determine the region in which the line's starting point lies.
27/// 2. Determine the region in which the line's ending point lies.
28/// 3. If both points lie in region 0000, the line is completely inside the clipping window and
29///    should be accepted.
30/// 4. If both points lie in the same region that is not 0000, the line is completely outside the
31///    clipping window and should be rejected.
32/// 5. If the points lie in different regions, the line is partially inside the clipping window and
33///    should be clipped.
34/// 6. Clip the line using the Cohen-Sutherland algorithm.
35/// 7. Repeat the process for the clipped line.
36///
37/// The Cohen-Sutherland algorithm is commonly used in computer graphics to clip lines against a
38/// rectangular window.
39///
40/// # Examples
41///
42/// ```
43/// use cohen_sutherland::clip_line;
44///
45/// let line = clip_line(
46///     Line { p1: Point { x: 0.0, y: 0.0 }, p2: Point { x: 10.0, y: 10.0 } },
47///     Window { x_min: 1.0, x_max: 9.0, y_min: 1.0, y_max: 9.0 },
48/// );
49///
50/// assert_eq!(line, Some(Line { p1: Point { x: 1.0, y: 1.0 }, p2: Point { x: 9.0, y: 9.0 } }));
51/// ```
52pub fn clip_line(mut line: LineSegment, window: Window) -> Option<LineSegment> {
53    let mut region_1 = Region::from_point(line.p1, window);
54    let mut region_2 = Region::from_point(line.p2, window);
55
56    while region_1 != Region::INSIDE || region_2 != Region::INSIDE {
57        if region_1.intersects(region_2) {
58            // The line is completely outside the clipping window.
59            return None;
60        }
61
62        if region_1 != Region::INSIDE {
63            line.p1 = calculate_intersection(line.p1, line.p2, region_1, window);
64            region_1 = Region::from_point(line.p1, window);
65        } else {
66            line.p2 = calculate_intersection(line.p2, line.p1, region_2, window);
67            region_2 = Region::from_point(line.p2, window);
68        };
69    }
70
71    Some(line)
72}
73
74fn calculate_intersection(p1: Point, p2: Point, region: Region, window: Window) -> Point {
75    if region.contains(Region::LEFT) {
76        let y = p1.y + (p2.y - p1.y) * (window.x_min - p1.x) / (p2.x - p1.x);
77        Point { x: window.x_min, y }
78    } else if region.contains(Region::RIGHT) {
79        let y = p1.y + (p2.y - p1.y) * (window.x_max - p1.x) / (p2.x - p1.x);
80        Point { x: window.x_max, y }
81    } else if region.contains(Region::BOTTOM) {
82        let x = p1.x + (p2.x - p1.x) * (window.y_min - p1.y) / (p2.y - p1.y);
83        Point { x, y: window.y_min }
84    } else if region.contains(Region::TOP) {
85        let x = p1.x + (p2.x - p1.x) * (window.y_max - p1.y) / (p2.y - p1.y);
86        Point { x, y: window.y_max }
87    } else {
88        p1
89    }
90}
91
92bitflags! {
93    /// Represents the regions in the Cohen-Sutherland algorithm.
94    #[derive(Debug, Clone, Copy, PartialEq, Eq)]
95    pub struct Region: u8 {
96        const INSIDE = 0b0000;
97        const LEFT = 0b0001;
98        const RIGHT = 0b0010;
99        const BOTTOM = 0b0100;
100        const TOP = 0b1000;
101    }
102}
103
104impl Region {
105    /// Determines the region in which a point lies.
106    pub fn from_point(point: Point, window: Window) -> Self {
107        let mut region = Region::INSIDE;
108        if point.x < window.x_min {
109            region |= Region::LEFT;
110        } else if point.x > window.x_max {
111            region |= Region::RIGHT;
112        }
113        if point.y < window.y_min {
114            region |= Region::BOTTOM;
115        } else if point.y > window.y_max {
116            region |= Region::TOP;
117        }
118        region
119    }
120}
121#[cfg(test)]
122mod tests {
123    use super::*;
124
125    #[test]
126    fn test_line_completely_inside() {
127        let line = clip_line(
128            LineSegment {
129                p1: Point { x: 2.0, y: 2.0 },
130                p2: Point { x: 8.0, y: 8.0 },
131            },
132            Window {
133                x_min: 1.0,
134                x_max: 9.0,
135                y_min: 1.0,
136                y_max: 9.0,
137            },
138        );
139        assert_eq!(
140            line,
141            Some(LineSegment {
142                p1: Point { x: 2.0, y: 2.0 },
143                p2: Point { x: 8.0, y: 8.0 }
144            })
145        );
146    }
147
148    #[test]
149    fn test_line_completely_outside() {
150        let line = clip_line(
151            LineSegment {
152                p1: Point { x: -1.0, y: -1.0 },
153                p2: Point { x: -5.0, y: -5.0 },
154            },
155            Window {
156                x_min: 1.0,
157                x_max: 9.0,
158                y_min: 1.0,
159                y_max: 9.0,
160            },
161        );
162        assert_eq!(line, None);
163    }
164
165    #[test]
166    fn test_line_partially_inside() {
167        let line = clip_line(
168            LineSegment {
169                p1: Point { x: 0.0, y: 0.0 },
170                p2: Point { x: 10.0, y: 10.0 },
171            },
172            Window {
173                x_min: 1.0,
174                x_max: 9.0,
175                y_min: 1.0,
176                y_max: 9.0,
177            },
178        );
179        assert_eq!(
180            line,
181            Some(LineSegment {
182                p1: Point { x: 1.0, y: 1.0 },
183                p2: Point { x: 9.0, y: 9.0 }
184            })
185        );
186    }
187
188    #[test]
189    fn test_line_vertical() {
190        let line = clip_line(
191            LineSegment {
192                p1: Point { x: 5.0, y: 0.0 },
193                p2: Point { x: 5.0, y: 10.0 },
194            },
195            Window {
196                x_min: 1.0,
197                x_max: 9.0,
198                y_min: 1.0,
199                y_max: 9.0,
200            },
201        );
202        assert_eq!(
203            line,
204            Some(LineSegment {
205                p1: Point { x: 5.0, y: 1.0 },
206                p2: Point { x: 5.0, y: 9.0 }
207            })
208        );
209    }
210
211    #[test]
212    fn test_line_horizontal() {
213        let line = clip_line(
214            LineSegment {
215                p1: Point { x: 0.0, y: 5.0 },
216                p2: Point { x: 10.0, y: 5.0 },
217            },
218            Window {
219                x_min: 1.0,
220                x_max: 9.0,
221                y_min: 1.0,
222                y_max: 9.0,
223            },
224        );
225        assert_eq!(
226            line,
227            Some(LineSegment {
228                p1: Point { x: 1.0, y: 5.0 },
229                p2: Point { x: 9.0, y: 5.0 }
230            })
231        );
232    }
233
234    #[test]
235    fn test_line_diagonal() {
236        let line = clip_line(
237            LineSegment {
238                p1: Point { x: -5.0, y: -5.0 },
239                p2: Point { x: 15.0, y: 15.0 },
240            },
241            Window {
242                x_min: 1.0,
243                x_max: 9.0,
244                y_min: 1.0,
245                y_max: 9.0,
246            },
247        );
248        assert_eq!(
249            line,
250            Some(LineSegment {
251                p1: Point { x: 1.0, y: 1.0 },
252                p2: Point { x: 9.0, y: 9.0 }
253            })
254        );
255    }
256}
line_clipping/cohen_sutherland.rs

line_clipping/
cohen_sutherland.rs
