/rust/registry/src/index.crates.io-6f17d22bba15001f/plotters-backend-0.3.7/src/rasterizer/polygon.rs

Source (jump to first uncovered line)
use crate::{BackendCoord, BackendStyle, DrawingBackend, DrawingErrorKind};

use std::cmp::{Ord, Ordering, PartialOrd};

#[derive(Clone, Debug)]
struct Edge {
    epoch: u32,
    total_epoch: u32,
    slave_begin: i32,
    slave_end: i32,
}

impl Edge {
    fn horizontal_sweep(mut from: BackendCoord, mut to: BackendCoord) -> Option<Edge> {
        if from.0 == to.0 {
            return None;
        }

        if from.0 > to.0 {
            std::mem::swap(&mut from, &mut to);
        }

        Some(Edge {
            epoch: 0,
            total_epoch: (to.0 - from.0) as u32,
            slave_begin: from.1,
            slave_end: to.1,
        })
    }

    fn vertical_sweep(from: BackendCoord, to: BackendCoord) -> Option<Edge> {
        Edge::horizontal_sweep((from.1, from.0), (to.1, to.0))
    }

    fn get_master_pos(&self) -> i32 {
        (self.total_epoch - self.epoch) as i32
    }

    fn inc_epoch(&mut self) {
        self.epoch += 1;
    }

    fn get_slave_pos(&self) -> f64 {
        f64::from(self.slave_begin)
            + (i64::from(self.slave_end - self.slave_begin) * i64::from(self.epoch)) as f64
                / f64::from(self.total_epoch)
    }
}

impl PartialOrd for Edge {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl PartialEq for Edge {
    fn eq(&self, other: &Self) -> bool {
        self.get_slave_pos() == other.get_slave_pos()
    }
}

impl Eq for Edge {}

impl Ord for Edge {
    fn cmp(&self, other: &Self) -> Ordering {
        self.get_slave_pos()
            .partial_cmp(&other.get_slave_pos())
            .unwrap()
    }
}

pub fn fill_polygon<DB: DrawingBackend, S: BackendStyle>(
    back: &mut DB,
    vertices: &[BackendCoord],
    style: &S,
) -> Result<(), DrawingErrorKind<DB::ErrorType>> {
    if let Some((x_span, y_span)) =
        vertices
            .iter()
            .fold(None, |res: Option<((i32, i32), (i32, i32))>, (x, y)| {
                Some(
                    res.map(|((min_x, max_x), (min_y, max_y))| {
                        (
                            (min_x.min(*x), max_x.max(*x)),
                            (min_y.min(*y), max_y.max(*y)),
                        )
                    })
                    .unwrap_or(((*x, *x), (*y, *y))),
                )
            })
    {
        // First of all, let's handle the case that all the points is in a same vertical or
        // horizontal line
        if x_span.0 == x_span.1 || y_span.0 == y_span.1 {
            return back.draw_line((x_span.0, y_span.0), (x_span.1, y_span.1), style);
        }

        let horizontal_sweep = x_span.1 - x_span.0 > y_span.1 - y_span.0;

        let mut edges: Vec<_> = vertices
            .iter()
            .zip(vertices.iter().skip(1))
            .map(|(a, b)| (*a, *b))
            .collect();
        edges.push((vertices[vertices.len() - 1], vertices[0]));
        edges.sort_by_key(|((x1, y1), (x2, y2))| {
            if horizontal_sweep {
                *x1.min(x2)
            } else {
                *y1.min(y2)
            }
        });

        for edge in &mut edges.iter_mut() {
            if horizontal_sweep {
                if (edge.0).0 > (edge.1).0 {
                    std::mem::swap(&mut edge.0, &mut edge.1);
                }
            } else if (edge.0).1 > (edge.1).1 {
                std::mem::swap(&mut edge.0, &mut edge.1);
            }
        }

        let (low, high) = if horizontal_sweep { x_span } else { y_span };

        let mut idx = 0;

        let mut active_edge: Vec<Edge> = vec![];

        for sweep_line in low..=high {
            let mut new_vec = vec![];

            for mut e in active_edge {
                if e.get_master_pos() > 0 {
                    e.inc_epoch();
                    new_vec.push(e);
                }
            }

            active_edge = new_vec;

            loop {
                if idx >= edges.len() {
                    break;
                }
                let line = if horizontal_sweep {
                    (edges[idx].0).0
                } else {
                    (edges[idx].0).1
                };
                if line > sweep_line {
                    break;
                }

                let edge_obj = if horizontal_sweep {
                    Edge::horizontal_sweep(edges[idx].0, edges[idx].1)
                } else {
                    Edge::vertical_sweep(edges[idx].0, edges[idx].1)
                };

                if let Some(edge_obj) = edge_obj {
                    active_edge.push(edge_obj);
                }

                idx += 1;
            }

            active_edge.sort();

            let mut first = None;
            let mut second = None;

            for edge in active_edge.iter() {
                if first.is_none() {
                    first = Some(edge.clone())
                } else if second.is_none() {
                    second = Some(edge.clone())
                }

                if let Some(a) = first.clone() {
                    if let Some(b) = second.clone() {
                        if a.get_master_pos() == 0 && b.get_master_pos() != 0 {
                            first = Some(b);
                            second = None;
                            continue;
                        }

                        if a.get_master_pos() != 0 && b.get_master_pos() == 0 {
                            first = Some(a);
                            second = None;
                            continue;
                        }

                        let from = a.get_slave_pos();
                        let to = b.get_slave_pos();

                        if a.get_master_pos() == 0 && b.get_master_pos() == 0 && to - from > 1.0 {
                            first = None;
                            second = None;
                            continue;
                        }

                        if horizontal_sweep {
                            check_result!(back.draw_line(
                                (sweep_line, from.ceil() as i32),
                                (sweep_line, to.floor() as i32),
                                &style.color(),
                            ));
                            check_result!(back.draw_pixel(
                                (sweep_line, from.floor() as i32),
                                style.color().mix(from.ceil() - from),
                            ));
                            check_result!(back.draw_pixel(
                                (sweep_line, to.ceil() as i32),
                                style.color().mix(to - to.floor()),
                            ));
                        } else {
                            check_result!(back.draw_line(
                                (from.ceil() as i32, sweep_line),
                                (to.floor() as i32, sweep_line),
                                &style.color(),
                            ));
                            check_result!(back.draw_pixel(
                                (from.floor() as i32, sweep_line),
                                style.color().mix(from.ceil() - from),
                            ));
                            check_result!(back.draw_pixel(
                                (to.ceil() as i32, sweep_line),
                                style.color().mix(to.floor() - to),
                            ));
                        }

                        first = None;
                        second = None;
                    }
                }
            }
        }
    }

    Ok(())
}

Coverage Report

Created: 2025-02-25 06:39

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