TUGboat, Volume 43 (2022), No. 3333

A graphical ellipse envelope construction
with GNU 3DLDF
Laurence Finston

that are not present in METAPOST, but it could
easily be adapted. For example, rotation about thez-axis could be replaced by calls to reflectedabout.
Constructing an ellipse envelope

Abstract
This article demonstrates the use of GNU 3DLDF fora graphical solution of the problem of constructing
the envelope of an ellipse and an approximation to
the curve itself.
Introduction
Before the universal availability of computers andgraphics software, technical drawings had to be madeby hand by draftsmen and -women, who were skilled
professionals. Making a technical drawing of evenmoderate complexity was time-consuming, painstaking and error-prone work, requiring much knowledge
and patience and the ability to endure frustration.
Erasures were difficult and a single error of conception or execution could render useless the work ofmany hours.
Well into the 20th century, graphical methods
for constructing curves were of importance for thecreation of technical drawings. In addition, such constructions were of central importance in the mathematics of the ancient Greeks, especially those constructions that only made use of a straight edge anddividers, with the added restriction that the use of
the dividers for measuring lengths was forbidden.
Even today, with computers and 3D graphic
software, graphical methods of constructing geometric figures retain their fascination and continue toprovide insight and diversion to those who appreciate elegant and ingenious solutions to mathematical
puzzles. In fact, the use of computers greatly increases the pleasure of creating technical drawings,
due to their speed, accuracy and the ease of making
corrections.
This article demonstrates the use of GNU 3DLDF for a graphical solution of the problem of constructing an ellipse found in Lockwood’s A Book ofCurves, p. 13 [2]. GNU 3DLDF is a package for threedimensional drawing with METAPOST and METAFONT output. It implements a language based on
the METAFONT language with many additional datatypes and operations. More information can be foundon the GNU 3DLDF website:
https://www.gnu.org/software/3dldf/LDF.html
The following figures are two-dimensional, so it
would have been possible to create them using METAPOST alone. They do use several features of 3DLDF

Draw a circle c with center C (fig. 1). AA0 is adiameter of c and S a point on AA0 . The distance
CS should be ≥ 53 CA. Q5 , Q10 and Q20 are points
on the perimeter of c such that 6 A0 SQ5 = 25◦ ,6 A0 SQ10 = 50◦ and 6 A0 SQ20 = 100◦ . R5 , R10
and R20 are points on the perimeter of c such that
6 SQ5 R5 = 6 SQ10 R10 = 6 SQ20 R20 = 90◦ . S 0 is S
rotated around C by 180◦ . That is, if xS = −k,x0S = k. S and S 0 are the foci of the ellipse.
With fixed S, as points Qx , Rx for 1 ≤ x ≤N − 1, N = 72 are added, whereby Qx and Rx areon the same side of AA0 , their intersections will form
an envelope describing an ellipse e with foci S andS 0 and major axis AA0 .

Q20
Q10
Q5
R20
A

S

C

S0

R10
R5
0

A

Fig. 1.
As points Qx and Rx are added, it becomes
clear that the intersections of the lines Qx Rx quickly
form an envelope revealing the outline of the ellipse.
(see fig. 2).
If this figure were to be drawn by hand, twolines would have to be drawn for each of the Qx Rx
pairs and the right angles 6 SQx Rx would have to beobtained. Placing a set square accurately so that Qx
and Rx were both squarely on the perimeter thirty
times would be quite a challenge.

A graphical ellipse envelope construction with GNU 3DLDF
doi.org/10.47397/tb/43-3/tb135finston-ellipse

334

Plate 1. A selection of set squares.
Assuming this feat was accomplished, the next
step would be to trace the curve of the ellipse. This
could be done with a flexible curve or a French curve.
I personally have never had good results with eitherof these tools, especially where the curvature wassmall.

TUGboat, Volume 43 (2022), No. 3
In figure 2, p29 lies in the first quadrant of theellipse, while xp30 lies in the second. It is not strictly
speaking necessary to find the intersection points px
for x > 29, since the intersection points in the first
quadrant may simply be rotated about the x- andy-axes in order to obtain points close to the ellipse in
the remaining three quadrants of e. Unless by chance,
they will not, however, be the same points that would
be found by continuing to find the intersection pointsof the lines Qx Rx .
By hand, this would be no less work than finding
p1 . . . p29 in the first place, but with the computer itis the work of a moment.
Q35 is already very close to A and Q35 R35 is not
too far from being vertical. Q36 , in fact, coincides
with A, Q36 R36 is vertical and the intersection pointT
p36 = Q36 R36 Q35 R35 doesn’t exist.
p29

