1 use crate::drawing::backend::{BackendCoord, BackendStyle, DrawingErrorKind};
2 use crate::drawing::DrawingBackend;
3
4 use crate::style::Color;
5
6 use std::cmp::{Ord, Ordering, PartialOrd};
7
8 #[derive(Clone, Debug)]
9 struct Edge {
10 epoch: u32,
11 total_epoch: u32,
12 slave_begin: i32,
13 slave_end: i32,
14 }
15
16 impl Edge {
horizontal_sweep(mut from: BackendCoord, mut to: BackendCoord) -> Option<Edge>17 fn horizontal_sweep(mut from: BackendCoord, mut to: BackendCoord) -> Option<Edge> {
18 if from.0 == to.0 {
19 return None;
20 }
21
22 if from.0 > to.0 {
23 std::mem::swap(&mut from, &mut to);
24 }
25
26 Some(Edge {
27 epoch: 0,
28 total_epoch: (to.0 - from.0) as u32,
29 slave_begin: from.1,
30 slave_end: to.1,
31 })
32 }
33
vertical_sweep(from: BackendCoord, to: BackendCoord) -> Option<Edge>34 fn vertical_sweep(from: BackendCoord, to: BackendCoord) -> Option<Edge> {
35 Edge::horizontal_sweep((from.1, from.0), (to.1, to.0))
36 }
37
get_master_pos(&self) -> i3238 fn get_master_pos(&self) -> i32 {
39 (self.total_epoch - self.epoch) as i32
40 }
41
inc_epoch(&mut self)42 fn inc_epoch(&mut self) {
43 self.epoch += 1;
44 }
45
get_slave_pos(&self) -> f6446 fn get_slave_pos(&self) -> f64 {
47 f64::from(self.slave_begin)
48 + (i64::from(self.slave_end - self.slave_begin) * i64::from(self.epoch)) as f64
49 / f64::from(self.total_epoch)
50 }
51 }
52
53 impl PartialOrd for Edge {
partial_cmp(&self, other: &Self) -> Option<Ordering>54 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
55 self.get_slave_pos().partial_cmp(&other.get_slave_pos())
56 }
57 }
58
59 impl PartialEq for Edge {
eq(&self, other: &Self) -> bool60 fn eq(&self, other: &Self) -> bool {
61 self.get_slave_pos() == other.get_slave_pos()
62 }
63 }
64
65 impl Eq for Edge {}
66
67 impl Ord for Edge {
cmp(&self, other: &Self) -> Ordering68 fn cmp(&self, other: &Self) -> Ordering {
69 self.get_slave_pos()
70 .partial_cmp(&other.get_slave_pos())
71 .unwrap()
72 }
73 }
74
fill_polygon<DB: DrawingBackend, S: BackendStyle>( back: &mut DB, vertices: &[BackendCoord], style: &S, ) -> Result<(), DrawingErrorKind<DB::ErrorType>>75 pub fn fill_polygon<DB: DrawingBackend, S: BackendStyle>(
76 back: &mut DB,
77 vertices: &[BackendCoord],
78 style: &S,
79 ) -> Result<(), DrawingErrorKind<DB::ErrorType>> {
80 if let Some((x_span, y_span)) =
81 vertices
82 .iter()
83 .fold(None, |res: Option<((i32, i32), (i32, i32))>, (x, y)| {
84 Some(
85 res.map(|((min_x, max_x), (min_y, max_y))| {
86 (
87 (min_x.min(*x), max_x.max(*x)),
88 (min_y.min(*y), max_y.max(*y)),
89 )
90 })
91 .unwrap_or(((*x, *x), (*y, *y))),
92 )
93 })
94 {
95 // First of all, let's handle the case that all the points is in a same vertical or
96 // horizontal line
97 if x_span.0 == x_span.1 || y_span.0 == y_span.1 {
98 return back.draw_line((x_span.0, y_span.0), (x_span.1, y_span.1), style);
99 }
100
101 let horizontal_sweep = x_span.1 - x_span.0 > y_span.1 - y_span.0;
102
103 let mut edges: Vec<_> = vertices
104 .iter()
105 .zip(vertices.iter().skip(1))
106 .map(|(a, b)| (*a, *b))
107 .collect();
108 edges.push((vertices[vertices.len() - 1], vertices[0]));
109 edges.sort_by_key(|((x1, y1), (x2, y2))| {
110 if horizontal_sweep {
111 *x1.min(x2)
112 } else {
113 *y1.min(y2)
114 }
115 });
116
117 for edge in &mut edges.iter_mut() {
118 if horizontal_sweep {
119 if (edge.0).0 > (edge.1).0 {
120 std::mem::swap(&mut edge.0, &mut edge.1);
121 }
122 } else if (edge.0).1 > (edge.1).1 {
123 std::mem::swap(&mut edge.0, &mut edge.1);
124 }
125 }
126
127 let (low, high) = if horizontal_sweep { x_span } else { y_span };
128
129 let mut idx = 0;
130
131 let mut active_edge: Vec<Edge> = vec![];
132
133 for sweep_line in low..=high {
134 let mut new_vec = vec![];
135
136 for mut e in active_edge {
137 if e.get_master_pos() > 0 {
138 e.inc_epoch();
139 new_vec.push(e);
140 }
141 }
142
143 active_edge = new_vec;
144
145 loop {
146 if idx >= edges.len() {
147 break;
148 }
149 let line = if horizontal_sweep {
150 (edges[idx].0).0
151 } else {
152 (edges[idx].0).1
153 };
154 if line > sweep_line {
155 break;
156 }
157
158 let edge_obj = if horizontal_sweep {
159 Edge::horizontal_sweep(edges[idx].0, edges[idx].1)
160 } else {
161 Edge::vertical_sweep(edges[idx].0, edges[idx].1)
162 };
163
164 if let Some(edge_obj) = edge_obj {
165 active_edge.push(edge_obj);
166 }
167
168 idx += 1;
169 }
170
171 active_edge.sort();
172
173 let mut first = None;
174 let mut second = None;
175
176 for edge in active_edge.iter() {
177 if first.is_none() {
178 first = Some(edge.clone())
179 } else if second.is_none() {
180 second = Some(edge.clone())
181 }
182
183 if let Some(a) = first.clone() {
184 if let Some(b) = second.clone() {
185 if a.get_master_pos() == 0 && b.get_master_pos() != 0 {
186 first = Some(b);
187 second = None;
188 continue;
189 }
190
191 if a.get_master_pos() != 0 && b.get_master_pos() == 0 {
192 first = Some(a);
193 second = None;
194 continue;
195 }
196
197 let from = a.get_slave_pos();
198 let to = b.get_slave_pos();
199
200 if a.get_master_pos() == 0 && b.get_master_pos() == 0 && to - from > 1.0 {
201 first = None;
202 second = None;
203 continue;
204 }
205
206 if horizontal_sweep {
207 check_result!(back.draw_line(
208 (sweep_line, from.ceil() as i32),
209 (sweep_line, to.floor() as i32),
210 &style.as_color(),
211 ));
212 check_result!(back.draw_pixel(
213 (sweep_line, from.floor() as i32),
214 &style.as_color().mix(from.ceil() - from),
215 ));
216 check_result!(back.draw_pixel(
217 (sweep_line, to.ceil() as i32),
218 &style.as_color().mix(to - to.floor()),
219 ));
220 } else {
221 check_result!(back.draw_line(
222 (from.ceil() as i32, sweep_line),
223 (to.floor() as i32, sweep_line),
224 &style.as_color(),
225 ));
226 check_result!(back.draw_pixel(
227 (from.floor() as i32, sweep_line),
228 &style.as_color().mix(from.ceil() - from),
229 ));
230 check_result!(back.draw_pixel(
231 (to.ceil() as i32, sweep_line),
232 &style.as_color().mix(to.floor() - to),
233 ));
234 }
235
236 first = None;
237 second = None;
238 }
239 }
240 }
241 }
242 }
243
244 Ok(())
245 }
246