How To Produce Ultra-Compact Vector Graphic Plots With Orthogonal Distance Fitting

1. Introduction

are a pure medium for visualizing mathematical capabilities. With vector graphics, a perform is approximated by segments of related cubic Bézier curves which might be rasterized (i.e. transformed into pixels) when they’re displayed [1]. As a result of rasterization is delayed, vector graphic photographs are naturally extra transportable than pixel-based photographs because the rendering will be tailor-made to its show atmosphere. Regardless of how a lot you zoom in on a vector graphics plot, you’ll at all times see crisp line segments; whereas when you zoom in sufficient on a rasterized picture, you’ll ultimately see the grainy blocks that characterize the pixels.

Whereas vector graphics are a wonderful format for plotting, producing good vector graphics will be difficult. Take into account, for instance, how we would undertake this instance plot from matplotlib [2] for the perform 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 related line segments (proven with the alternating colours). Whereas the plot seems 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 way of and preserved within the outputted picture. With some changes, although, we are able to enhance the dimensions considerably with out sacrificing the standard of the picture.

The essential primitive of vector graphics is the parametric cubic, represented as a cubic Bézier curve. With piecewise cubic Bézier curves, now we have much more knobs we are able to regulate to approximate capabilities than if we limit ourselves to piecewise linear or piecewise (nonparametric) cubic segments. Utilizing the orthogonal distance becoming (ODF) algorithm from this paper, we are able to produce a plot of the perform that requires solely 8 Bézier segments and is visually indistinguishable from the matplotlib graphic. Under I present the plot’s illustration in TikZ. Later I’ll present how we are able to simply flip the TikZ command into an SVG picture for the online 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 perform f, it first matches a Chebyshev collection to approximate f. For analytic capabilities, interpolation in Chebyshev nodes offers fast geometric convergence [4]. This is much better than the usually fourth order convergence you’re going to get with interpolation in cubic splines and significantly better than the quadratic convergence you’re going to get with piecewise linear interpolation [5]. By interpolating in Chebyshev nodes, we are able to scale back the variety of instances we have to consider f. Utilizing a trust-region optimizer, the algorithm then seems for a cubic Bézier curve that optimally approximates the goal perform. If the maximal orthogonal distance between the fitted Bézier curve and the Chebyshev collection for f is lower than a goal threshold, then, nice, we’re completed; in any other case, we cut up the area in two and repeat the method. I element the steps beneath.

Algorithm F (match a Bézier path to a perform). Given a parametric perform 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 collection 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 are able to use f~ as a proxy for f and that any loss in accuracy will probably 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 way of F3 for f_l and f_r till the brink is reached. See §4 for extra particulars.

Within the subsequent part, I describe match arbitrary capabilities with Algorithm F utilizing the Python package deal bbai (https://github.com/rnburn/bbai).

2. Performance Tour

The beneath code demonstrates the fundamental activity of becoming a perform 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 perform simply matches 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 will additionally match parametric capabilities by offering each an x and a y perform.

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 higher element the place we match a Bézier curve, g, to approximate f~. The algorithm is much like Penner’s algorithm from [3] however with a couple 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 are able to regulate. 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 will be simply solved for by discovering the eigenvalues of its related colleague matrix [4].

We will use a Clenshaw Curtis quadrature to approximate the target perform

The gradient and Hessian of h will be computed utilizing the implicit perform theorem. See [3] for the equations. We will now put collectively the becoming algorithm.

Algorithm B (match a Bézier curve to a perform). Given a parametric perform f~(t) = (f~_x (t), f~_y (t)), a ≤ t ≤ b, discover parameters θ to reduce h(θ).

B1. If attainable, 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 phase that passes by way of 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 gained’t get caught at saddle factors. By utilizing second order info 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 higher 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 perform f~(t) = (f~_x(t), f~_y(t)), a ≤ t ≤ b, and a Bézier curve g, resolve 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

Observe that the left-hand and right-hand values might differ. Outline the capabilities

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 way of M4 for [a, t_0 −h_l] and [t_0 +h_r,b]. In any other case, return D_max.

Keep in mind from Algorithm F that f~ is represented as a Chebyshev collection so it’s a simple step to compute the Chebyshev collection representations for r~_l and r~_r. Thus, Step M4 will be achieved by making use of Boyd’s root discovering algorithm [6].

The determine beneath exhibits the results of the max distance algorithm when attempting to suit the perform 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 will see that though there are a number of native optima, Algorithm M appropriately identifies the worldwide optimum.

5. Tips on how to Produce SVG Photographs

On this part, I’ll present produce an SVG picture from the TikZ path that bbai generates. I’ll additionally present how we are able to draw axes and annotate. One solution to produce SVG photographs 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]). Nevertheless, if the objective is to provide an SVG graphic, I discover it simpler to to make use of the MetaPost software which might output to SVG immediately [10].

MetaPost offers an image drawing language. Utilizing its command line utility mpost, which needs to be included as a part of a TeX Reside set up, we are able to shortly produce an SVG plot. It accepts the identical command for drawing paths as TikZ. Right here, as an illustration, 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.

Operating the command

mpost plt.mp

will produce an SVG for the trail as plt-1.svg. We will 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 capabilities. I didn’t spend a number of time optimizing the algorithm’s implementation so I’m positive that these numbers might be improved considerably. The principle takeaway needs to be that the algorithm is at the very least quick sufficient to be sensible for a lot of widespread instances. The examples are all taken from [4], and all of the capabilities are match over the vary −1 ≤ t ≤ 1.

7. Conclusions

For analytic or capabilities which might be differentiable to a excessive diploma, we’ve seen that Algorithm F offers an environment friendly and sensible solution to generate a minimal illustration as a Bézier path, which might then be used to provide a vector graphic.

One space of future work is perhaps to increase the algorithm to work higher for capabilities with kinks (i.e. factors the place the perform is just not analytic).

References and Notes

[1] So far as I’m conscious, the entire main vector graphics codecs (e.g. SVG, postscript) use cubic Bézier curves because the core primitive. Whereas a few of the codecs present different fundamental graphics like circles, and many others, these are all simply wrappers on prime of cubic Bézier curve approximations.

[2] The instance is customized from https://matplotlib.org/stable/gallery/pyplots/pyplot_two_subplots.html.

[3] Alvin Penner. Becoming a cubic Bézier to a parametric perform. The Faculty Arithmetic Journal, 50(3): 185–196, 2019.

[4] Lloyd N. Trefethen. Approximation idea and approximation observe. 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 way of Chebyshev enlargement and polynomial rootfinding.SIAM Journal on Numerical Evaluation, 40(5): 1666–1682, 2003.

[7] Jared Aurentz, Lloyd N. Trefethen. Chopping a Chebyshev collection. 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. Pastime, Metapost, 2024. https://www.tug.org/docs/metapost/mpman.pdf.