Skip to main content

font_model/
outline.rs

1//! Resolved outlines: [`Command`], [`Path`], [`Outline`], and [`Bbox`].
2//!
3//! An [`Outline`] is the *resolved* form a renderer or writer consumes: a
4//! vector of closed [`Path`]s, every segment absolute, in font units. Nothing
5//! here is curve-type specific — a quadratic and a cubic segment sit in the
6//! same enum, so a `glyf` (quadratic) outline and a CFF (cubic) outline both
7//! land in the same shape.
8//!
9//! # Exactness
10//!
11//! Two things in this module are computed *exactly*, not approximated by
12//! flattening:
13//!
14//! - [`Bbox`] solves each curve's derivative for its axis extrema, so the box
15//!   contains the curve and not merely its control hull.
16//! - [`Path::signed_area`] integrates `x dy − y dx` in the Bézier's power
17//!   basis, so a circle's area comes out as the circle's area.
18//!
19//! Both properties are what a rasterizer's bounds check and a writer's area
20//! heuristic depend on.
21//!
22//! # Winding
23//!
24//! [`Path::winding`] names the sign of the signed area. Positive is
25//! counter-clockwise in a y-up system. TrueType's outer contours run
26//! clockwise in font units, so a typical `'O'` reports [`Winding::Clockwise`].
27//!
28//! ```
29//! use font_model::{Path, Winding};
30//!
31//! // A unit square, counter-clockwise in y-up.
32//! let mut p = Path::starting_at(0.0, 0.0);
33//! p.line_to(1.0, 0.0);
34//! p.line_to(1.0, 1.0);
35//! p.line_to(0.0, 1.0);
36//! p.close();
37//!
38//! assert!((p.signed_area() - 1.0).abs() < 1e-6);
39//! assert_eq!(p.winding(), Winding::CounterClockwise);
40//!
41//! // Relative and absolute construction agree exactly.
42//! let mut r = Path::starting_at(0.0, 0.0);
43//! r.line_by(1.0, 0.0);
44//! r.line_by(0.0, 1.0);
45//! r.line_by(-1.0, 0.0);
46//! r.close();
47//! assert_eq!(r.commands(), p.commands());
48//! ```
49
50use alloc::vec;
51use alloc::vec::Vec;
52
53/// One resolved path segment, absolute.
54#[derive(Debug, Clone, Copy, PartialEq)]
55pub enum Command {
56    /// Start a new subpath at this point.
57    MoveTo(f32, f32),
58    /// Straight segment to this point.
59    LineTo(f32, f32),
60    /// Quadratic segment: control point, then the on-curve endpoint.
61    QuadTo(f32, f32, f32, f32),
62    /// Cubic segment: two control points, then the on-curve endpoint.
63    CubicTo(f32, f32, f32, f32, f32, f32),
64    /// Close the current subpath. The line back to the subpath start is
65    /// *implicit*: the stored command list gains no synthetic `LineTo`, but
66    /// [`Path::area`], [`Path::bbox`], and every consumer of a
67    /// [`Path`] account for it.
68    Close,
69}
70
71impl Command {
72    /// The on-curve point this command ends at (`None` for
73    /// [`Command::Close`]).
74    #[must_use]
75    pub fn end_point(&self) -> Option<(f32, f32)> {
76        match *self {
77            Command::MoveTo(x, y) | Command::LineTo(x, y) => Some((x, y)),
78            Command::QuadTo(_, _, x, y) | Command::CubicTo(_, _, _, _, x, y) => Some((x, y)),
79            Command::Close => None,
80        }
81    }
82
83    /// [`Command::MoveTo`] as a standalone command.
84    #[must_use]
85    pub const fn move_to(x: f32, y: f32) -> Self {
86        Command::MoveTo(x, y)
87    }
88
89    /// [`Command::LineTo`] as a standalone command.
90    #[must_use]
91    pub const fn line_to(x: f32, y: f32) -> Self {
92        Command::LineTo(x, y)
93    }
94
95    /// [`Command::QuadTo`] as a standalone command.
96    #[must_use]
97    pub const fn quad_to(cx: f32, cy: f32, x: f32, y: f32) -> Self {
98        Command::QuadTo(cx, cy, x, y)
99    }
100
101    /// [`Command::CubicTo`] as a standalone command.
102    #[must_use]
103    #[allow(clippy::too_many_arguments)]
104    pub const fn cubic_to(c1x: f32, c1y: f32, c2x: f32, c2y: f32, x: f32, y: f32) -> Self {
105        Command::CubicTo(c1x, c1y, c2x, c2y, x, y)
106    }
107
108    /// [`Command::Close`] as a standalone command.
109    #[must_use]
110    pub const fn close() -> Self {
111        Command::Close
112    }
113
114    /// Rewrite this command as deltas from `current`, the point the segment
115    /// starts at: `(opcode, [dx, dy, dx2, dy2])`.
116    ///
117    /// The model stores absolute commands; this is the relative view a writer
118    /// emits for delta-encoded contours. The array holds
119    /// `[dx, dy, dx2, dy2, dx3, dy3]` — control points and endpoint, each as a
120    /// delta from `current`; unused trailing slots are zero. Opcodes: 0 move,
121    /// 1 line, 2 quad, 3 cubic, 4 close.
122    #[must_use]
123    pub fn relative_to(&self, current: (f32, f32)) -> (u8, [f32; 6]) {
124        let (cx, cy) = current;
125        match *self {
126            Command::MoveTo(x, y) => (0, [x - cx, y - cy, 0.0, 0.0, 0.0, 0.0]),
127            Command::LineTo(x, y) => (1, [x - cx, y - cy, 0.0, 0.0, 0.0, 0.0]),
128            Command::QuadTo(c1x, c1y, x, y) => (2, [c1x - cx, c1y - cy, x - cx, y - cy, 0.0, 0.0]),
129            Command::CubicTo(c1x, c1y, c2x, c2y, x, y) => {
130                (3, [c1x - cx, c1y - cy, c2x - cx, c2y - cy, x - cx, y - cy])
131            }
132            Command::Close => (4, [0.0; 6]),
133        }
134    }
135}
136
137/// An axis-aligned bounding box in font units.
138///
139/// The box is empty until a point is added; an empty box contains nothing and
140/// has zero extent.
141#[derive(Debug, Clone, Copy, PartialEq)]
142pub struct Bbox {
143    min_x: f32,
144    min_y: f32,
145    max_x: f32,
146    max_y: f32,
147}
148
149impl Default for Bbox {
150    fn default() -> Self {
151        Self::empty()
152    }
153}
154
155impl Bbox {
156    /// The empty box.
157    #[must_use]
158    pub const fn empty() -> Self {
159        Bbox {
160            min_x: f32::INFINITY,
161            min_y: f32::INFINITY,
162            max_x: f32::NEG_INFINITY,
163            max_y: f32::NEG_INFINITY,
164        }
165    }
166
167    /// A box spanning two corners, in any order.
168    #[must_use]
169    pub fn from_corners(x0: f32, y0: f32, x1: f32, y1: f32) -> Self {
170        Bbox {
171            min_x: if x0 < x1 { x0 } else { x1 },
172            min_y: if y0 < y1 { y0 } else { y1 },
173            max_x: if x0 > x1 { x0 } else { x1 },
174            max_y: if y0 > y1 { y0 } else { y1 },
175        }
176    }
177
178    /// The box of an arbitrary point set.
179    #[must_use]
180    pub fn from_points(points: impl IntoIterator<Item = (f32, f32)>) -> Self {
181        let mut b = Bbox::empty();
182        for (x, y) in points {
183            b.extend(x, y);
184        }
185        b
186    }
187
188    /// Grow the box to include a point.
189    pub fn extend(&mut self, x: f32, y: f32) {
190        if x < self.min_x {
191            self.min_x = x;
192        }
193        if y < self.min_y {
194            self.min_y = y;
195        }
196        if x > self.max_x {
197            self.max_x = x;
198        }
199        if y > self.max_y {
200            self.max_y = y;
201        }
202    }
203
204    /// Grow the box to include `other` (a no-op for an empty `other`).
205    pub fn union(&mut self, other: &Bbox) {
206        if other.is_empty() {
207            return;
208        }
209        self.extend(other.min_x, other.min_y);
210        self.extend(other.max_x, other.max_y);
211    }
212
213    /// True when no point has been added.
214    #[must_use]
215    pub const fn is_empty(&self) -> bool {
216        self.min_x > self.max_x
217    }
218
219    /// Minimum x (`f32::INFINITY` when empty).
220    #[must_use]
221    pub const fn min_x(&self) -> f32 {
222        self.min_x
223    }
224
225    /// Minimum y (`f32::INFINITY` when empty).
226    #[must_use]
227    pub const fn min_y(&self) -> f32 {
228        self.min_y
229    }
230
231    /// Maximum x (`f32::NEG_INFINITY` when empty).
232    #[must_use]
233    pub const fn max_x(&self) -> f32 {
234        self.max_x
235    }
236
237    /// Maximum y (`f32::NEG_INFINITY` when empty).
238    #[must_use]
239    pub const fn max_y(&self) -> f32 {
240        self.max_y
241    }
242
243    /// Width; zero when empty.
244    #[must_use]
245    pub fn width(&self) -> f32 {
246        if self.is_empty() {
247            0.0
248        } else {
249            self.max_x - self.min_x
250        }
251    }
252
253    /// Height; zero when empty.
254    #[must_use]
255    pub fn height(&self) -> f32 {
256        if self.is_empty() {
257            0.0
258        } else {
259            self.max_y - self.min_y
260        }
261    }
262
263    /// True when the point is inside or on the boundary. An empty box
264    /// contains nothing.
265    #[must_use]
266    pub fn contains(&self, x: f32, y: f32) -> bool {
267        !self.is_empty() && x >= self.min_x && x <= self.max_x && y >= self.min_y && y <= self.max_y
268    }
269
270    /// Translate the box (an empty box stays empty).
271    #[must_use]
272    pub fn translated(&self, dx: f32, dy: f32) -> Bbox {
273        if self.is_empty() {
274            return Bbox::empty();
275        }
276        Bbox::from_corners(
277            self.min_x + dx,
278            self.min_y + dy,
279            self.max_x + dx,
280            self.max_y + dy,
281        )
282    }
283
284    /// The four corners, counter-clockwise from the minimum corner.
285    #[must_use]
286    pub fn corners(&self) -> [(f32, f32); 4] {
287        [
288            (self.min_x, self.min_y),
289            (self.max_x, self.min_y),
290            (self.max_x, self.max_y),
291            (self.min_x, self.max_y),
292        ]
293    }
294}
295
296/// Orientation of a closed path, by the sign of its signed area.
297#[derive(Debug, Clone, Copy, PartialEq, Eq)]
298pub enum Winding {
299    /// Positive signed area: counter-clockwise in a y-up system.
300    CounterClockwise,
301    /// Negative signed area: clockwise in a y-up system (TrueType's outer
302    /// contour direction).
303    Clockwise,
304    /// Zero signed area: a degenerate contour — a single point, a zero-area
305    /// sliver, or an open path with no drawn segments.
306    Degenerate,
307}
308
309/// One subpath: an ordered run of [`Command`]s with a cached current point.
310///
311/// Every `*_to` constructor is absolute; every `*_by` constructor is relative
312/// to the current point and resolves to the *identical* absolute command, so
313/// a path built either way compares equal.
314#[derive(Debug, Clone, Default, PartialEq)]
315pub struct Path {
316    commands: Vec<Command>,
317    start: (f32, f32),
318    current: (f32, f32),
319}
320
321impl Path {
322    /// An empty path.
323    #[must_use]
324    pub fn new() -> Self {
325        Path {
326            commands: Vec::new(),
327            start: (0.0, 0.0),
328            current: (0.0, 0.0),
329        }
330    }
331
332    /// A path holding a single `MoveTo` — the usual first call.
333    #[must_use]
334    pub fn starting_at(x: f32, y: f32) -> Self {
335        let mut p = Path::new();
336        p.move_to(x, y);
337        p
338    }
339
340    /// The commands, in order.
341    #[must_use]
342    pub fn commands(&self) -> &[Command] {
343        &self.commands
344    }
345
346    /// Number of commands.
347    #[must_use]
348    pub fn len(&self) -> usize {
349        self.commands.len()
350    }
351
352    /// True when the path holds no commands.
353    #[must_use]
354    pub fn is_empty(&self) -> bool {
355        self.commands.is_empty()
356    }
357
358    /// The current point: the end of the last on-curve command, the subpath
359    /// start after a `Close`, or `(0, 0)` for an empty path.
360    #[must_use]
361    pub const fn current_point(&self) -> (f32, f32) {
362        self.current
363    }
364
365    /// The start of the current subpath.
366    #[must_use]
367    pub const fn start_point(&self) -> (f32, f32) {
368        self.start
369    }
370
371    /// Absolute `MoveTo`, starting a new subpath.
372    pub fn move_to(&mut self, x: f32, y: f32) -> &mut Self {
373        self.start = (x, y);
374        self.current = (x, y);
375        self.commands.push(Command::MoveTo(x, y));
376        self
377    }
378
379    /// Relative `MoveTo`.
380    pub fn move_by(&mut self, dx: f32, dy: f32) -> &mut Self {
381        let (x, y) = self.current;
382        self.move_to(x + dx, y + dy)
383    }
384
385    /// Absolute `LineTo`.
386    pub fn line_to(&mut self, x: f32, y: f32) -> &mut Self {
387        self.current = (x, y);
388        self.commands.push(Command::LineTo(x, y));
389        self
390    }
391
392    /// Relative `LineTo`.
393    pub fn line_by(&mut self, dx: f32, dy: f32) -> &mut Self {
394        let (x, y) = self.current;
395        self.line_to(x + dx, y + dy)
396    }
397
398    /// Absolute `QuadTo`.
399    pub fn quad_to(&mut self, cx: f32, cy: f32, x: f32, y: f32) -> &mut Self {
400        self.current = (x, y);
401        self.commands.push(Command::QuadTo(cx, cy, x, y));
402        self
403    }
404
405    /// Relative `QuadTo`: control point and endpoint both relative to the
406    /// current point.
407    pub fn quad_by(&mut self, dcx: f32, dcy: f32, dx: f32, dy: f32) -> &mut Self {
408        let (x, y) = self.current;
409        self.quad_to(x + dcx, y + dcy, x + dx, y + dy)
410    }
411
412    /// Absolute `CubicTo`.
413    pub fn cubic_to(
414        &mut self,
415        c1x: f32,
416        c1y: f32,
417        c2x: f32,
418        c2y: f32,
419        x: f32,
420        y: f32,
421    ) -> &mut Self {
422        self.current = (x, y);
423        self.commands
424            .push(Command::CubicTo(c1x, c1y, c2x, c2y, x, y));
425        self
426    }
427
428    /// Relative `CubicTo`: both control points and the endpoint relative to
429    /// the current point.
430    #[allow(clippy::too_many_arguments)]
431    pub fn cubic_by(
432        &mut self,
433        dc1x: f32,
434        dc1y: f32,
435        dc2x: f32,
436        dc2y: f32,
437        dx: f32,
438        dy: f32,
439    ) -> &mut Self {
440        let (x, y) = self.current;
441        self.cubic_to(x + dc1x, y + dc1y, x + dc2x, y + dc2y, x + dx, y + dy)
442    }
443
444    /// `Close`: append the explicit `Close` command and reset the current
445    /// point to the subpath start.
446    pub fn close(&mut self) -> &mut Self {
447        self.commands.push(Command::Close);
448        self.current = self.start;
449        self
450    }
451
452    /// Drop the trailing `Close`, leaving the subpath open. `None` when the
453    /// path was not closed.
454    pub fn open(&mut self) -> Option<Command> {
455        if !self.is_closed() {
456            return None;
457        }
458        let popped = self.commands.pop();
459        self.recache();
460        popped
461    }
462
463    /// Truncate to `len` commands. `None` when `len` exceeds the length.
464    ///
465    /// The cached current point and subpath start are recomputed, so the path
466    /// stays internally consistent.
467    pub fn truncate(&mut self, len: usize) -> Option<()> {
468        if len > self.commands.len() {
469            return None;
470        }
471        self.commands.truncate(len);
472        self.recache();
473        Some(())
474    }
475
476    /// Append a raw command, keeping the cached current point in step.
477    pub fn push(&mut self, cmd: Command) -> &mut Self {
478        match cmd {
479            Command::MoveTo(x, y) => {
480                self.move_to(x, y);
481            }
482            Command::LineTo(x, y) => {
483                self.line_to(x, y);
484            }
485            Command::QuadTo(cx, cy, x, y) => {
486                self.quad_to(cx, cy, x, y);
487            }
488            Command::CubicTo(c1x, c1y, c2x, c2y, x, y) => {
489                self.cubic_to(c1x, c1y, c2x, c2y, x, y);
490            }
491            Command::Close => {
492                self.close();
493            }
494        }
495        self
496    }
497
498    /// True when the path ends with an explicit `Close`.
499    #[must_use]
500    pub fn is_closed(&self) -> bool {
501        matches!(self.commands.last(), Some(Command::Close))
502    }
503
504    /// Close the path unless it is empty or already closed. Idempotent.
505    pub fn ensure_closed(&mut self) -> &mut Self {
506        if !self.commands.is_empty() && !self.is_closed() {
507            self.close();
508        }
509        self
510    }
511
512    /// Exact bounding box: line endpoints plus the true interior extrema of
513    /// every quadratic and cubic. `None` for a path with no points.
514    ///
515    /// ```
516    /// use font_model::Path;
517    ///
518    /// // A cubic from (0,0) through controls (3,0) (3,3) to (0,3): the exact
519    /// // box reaches well inside the control hull's x = 3.
520    /// let mut p = Path::starting_at(0.0, 0.0);
521    /// p.cubic_to(3.0, 0.0, 3.0, 3.0, 0.0, 3.0);
522    /// p.close();
523    /// let b = p.bbox().expect("non-empty");
524    /// assert!(b.max_x() < 3.0);
525    ///
526    /// // The known extreme of this cubic: x peaks at 2.25.
527    /// assert!((b.max_x() - 2.25).abs() < 1e-5, "max_x {}", b.max_x());
528    /// ```
529    #[must_use]
530    pub fn bbox(&self) -> Option<Bbox> {
531        let mut b = Bbox::empty();
532        let mut cur = (0.0, 0.0);
533        let mut start = (0.0, 0.0);
534        let mut any = false;
535        for cmd in &self.commands {
536            match *cmd {
537                Command::MoveTo(x, y) => {
538                    b.extend(x, y);
539                    cur = (x, y);
540                    start = cur;
541                    any = true;
542                }
543                Command::LineTo(x, y) => {
544                    b.extend(x, y);
545                    cur = (x, y);
546                    any = true;
547                }
548                Command::QuadTo(cx, cy, x, y) => {
549                    let p = [(cur.0, cur.1), (cx, cy), (x, y)];
550                    b.extend(x, y);
551                    // Each axis has its own interior extremum, at its own `t`.
552                    for t in quad_derivative_roots(p[0].0, p[1].0, p[2].0) {
553                        b.extend(quad_at_x(p, t), quad_at_y(p, t));
554                    }
555                    for t in quad_derivative_roots(p[0].1, p[1].1, p[2].1) {
556                        b.extend(quad_at_x(p, t), quad_at_y(p, t));
557                    }
558                    cur = (x, y);
559                    any = true;
560                }
561                Command::CubicTo(c1x, c1y, c2x, c2y, x, y) => {
562                    let p = [(cur.0, cur.1), (c1x, c1y), (c2x, c2y), (x, y)];
563                    b.extend(x, y);
564                    // Each axis has its own interior extrema, at its own `t`.
565                    for t in cubic_derivative_roots(p[0].0, p[1].0, p[2].0, p[3].0) {
566                        b.extend(cubic_at_x(p, t), cubic_at_y(p, t));
567                    }
568                    for t in cubic_derivative_roots(p[0].1, p[1].1, p[2].1, p[3].1) {
569                        b.extend(cubic_at_x(p, t), cubic_at_y(p, t));
570                    }
571                    cur = (x, y);
572                    any = true;
573                }
574                Command::Close => {
575                    cur = start;
576                    any = true;
577                }
578            }
579        }
580        if any {
581            Some(b)
582        } else {
583            None
584        }
585    }
586
587    /// Signed area of the path in square font units, treating every subpath
588    /// as closed. Curves contribute their exact analytic integral, so this is
589    /// not a flattened approximation.
590    #[must_use]
591    pub fn signed_area(&self) -> f32 {
592        let mut acc = 0.0f32;
593        for seg in self.subpaths() {
594            acc += seg.signed_area();
595        }
596        acc
597    }
598
599    /// Unsigned area.
600    #[must_use]
601    pub fn area(&self) -> f32 {
602        crate::num::abs(self.signed_area())
603    }
604
605    /// Orientation by signed-area sign.
606    #[must_use]
607    pub fn winding(&self) -> Winding {
608        let a = self.signed_area();
609        if a > 0.0 {
610            Winding::CounterClockwise
611        } else if a < 0.0 {
612            Winding::Clockwise
613        } else {
614            Winding::Degenerate
615        }
616    }
617
618    /// Reverse the direction of every subpath, keeping the same geometry.
619    /// The way to normalise a mixed-direction contour set.
620    pub fn reverse(&mut self) {
621        let subpaths = self.subpaths();
622        let mut out: Vec<Command> = Vec::with_capacity(self.commands.len());
623        for seg in &subpaths {
624            if seg.points.len() < 2 {
625                continue;
626            }
627            if seg.segments.is_empty() {
628                continue;
629            }
630            // Original segment `i` runs `points[i] → points[i + 1]`, so its
631            // reversal runs `points[i + 1] → points[i]` and the reversed
632            // subpath begins at the last drawn point.
633            let start = *seg.points.first().unwrap_or(&(0.0, 0.0));
634            let begin = seg.segments.last().map_or(start, |s| s.to());
635            out.push(Command::MoveTo(begin.0, begin.1));
636            for (i, s) in seg.segments.iter().enumerate().rev() {
637                let to = match i.checked_sub(1).and_then(|k| seg.segments.get(k)) {
638                    Some(prev) => prev.to(),
639                    None => start,
640                };
641                match *s {
642                    Segment::Line { .. } => out.push(Command::LineTo(to.0, to.1)),
643                    Segment::Quad { c, .. } => out.push(Command::QuadTo(c.0, c.1, to.0, to.1)),
644                    Segment::Cubic { c1, c2, .. } => {
645                        out.push(Command::CubicTo(c2.0, c2.1, c1.0, c1.1, to.0, to.1));
646                    }
647                }
648            }
649            if seg.closed {
650                out.push(Command::Close);
651            }
652        }
653        self.commands = out;
654        self.recache();
655    }
656
657    /// Every on-curve and control point, in command order.
658    pub fn points(&self) -> Vec<(f32, f32)> {
659        let mut out = Vec::new();
660        for cmd in &self.commands {
661            match *cmd {
662                Command::MoveTo(x, y) | Command::LineTo(x, y) => out.push((x, y)),
663                Command::QuadTo(cx, cy, x, y) => {
664                    out.push((cx, cy));
665                    out.push((x, y));
666                }
667                Command::CubicTo(c1x, c1y, c2x, c2y, x, y) => {
668                    out.push((c1x, c1y));
669                    out.push((c2x, c2y));
670                    out.push((x, y));
671                }
672                Command::Close => {}
673            }
674        }
675        out
676    }
677
678    /// The path split into its subpaths, each with its on-curve points and
679    /// segments in order. Each subpath's point list repeats its start at the
680    /// end when closed.
681    #[must_use]
682    pub fn subpaths(&self) -> Vec<Subpath> {
683        let mut out: Vec<Subpath> = Vec::new();
684        let mut cur: Option<Subpath> = None;
685        let mut pt = (0.0f32, 0.0f32);
686        for cmd in &self.commands {
687            match *cmd {
688                Command::MoveTo(x, y) => {
689                    if let Some(sp) = cur.take() {
690                        out.push(sp);
691                    }
692                    pt = (x, y);
693                    cur = Some(Subpath {
694                        points: vec![pt],
695                        segments: Vec::new(),
696                        closed: false,
697                    });
698                }
699                Command::LineTo(x, y) => {
700                    if let Some(sp) = cur.as_mut() {
701                        sp.segments.push(Segment::Line { to: (x, y) });
702                        sp.points.push((x, y));
703                    }
704                    pt = (x, y);
705                }
706                Command::QuadTo(cx, cy, x, y) => {
707                    if let Some(sp) = cur.as_mut() {
708                        sp.segments.push(Segment::Quad {
709                            c: (cx, cy),
710                            to: (x, y),
711                        });
712                        sp.points.push((x, y));
713                    }
714                    pt = (x, y);
715                }
716                Command::CubicTo(c1x, c1y, c2x, c2y, x, y) => {
717                    if let Some(sp) = cur.as_mut() {
718                        sp.segments.push(Segment::Cubic {
719                            c1: (c1x, c1y),
720                            c2: (c2x, c2y),
721                            to: (x, y),
722                        });
723                        sp.points.push((x, y));
724                    }
725                    pt = (x, y);
726                }
727                Command::Close => {
728                    if let Some(mut sp) = cur.take() {
729                        sp.closed = true;
730                        let start = sp.points.first().copied().unwrap_or(pt);
731                        sp.points.push(start);
732                        out.push(sp);
733                    }
734                }
735            }
736        }
737        // An unterminated subpath keeps its points as drawn: no repeated
738        // start. Its implicit closing line is accounted for by
739        // [`Subpath::signed_area`], not by a duplicate point.
740        if let Some(sp) = cur.take() {
741            out.push(sp);
742        }
743        out
744    }
745
746    /// Recompute the cached current point and subpath start from the
747    /// command list. Called after a bulk rewrite of `commands`.
748    fn recache(&mut self) {
749        self.current = (0.0, 0.0);
750        self.start = (0.0, 0.0);
751        for cmd in &self.commands {
752            match *cmd {
753                Command::MoveTo(x, y) => {
754                    self.start = (x, y);
755                    self.current = (x, y);
756                }
757                cmd => {
758                    if let Some(p) = cmd.end_point() {
759                        self.current = p;
760                    } else if matches!(cmd, Command::Close) {
761                        self.current = self.start;
762                    }
763                }
764            }
765        }
766    }
767}
768
769/// One drawing segment of a decomposed [`Subpath`].
770///
771/// `to` is the segment's **endpoint**; its start point is the previous
772/// segment's endpoint, or the subpath's first point.
773#[derive(Debug, Clone, Copy, PartialEq)]
774enum Segment {
775    Line {
776        /// Endpoint.
777        to: (f32, f32),
778    },
779    Quad {
780        /// Control point.
781        c: (f32, f32),
782        /// Endpoint.
783        to: (f32, f32),
784    },
785    Cubic {
786        /// First control point.
787        c1: (f32, f32),
788        /// Second control point.
789        c2: (f32, f32),
790        /// Endpoint.
791        to: (f32, f32),
792    },
793}
794
795impl Segment {
796    /// The segment's endpoint.
797    fn to(&self) -> (f32, f32) {
798        match *self {
799            Segment::Line { to } | Segment::Quad { to, .. } | Segment::Cubic { to, .. } => to,
800        }
801    }
802}
803
804/// One drawing segment, flattened for a consumer that wants the numbers
805/// rather than the curve type.
806///
807/// `kind` is 1 line, 2 quad, 3 cubic. Unused control slots hold `(0.0, 0.0)`.
808#[derive(Debug, Clone, Copy, PartialEq)]
809pub struct FlatSegment {
810    /// 1 line, 2 quad, 3 cubic.
811    pub kind: u8,
812    /// First control point, `(0.0, 0.0)` for a line.
813    pub c1: (f32, f32),
814    /// Second control point, `(0.0, 0.0)` unless this is a cubic.
815    pub c2: (f32, f32),
816    /// The segment's endpoint.
817    pub to: (f32, f32),
818}
819
820/// One subpath decomposed into on-curve points and segments.
821#[derive(Debug, Clone, PartialEq)]
822pub struct Subpath {
823    /// On-curve points: the start, each segment endpoint, and (when closed)
824    /// a repeat of the start.
825    pub points: Vec<(f32, f32)>,
826    /// The drawing segments, in order.
827    segments: Vec<Segment>,
828    /// True when the subpath ended with an explicit `Close`.
829    pub closed: bool,
830}
831
832impl Subpath {
833    /// Number of drawing segments.
834    #[must_use]
835    pub fn segment_count(&self) -> usize {
836        self.segments.len()
837    }
838
839    /// The drawing segments, in order, as `(kind, c1, c2, to)` with `kind`:
840    /// 1 line, 2 quad, 3 cubic. Control slots are `(0.0, 0.0)` when unused.
841    ///
842    /// ```
843    /// use font_model::{Path, Winding};
844    ///
845    /// // A square: four line segments, no controls.
846    /// let mut p = Path::starting_at(0.0, 0.0);
847    /// p.line_to(1.0, 0.0);
848    /// p.line_to(1.0, 1.0);
849    /// p.line_to(0.0, 1.0);
850    /// p.close();
851    /// let subs = p.subpaths();
852    /// assert_eq!(subs.len(), 1);
853    /// assert_eq!(subs[0].segment_count(), 3);
854    /// ```
855    #[must_use]
856    pub fn segments(&self) -> Vec<FlatSegment> {
857        self.segments
858            .iter()
859            .map(|s| match *s {
860                Segment::Line { to } => FlatSegment {
861                    kind: 1,
862                    c1: (0.0, 0.0),
863                    c2: (0.0, 0.0),
864                    to,
865                },
866                Segment::Quad { c, to } => FlatSegment {
867                    kind: 2,
868                    c1: c,
869                    c2: (0.0, 0.0),
870                    to,
871                },
872                Segment::Cubic { c1, c2, to } => FlatSegment {
873                    kind: 3,
874                    c1,
875                    c2,
876                    to,
877                },
878            })
879            .collect()
880    }
881
882    /// Signed area: each segment's exact analytic contribution plus the
883    /// closing line when the subpath is open but has drawn segments.
884    #[must_use]
885    pub fn signed_area(&self) -> f32 {
886        let Some(start) = self.points.first() else {
887            return 0.0;
888        };
889        let mut from = *start;
890        let mut acc = 0.0f32;
891        for seg in &self.segments {
892            acc += segment_area(from, seg);
893            from = seg.to();
894        }
895        // Implicit closing line back to the start.
896        if !self.points.is_empty() {
897            acc += cross(from, *start);
898        }
899        acc * 0.5
900    }
901
902    /// Exact bounding box over the subpath, `None` when it has no points.
903    #[must_use]
904    pub fn bbox(&self) -> Option<Bbox> {
905        let mut b = Bbox::empty();
906        for p in &self.points {
907            b.extend(p.0, p.1);
908        }
909        let mut from = self.points.first().copied().unwrap_or((0.0, 0.0));
910        for seg in &self.segments {
911            match *seg {
912                Segment::Line { .. } => {}
913                Segment::Quad { c, to } => {
914                    let p = [from, c, to];
915                    for t in quad_derivative_roots(p[0].0, p[1].0, p[2].0) {
916                        b.extend(quad_at_x(p, t), quad_at_y(p, t));
917                    }
918                    for t in quad_derivative_roots(p[0].1, p[1].1, p[2].1) {
919                        b.extend(quad_at_x(p, t), quad_at_y(p, t));
920                    }
921                }
922                Segment::Cubic { c1, c2, to } => {
923                    let p = [from, c1, c2, to];
924                    for t in cubic_derivative_roots(p[0].0, p[1].0, p[2].0, p[3].0) {
925                        b.extend(cubic_at_x(p, t), cubic_at_y(p, t));
926                    }
927                    for t in cubic_derivative_roots(p[0].1, p[1].1, p[2].1, p[3].1) {
928                        b.extend(cubic_at_x(p, t), cubic_at_y(p, t));
929                    }
930                }
931            }
932            from = seg.to();
933        }
934        if b.is_empty() {
935            None
936        } else {
937            Some(b)
938        }
939    }
940}
941
942/// A glyph's resolved outline: contours in font units.
943///
944/// The model stores contours *closed* — [`Outline::push_contour`] closes what
945/// it is handed, and [`Outline::validate`] is what proves it.
946#[derive(Debug, Clone, Default, PartialEq)]
947pub struct Outline {
948    contours: Vec<Path>,
949}
950
951impl Outline {
952    /// An empty outline (a space-like glyph).
953    #[must_use]
954    pub fn new() -> Self {
955        Outline {
956            contours: Vec::new(),
957        }
958    }
959
960    /// The contours.
961    #[must_use]
962    pub fn contours(&self) -> &[Path] {
963        &self.contours
964    }
965
966    /// The contours, mutably — for an editor reshaping a glyph.
967    pub fn contours_mut(&mut self) -> &mut Vec<Path> {
968        &mut self.contours
969    }
970
971    /// Add a contour, closing it first if needed.
972    pub fn push_contour(&mut self, path: Path) -> &mut Self {
973        let mut path = path;
974        path.ensure_closed();
975        self.contours.push(path);
976        self
977    }
978
979    /// Number of contours.
980    #[must_use]
981    pub fn len(&self) -> usize {
982        self.contours.len()
983    }
984
985    /// True when the outline has no contours.
986    #[must_use]
987    pub fn is_empty(&self) -> bool {
988        self.contours.is_empty()
989    }
990
991    /// Number of on-curve and control points across every contour.
992    #[must_use]
993    pub fn point_count(&self) -> usize {
994        self.contours.iter().map(Path::len).sum()
995    }
996
997    /// Exact bounding box over every contour, `None` when there are none.
998    #[must_use]
999    pub fn bbox(&self) -> Option<Bbox> {
1000        let mut b = Bbox::empty();
1001        for c in &self.contours {
1002            for sp in c.subpaths() {
1003                if let Some(sb) = sp.bbox() {
1004                    b.union(&sb);
1005                }
1006            }
1007        }
1008        if b.is_empty() {
1009            None
1010        } else {
1011            Some(b)
1012        }
1013    }
1014
1015    /// Total unsigned area: outer contours and holes alike.
1016    #[must_use]
1017    pub fn area(&self) -> f32 {
1018        self.contours.iter().map(Path::area).sum()
1019    }
1020
1021    /// Net signed area: outer contours minus holes when the holes run the
1022    /// other way.
1023    #[must_use]
1024    pub fn signed_area(&self) -> f32 {
1025        self.contours.iter().map(Path::signed_area).sum()
1026    }
1027
1028    /// Validate the outline against the model invariants: every contour
1029    /// closed, every coordinate finite.
1030    ///
1031    /// # Errors
1032    /// [`ModelError::UnclosedContour`] naming the contour index, or
1033    /// [`ModelError::NonFiniteCoordinate`] naming the contour, command index,
1034    /// and field (`"x"`, `"control1.y"`, …).
1035    ///
1036    /// [`ModelError::UnclosedContour`]: crate::ModelError::UnclosedContour
1037    /// [`ModelError::NonFiniteCoordinate`]: crate::ModelError::NonFiniteCoordinate
1038    pub fn validate(&self, glyph: crate::GlyphId) -> Result<(), crate::ModelError> {
1039        use crate::ModelError;
1040        for (ci, contour) in self.contours.iter().enumerate() {
1041            if !contour.is_closed() {
1042                return Err(ModelError::UnclosedContour { glyph, contour: ci });
1043            }
1044            for (ki, cmd) in contour.commands().iter().enumerate() {
1045                let check = |x: f32, y: f32, xf: &'static str, yf: &'static str| {
1046                    if !x.is_finite() {
1047                        return Err(ModelError::NonFiniteCoordinate {
1048                            glyph,
1049                            contour: ci,
1050                            command: ki,
1051                            field: xf,
1052                        });
1053                    }
1054                    if !y.is_finite() {
1055                        return Err(ModelError::NonFiniteCoordinate {
1056                            glyph,
1057                            contour: ci,
1058                            command: ki,
1059                            field: yf,
1060                        });
1061                    }
1062                    Ok(())
1063                };
1064                match *cmd {
1065                    Command::MoveTo(x, y) | Command::LineTo(x, y) => check(x, y, "x", "y")?,
1066                    Command::QuadTo(cx, cy, x, y) => {
1067                        check(cx, cy, "control.x", "control.y")?;
1068                        check(x, y, "x", "y")?;
1069                    }
1070                    Command::CubicTo(c1x, c1y, c2x, c2y, x, y) => {
1071                        check(c1x, c1y, "control1.x", "control1.y")?;
1072                        check(c2x, c2y, "control2.x", "control2.y")?;
1073                        check(x, y, "x", "y")?;
1074                    }
1075                    Command::Close => {}
1076                }
1077            }
1078        }
1079        Ok(())
1080    }
1081}
1082
1083// -- exact curve helpers ---------------------------------------------------
1084
1085/// `cross(a, b)` = `a.x * b.y − a.y * b.x`.
1086fn cross(a: (f32, f32), b: (f32, f32)) -> f32 {
1087    a.0 * b.1 - a.1 * b.0
1088}
1089
1090/// Exact `∫₀¹ (x y′ − y x′) dt` contribution of one segment, via the
1091/// Bézier's power basis. Straight lines use the closed form `cross(p₀, p₁)`.
1092fn segment_area(from: (f32, f32), seg: &Segment) -> f32 {
1093    match *seg {
1094        Segment::Line { to } => cross(from, to),
1095        Segment::Quad { c, to } => {
1096            let xp = quadratic_power(from.0, c.0, to.0);
1097            let yp = quadratic_power(from.1, c.1, to.1);
1098            integrate_cross(&xp, &yp)
1099        }
1100        Segment::Cubic { c1, c2, to } => {
1101            let xp = cubic_power(from.0, c1.0, c2.0, to.0);
1102            let yp = cubic_power(from.1, c1.1, c2.1, to.1);
1103            integrate_cross(&xp, &yp)
1104        }
1105    }
1106}
1107
1108/// Power-basis coefficients of a quadratic Bézier, ascending in `t`.
1109fn quadratic_power(p0: f32, p1: f32, p2: f32) -> [f32; 3] {
1110    [p0, 2.0 * (p1 - p0), (p0 - 2.0 * p1 + p2)]
1111}
1112
1113/// Power-basis coefficients of a cubic Bézier, ascending in `t`.
1114fn cubic_power(p0: f32, p1: f32, p2: f32, p3: f32) -> [f32; 4] {
1115    [
1116        p0,
1117        3.0 * (p1 - p0),
1118        3.0 * (p0 - 2.0 * p1 + p2),
1119        (p3 - 3.0 * p2 + 3.0 * p1 - p0),
1120    ]
1121}
1122
1123/// Differentiate a power-basis polynomial (length shrinks by one).
1124fn derivative(p: &[f32]) -> Vec<f32> {
1125    p.iter()
1126        .enumerate()
1127        .skip(1)
1128        .map(|(i, c)| c * i as f32)
1129        .collect()
1130}
1131
1132/// Multiply two power-basis polynomials.
1133fn mul(a: &[f32], b: &[f32]) -> Vec<f32> {
1134    let mut out = vec![0.0f32; a.len() + b.len() - 1];
1135    for (i, &ai) in a.iter().enumerate() {
1136        for (j, &bj) in b.iter().enumerate() {
1137            if let Some(slot) = out.get_mut(i + j) {
1138                *slot += ai * bj;
1139            }
1140        }
1141    }
1142    out
1143}
1144
1145/// `∫₀¹ (x y′ − y x′) dt` for two power-basis polynomials.
1146fn integrate_cross(xp: &[f32], yp: &[f32]) -> f32 {
1147    let a = mul(xp, &derivative(yp));
1148    let b = mul(yp, &derivative(xp));
1149    let mut acc = 0.0f32;
1150    for (i, ca) in a.iter().enumerate() {
1151        let cb = b.get(i).copied().unwrap_or(0.0);
1152        let k = (i + 1) as f32;
1153        acc += (ca - cb) / k;
1154    }
1155    acc
1156}
1157
1158/// Quadratic x at `t`.
1159fn quad_at_x(p: [(f32, f32); 3], t: f32) -> f32 {
1160    let mt = 1.0 - t;
1161    mt * mt * p[0].0 + 2.0 * mt * t * p[1].0 + t * t * p[2].0
1162}
1163
1164/// Quadratic y at `t`.
1165fn quad_at_y(p: [(f32, f32); 3], t: f32) -> f32 {
1166    let mt = 1.0 - t;
1167    mt * mt * p[0].1 + 2.0 * mt * t * p[1].1 + t * t * p[2].1
1168}
1169
1170/// Interior roots of a quadratic Bézier's derivative on one axis — where the
1171/// curve itself reaches an axis extreme.
1172fn quad_derivative_roots(a0: f32, a1: f32, a2: f32) -> Vec<f32> {
1173    let qa = 2.0 * (a0 - 2.0 * a1 + a2);
1174    let qb = 2.0 * (a1 - a0);
1175    if crate::num::abs(qa) < 1e-9 {
1176        return Vec::new();
1177    }
1178    let t = -qb / qa;
1179    if t > 0.0 && t < 1.0 {
1180        vec![t]
1181    } else {
1182        Vec::new()
1183    }
1184}
1185
1186/// Cubic x at `t`.
1187fn cubic_at_x(p: [(f32, f32); 4], t: f32) -> f32 {
1188    let mt = 1.0 - t;
1189    mt * mt * mt * p[0].0
1190        + 3.0 * mt * mt * t * p[1].0
1191        + 3.0 * mt * t * t * p[2].0
1192        + t * t * t * p[3].0
1193}
1194
1195/// Cubic y at `t`.
1196fn cubic_at_y(p: [(f32, f32); 4], t: f32) -> f32 {
1197    let mt = 1.0 - t;
1198    mt * mt * mt * p[0].1
1199        + 3.0 * mt * mt * t * p[1].1
1200        + 3.0 * mt * t * t * p[2].1
1201        + t * t * t * p[3].1
1202}
1203
1204/// Interior roots of a cubic Bézier's derivative on one axis — the curve's
1205/// own axis extrema, exact rather than a control-hull bound.
1206fn cubic_derivative_roots(a0: f32, a1: f32, a2: f32, a3: f32) -> Vec<f32> {
1207    let qa = 3.0 * (-a0 + 3.0 * a1 - 3.0 * a2 + a3);
1208    let qb = 6.0 * (a0 - 2.0 * a1 + a2);
1209    let qc = 3.0 * (a1 - a0);
1210    let mut out = Vec::new();
1211    let mut push = |t: f32| {
1212        if t > 0.0 && t < 1.0 {
1213            out.push(t);
1214        }
1215    };
1216    if crate::num::abs(qa) < 1e-9 {
1217        if crate::num::abs(qb) >= 1e-9 {
1218            push(-qc / qb);
1219        }
1220        return out;
1221    }
1222    let disc = qb * qb - 4.0 * qa * qc;
1223    if disc >= 0.0 {
1224        let s = crate::num::sqrt(disc);
1225        push((-qb + s) / (2.0 * qa));
1226        push((-qb - s) / (2.0 * qa));
1227    }
1228    out
1229}
1230
1231#[cfg(test)]
1232mod tests {
1233    #![allow(
1234        clippy::unwrap_used,
1235        clippy::expect_used,
1236        clippy::indexing_slicing,
1237        clippy::panic,
1238        clippy::float_cmp
1239    )]
1240    use super::{Bbox, Command, Outline, Path, Subpath, Winding};
1241    use alloc::vec;
1242
1243    // Test harness: assertions legitimately panic; the lib target stays
1244    // lint-clean.
1245
1246    /// A 10×10 square starting at the origin, counter-clockwise.
1247    fn square() -> Path {
1248        let mut p = Path::starting_at(0.0, 0.0);
1249        p.line_to(10.0, 0.0);
1250        p.line_to(10.0, 10.0);
1251        p.line_to(0.0, 10.0);
1252        p.close();
1253        p
1254    }
1255
1256    #[test]
1257    fn bbox_of_lines() {
1258        let b = square().bbox().expect("bbox");
1259        assert_eq!((b.min_x(), b.min_y()), (0.0, 0.0));
1260        assert_eq!((b.max_x(), b.max_y()), (10.0, 10.0));
1261        assert_eq!(b.width(), 10.0);
1262        assert_eq!(b.height(), 10.0);
1263    }
1264
1265    #[test]
1266    fn bbox_cubic_holds_the_curve_not_the_hull() {
1267        // (0,0) → (3,0) → (3,3) → (0,3): x peaks at 2.25 inside the hull's 3.
1268        let mut p = Path::starting_at(0.0, 0.0);
1269        p.cubic_to(3.0, 0.0, 3.0, 3.0, 0.0, 3.0);
1270        p.close();
1271        let b = p.bbox().expect("bbox");
1272        assert!(b.max_x() < 3.0, "bbox {} includes the hull", b.max_x());
1273        assert!((b.max_x() - 2.25).abs() < 1e-4, "max_x {}", b.max_x());
1274        assert!((b.max_y() - 3.0).abs() < 1e-5);
1275    }
1276
1277    #[test]
1278    fn bbox_quadratic_interior_extremum() {
1279        // (0,0) → (2,4) → (4,0): max y = 2 at t = 0.5.
1280        let mut p = Path::starting_at(0.0, 0.0);
1281        p.quad_to(2.0, 4.0, 4.0, 0.0);
1282        p.close();
1283        let b = p.bbox().expect("bbox");
1284        assert!((b.max_y() - 2.0).abs() < 1e-5, "max_y {}", b.max_y());
1285        assert!((b.max_x() - 4.0).abs() < 1e-5, "max_x {}", b.max_x());
1286    }
1287
1288    #[test]
1289    fn bbox_contains_every_sampled_point() {
1290        let mut p = Path::starting_at(0.0, 0.0);
1291        p.cubic_to(3.0, -2.0, -4.0, 5.0, 1.0, 2.0);
1292        p.quad_to(2.0, 2.0, 0.0, 0.0);
1293        p.close();
1294        let b = p.bbox().expect("bbox");
1295        let a = [(0.0, 0.0), (3.0, -2.0), (-4.0, 5.0), (1.0, 2.0)];
1296        for i in 0..=200 {
1297            let t = i as f32 / 200.0;
1298            let mt = 1.0 - t;
1299            let x = mt * mt * mt * a[0].0
1300                + 3.0 * mt * mt * t * a[1].0
1301                + 3.0 * mt * t * t * a[2].0
1302                + t * t * t * a[3].0;
1303            let y = mt * mt * mt * a[0].1
1304                + 3.0 * mt * mt * t * a[1].1
1305                + 3.0 * mt * t * t * a[2].1
1306                + t * t * t * a[3].1;
1307            assert!(b.contains(x, y), "sample ({x}, {y}) outside {b:?}");
1308        }
1309    }
1310
1311    #[test]
1312    fn bbox_of_empty_and_point_only_paths() {
1313        assert!(Path::new().bbox().is_none());
1314        let mut p = Path::starting_at(1.0, 1.0);
1315        p.close();
1316        let b = p.bbox().expect("point bbox");
1317        assert_eq!(b.width(), 0.0);
1318    }
1319
1320    #[test]
1321    fn area_and_winding_sign() {
1322        let ccw = square();
1323        assert!((ccw.signed_area() - 100.0).abs() < 1e-3);
1324        assert_eq!(ccw.winding(), Winding::CounterClockwise);
1325        assert_eq!(ccw.area(), 100.0);
1326
1327        let mut cw = Path::starting_at(0.0, 0.0);
1328        cw.line_to(0.0, 10.0);
1329        cw.line_to(10.0, 10.0);
1330        cw.line_to(10.0, 0.0);
1331        cw.close();
1332        assert!((cw.signed_area() + 100.0).abs() < 1e-3);
1333        assert_eq!(cw.winding(), Winding::Clockwise);
1334        assert_eq!(cw.area(), 100.0);
1335    }
1336
1337    #[test]
1338    fn degenerate_winding() {
1339        let mut p = Path::starting_at(1.0, 1.0);
1340        p.close();
1341        assert_eq!(p.winding(), Winding::Degenerate);
1342        assert_eq!(p.area(), 0.0);
1343        let open = Path::starting_at(0.0, 0.0);
1344        assert_eq!(open.winding(), Winding::Degenerate);
1345    }
1346
1347    /// Four quadratics approximating the unit circle. A quadratic's control
1348    /// point is the *tangent intersection* (1, 1) — the 0.552 magic constant is
1349    /// a cubic one — so the shape is a coarse approximation and the area
1350    /// tolerance is correspondingly loose.
1351    fn quad_circle() -> Path {
1352        let mut c = Path::starting_at(1.0, 0.0);
1353        c.quad_to(1.0, 1.0, 0.0, 1.0);
1354        c.quad_to(-1.0, 1.0, -1.0, 0.0);
1355        c.quad_to(-1.0, -1.0, 0.0, -1.0);
1356        c.quad_to(1.0, -1.0, 1.0, 0.0);
1357        c.close();
1358        c
1359    }
1360
1361    /// Four cubic arcs approximating the unit circle, with the standard
1362    /// `4/3·tan(π/8)` control offset 0.55228475.
1363    fn cubic_circle() -> Path {
1364        let k = 0.552_284_8_f32;
1365        let mut c = Path::starting_at(1.0, 0.0);
1366        c.cubic_to(1.0, k, k, 1.0, 0.0, 1.0);
1367        c.cubic_to(-k, 1.0, -1.0, k, -1.0, 0.0);
1368        c.cubic_to(-1.0, -k, -k, -1.0, 0.0, -1.0);
1369        c.cubic_to(k, -1.0, 1.0, -k, 1.0, 0.0);
1370        c.close();
1371        c
1372    }
1373
1374    #[test]
1375    fn quadratic_circle_area_matches_its_own_polygon() {
1376        // Green's theorem, checked against the exact analytic value: for four
1377        // quadratics with control points at the tangent intersections, the
1378        // enclosed area is exactly 10/3 (the polygonal approximation of a
1379        // circle inscribed in the unit square's rotated twin), well above pi.
1380        let c = quad_circle();
1381        assert!(
1382            (c.signed_area() - 3.333_333_3).abs() < 1e-3,
1383            "quad circle area {}",
1384            c.signed_area()
1385        );
1386        assert_eq!(c.winding(), Winding::CounterClockwise);
1387        // And it is still close to the circle it approximates.
1388        assert!(
1389            (c.area() - core::f32::consts::PI).abs() < 0.2,
1390            "quad circle area {}",
1391            c.area()
1392        );
1393    }
1394
1395    #[test]
1396    fn cubic_circle_area_is_pi_to_1e_3() {
1397        // Four cubic arcs approximate the circle to ~3e-4 in area, so the
1398        // tolerance is set by the *approximation*, not the area integral — the
1399        // integral itself is exact for these curves.
1400        let c = cubic_circle();
1401        assert!(
1402            (c.signed_area() - core::f32::consts::PI).abs() < 1e-3,
1403            "cubic circle area {}",
1404            c.signed_area()
1405        );
1406        let b = c.bbox().expect("bbox");
1407        assert!((b.max_x() - 1.0).abs() < 1e-6 && (b.min_y() + 1.0).abs() < 1e-6);
1408    }
1409
1410    #[test]
1411    fn absolute_and_relative_agree() {
1412        let mut a = Path::starting_at(0.0, 0.0);
1413        a.line_to(10.0, 0.0);
1414        a.quad_to(12.0, 4.0, 10.0, 8.0);
1415        a.cubic_to(8.0, 10.0, 4.0, 10.0, 0.0, 8.0);
1416        a.close();
1417
1418        let mut b = Path::starting_at(0.0, 0.0);
1419        b.line_by(10.0, 0.0);
1420        b.quad_by(2.0, 4.0, 0.0, 8.0);
1421        b.cubic_by(-2.0, 2.0, -6.0, 2.0, -10.0, 0.0);
1422        b.close();
1423
1424        assert_eq!(a.commands(), b.commands());
1425        assert_eq!(a.signed_area(), b.signed_area());
1426        assert_eq!(a.bbox(), b.bbox());
1427    }
1428
1429    #[test]
1430    fn move_by_starts_a_subpath() {
1431        let mut p = Path::starting_at(0.0, 0.0);
1432        p.line_to(1.0, 0.0);
1433        // Relative to the current point (1, 0), so the new subpath starts at
1434        // (2, 1) — the delta is not applied to the origin.
1435        p.move_by(1.0, 1.0);
1436        p.line_to(2.0, 1.0);
1437        p.close();
1438        assert_eq!(p.start_point(), (2.0, 1.0));
1439        assert_eq!(p.len(), 5);
1440        assert_eq!(p.subpaths().len(), 2);
1441    }
1442
1443    #[test]
1444    fn close_is_implicit_but_accounted() {
1445        let mut open = Path::starting_at(0.0, 0.0);
1446        open.line_to(10.0, 0.0);
1447        open.line_to(10.0, 10.0);
1448        open.line_to(0.0, 10.0);
1449        assert!(!open.is_closed());
1450        let closed = {
1451            let mut c = open.clone();
1452            c.close();
1453            c
1454        };
1455        assert_eq!(open.len() + 1, closed.len());
1456        // The area is the same: the closing line is implicit either way.
1457        assert!((open.signed_area() - closed.signed_area()).abs() < 1e-4);
1458        assert!((closed.area() - 100.0).abs() < 1e-3);
1459    }
1460
1461    #[test]
1462    fn ensure_closed_is_idempotent() {
1463        let mut p = square();
1464        p.ensure_closed();
1465        assert_eq!(p.len(), 5);
1466        let mut e = Path::new();
1467        e.ensure_closed();
1468        assert!(e.is_empty());
1469    }
1470
1471    #[test]
1472    fn end_point_of_each_command() {
1473        assert_eq!(Command::move_to(1.0, 2.0).end_point(), Some((1.0, 2.0)));
1474        assert_eq!(Command::line_to(1.0, 2.0).end_point(), Some((1.0, 2.0)));
1475        assert_eq!(
1476            Command::quad_to(0.0, 0.0, 1.0, 2.0).end_point(),
1477            Some((1.0, 2.0))
1478        );
1479        assert_eq!(
1480            Command::cubic_to(0.0, 0.0, 0.0, 0.0, 1.0, 2.0).end_point(),
1481            Some((1.0, 2.0))
1482        );
1483        assert_eq!(Command::close().end_point(), None);
1484    }
1485
1486    #[test]
1487    fn relative_to_reports_every_opcode() {
1488        let cur = (3.0, 4.0);
1489        assert_eq!(
1490            Command::line_to(5.0, 6.0).relative_to(cur),
1491            (1, [2.0, 2.0, 0.0, 0.0, 0.0, 0.0])
1492        );
1493        assert_eq!(Command::move_to(3.0, 4.0).relative_to(cur), (0, [0.0; 6]));
1494        assert_eq!(
1495            Command::quad_to(3.0, 4.0, 5.0, 6.0).relative_to(cur),
1496            (2, [0.0, 0.0, 2.0, 2.0, 0.0, 0.0])
1497        );
1498        let (op, d) = Command::cubic_to(3.0, 4.0, 5.0, 6.0, 7.0, 8.0).relative_to(cur);
1499        assert_eq!(op, 3);
1500        assert_eq!(d, [0.0, 0.0, 2.0, 2.0, 4.0, 4.0]);
1501        assert_eq!(Command::close().relative_to(cur), (4, [0.0; 6]));
1502    }
1503
1504    #[test]
1505    fn outline_aggregates_and_nets_holes() {
1506        let mut o = Outline::new();
1507        assert!(o.is_empty());
1508        assert!(o.bbox().is_none());
1509        assert_eq!(o.area(), 0.0);
1510        assert_eq!(o.point_count(), 0);
1511        o.push_contour(square());
1512        let mut hole = Path::starting_at(2.0, 2.0);
1513        hole.line_to(2.0, 8.0);
1514        hole.line_to(8.0, 8.0);
1515        hole.line_to(8.0, 2.0);
1516        o.push_contour(hole);
1517        assert_eq!(o.len(), 2);
1518        // The hole runs clockwise, so the net area is the 6x6... ring.
1519        assert!((o.signed_area() - 64.0).abs() < 1e-3, "{}", o.signed_area());
1520        // Total unsigned area counts both.
1521        assert!((o.area() - 136.0).abs() < 1e-3, "{}", o.area());
1522        let b = o.bbox().expect("bbox");
1523        assert_eq!(b.max_x(), 10.0);
1524        assert_eq!(o.point_count(), 10);
1525    }
1526
1527    #[test]
1528    fn outline_push_closes_and_validate_accepts() {
1529        let mut p = Path::starting_at(0.0, 0.0);
1530        p.line_to(1.0, 0.0);
1531        p.line_to(1.0, 1.0);
1532        assert!(!p.is_closed());
1533        let mut o = Outline::new();
1534        o.push_contour(p);
1535        assert!(o.contours()[0].is_closed());
1536        assert!(o.validate(crate::GlyphId::new(0)).is_ok());
1537    }
1538
1539    #[test]
1540    fn validate_reports_unclosed_contour_index() {
1541        let mut o = Outline::new();
1542        o.push_contour(square());
1543        let mut q = Path::starting_at(0.0, 0.0);
1544        q.line_to(1.0, 1.0);
1545        o.contours_mut().push(q);
1546        match o.validate(crate::GlyphId::new(5)).unwrap_err() {
1547            crate::ModelError::UnclosedContour { glyph, contour } => {
1548                assert_eq!(glyph.to_u32(), 5);
1549                assert_eq!(contour, 1);
1550            }
1551            other => panic!("expected UnclosedContour, got {other:?}"),
1552        }
1553    }
1554
1555    #[test]
1556    fn validate_reports_each_non_finite_field() {
1557        let cases: [(f32, f32, f32, &str); 1] = [(f32::NAN, 0.0, 0.0, "x")];
1558        for (x, _y, _z, field) in cases {
1559            let mut o = Outline::new();
1560            let mut p = Path::starting_at(x, 0.0);
1561            p.line_to(1.0, 1.0);
1562            p.close();
1563            o.push_contour(p);
1564            let e = o.validate(crate::GlyphId::new(1)).unwrap_err();
1565            match e {
1566                crate::ModelError::NonFiniteCoordinate {
1567                    glyph,
1568                    contour,
1569                    command,
1570                    field: got,
1571                } => {
1572                    assert_eq!(glyph.to_u32(), 1);
1573                    assert_eq!(contour, 0);
1574                    assert_eq!(command, 0);
1575                    assert_eq!(got, field);
1576                }
1577                other => panic!("expected NonFiniteCoordinate, got {other:?}"),
1578            }
1579        }
1580
1581        // Infinite control y on a cubic names control1.y.
1582        let mut o = Outline::new();
1583        let mut s = Path::starting_at(0.0, 0.0);
1584        s.cubic_to(0.0, f32::INFINITY, 1.0, 1.0, 1.0, 1.0);
1585        s.close();
1586        o.push_contour(s);
1587        assert!(matches!(
1588            o.validate(crate::GlyphId::new(2)).unwrap_err(),
1589            crate::ModelError::NonFiniteCoordinate {
1590                field: "control1.y",
1591                ..
1592            }
1593        ));
1594
1595        // Infinite quad endpoint x names x.
1596        let mut o = Outline::new();
1597        let mut q = Path::starting_at(0.0, 0.0);
1598        q.quad_to(1.0, 1.0, f32::NEG_INFINITY, 1.0);
1599        q.close();
1600        o.push_contour(q);
1601        assert!(matches!(
1602            o.validate(crate::GlyphId::new(3)).unwrap_err(),
1603            crate::ModelError::NonFiniteCoordinate { field: "x", .. }
1604        ));
1605
1606        // An infinite quad *control* names control.x, so the control is checked
1607        // before the endpoint.
1608        let mut o = Outline::new();
1609        let mut q = Path::starting_at(0.0, 0.0);
1610        q.quad_to(f32::INFINITY, 1.0, f32::NEG_INFINITY, 1.0);
1611        q.close();
1612        o.push_contour(q);
1613        assert!(matches!(
1614            o.validate(crate::GlyphId::new(7)).unwrap_err(),
1615            crate::ModelError::NonFiniteCoordinate {
1616                field: "control.x",
1617                ..
1618            }
1619        ));
1620
1621        // Infinite control2.x on a cubic names control2.x.
1622        let mut o = Outline::new();
1623        let mut r = Path::starting_at(0.0, 0.0);
1624        r.cubic_to(1.0, 1.0, f32::INFINITY, 1.0, 1.0, 1.0);
1625        r.close();
1626        o.push_contour(r);
1627        assert!(matches!(
1628            o.validate(crate::GlyphId::new(4)).unwrap_err(),
1629            crate::ModelError::NonFiniteCoordinate {
1630                field: "control2.x",
1631                ..
1632            }
1633        ));
1634
1635        // Infinite control.x on a quad names control.x.
1636        let mut o = Outline::new();
1637        let mut t = Path::starting_at(0.0, 0.0);
1638        t.quad_to(f32::INFINITY, 1.0, 1.0, 1.0);
1639        t.close();
1640        o.push_contour(t);
1641        assert!(matches!(
1642            o.validate(crate::GlyphId::new(6)).unwrap_err(),
1643            crate::ModelError::NonFiniteCoordinate {
1644                field: "control.x",
1645                ..
1646            }
1647        ));
1648    }
1649
1650    #[test]
1651    fn reverse_flips_winding() {
1652        let mut p = square();
1653        p.reverse();
1654        assert_eq!(p.winding(), Winding::Clockwise);
1655        assert_eq!(p.area(), 100.0);
1656        assert_eq!(p.len(), 5);
1657        assert!(p.is_closed());
1658    }
1659
1660    #[test]
1661    fn reverse_preserves_curve_geometry() {
1662        let mut p = Path::starting_at(0.0, 0.0);
1663        p.cubic_to(3.0, 0.0, 3.0, 3.0, 0.0, 3.0);
1664        p.quad_to(-3.0, 3.0, 0.0, 0.0);
1665        p.close();
1666        let before_area = p.area();
1667        let before_bbox = p.bbox().expect("bbox");
1668        p.reverse();
1669        // Reversing flips the direction, so the winding flips with it — the
1670        // geometry is unchanged.
1671        assert_eq!(p.winding(), Winding::Clockwise);
1672        assert!((p.area() - before_area).abs() < 1e-3);
1673        let after = p.bbox().expect("bbox");
1674        assert!((after.min_x() - before_bbox.min_x()).abs() < 1e-4);
1675        assert!((after.max_x() - before_bbox.max_x()).abs() < 1e-4);
1676        assert!((after.min_y() - before_bbox.min_y()).abs() < 1e-4);
1677        assert!((after.max_y() - before_bbox.max_y()).abs() < 1e-4);
1678        // Reversing twice restores the geometry and the winding. The command
1679        // *list* need not come back: a quad followed by a cubic reverses to a
1680        // cubic followed by a quad, which is an equivalent but different
1681        // stream — so the invariant checked here is geometric, not textual.
1682        p.reverse();
1683        assert_eq!(p.winding(), Winding::CounterClockwise);
1684        let back = p.bbox().expect("bbox");
1685        assert!((back.min_x() - before_bbox.min_x()).abs() < 1e-4);
1686        assert!((back.max_y() - before_bbox.max_y()).abs() < 1e-4);
1687        assert!((p.area() - before_area).abs() < 1e-3);
1688    }
1689
1690    #[test]
1691    fn reverse_multi_subpath_keeps_areas() {
1692        let mut p = Path::starting_at(0.0, 0.0);
1693        p.line_to(1.0, 0.0);
1694        p.line_to(1.0, 1.0);
1695        p.move_to(5.0, 5.0);
1696        p.line_to(6.0, 5.0);
1697        p.line_to(6.0, 6.0);
1698        p.close();
1699        let before = p.area();
1700        p.reverse();
1701        assert!((p.area() - before).abs() < 1e-4);
1702        assert!(p.is_closed());
1703        assert_eq!(p.subpaths().len(), 2);
1704    }
1705
1706    #[test]
1707    fn reverse_of_a_path_with_no_segments_is_empty() {
1708        // A lone `MoveTo` + `Close` draws nothing, so there is nothing to
1709        // reverse: the result is empty rather than a `MoveTo` with no shape.
1710        let mut p = Path::starting_at(0.0, 0.0);
1711        p.close();
1712        p.reverse();
1713        assert!(p.is_empty());
1714        assert_eq!(p.area(), 0.0);
1715        let mut e = Path::new();
1716        e.reverse();
1717        assert!(e.is_empty());
1718    }
1719
1720    #[test]
1721    fn points_lists_controls() {
1722        let mut p = Path::starting_at(0.0, 0.0);
1723        p.quad_to(1.0, 1.0, 2.0, 0.0);
1724        p.cubic_to(3.0, 0.0, 4.0, 0.0, 5.0, 0.0);
1725        p.close();
1726        let pts = p.points();
1727        // MoveTo + quad(control, end) + cubic(2 controls, end); `Close` adds
1728        // none.
1729        assert_eq!(pts.len(), 6);
1730        assert_eq!(pts[0], (0.0, 0.0));
1731        assert_eq!(pts[1], (1.0, 1.0));
1732    }
1733
1734    #[test]
1735    fn push_matches_typed_constructors() {
1736        let mut a = Path::starting_at(1.0, 2.0);
1737        a.quad_to(3.0, 4.0, 5.0, 6.0);
1738        let mut b = Path::new();
1739        b.push(Command::MoveTo(1.0, 2.0));
1740        b.push(Command::QuadTo(3.0, 4.0, 5.0, 6.0));
1741        assert_eq!(a.commands(), b.commands());
1742        assert_eq!(b.current_point(), (5.0, 6.0));
1743        assert_eq!(b.start_point(), (1.0, 2.0));
1744    }
1745
1746    #[test]
1747    fn subpath_exposes_segments() {
1748        let mut p = Path::starting_at(0.0, 0.0);
1749        p.line_to(1.0, 0.0);
1750        p.quad_to(1.0, 1.0, 0.0, 1.0);
1751        p.cubic_to(-1.0, 1.0, -1.0, 0.0, 0.0, 0.0);
1752        p.close();
1753        let subs = p.subpaths();
1754        assert_eq!(subs.len(), 1);
1755        let sp: &Subpath = &subs[0];
1756        assert!(sp.closed);
1757        assert_eq!(sp.segment_count(), 3);
1758        assert_eq!(sp.points.len(), 5, "start + 3 ends + closing repeat");
1759        let segs = sp.segments();
1760        assert_eq!(segs[0].kind, 1);
1761        assert_eq!(segs[1].kind, 2);
1762        assert_eq!(segs[2].kind, 3);
1763        assert_eq!(segs[0].c1, (0.0, 0.0), "a line has no controls");
1764        assert_eq!(segs[1].c1, (1.0, 1.0), "the quad's control point");
1765        // The subpath's area is the path's area — the two views agree exactly,
1766        // which is the property that makes `subpaths` usable as a decomposition.
1767        assert_eq!(sp.signed_area(), p.signed_area());
1768        assert!(sp.signed_area() > 0.0, "counter-clockwise");
1769        // The cubic `(0,1) → (-1,1) (-1,0) → (0,0)` reaches x = -0.75 at its
1770        // midpoint; the exact box finds it, a control hull would say -1.
1771        assert!((sp.bbox().expect("bbox").min_x() + 0.75).abs() < 1e-5);
1772    }
1773
1774    #[test]
1775    fn subpaths_of_open_and_empty_paths() {
1776        assert!(Path::new().subpaths().is_empty());
1777        let open = Path::starting_at(0.0, 0.0);
1778        let subs = open.subpaths();
1779        assert_eq!(subs.len(), 1);
1780        assert!(!subs[0].closed);
1781        assert_eq!(subs[0].signed_area(), 0.0);
1782        assert!(subs[0].bbox().is_some());
1783        // An open subpath does not repeat its start point; a closed one does.
1784        let mut closed = Path::starting_at(0.0, 0.0);
1785        closed.line_to(1.0, 0.0);
1786        closed.close();
1787        assert_eq!(closed.subpaths()[0].points.len(), 3);
1788        let mut unclosed = Path::starting_at(0.0, 0.0);
1789        unclosed.line_to(1.0, 0.0);
1790        assert_eq!(unclosed.subpaths()[0].points.len(), 2);
1791        // An open path's area still accounts for its implicit closing line.
1792        let mut tri = Path::starting_at(0.0, 0.0);
1793        tri.line_to(10.0, 0.0);
1794        tri.line_to(0.0, 10.0);
1795        assert!((tri.signed_area() - 50.0).abs() < 1e-4);
1796    }
1797
1798    #[test]
1799    fn bbox_helpers() {
1800        assert!(Bbox::empty().is_empty());
1801        assert_eq!(Bbox::empty().width(), 0.0);
1802        assert_eq!(Bbox::empty().height(), 0.0);
1803        assert!(!Bbox::empty().contains(0.0, 0.0));
1804        let b = Bbox::from_corners(10.0, 20.0, 0.0, 5.0);
1805        assert_eq!(b.min_x(), 0.0);
1806        assert_eq!(b.max_y(), 20.0);
1807        assert!(b.contains(5.0, 10.0));
1808        assert!(b.contains(0.0, 5.0), "boundary counts as inside");
1809        assert!(!b.contains(-1.0, 10.0));
1810        let t = b.translated(1.0, 1.0);
1811        assert_eq!(t.min_x(), 1.0);
1812        assert!(Bbox::empty().translated(1.0, 1.0).is_empty());
1813        let mut u = Bbox::from_points(vec![(0.0, 0.0), (3.0, 4.0)]);
1814        assert_eq!(u.max_y(), 4.0);
1815        let snapshot = u;
1816        u.union(&Bbox::from_corners(-1.0, -1.0, -1.0, -1.0));
1817        assert_eq!(u.min_x(), -1.0);
1818        assert_eq!(snapshot.min_x(), 0.0, "union took by value");
1819        u.union(&Bbox::empty());
1820        assert_eq!(u.min_x(), -1.0);
1821        assert_eq!(Bbox::default(), Bbox::empty());
1822        assert_eq!(b.corners()[0], (0.0, 5.0));
1823        assert_eq!(b.corners()[3], (0.0, 20.0));
1824    }
1825
1826    #[test]
1827    fn many_points_bbox_contains_all() {
1828        let mut p = Path::starting_at(0.0, 0.0);
1829        for i in 1..100 {
1830            p.line_to(f32::from(u16::try_from(i).unwrap_or(99)), 0.0);
1831        }
1832        let b = p.bbox().expect("bbox");
1833        assert_eq!(b.max_x(), 99.0);
1834        for pt in p.points() {
1835            assert!(b.contains(pt.0, pt.1), "point {pt:?} outside {b:?}");
1836        }
1837    }
1838
1839    #[test]
1840    fn outline_default_is_empty() {
1841        let o = Outline::default();
1842        assert!(o.is_empty());
1843        assert_eq!(o.contours().len(), 0);
1844        assert_eq!(o.signed_area(), 0.0);
1845    }
1846}