Repository navigation
Expand file tree
/
Copy pathdoc.go
More file actions
204 lines (203 loc) · 9.4 KB
/
Copy pathdoc.go
File metadata and controls
204 lines (203 loc) · 9.4 KB
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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
// SPDX-FileCopyrightText: 2018 Raph Levien
// SPDX-FileCopyrightText: 2024 Dominik Honnef and contributors
//
// SPDX-License-Identifier: MIT
// SPDX-FileAttributionText: https://github.com/linebender/kurbo
// Package curve provides primitives and routines for 2D shapes, curves, and
// paths. It was designed to serve the needs of 2D graphics applications, but it
// is intended to be general enough to be useful for other applications.
//
// # Kurbo
//
// This package is a manual, idiomatic Go port of the [kurbo] Rust crate. Kurbo
// contains several novel approaches to problems in 2D curve design,
// particularly stroke expansion. This package's development will closely follow
// kurbo's.
//
// We may introduce functionality of our own, but this will likely be limited to
// simple features.
//
// # Features
//
// We provide the following notable features:
//
// - Curve fitting (see [FitToBezPath])
// - Stroke expansion (see [StrokePath])
// - Dashing (see [Dash])
// - Curve simplification (see [Simplify])
// - Affine transformations (see [Affine])
// - Approximating cubic Béziers with quadratic splines (see [CubicBez.ApproxQuadSpline])
// - Flattening paths to lines (see [Flatten])
//
// # Shapes, parametric curves, and paths
//
// The three core primitives of this package are shapes, curves, and paths.
//
// [Shape] describes geometric shapes that have a perimeter and a bounding box,
// and that can be converted to a series of path elements. [ClosedShape]
// describes those shapes that additionally have a closed outline (such as
// rectangles, but not lines) and thus have an area and can compute a point's
// [winding number].
//
// This package includes the following shapes:
// - [Arc]
// - [Circle]
// - [CircleSector]
// - [Annulus]
// - [AnnulusSector]
// - [CubicBez]
// - [Ellipse]
// - [Line]
// - [QuadBez]
// - [Rect]
// - [RoundedRect]
// - [Triangle]
//
// [ParametricCurve] describes parametrized curves. These curves can be
// evaluated at t ∈ [0, 1] and return pairs of (x, y) values, commonly
// interpreted as points in a 2D Cartesian coordinate system. The simplest
// parametric curve is the [Line], whose evaluation is a simple linear
// interpolation between its start and end points. More complex curves are the
// quadratic and cubic Béziers, for example.
//
// [PathLengther] is an optional interface implemented by curves that can compute
// their length. [PathLengthSolver] is an optional interface
// implemented by curves that can efficiently solve for t given an arc length.
//
// [FittableCurve] is closely related to [ParametricCurve] and describes
// parametrized curves in a way that allows efficient curve fitting. Using curve
// fitting, arbitrary curves can be approximated with paths. See the example of
// [FitToBezPathOpt] for a custom curve that implements a quartic function and
// that gets approximated by cubic Béziers.
//
// This package includes the following curves:
// - [Line]
// - [CubicBez]
// - [PathSegment] (as it is a wrapper for [Line], [CubicBez], and [QuadBez])
// - [QuadBez]
//
// # Bézier paths
//
// Bézier paths consist of lines and quadratic and cubic Béziers. All shapes can
// represent themselves as Bézier paths, and more complex curves can be
// approximated by them.
//
// [BezPath] represents Bézier paths as a slice of path elements and provides
// methods for building paths as well as for any path manipulation that needs
// access to the collection of path elements. The two other representations are
// iter.Seq[PathElement] and iter.Seq[PathSegment], see the Iterators section
// for more on that.
//
// # Path elements and segments
//
// This package provides two representations for paths: [PathElement] and
// [PathSegment]. Path elements are akin to drawing commands in graphics APIs
// like PostScript, consisting of pen moves ([MoveTo]) and various drawing
// commands ([LineTo], [QuadTo], etc.) Each command moves the current position
// of the pen, which acts as the start position of the following drawing
// command.
//
// Segments, on the other hand, are self-contained descriptions of a portion of
// the path, containing explicit start points.
//
// Using [Elements] and [Segments], you can freely convert between the two
// representations.
//
// The package supports [MoveTo], [LineTo], [QuadTo], [CubicTo], and [ClosePath]
// path elements, and correspondingly has path segments for lines, quadratic
// Béziers, and cubic Béziers.
//
// # Cubic Béziers
//
// The primary curve used by this package is the cubic Bézier. Functions that
// convert shapes to paths do so by approximating them with cubic Béziers (and
// lines). Similarly, curve fitting approximates curves with cubic Béziers (and
// lines). This is done because cubic Béziers hit the sweet spot of
// expressiveness and computability.
//
// However, we also provide functions for working with quadratic Béziers,
// including approximating cubic Béziers with quadratic Béziers. This
// functionality is particularly useful for font design, as TrueType fonts
// (unlike OpenType) use quadratic Béziers.
//
// # Direction of the y-axis
//
// This package is agnostic to whether the y-axis points up or down. Positive
// angles are defined such that when going in the positive x direction, they
// point towards positive y. The same applies to oriented area, winding numbers,
// curvature, etc. For y-up coordinate systems, this results in counterclockwise
// traversal, while for y-down coordinate systems it results in clockwise
// traversal.
//
// A = (1, 1)
// B = (4, 1)
// C = (4, 4)
// D = (1, 4)
//
// y-up │ y-down
// y │
// ^ │ 0-------------------------> x
// | │ |
// | │ | A +------->-------+ B
// | D +-------<-------+ C │ | | |
// | | | │ | ^ v
// | v ^ │ | | |
// | | | │ | D +-------<-------+ C
// | A +------->-------+ B │ |
// | │ v
// 0-------------------------> x │ y
// │
//
// You can also use [FlipY] (followed by a translation of the origin) to convert
// between y-up and y-down.
//
// We try to avoid using the terms "top" and "bottom" when referring to edges of
// shapes, as these are only meaningful when specifying the direction of the
// y-axis.
//
// # Oriented area / signed area
//
// The Area method on shapes returns their oriented area. The oriented area of a
// closed shape is its enclosed area, with the sign depending on the order of
// traversal. In a y-down coordinate system, the area is positive for clockwise
// traversal, while in a y-up one, it is positive for anticlockwise traversal.
//
// When open shapes, such as [CubicBez], implement this method, they compute
// their contribution to the overall area of a closed shape, such as a
// closed [BezPath] made up of multiple curves.
//
// The oriented area is also commonly called the signed area, but we wanted
// to avoid confusion with the definition from calculus, where the signed
// area of a curve is the area between the curve and the x-axis. This is not
// the case here.
//
// # Literature
//
// This package makes use of the following ideas:
// - [A Primer on Bézier Curves]
// - [Algorithm 1010: Boosting Efficiency in Solving Quartic Equations with No Compromise in Accuracy] by Orellana and De Michele
// - [An Enhancement of the Bisection Method Average Performance Preserving Minmax Optimality] by Oliveira and Takahashi
// - [Approximate a circle with cubic Bézier curves] by Spencer Mortensen
// - [Calculating Area of Closed Curves in ℝ²]
// - [Fitting cubic Bézier curves] by Raph Levien
// - [Flattening quadratic Béziers] by Raph Levien
// - [Green's theorem]
// - [How to solve a cubic equation, revisited] by Christoph Peters
// - [Parallel curves of cubic Béziers] by Raph Levien
// - [Simplifying Bézier paths] by Raph Levien
// - https://github.com/Pomax/BezierInfo-2/issues/238
//
// [A Primer on Bézier Curves]: https://pomax.github.io/bezierinfo/
// [Algorithm 1010: Boosting Efficiency in Solving Quartic Equations with No Compromise in Accuracy]: https://cristiano-de-michele.netlify.app/publication/orellana-2020/orellana-2020.pdf
// [An Enhancement of the Bisection Method Average Performance Preserving Minmax Optimality]: https://dl.acm.org/doi/10.1145/3423597
// [Approximate a circle with cubic Bézier curves]: https://spencermortensen.com/articles/bezier-circle/
// [Fitting cubic Bézier curves]: https://raphlinus.github.io/curves/2021/03/11/bezier-fitting.html
// [Flattening quadratic Béziers]: https://raphlinus.github.io/graphics/curves/2019/12/23/flatten-quadbez.html
// [Green's theorem]: https://en.wikipedia.org/wiki/Green%27s_theorem
// [How to solve a cubic equation, revisited]: https://momentsingraphics.de/CubicRoots.html
// [Parallel curves of cubic Béziers]: https://raphlinus.github.io/curves/2022/09/09/parallel-beziers.html
// [Simplifying Bézier paths]: https://raphlinus.github.io/curves/2023/04/18/bezpath-simplify.html
// [Calculating Area of Closed Curves in ℝ²]: http://ich.deanmcnamee.com/graphics/2016/03/30/CurveArea.html
// [kurbo]: https://github.com/linebender/kurbo
// [winding number]: https://en.wikipedia.org/wiki/Winding_number
package curve