plotters_backend/rasterizer/
path.rs

1use crate::BackendCoord;
2
3// Compute the tanginal and normal vectors of the given straight line.
4fn get_dir_vector(from: BackendCoord, to: BackendCoord, flag: bool) -> ((f64, f64), (f64, f64)) {
5    let v = (i64::from(to.0 - from.0), i64::from(to.1 - from.1));
6    let l = ((v.0 * v.0 + v.1 * v.1) as f64).sqrt();
7
8    let v = (v.0 as f64 / l, v.1 as f64 / l);
9
10    if flag {
11        (v, (v.1, -v.0))
12    } else {
13        (v, (-v.1, v.0))
14    }
15}
16
17// Compute the polygonized vertex of the given angle
18// d is the distance between the polygon edge and the actual line.
19// d can be negative, this will emit a vertex on the other side of the line.
20fn compute_polygon_vertex(triple: &[BackendCoord; 3], d: f64, buf: &mut Vec<BackendCoord>) {
21    buf.clear();
22
23    // Compute the tanginal and normal vectors of the given straight line.
24    let (a_t, a_n) = get_dir_vector(triple[0], triple[1], false);
25    let (b_t, b_n) = get_dir_vector(triple[2], triple[1], true);
26
27    // Compute a point that is d away from the line for line a and line b.
28    let a_p = (
29        f64::from(triple[1].0) + d * a_n.0,
30        f64::from(triple[1].1) + d * a_n.1,
31    );
32    let b_p = (
33        f64::from(triple[1].0) + d * b_n.0,
34        f64::from(triple[1].1) + d * b_n.1,
35    );
36
37    // Check if 3 points are colinear, up to precision. If so, just emit the point.
38    if (a_t.1 * b_t.0 - a_t.0 * b_t.1).abs() <= f64::EPSILON {
39        buf.push((a_p.0 as i32, a_p.1 as i32));
40        return;
41    }
42
43    // So we are actually computing the intersection of two lines:
44    // a_p + u * a_t and b_p + v * b_t.
45    // We can solve the following vector equation:
46    // u * a_t + a_p = v * b_t + b_p
47    //
48    // which is actually a equation system:
49    // u * a_t.0 - v * b_t.0 = b_p.0 - a_p.0
50    // u * a_t.1 - v * b_t.1 = b_p.1 - a_p.1
51
52    // The following vars are coefficients of the linear equation system.
53    // a0*u + b0*v = c0
54    // a1*u + b1*v = c1
55    // in which x and y are the coordinates that two polygon edges intersect.
56
57    let a0 = a_t.0;
58    let b0 = -b_t.0;
59    let c0 = b_p.0 - a_p.0;
60    let a1 = a_t.1;
61    let b1 = -b_t.1;
62    let c1 = b_p.1 - a_p.1;
63
64    // Since the points are not collinear, the determinant is not 0, and we can get a intersection point.
65    let u = (c0 * b1 - c1 * b0) / (a0 * b1 - a1 * b0);
66    let x = a_p.0 + u * a_t.0;
67    let y = a_p.1 + u * a_t.1;
68
69    let cross_product = a_t.0 * b_t.1 - a_t.1 * b_t.0;
70    if (cross_product < 0.0 && d < 0.0) || (cross_product > 0.0 && d > 0.0) {
71        // Then we are at the outer side of the angle, so we need to consider a cap.
72        let dist_square = (x - triple[1].0 as f64).powi(2) + (y - triple[1].1 as f64).powi(2);
73        // If the point is too far away from the line, we need to cap it.
74        if dist_square > d * d * 16.0 {
75            buf.push((a_p.0.round() as i32, a_p.1.round() as i32));
76            buf.push((b_p.0.round() as i32, b_p.1.round() as i32));
77            return;
78        }
79    }
80
81    buf.push((x.round() as i32, y.round() as i32));
82}
83
84fn traverse_vertices<'a>(
85    mut vertices: impl Iterator<Item = &'a BackendCoord>,
86    width: u32,
87    mut op: impl FnMut(BackendCoord),
88) {
89    let mut a = vertices.next().unwrap();
90    let mut b = vertices.next().unwrap();
91
92    while a == b {
93        a = b;
94        if let Some(new_b) = vertices.next() {
95            b = new_b;
96        } else {
97            return;
98        }
99    }
100
101    let (_, n) = get_dir_vector(*a, *b, false);
102
103    op((
104        (f64::from(a.0) + n.0 * f64::from(width) / 2.0).round() as i32,
105        (f64::from(a.1) + n.1 * f64::from(width) / 2.0).round() as i32,
106    ));
107
108    let mut recent = [(0, 0), *a, *b];
109    let mut vertex_buf = Vec::with_capacity(3);
110
111    for p in vertices {
112        if *p == recent[2] {
113            continue;
114        }
115        recent.swap(0, 1);
116        recent.swap(1, 2);
117        recent[2] = *p;
118        compute_polygon_vertex(&recent, f64::from(width) / 2.0, &mut vertex_buf);
119        vertex_buf.iter().cloned().for_each(&mut op);
120    }
121
122    let b = recent[1];
123    let a = recent[2];
124
125    let (_, n) = get_dir_vector(a, b, true);
126
127    op((
128        (f64::from(a.0) + n.0 * f64::from(width) / 2.0).round() as i32,
129        (f64::from(a.1) + n.1 * f64::from(width) / 2.0).round() as i32,
130    ));
131}
132
133/// Covert a path with >1px stroke width into polygon.
134pub fn polygonize(vertices: &[BackendCoord], stroke_width: u32) -> Vec<BackendCoord> {
135    if vertices.len() < 2 {
136        return vec![];
137    }
138
139    let mut ret = vec![];
140
141    traverse_vertices(vertices.iter(), stroke_width, |v| ret.push(v));
142    traverse_vertices(vertices.iter().rev(), stroke_width, |v| ret.push(v));
143
144    ret
145}
146
147#[cfg(test)]
148mod test {
149    use super::*;
150
151    /// Test for regression with respect to https://github.com/plotters-rs/plotters/issues/562
152    #[test]
153    fn test_no_inf_in_compute_polygon_vertex() {
154        let path = [(335, 386), (338, 326), (340, 286)];
155        let mut buf = Vec::new();
156        compute_polygon_vertex(&path, 2.0, buf.as_mut());
157        assert!(!buf.is_empty());
158        let nani32 = f64::INFINITY as i32;
159        assert!(!buf.iter().any(|&v| v.0 == nani32 || v.1 == nani32));
160    }
161
162    /// Correct 90 degree turn to the right
163    #[test]
164    fn standard_corner() {
165        let path = [(10, 10), (20, 10), (20, 20)];
166        let mut buf = Vec::new();
167        compute_polygon_vertex(&path, 2.0, buf.as_mut());
168        assert!(!buf.is_empty());
169        let buf2 = vec![(18, 12)];
170        assert_eq!(buf, buf2);
171    }
172}
plotters_backend/rasterizer/path.rs

plotters_backend/rasterizer/
path.rs
