1use crate::geom::{Matrix, Point};
5
6#[derive(Debug, Clone, PartialEq)]
8pub struct Dash {
9 pub pattern: Vec<f64>,
11 pub phase: f64,
13}
14
15impl Dash {
16 pub fn solid() -> Self {
18 Self {
19 pattern: Vec::new(),
20 phase: 0.0,
21 }
22 }
23
24 pub fn is_solid(&self) -> bool {
26 self.pattern.is_empty() || self.pattern.iter().all(|length| *length <= 0.0)
27 }
28}
29
30#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32pub enum Cap {
33 Butt,
35 Round,
37 Square,
39}
40
41#[derive(Debug, Clone, Copy, PartialEq, Eq)]
47pub enum Join {
48 Miter,
50 Round,
52 Bevel,
54}
55
56#[derive(Debug, Clone, Copy, PartialEq)]
58pub enum Segment {
59 Line(Point),
61 Cubic {
63 c1: Point,
65 c2: Point,
67 to: Point,
69 },
70}
71
72#[derive(Debug, Clone, PartialEq)]
74pub struct Subpath {
75 pub start: Point,
77 pub segments: Vec<Segment>,
79 pub closed: bool,
81}
82
83#[derive(Debug, Clone, Default, PartialEq)]
85pub struct Path {
86 pub subpaths: Vec<Subpath>,
88}
89
90impl Path {
91 pub fn new() -> Self {
93 Self::default()
94 }
95
96 pub fn is_empty(&self) -> bool {
98 self.subpaths
99 .iter()
100 .all(|subpath| subpath.segments.is_empty())
101 }
102
103 pub fn move_to(&mut self, point: Point) {
105 self.subpaths.push(Subpath {
106 start: point,
107 segments: Vec::new(),
108 closed: false,
109 });
110 }
111
112 pub fn line_to(&mut self, point: Point) {
114 if let Some(subpath) = self.subpaths.last_mut() {
115 subpath.segments.push(Segment::Line(point));
116 } else {
117 self.move_to(point);
118 }
119 }
120
121 pub fn curve_to(&mut self, c1: Point, c2: Point, to: Point) {
123 if let Some(subpath) = self.subpaths.last_mut() {
124 subpath.segments.push(Segment::Cubic { c1, c2, to });
125 } else {
126 self.move_to(to);
127 }
128 }
129
130 pub fn close(&mut self) {
132 if let Some(subpath) = self.subpaths.last_mut() {
133 subpath.closed = true;
134 }
135 }
136
137 pub fn add_rect(&mut self, x: f64, y: f64, width: f64, height: f64) {
139 self.move_to(Point::new(x, y));
140 self.line_to(Point::new(x + width, y));
141 self.line_to(Point::new(x + width, y + height));
142 self.line_to(Point::new(x, y + height));
143 self.close();
144 }
145
146 pub fn flatten(&self, ctm: Matrix) -> Vec<Vec<Point>> {
152 const CURVE_STEPS: usize = 24;
153 let mut polylines = Vec::with_capacity(self.subpaths.len());
154 for subpath in &self.subpaths {
155 let mut points = vec![ctm.apply(subpath.start)];
156 let mut current = subpath.start;
157 for segment in &subpath.segments {
158 match *segment {
159 Segment::Line(to) => {
160 points.push(ctm.apply(to));
161 current = to;
162 }
163 Segment::Cubic { c1, c2, to } => {
164 for step in 1..=CURVE_STEPS {
165 let t = step as f64 / CURVE_STEPS as f64;
166 points.push(ctm.apply(cubic_at(current, c1, c2, to, t)));
167 }
168 current = to;
169 }
170 }
171 }
172 if subpath.closed && points.len() > 1 {
173 let first = points[0];
174 let last = *points.last().expect("non-empty");
175 if (first.x - last.x).abs() > f64::EPSILON
176 || (first.y - last.y).abs() > f64::EPSILON
177 {
178 points.push(first);
179 }
180 }
181 if points.len() > 1 {
182 polylines.push(points);
183 }
184 }
185 polylines
186 }
187}
188
189fn cubic_at(p0: Point, c1: Point, c2: Point, p3: Point, t: f64) -> Point {
190 let u = 1.0 - t;
191 let a = u * u * u;
192 let b = 3.0 * u * u * t;
193 let c = 3.0 * u * t * t;
194 let d = t * t * t;
195 Point::new(
196 a * p0.x + b * c1.x + c * c2.x + d * p3.x,
197 a * p0.y + b * c1.y + c * c2.y + d * p3.y,
198 )
199}
200
201pub fn dash_polyline(polyline: &[Point], dash: &Dash, ctm_scale: f64) -> Vec<Vec<Point>> {
207 if dash.is_solid() || polyline.len() < 2 {
208 return vec![polyline.to_vec()];
209 }
210 let pattern: Vec<f64> = dash
211 .pattern
212 .iter()
213 .map(|length| (length * ctm_scale).abs())
214 .filter(|length| *length > 1e-9)
215 .collect();
216 if pattern.is_empty() {
217 return vec![polyline.to_vec()];
218 }
219 let mut runs = Vec::new();
220 let mut current_run: Vec<Point> = Vec::new();
221 let mut index = 0usize;
223 let mut remaining = pattern[0];
224 let mut phase = dash.phase * ctm_scale;
225 while phase > 0.0 {
226 if phase >= remaining {
227 phase -= remaining;
228 index = (index + 1) % pattern.len();
229 remaining = pattern[index];
230 } else {
231 remaining -= phase;
232 phase = 0.0;
233 }
234 }
235 let mut on = index.is_multiple_of(2);
236 if on {
237 current_run.push(polyline[0]);
238 }
239 for window in polyline.windows(2) {
240 let mut start = window[0];
241 let end = window[1];
242 let dx = end.x - start.x;
243 let dy = end.y - start.y;
244 let length = (dx * dx + dy * dy).sqrt();
245 if length <= 1e-12 {
246 continue;
247 }
248 let unit_x = dx / length;
249 let unit_y = dy / length;
250 let mut travelled = 0.0;
251 while travelled < length {
252 let step = remaining.min(length - travelled);
253 let next = Point::new(start.x + unit_x * step, start.y + unit_y * step);
254 if on {
255 if current_run.is_empty() {
256 current_run.push(start);
257 }
258 current_run.push(next);
259 }
260 travelled += step;
261 remaining -= step;
262 if remaining <= 1e-9 {
263 if on && current_run.len() > 1 {
264 runs.push(std::mem::take(&mut current_run));
265 }
266 index = (index + 1) % pattern.len();
267 remaining = pattern[index];
268 on = index.is_multiple_of(2);
269 }
270 start = next;
271 }
272 }
273 if on && current_run.len() > 1 {
274 runs.push(current_run);
275 }
276 runs
277}
278
279pub fn stroke_outline(polylines: &[Vec<Point>], width: f64, cap: Cap) -> Vec<Vec<Point>> {
284 let half = (width / 2.0).max(0.0);
285 if half <= 0.0 {
286 return Vec::new();
287 }
288 let mut polygons = Vec::new();
289 for polyline in polylines {
290 if polyline.len() < 2 {
291 continue;
292 }
293 let last_index = polyline.len() - 2;
294 for (index, window) in polyline.windows(2).enumerate() {
295 let start = window[0];
296 let end = window[1];
297 let first = index == 0;
298 let last = index == last_index;
299 let (from, to) = if cap == Cap::Square {
302 (
303 if first {
304 extend(start, end, half)
305 } else {
306 start
307 },
308 if last { extend(end, start, half) } else { end },
309 )
310 } else {
311 (start, end)
312 };
313 let quad = segment_quad(from, to, half);
314 if quad.is_empty() {
315 continue;
316 }
317 polygons.push(oriented(quad));
318 if !first {
321 polygons.push(oriented(circle(start, half)));
322 }
323 if last && cap == Cap::Round {
324 polygons.push(oriented(circle(end, half)));
325 }
326 }
327 if cap == Cap::Round {
328 polygons.push(oriented(circle(polyline[0], half)));
329 }
330 }
331 polygons
332}
333
334fn extend(from: Point, towards: Point, distance: f64) -> Point {
336 let dx = towards.x - from.x;
337 let dy = towards.y - from.y;
338 let length = (dx * dx + dy * dy).sqrt();
339 if length <= 1e-12 {
340 return from;
341 }
342 Point::new(
343 from.x - dx / length * distance,
344 from.y - dy / length * distance,
345 )
346}
347
348fn segment_quad(start: Point, end: Point, half: f64) -> Vec<Point> {
349 let dx = end.x - start.x;
350 let dy = end.y - start.y;
351 let length = (dx * dx + dy * dy).sqrt();
352 if length <= 1e-12 {
353 return Vec::new();
354 }
355 let nx = -dy / length * half;
356 let ny = dx / length * half;
357 vec![
358 Point::new(start.x + nx, start.y + ny),
359 Point::new(end.x + nx, end.y + ny),
360 Point::new(end.x - nx, end.y - ny),
361 Point::new(start.x - nx, start.y - ny),
362 ]
363}
364
365pub fn circle(center: Point, radius: f64) -> Vec<Point> {
367 const SEGMENTS: usize = 16;
368 let mut points = Vec::with_capacity(SEGMENTS);
369 for step in 0..SEGMENTS {
370 let angle = step as f64 / SEGMENTS as f64 * std::f64::consts::TAU;
371 points.push(Point::new(
372 center.x + radius * angle.cos(),
373 center.y + radius * angle.sin(),
374 ));
375 }
376 points
377}
378
379fn oriented(mut polygon: Vec<Point>) -> Vec<Point> {
382 let area = signed_area(&polygon);
383 if area < 0.0 {
384 polygon.reverse();
385 }
386 polygon
387}
388
389fn signed_area(polygon: &[Point]) -> f64 {
390 let mut sum = 0.0;
391 for index in 0..polygon.len() {
392 let current = polygon[index];
393 let next = polygon[(index + 1) % polygon.len()];
394 sum += current.x * next.y - next.x * current.y;
395 }
396 sum / 2.0
397}
398
399#[cfg(test)]
400mod tests {
401 use super::{dash_polyline, stroke_outline, Cap, Dash, Path};
402 use crate::geom::{Matrix, Point};
403
404 #[test]
405 fn rectangles_flatten_to_closed_polylines() {
406 let mut path = Path::new();
407 path.add_rect(0.0, 0.0, 10.0, 20.0);
408 let polylines = path.flatten(Matrix::IDENTITY);
409 assert_eq!(polylines.len(), 1);
410 assert_eq!(polylines[0].len(), 5, "four corners plus the closing point");
411 assert_eq!(polylines[0][0], Point::new(0.0, 0.0));
412 assert_eq!(polylines[0][2], Point::new(10.0, 20.0));
413 }
414
415 #[test]
416 fn curves_are_subdivided() {
417 let mut path = Path::new();
418 path.move_to(Point::new(0.0, 0.0));
419 path.curve_to(
420 Point::new(0.0, 10.0),
421 Point::new(10.0, 10.0),
422 Point::new(10.0, 0.0),
423 );
424 let polylines = path.flatten(Matrix::IDENTITY);
425 assert_eq!(polylines[0].len(), 25);
426 assert_eq!(*polylines[0].last().expect("end"), Point::new(10.0, 0.0));
427 }
428
429 #[test]
430 fn a_solid_dash_keeps_the_polyline() {
431 let line = vec![Point::new(0.0, 0.0), Point::new(10.0, 0.0)];
432 let runs = dash_polyline(&line, &Dash::solid(), 1.0);
433 assert_eq!(runs.len(), 1);
434 assert_eq!(runs[0], line);
435 }
436
437 #[test]
438 fn a_dash_pattern_splits_the_line() {
439 let line = vec![Point::new(0.0, 0.0), Point::new(20.0, 0.0)];
440 let dash = Dash {
441 pattern: vec![5.0, 5.0],
442 phase: 0.0,
443 };
444 let runs = dash_polyline(&line, &dash, 1.0);
445 assert_eq!(runs.len(), 2);
446 assert_eq!(runs[0], vec![Point::new(0.0, 0.0), Point::new(5.0, 0.0)]);
447 assert_eq!(runs[1], vec![Point::new(10.0, 0.0), Point::new(15.0, 0.0)]);
448 }
449
450 #[test]
451 fn a_phase_offsets_the_first_run() {
452 let line = vec![Point::new(0.0, 0.0), Point::new(20.0, 0.0)];
453 let dash = Dash {
454 pattern: vec![5.0, 5.0],
455 phase: 2.0,
456 };
457 let runs = dash_polyline(&line, &dash, 1.0);
458 assert_eq!(runs[0][0], Point::new(0.0, 0.0));
459 assert_eq!(runs[0][1], Point::new(3.0, 0.0));
460 }
461
462 #[test]
463 fn strokes_become_polygons_around_the_line() {
464 let line = vec![Point::new(10.0, 10.0), Point::new(30.0, 10.0)];
465 let polygons = stroke_outline(&[line], 4.0, Cap::Butt);
466 assert!(!polygons.is_empty());
467 for polygon in &polygons {
469 assert!(super::signed_area(polygon) >= 0.0);
470 }
471 let quad = &polygons[0];
473 let min_y = quad.iter().fold(f64::MAX, |min, point| min.min(point.y));
474 let max_y = quad.iter().fold(f64::MIN, |max, point| max.max(point.y));
475 assert!((min_y - 8.0).abs() < 1e-9, "{min_y}");
476 assert!((max_y - 12.0).abs() < 1e-9, "{max_y}");
477 }
478}