p30
Q20

Q10
R30

R35
Q30

Q5
R20

Q35
A

C

R10
R5
0

A

Plate 2. A set of French curves and a flexible curve.

Fig. 2.

On the other hand, when tracing a curve approximating the ellipse using points on the envelope
using a computer, it doesn’t suffice to intuitively
recognize the rough shape of the ellipse. While it is
not necessary to find all of the intersection points
that are closest to the ellipse, it is necessary to finda sufficient number of them to trace a good approximation to the latter and to ensure that all of thepoints chosen are as close as possible to the ellipse.
FigureT 2 shows the intersectionT points p29 =Q29 R29 Q28 R28 and p30 = Q30 R30 Q29 R29 . The
T
intersection points used are thus px = Qx Rx
Qx−1 Rx−1 for x > 1.

Figure 3 shows the result of continuing to findQx and Rx , up to Q71 and R71 (Q72 , or generally
QN = A) and draw the lines Qx Rx . In this figure,some portions of the lines that converge at S havebeen erased so that the dots and labels may beseen and to avoid a large, unsightly splotch of ink
around S.
S 0 is the reflection of S about the y-axis. S and0
S are the foci of the ellipse. The major axis is AA0
but the minor axis is not so easy to determine. It is
twice the distance from C to a point w on the ellipse
on the line through C perpendicular to AA0 , to theleft of p29 and to the right of p30 , which are bothclose to the ellipse, but not actually on it. I will have

Laurence Finston

TUGboat, Volume 43 (2022), No. 3335

to give some thought to how to determine w without“cheating”.
To execute this drawing in pen-and-ink would
be a nightmare.

Qa+1 Ra+1 are closer to C than its intersection points
with other lines Qx Rx and would hence produce theclosest approximation to an ellipse. However, I would
have to think about whether I could prove this withmy limited mathematical skills.
As examples of the positions of other intersecTtion points, g43 is the intersection point Q10 R10
Q25 R25 and lies close to the perimeter of the ellipseTand g44 is the intersection point Q5 R5 Q30 R30 andlies outside c.
p25

p30
A

A0
S

p20

Q25

S0

Q10

p35
A

S

p15

p10
g44
Q5
g43
R25
R10
A0 R5
p70
0
S
p65
p60

Fig. 3.
Figure 4 shows the intersection points p10 , p15 ,. . . p70 . Clearly, the length of arc px−1 px increases
as px approaches A and decreases again as it passes
it and approaches A0 again.
The N points A, A0 and px for 0 < x < N ,N = 72, x =6 36 would normally be sufficient for
creating an ellipse object in 3DLDF, if we were toconsider them to be close enough to the ellipse to beusable, unless it were to be projected with extreme
foreshortening, which requires there to be enoughpoints on a path to prevent it from “going out of
shape” when the projected path is passed to METAPOST for displaying or printing, as explained in thearticle “An Introduction to GNU 3DLDF” (pp. 319–
332 in this issue).
It would nevertheless be somewhat unsatisfying
to have such different arc lengths depending on theposition on the circle of the points used for generating
the envelope and using points that were only close
to the ellipse inside of actually on it for the path.
Instead, 3DLDF uses the parametric equation for
an ellipse to generate the path for objects of typeellipse, i.e.,(x, y) = (a cos(t), b sin(t)) for 0 ≤ t ≤ 2π .
T
Using the intersection points px = Qx Rx
Qx−1 Rx−1 appears to produce nearly correct results. It would seem that the intersection point ofa line Qa Ra with its adjacent lines Qa−1 Ra−1 and

p40
p55
p45

p50

Fig. 4.
Figure 5 shows all of the intersection points
p1 . . . p35 , p37 . . . p71 , plus A and A0 , with A0 and thepoints with odd indices in red and A and the ones
with even indices in blue.

A graphical ellipse envelope construction with GNU 3DLDF

336

TUGboat, Volume 43 (2022), No. 3

e
q1 0

A

A0
S

S

0

A

R30
R29
q0

