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. If so, just emit the point.
38 if a_t.1 * b_t.0 == a_t.0 * b_t.1 {
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 let mut x = f64::INFINITY;
65 let mut y = f64::INFINITY;
66
67 // Well if the determinant is not 0, then we can actuall get a intersection point.
68 if (a0 * b1 - a1 * b0).abs() > f64::EPSILON {
69 let u = (c0 * b1 - c1 * b0) / (a0 * b1 - a1 * b0);
70
71 x = a_p.0 + u * a_t.0;
72 y = a_p.1 + u * a_t.1;
73 }
74
75 let cross_product = a_t.0 * b_t.1 - a_t.1 * b_t.0;
76 if (cross_product < 0.0 && d < 0.0) || (cross_product > 0.0 && d > 0.0) {
77 // Then we are at the outter side of the angle, so we need to consider a cap.
78 let dist_square = (x - triple[1].0 as f64).powi(2) + (y - triple[1].1 as f64).powi(2);
79 // If the point is too far away from the line, we need to cap it.
80 if dist_square > d * d * 16.0 {
81 buf.push((a_p.0.round() as i32, a_p.1.round() as i32));
82 buf.push((b_p.0.round() as i32, b_p.1.round() as i32));
83 return;
84 }
85 }
86
87 buf.push((x.round() as i32, y.round() as i32));
88}
89
90fn traverse_vertices<'a>(
91 mut vertices: impl Iterator<Item = &'a BackendCoord>,
92 width: u32,
93 mut op: impl FnMut(BackendCoord),
94) {
95 let mut a = vertices.next().unwrap();
96 let mut b = vertices.next().unwrap();
97
98 while a == b {
99 a = b;
100 if let Some(new_b) = vertices.next() {
101 b = new_b;
102 } else {
103 return;
104 }
105 }
106
107 let (_, n) = get_dir_vector(*a, *b, false);
108
109 op((
110 (f64::from(a.0) + n.0 * f64::from(width) / 2.0).round() as i32,
111 (f64::from(a.1) + n.1 * f64::from(width) / 2.0).round() as i32,
112 ));
113
114 let mut recent = [(0, 0), *a, *b];
115 let mut vertex_buf = Vec::with_capacity(3);
116
117 for p in vertices {
118 if *p == recent[2] {
119 continue;
120 }
121 recent.swap(0, 1);
122 recent.swap(1, 2);
123 recent[2] = *p;
124 compute_polygon_vertex(&recent, f64::from(width) / 2.0, &mut vertex_buf);
125 vertex_buf.iter().cloned().for_each(&mut op);
126 }
127
128 let b = recent[1];
129 let a = recent[2];
130
131 let (_, n) = get_dir_vector(a, b, true);
132
133 op((
134 (f64::from(a.0) + n.0 * f64::from(width) / 2.0).round() as i32,
135 (f64::from(a.1) + n.1 * f64::from(width) / 2.0).round() as i32,
136 ));
137}
138
139/// Covert a path with >1px stroke width into polygon.
140pub fn polygonize(vertices: &[BackendCoord], stroke_width: u32) -> Vec<BackendCoord> {
141 if vertices.len() < 2 {
142 return vec![];
143 }
144
145 let mut ret = vec![];
146
147 traverse_vertices(vertices.iter(), stroke_width, |v| ret.push(v));
148 traverse_vertices(vertices.iter().rev(), stroke_width, |v| ret.push(v));
149
150 ret
151}
152