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