p30 p29

Q29
Q30

p25

p20
p15
p10
p5

C

A0

q3 0

Fig. 5.

Fig. 7.

Figure 6 shows the quarter ellipse q0 containing
points A and the intersection points p1 . . . p29 . This
figure also shows that Q29 R29 and Q30 R30 intersect
at p30 .

Q29
Q30

A

p30 p29
p25

C

R30
R29
q0

The following listings contain only the parts of the
3DLDF program for the figures in this article that areof particular interest. Labels, “bookkeeping chores”
and other items have been left out in the interest ofcomprehensibility. The full code may be found here:
https://www.gnu.org/software/3dldf/
ellipses.html#Constructions
Let’s start with some basic declarations:

p20
p15
p10
p5
A0

Fig. 6.
Figure 7 shows the completed approximation
to an ellipse ea consisting of the combination of thepaths q0 , q1 0 and q3 0 where q1 0 is the reflection of q0
about the y-axis with the order of the points reversedand q3 0 is q0 q1 0 reflected about the x-axis and withthe order of the points reversed.

Laurence Finston

The annotated GNU 3DLDF code

point p[];point R[];
point Q[];
point a[];point d[];path q[];circle c[];numeric n[];boolean b[];bool_point_vector bpv;
picture v[];

Everything here is just the same as it would
be in METAFONT except for point p[] and theother point array declarations, circle c[] andbool_point_vector bpv. point is the 3D equivalent of pair and circle is a type in 3DLDF similar
to a path, except its radius is stored as part ofthe object and there are special operations that apply to circles that don’t apply to paths, such as
get_center and the predicate is_circular.
Of course, as mentioned above, the figures in thisarticle do not require any 3D calculations and could

TUGboat, Volume 43 (2022), No. 3337

as easily have been created using METAPOST with afew changes. Nonetheless, in 3DLDF, points in space,whether two-dimensional or three-dimensional, arerepresented by objects of type point and the typepair doesn’t exist.
bool_point is a type in 3DLDF that combines aboolean and a point in a single object. bool_point
objects may be returned as the result of operations,such as intersection_point, whereby the booleanpart indicates whether a particular condition is trueor false, e.g., whether the point lies on one or bothof the paths.
bool_point_vector is a 3DLDF type containing multiple bool_point objects. It is a so-called“vector-type”. The latter are similar to arrays, e.g.,bool_point[], except that a vector-type object may
be returned as the result of an operation or operated
upon as a single object, whereas these things aren’t
possible for arrays.
c0 := unit_circle scaled (3cm, 0, 3cm)
rotated (90, 0);draw c0;
point C;C := origin;
point A;A := get_point 16 c0;
point Aprime;
Aprime := get_point 0 c0;
draw A -- Aprime;
point S;
S := mediate(A, C, .2);

unit_circle is a predefined constant of typecircle. Unlike METAFONT, where the “canonical”
unit is the pixel and METAPOST, where it is the
PostScript point or big point (1bp = 1/72 in), in 3DLDF, the canonical unit is the centimeter and thus
unit_circle has radius (not diameter!) 1cm. And
unlike fullcircle, which has 8 points in METAFONT, unit_circle has 32, thus point 16 of c0 is at
the halfway point around the circle.
32 points is normally about enough to prevent acircle from “going out of shape” when it is projectedwith a moderate amount of foreshortening. See “AnIntroduction to GNU 3DLDF” in this issue.
There are three other differences with respect
to METAFONT in this section of the code:• All of the assignments are actual assignments
using := rather than equations using =. Unfortunately, 3DLDF doesn’t (yet?) share METAFONT’s “amazing ability to deduce explicit values from implicit statements” [1, p. 83].
• get_point is the equivalent in 3DLDF of point
in METAFONT, as in hpair primaryi −→ point
hnumeric expressioni of hpath primaryi [1, p. 73].

