1use crate::{
2 draw_target::DrawTarget,
3 geometry::{Point, Size},
4 primitives::{Line, PointsIter, Rectangle},
5};
6use core::ops::Range;
7
8/// Scanline.
9#[derive(Debug, Clone, Eq, PartialEq, Hash)]
10#[cfg_attr(feature = "defmt", derive(::defmt::Format))]
11pub struct Scanline {
12 pub y: i32,
13 pub x: Range<i32>,
14}
15
16impl Scanline {
17 /// Creates a new scanline.
18 pub const fn new(y: i32, x: Range<i32>) -> Self {
19 Self { y, x }
20 }
21
22 /// Creates a new empty scanline.
23 pub const fn new_empty(y: i32) -> Self {
24 Self::new(y, 0..0)
25 }
26
27 /// Returns `true` if the x range of the scanline is empty.
28 pub fn is_empty(&self) -> bool {
29 self.x.is_empty()
30 }
31
32 /// Extends the scanline to include the given x coordinate.
33 fn extend(&mut self, x: i32) {
34 if self.is_empty() {
35 self.x = x..x + 1;
36 } else if x < self.x.start {
37 self.x.start = x;
38 } else if x >= self.x.end {
39 self.x.end = x + 1;
40 }
41 }
42
43 /// Intersect a horizontal scan line with the Bresenham representation of this line segment.
44 ///
45 /// Intersection lines produced by this function are sorted so that the start always lies to the
46 /// left of the end.
47 pub fn bresenham_intersection(&mut self, line: &Line) {
48 // Check if the scanline is in the y range of the line.
49 let y_range = if line.start.y <= line.end.y {
50 line.start.y..=line.end.y
51 } else {
52 line.end.y..=line.start.y
53 };
54
55 if !y_range.contains(&self.y) {
56 return;
57 }
58
59 let y = self.y;
60
61 line.points()
62 .skip_while(|p| p.y != y)
63 .take_while(|p| p.y == y)
64 .for_each(|p| {
65 self.extend(p.x);
66 });
67 }
68
69 /// Check for lines that are adjacent or overlapping.
70 ///
71 /// This assumes that both lines have the same y coordinate.
72 fn touches(&self, other: &Scanline) -> bool {
73 debug_assert_eq!(
74 self.y, other.y,
75 "try_extend must be called with scanlines with equal y coordinate"
76 );
77
78 if self.is_empty() || other.is_empty() {
79 return false;
80 }
81
82 let range = self.x.start - 1..=self.x.end;
83
84 range.contains(&(other.x.start)) || range.contains(&(other.x.end - 1)) || {
85 // PERF: If the other conditions short circuit, this won't be computed.
86 let range = other.x.start - 1..=other.x.end;
87
88 range.contains(&(self.x.start)) || range.contains(&(self.x.end - 1))
89 }
90 }
91
92 /// Tries to extend this line by another line.
93 ///
94 /// The line is only extended when the other line overlaps this line or is directly adjacent
95 /// to this line.
96 ///
97 /// Returns `true` if the line was extended and `false` otherwise.
98 pub fn try_extend(&mut self, other: &Scanline) -> bool {
99 debug_assert_eq!(
100 self.y, other.y,
101 "try_extend must be called with scanlines with equal y coordinate"
102 );
103
104 if self.touches(other) {
105 self.x.start = self.x.start.min(other.x.start);
106 self.x.end = self.x.end.max(other.x.end);
107
108 true
109 } else {
110 false
111 }
112 }
113
114 /// Converts the scanline into a 1px high rectangle.
115 pub fn to_rectangle(&self) -> Rectangle {
116 let width = if !self.is_empty() {
117 (self.x.end - self.x.start) as u32
118 } else {
119 0
120 };
121
122 Rectangle::new(Point::new(self.x.start, self.y), Size::new(width, 1))
123 }
124
125 /// Returns a clone of the scanline if it isn't empty.
126 ///
127 /// This method is used similar to `Option::take`, but was renamed to `try_take` because
128 /// of a naming conflict with `Iterator::take`.
129 pub fn try_take(&mut self) -> Option<Self> {
130 if !self.is_empty() {
131 let ret = self.clone();
132 self.x = 0..0;
133 Some(ret)
134 } else {
135 None
136 }
137 }
138
139 /// Draws the scanline.
140 pub fn draw<T>(&self, target: &mut T, color: T::Color) -> Result<(), T::Error>
141 where
142 T: DrawTarget,
143 {
144 if self.is_empty() {
145 return Ok(());
146 }
147
148 let width = (self.x.end - self.x.start) as u32;
149
150 target.fill_solid(
151 &Rectangle::new(Point::new(self.x.start, self.y), Size::new(width, 1)),
152 color,
153 )
154 }
155}
156
157impl Iterator for Scanline {
158 type Item = Point;
159
160 fn next(&mut self) -> Option<Self::Item> {
161 self.x.next().map(|x: i32| Point::new(x, self.y))
162 }
163}
164
165#[cfg(test)]
166mod tests {
167 use super::*;
168
169 fn run_touches_test(s1: i32, e1: i32, s2: i32, e2: i32, expected: bool, ident: &str) {
170 let mut l1 = Scanline::new_empty(0);
171 l1.extend(s1);
172 l1.extend(e1);
173
174 let mut l2 = Scanline::new_empty(0);
175 l2.extend(s2);
176 l2.extend(e2);
177
178 assert_eq!(l1.touches(&l2), expected, "{}", ident);
179 }
180
181 #[test]
182 fn check_touches() {
183 run_touches_test(30, 40, 5, 15, false, "Reversed");
184 run_touches_test(0, 6, 5, 10, true, "Contained");
185 run_touches_test(11, 13, 11, 14, true, "Contained 2");
186 run_touches_test(10, 15, 25, 35, false, "Separated");
187 run_touches_test(10, 10, 10, 10, true, "Zero size");
188 run_touches_test(10, 20, 10, 20, true, "Equal");
189 run_touches_test(10, 20, 20, 10, true, "Equal reversed");
190 run_touches_test(79, 82, 82, 92, true, "Overlapping lines 1");
191 run_touches_test(82, 92, 79, 82, true, "Overlapping lines 1, reversed");
192 run_touches_test(80, 83, 83, 94, true, "Overlapping lines 2");
193 run_touches_test(83, 94, 80, 83, true, "Overlapping lines 2, reversed");
194 run_touches_test(83, 94, 94, 100, true, "Adjacent");
195 }
196
197 #[test]
198 fn issue_489_filled_triangle_bug() {
199 let mut l1 = Scanline { y: 5, x: 18..20 };
200 let l2 = Scanline { y: 5, x: 11..26 };
201
202 assert_eq!(l1.touches(&l2), true, "l1 touches l2");
203
204 let result = l1.try_extend(&l2);
205
206 assert_eq!(result, true);
207 assert_eq!(l1, Scanline { y: 5, x: 11..26 });
208 }
209}
210