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