In 3DLDF, as previously mentioned, the symbol
point is a “declarator” used to declare point
objects and its use as an operator would havecaused conflicts in the grammar generated by
the parser generator GNU Bison.
• Nor did Bison allow METAFONT’s syntax for the
mediation operation, e.g., .5[p0, p1] because
it would have conflicted with the other uses ofbrackets. Therefore, the operator mediate must
be used instead.
In 3DLDF, as in METAFONT, A’ would havebeen a valid name for a variable. However, I generally
don’t use such variable names and I thought it would
be potentially confusing, so I used Aprime instead.
numeric j;
j := 0;As in METAFONT, j could just have been usedwithout explicitly declaring it as a numeric. Doingso is considered good programming style, although it
may be overkill here and I have some doubts about
whether every member of the “programming stylepolice” actually has practical experience writing computer programs.
numeric N, k;
N := 72;
K := 360/N;
for i = 0 upto 100:
Q[i] := Aprime rotated (0, 0, 0 + (i * K));d[j] := Q[i] shifted (0, 0, 1);d[j+1] := S rotatedaround (Q[i], d[j]) 90;
bpv := (Q[i] -- d[j+1])
intersection_points c0;
a0 := bpv0;
a1 := bpv1;
if xpart a0 > xpart a1:
a2 := a0;else:
a2 := a1;fi
R[i] := a2;
j += 2;
endfor;

The loop in this section of the code is where
the real action of the program begins. Qx is foundby rotating A0 about C, the perpendicular to SQx
through Qx is found and Rx is found as the intersection point of the perpendicular with c0 withthe greatest x-coordinate. A circle and a line, that
is, a path with two points and a simple connector,
that is, one without any modifiers that would cause
it to diverge from a straight line, can have 0 to 2
intersections.

A graphical ellipse envelope construction with GNU 3DLDF

338

TUGboat, Volume 43 (2022), No. 3

Please note that this loop finds the points Qx
in a different way than in the description in section “Constructing an ellipse envelope” on page 333.
However, it is completely arbitrary how these points
are found.
Again, in most ways, the 3DLDF code would
mostly be valid in METAFONT, but there are several
important differences:
In METAFONT, rotation is about a 2D point,either the origin, with plain rotated, or about anarbitrary point with rotatedaround. In 3DLDF,
rotation is about the x-, y- and z-axes with rotatedand about an axis specified as two points with theoperator rotated_around.
METAFONT provides the primitive operationintersectiontimes and a related macro named
intersectionpoint, both of which return a single
pair as their result. Therefore, if two paths intersect
more than once, information about only one of theintersections is returned.
For 3DLDF, where geometric figures play a muchgreater role than in METAFONT, this behavior would
not be acceptable, so bool_point_vectors are usedas the type of the return values for the various operations that return intersection points or times.
The a0 := bpv0 and a1 := bpv1 statements
show that bool_points can be assigned to points,
whereby the boolean component of the bool_point
is discarded. For many but not all operations in 3DLDF, bool_points may be used in place of points.
It is worth noting that the intersection pointsof lines with each other and lines with circles in thisprogram are not found as in METAFONT. There, allpaths are implemented as Bézier curves and intersection times and points are found with a routine thatapplies to all Bézier curves, irrespective of shape.
In 3DLDF, the intersections of lines with eachother and with other geometric figures, such as circles, are used by combining and solving the implicit
equations of the figures. However, since there are
no restrictions on the transformations that can beapplied to objects in 3DLDF, they must be tested toensure that the equations still apply. For this purpose, 3DLDF implements the predicate operations
is_linear, is_circular, is_elliptical, etc.
Here is the next portion of code we’ll consider:q0 += ..;
q1 += ..;
q0 += Aprime;

This, unlike what we’ve seen before, would not
be valid METAFONT code. 3DLDF implements theoperators +=, -=, *= and /= for the operations assignment with addition, subtraction, multiplication anddivision, respectively. While 3DLDF for the most
Laurence Finston

part shares METAFONT’s scanning rules, these operators break these rules, as = belongs to category
1, + and - to category 3 and * and / to category 4[1, pp. 50–51]. However, this was easy to implement
and has never caused any problems.
Here, the connector .. is put onto paths q0 and
q1 (which start out without any points) and Aprime
is put onto q0 as its first point.
for i = 1 upto (N - 1):
if i <> 36:
p[i] := (Q[i] -- R[i])intersection_point (Q[i-1] -- R[i-1]);b[i] := p[i] rotated (0, 180);
if i < 30:
q0 += p[i];q1 += b[i];fielse:message "Skipping p36.";fi
endfor;v0 := current_picture;

