1 | use crate::BackendCoord; |
---|---|

2 | |

3 | // Compute the tanginal and normal vectors of the given straight line. |

4 | fn 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. |

20 | fn 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 | |

90 | fn 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. |

140 | pub 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 |