1. Introduction
are a pure medium for visualizing mathematical features. With vector graphics, a operate is approximated by segments of linked cubic Bézier curves which are rasterized (i.e. transformed into pixels) when they’re displayed [1]. As a result of rasterization is delayed, vector graphic pictures are naturally extra moveable than pixel-based pictures because the rendering could be tailor-made to its show surroundings. Irrespective of how a lot you zoom in on a vector graphics plot, you’ll at all times see crisp line segments; whereas in case you zoom in sufficient on a rasterized picture, you’ll finally see the grainy blocks that characterize the pixels.
Whereas vector graphics are a superb format for plotting, producing good vector graphics could be difficult. Think about, for instance, how we’d undertake this instance plot from matplotlib [2] for the operate f(t) = exp(−t)cos(−2πt), 0 ≤ t ≤ 5, to provide an SVG picture:
import matplotlib.pyplot as plt
import numpy as np
def f(t):
return np.exp(-t) * np.cos(2*np.pi*t)
t = np.arange(0.0, 5.0, 0.02)
plt.plot(t, f(t))
plt.savefig('fig.svg')
Matplotlib approximates the graceful plot with 250 piecewise linked line segments (proven with the alternating colours). Whereas the plot appears to be like good, it’s a lot bigger than it must be. If, as a substitute, we had been producing a rasterized picture like a PNG, the main points of how the curve is constructed wouldn’t matter; however with a vector graphic the person line segments are handed by and preserved within the outputted picture. With some changes, although, we will enhance the scale considerably with out sacrificing the standard of the picture.
The fundamental primitive of vector graphics is the parametric cubic, represented as a cubic Bézier curve. With piecewise cubic Bézier curves, we’ve much more knobs we will modify to approximate features than if we limit ourselves to piecewise linear or piecewise (nonparametric) cubic segments. Utilizing the orthogonal distance becoming (ODF) algorithm from this paper, we will produce a plot of the operate that requires solely 8 Bézier segments and is visually indistinguishable from the matplotlib graphic. Beneath I present the plot’s illustration in TikZ. Later I’ll present how we will simply flip the TikZ command into an SVG picture for the net utilizing MetaPost.
draw (0.00000, 2.50000) .. controls (0.39088, 2.10882) and (0.61233, -1.05415) ..
(1.18750, 0.36510) .. controls (1.60393, 1.31193) and (1.71252, 2.10800) ..
(2.37500, 0.95127) .. controls (2.88922, 0.15365) and (3.15477, 0.95162) ..
(3.56250, 1.11921) .. controls (3.98299, 1.31658) and (4.26123, 0.78781) ..
(4.75000, 0.82415) .. controls (5.02221, 0.81871) and (5.38203, 1.12388) ..
(5.93750, 0.99939) .. controls (5.96426, 1.01981) and (6.36975, 0.82102) ..
(7.12500, 0.95127) .. controls (8.08129, 1.04760) and (7.44859, 0.87986) ..
(9.50000, 0.96171);
The algorithm builds on Alvin Penner’s work [3]. Given a parametric operate f, it first suits a Chebyshev sequence to approximate f. For analytic features, interpolation in Chebyshev nodes gives fast geometric convergence [4]. This is much better than the sometimes fourth order convergence you’ll get with interpolation in cubic splines and significantly better than the quadratic convergence you’ll get with piecewise linear interpolation [5]. By interpolating in Chebyshev nodes, we will scale back the variety of occasions we have to consider f. Utilizing a trust-region optimizer, the algorithm then appears to be like for a cubic Bézier curve that optimally approximates the goal operate. If the maximal orthogonal distance between the fitted Bézier curve and the Chebyshev sequence for f is lower than a goal threshold, then, nice, we’re finished; in any other case, we break up the area in two and repeat the method. I element the steps beneath.
Algorithm F (match a Bézier path to a operate). Given a parametric operate f (t) = (f_x (t), f_y (t)), a ≤ t ≤ b, match a Bezier path, g, to f in order that
F1. Utilizing the algorithm developed by Jared Aurentz and Lloyd Trefethen from [7], match Chebyshev sequence f~_x , f~_y to f_x, f_y. When f is analytic or differentiable to a excessive diploma, the match is often near machine precision so going ahead we assume that we will use f~ as a proxy for f and that any loss in accuracy can be negligible.
F2. Utilizing a belief area optimizer [8] and Penner’s algorithm [3], match a Bezier curve g to reduce
Extra particulars for this step are supplied in §3.
F3. Compute
If M is lower than the goal threshold, terminate; in any other case, set
and repeat steps F1 by F3 for f_l and f_r till the edge is reached. See §4 for extra particulars.
Within the subsequent part, I describe easy methods to match arbitrary features with Algorithm F utilizing the Python package deal bbai (https://github.com/rnburn/bbai).
2. Performance Tour
The beneath code demonstrates the fundamental process of becoming a operate to a specified window:
from bbai.graphics import BezierPath
import numpy as np
def f(t):
return np.exp(-t * t)
path = BezierPath(
dst_xmin=0, dst_xmax=9.5,
dst_ymin=0, dst_ymax=2)
path.match(f, -2, 2)
print(path.tikz_)outputs
draw (0.000, 0.000)..controls (2.684, 0.092) and (3.273, 1.952)
.. (4.750, 2.000)..controls (6.229, 1.951) and (6.815, 0.092)
.. (9.500, 0.000);
By default, the library will scale the plot in order that the operate simply suits within the window outlined by dst_xmin, dst_xmax, dst_ymin, and dst_ymax; however that may be modified by additionally specifying a supply window with src_xmin, src_xmax, src_ymin, and src_ymax. The algorithm makes use of 1.0 × 10^-2 because the default most orthogonal distance threshold which, for perspective, is one hundredth of TikZ’s default line width.
We are able to additionally match parametric features by offering each an x and a y operate.
from bbai.graphics import BezierPath
import numpy as np
R, r, d = 5, 3, 5
def fx(t):
return (R-r)*np.cos(t) + d*np.cos((R-r)/r*t)
def fy(t):
return (R-r)*np.sin(t) - d*np.sin((R-r)/r*t)
path = BezierPath(
dst_xmin=0, dst_xmax=2.5,
dst_ymin=0, dst_ymax=2.5)
path.match(fx, fy, 0, 2*np.pi*r*d/R)
print(path.tikz_)outputs
draw (2.500, 1.250)..controls (2.533, 1.060) and (1.400, 0.745)
.. (0.850, 0.578)..controls (-0.049, 0.321) and (-0.145, 0.403)
.. (0.148, 0.876)..controls (0.197, 0.986) and (1.203, 2.351)
.. (1.405, 2.450)..controls (1.594, 2.564) and (1.722, 2.598)
.. (1.716, 1.250)..controls (1.722, -0.033) and (1.609, -0.085)
.. (1.405, 0.049)..controls (1.203, 0.149) and (0.197, 1.514)
.. (0.149, 1.624)..controls (-0.137, 2.086) and (-0.067, 2.185)
.. (0.851, 1.921)..controls (1.203, 1.809) and (2.534, 1.455)
.. (2.5000, 1.2500);
3. The Becoming Algorithm
This part breaks down Step F2 in better element the place we match a Bézier curve, g, to approximate f~. The algorithm is just like Penner’s algorithm from [3] however with a number of modifications. A cubic Bézier curve is parameterized by 4 factors. Within the becoming algorithm, we match the endpoints of f~ which provides us two factors or 4 parameters that we will modify. Let θ denote the adjustable parameters; let B_θ denote the cubic Bézier curve with parameters θ that matches the endpoints f~(a) and f~(b); and outline
Primary calculus tells us that s_t should both be an endpoint or it should fulfill the equation
As B_θ is a parametric cubic, the values of s that fulfill the equation are the roots of a quintic which could be simply solved for by discovering the eigenvalues of its related colleague matrix [4].
We are able to use a Clenshaw Curtis quadrature to approximate the target operate
The gradient and Hessian of h could be computed utilizing the implicit operate theorem. See [3] for the equations. We are able to now put collectively the becoming algorithm.
Algorithm B (match a Bézier curve to a operate). Given a parametric operate f~(t) = (f~_x (t), f~_y (t)), a ≤ t ≤ b, discover parameters θ to reduce h(θ).
B1. If potential, choose θ_0 in order that B_{θ_0} matches the curvature of f~ at a and b; in any other case, choose θ_0 in order that B_{θ_0} is the road section that passes by f(a) and f(b).
B2. Ranging from θ_0 and utilizing h, ∇h, and ∇^2 h, step a trust-region optimizer [8] till both we’ve come suitably near an optimum or we’ve exceeded a predetermined most variety of steps
The key benefit of utilizing a trust-region optimizer for Step B2 is that it received’t get caught at saddle factors. Through the use of second order data mixed with an adaptive “belief area”, a trust-region optimizer can nonetheless make progress even when ∇h is close to zero and ∇^2h is indefinite.
4. The Max Distance Algorithm
This part breaks down Step F3 in better element the place given a cubic Bézier curve, g, we compute the utmost orthogonal distance from g to f. With s_t outlined as in §3, put
and outline the next algorithm:
Algorithm M (discover most orthogonal distance). Given a parametric operate f~(t) = (f~_x(t), f~_y(t)), a ≤ t ≤ b, and a Bézier curve g, remedy argmax_t r(t).
M1. Set D_max ← 0.
M2. Utilizing the bisection technique, begin from the interval [a, b] and discover a native most t_0 of r. Set D_max ← max(D_max, r(t_0)).
M3. Put s_0 ← s_{t_0} and let s_l0′ , s_l0′′ , s_r0′ , and s_r0′′ denote the left and proper derivatives for
Word that the left-hand and right-hand values might differ. Outline the features
and
M4. Discover the smallest h_l>0 and h_r>0 such that
If appropriate h_l and h_r exist, repeat Steps M2 by M4 for [a, t_0 −h_l] and [t_0 +h_r,b]. In any other case, return D_max.
Bear in mind from Algorithm F that f~ is represented as a Chebyshev sequence so it’s a simple step to compute the Chebyshev sequence representations for r~_l and r~_r. Thus, Step M4 could be achieved by making use of Boyd’s root discovering algorithm [6].
The determine beneath reveals the results of the max distance algorithm when making an attempt to suit the operate f(t)=(.1+t) sin(t), 0 ≤ t ≤ 2π, with solely a single Bézier curve,
draw (0.000, 1.800)..controls (4.484, 4.660) and (8.448, -3.442)..(9.500, 1.800);We are able to see that despite the fact that there are a number of native optima, Algorithm M accurately identifies the worldwide optimum.
5. Learn how to Produce SVG Pictures
On this part, I’ll present easy methods to produce an SVG picture from the TikZ path that bbai generates. I’ll additionally present how we will draw axes and annotate. One method to produce SVG pictures is embed the TikZ drawing instructions right into a latex doc, run lualatex with the –output-format=dvi possibility, then use dvisvgm to transform the dvi file to an SVG picture, as described within the TikZ handbook (see §10.2.4 of [9]). Nonetheless, if the aim is to provide an SVG graphic, I discover it simpler to to make use of the MetaPost software which may output to SVG instantly [10].
MetaPost gives an image drawing language. Utilizing its command line utility mpost, which must be included as a part of a TeX Dwell set up, we will shortly produce an SVG plot. It accepts the identical command for drawing paths as TikZ. Right here, as an example, is how we might produce an SVG picture for the plot from §1.
% plt.mp
outputformat := "svg";
outputtemplate := "%j-%c.svg";
prologues:=3;
beginfig(1);
draw (0.00000, 2.50000) .. controls (0.39088, 2.10882) and (0.61233, -1.05415) ..
(1.18750, 0.36510) .. controls (1.60393, 1.31193) and (1.71252, 2.10800) ..
(2.37500, 0.95127) .. controls (2.88922, 0.15365) and (3.15477, 0.95162) ..
(3.56250, 1.11921) .. controls (3.98299, 1.31658) and (4.26123, 0.78781) ..
(4.75000, 0.82415) .. controls (5.02221, 0.81871) and (5.38203, 1.12388) ..
(5.93750, 0.99939) .. controls (5.96426, 1.01981) and (6.36975, 0.82102) ..
(7.12500, 0.95127) .. controls (8.08129, 1.04760) and (7.44859, 0.87986) ..
(9.50000, 0.96171);
endfig;
finish.Working the command
mpost plt.mpwill produce an SVG for the trail as plt-1.svg. We are able to use the MetaPost instructions drawarrow and label so as to add some axes. Right here is supply code after rescaling and including the axes:
% plt.mp
outputformat := "svg";
outputtemplate := "%j-%c.svg";
prologues:=3;
beginfig(1);
path pth;
pth := (0.00000, 2.50000) .. controls (0.39088, 2.10882) and (0.61233, -1.05415) ..
(1.18750, 0.36510) .. controls (1.60393, 1.31193) and (1.71252, 2.10800) ..
(2.37500, 0.95127) .. controls (2.88922, 0.15365) and (3.15477, 0.95162) ..
(3.56250, 1.11921) .. controls (3.98299, 1.31658) and (4.26123, 0.78781) ..
(4.75000, 0.82415) .. controls (5.02221, 0.81871) and (5.38203, 1.12388) ..
(5.93750, 0.99939) .. controls (5.96426, 1.01981) and (6.36975, 0.82102) ..
(7.12500, 0.95127) .. controls (8.08129, 1.04760) and (7.44859, 0.87986) ..
(9.50000, 0.96171);
draw pth scaled 50;
numeric xlim, ylim;
xlim := xpart urcorner currentpicture;
ylim := ypart urcorner currentpicture;
drawarrow (-10, -10) -- (xlim, -10);
drawarrow (-10,-10) -- (-10, ylim);
label.bot(btex $x$ etex, (xlim, -10));
label.lft(btex $y$ etex, (-10, ylim));
endfig;
finish.
6. Benchmarks
On this sections I measure how lengthy it takes me to compute Bezier paths for numerous features. I didn’t spend a whole lot of time optimizing the algorithm’s implementation so I’m certain that these numbers could possibly be improved considerably. The primary takeaway must be that the algorithm is a minimum of quick sufficient to be sensible for a lot of frequent circumstances. The examples are all taken from [4], and all of the features are match over the vary −1 ≤ t ≤ 1.
7. Conclusions
For analytic or features which are differentiable to a excessive diploma, we’ve seen that Algorithm F gives an environment friendly and sensible method to generate a minimal illustration as a Bézier path, which may then be used to provide a vector graphic.
One space of future work may be to increase the algorithm to work higher for features with kinks (i.e. factors the place the operate just isn’t analytic).
References and Notes
[1] So far as I’m conscious, all the main vector graphics codecs (e.g. SVG, postscript) use cubic Bézier curves because the core primitive. Whereas a number of the codecs present different fundamental graphics like circles, and so on, these are all simply wrappers on high of cubic Bézier curve approximations.
[2] The instance is tailored from https://matplotlib.org/secure/gallery/pyplots/pyplot_two_subplots.html.
[3] Alvin Penner. Becoming a cubic Bézier to a parametric operate. The Faculty Arithmetic Journal, 50(3): 185–196, 2019.
[4] Lloyd N. Trefethen. Approximation concept and approximation follow. SIAM, 2020.
[5] C. A. Corridor. On error bounds for spline interpolation. Journal of Approximation Principle, 1: 209–218, 1968.
[6] John Boyd. Computing zeros on an actual interval by Chebyshev growth and polynomial rootfinding.SIAM Journal on Numerical Evaluation, 40(5): 1666–1682, 2003.
[7] Jared Aurentz, Lloyd N. Trefethen. Chopping a Chebyshev sequence. ACM Transactions on Mathematical Software program, 43(4): 1–21, 2017.
[8] Jorge Nocedal, Stephen J. Wright. Numerical optimization, second version. Springer, 2000.
[9] The TikZ and PGF Packages, 2026. https://tikz.dev.
[10] John D. Passion, Metapost, 2024. https://www.tug.org/docs/metapost/mpman.pdf.