A second loop findsTthe N − 2 = 70 intersection
points px = Qx Rx
Qx−1 Rx−1 for 1 ≤ x < N ,x 6= 36. Q36 R36 is skipped, because Q36 coincidesTwith A and thus Q36 R36
Q35 R35 doesn’t exist.
The intersection points are appended to q0. In
addition, they are rotated 180◦ about the y-axis
and appended to q1. Since ellipses are symmetricalabout their major and minor axes, I only have to findthe intersection points in the upper right quadrantof c0 and can rotate them into the other quadrants
instead of finding the intersection points in the latter,although that would certainly be possible with theconstruction described by Lockwood, whereby the
points would be different.
Unlike the convention in TEX and METAFONT,
where the names of macros, variables, etc., are run
together, I favor the use of the underline character in variable names. However, currentpicture
may be used as a synonym for current_picture,
rotatedaround for rotated_around, withpen forwith_pen and similarly for many other names ofoperators and predefined variables and constants.
Thus far, I have left out most of the drawing
and labelling commands. However, the following areof special interest:
undrawdot Sprime with_pen pensquarescaled (.65cm, .65cm, .65cm);
dotlabel.bot("$S’$", Sprime);
undrawdot S with_pen pencircle
scaled (.25cm, .25cm, .25cm);
drawdot S with_pen dot_pen;

TUGboat, Volume 43 (2022), No. 3

339

About S and S 0 : undrawdot uses a large circularor square pen, respectively, to clear out a space sothat the labels may be seen and, the case of S, toavoid a large splotch of black ink. In addition, aselection of lines is drawn over the white space toshow that the lines Qx Rx converge at S.
q2 := q0 .. reversed q1;
q3 := q2 rotated (180, 0);
q4 := q2 .. reversed q3;
q4 += cycle;
drawarrow q0 with_color red
with_pen medium_pen;
draw q0 .. reversed q1 .. reversed q3.. Aprime .. cycle
with_pen pencircle
scaled (2.5mm, 2.5mm, 2.5mm);
undraw q0 .. reversed q1 .. reversed q3.. Aprime .. cycle
with_pen pencircle
scaled (1.5mm, 1.5mm, 1.5mm);
drawarrow q0 with_color red;drawarrow reversed q1 with_color dark_green;
drawarrow reversed q3 with_color blue;

This is the code that draws the constructed
approximation to an ellipse ea . I’ve included thedrawing commands here because, together with theerasures above, this is a good example of technicaldrawing tasks that are trivial with the computer but
would be difficult to execute by hand and likely tocause much wailing and gnashing of teeth.
To create the black outlines of ea , it is firstdrawn using a large pencircle of 2.5mm diameter.
To compare, in technical drawings, 0.5mm is thesize used most. For example, acrylic templates fordrawing shapes are designed for use with technicalpens with 0.5mm nibs. (Other commonly available
sizes are 0.25mm, 0.7mm and 1mm.) In this article,
the “standard” pen size is 0.333mm. Then, themiddle of the curve is cleared out by undrawing itwith a pencircle of diameter 1.5mm. Finally, thepaths q0 , q1 0 and q3 0 , whereby the latter two aresimply q1 and q3 reversed, are drawn in color andwith arrows using a pencircle of diameter 0.5mm.

In METAFONT, pencircle would be scaled using a single numeric value while pensquare would
be scaled using two. In 3DLDF, a drawing commandcopies an object such as a path, associates the copy
with any items such as pens or colors that are specified in the command and puts them all together
onto a picture, current_picture by default. The
pens are only used when endfig or output causes
METAFONT or METAPOST code to be written to an
output file. They are therefore purely 2D objects.
While they may be scaled using three numerical values, in fact only the x- and y-coordinates are used
and the z-coordinate is ignored, even when the object
is projected using the parallel projection onto thex-z plane.
Since this may change in the future, it is safest
to specify all three dimensions when scaling a pen.
Acknowledgements. Many thanks to Denis Roegel
and Bogusław Jackowski for improving this article
with their corrections and suggestions.
References[1] Knuth, Donald E. The METAFONT book.
Reading, Massachusetts: Addison Wesley
Publishing Company, 1986.
[2] Lockwood, E.H. A Book of Curves. Cambridge,
UK: Cambridge University Press, 1961.
 Laurence Finston
Germany
Laurence.Finston@gmx.de

A graphical ellipse envelope construction with GNU 3DLDF