<< . .

. 17
( : 45)



. . >>

precontrol
What is the length of ˜subpath (2.718, 3.142) of p™ ?
interpath
interpolate between paths
Besides ˜point t of p™, allows you to speak of ˜postcontrol t of p™
Knuth, D E
and ˜precontrol t of p™; this gives access to the control points of a path. Let Knuth, J C
valentine
p = z0 . . controls u0 and v1 . . z1 etc. zn’1 . . controls un’1 and vn . . zn . heart

If t < n, postcontrol t of p is the ¬rst control point in subpath (t, n) of p; if t ≥ n,
postcontrol t of p is zn . If t > 0, precontrol t of p is the last control point in subpath (0, t)
of p; if t ¤ 0, precontrol t of p is z0 . In particular, if t is an integer, postcontrol t of p
is ut for 0 ¤ t < n, and precontrol t of p is vt for 0 < t ¤ n.
The ability to extract key points and control points makes it possible to de¬ne
™s interpath function, which
interesting operations such as plain
allows you to interpolate between paths. For example, ˜interpath (1/3, p, q)™ will produce
a path of length n whose points are 1/3[point t of p, point t of q] for 0 ¤ t ¤ n, given
any paths p and q of length n. It can be de¬ned by a fairly simple program:
vardef interpath (expr a, p, q) =
for t = 0 upto length p ’ 1: a[point t of p, point t of q]
. . controls a[postcontrol t of p, postcontrol t of q]
and a[precontrol t + 1 of p, precontrol t + 1 of q] . . endfor
if cycle p: cycle % assume that p, q are both cycles or both noncycles
else: a[point in¬nity of p, point in¬nity of q] ¬ enddef ;
On February 14, 1979, the author bought a box of chocolates and placed the
box on a piece of graph paper (after suitably disposing of the contents). The
experimental data gathered in this way led to a “de¬nitive” heart shape:
heart = (100, 162) . . (140, 178){right } . . (195, 125){down }
. . (100, 0){curl 0} . . {up }(5, 125) . . {right }(60, 178) . . (100, 162);
It is interesting to interpolate between heart and other paths, by using a program like
for n = 0 upto 10: draw interpath (n/10, p, heart ); endfor.
For example, the left illustration below was obtained by taking
p = (100, 0) - - (300, 0) - - (200, 0) - - (100, 0) - - (0, 0) - - (’100, 0) - - (100, 0);
notice that interpath doesn™t necessarily preserve smoothness at the key points. The
right illustration was obtained by duplicating point (100, 0) in heart (thereby making
it a path of length 7) and taking
p = (100, 200) - - (200, 200) - - (200, 100)
- - (200, 0) - - (0, 0) - - (0, 100) - - (0, 200) - - (100, 200).




(Figure 14bb&cc will be inserted here; too bad you can™t see it now.)
Chapter 14: Paths 135


Plain allows you to say ˜direction t of p™ in order to determine the direction
directiontime
direction in which path p is moving at time t. This is simply an abbreviation
dir
for ˜(postcontrol t of p) ’ (precontrol t of p)™. Sometimes a path veers abruptly and has angle
no unique direction; in this case the direction function gives a result somewhere between epsilon
directionpoint
the two possible extremes. For example, the heart path above turns a corner at time 3; fullcircle
˜direction 3 of heart ™ turns out to be (’93.29172, 0), but ˜direction 3 ’ epsilon of heart ™
is (’46.64589, ’31.63852) and ˜direction 3 + epsilon of heart ™ is (’46.64589, 31.63852).

Conversely, can tell you when a path heads in a given direction.
You just ask for ˜directiontime w of p™, where w is a direction vector and p is
a path. This operation is best understood by looking at examples, so let™s resume our
dialog with the computer by applying to the ˜expr™ ¬le as in Chapter 8.
When ¬rst says ˜gimme™, our opening strategy this time will be to type

hide(p3 = (0,0){right}..{up}(1,1)) p3

so that we have a new path to play with. Now the fun begins:

You type And the result is
directiontime right of p3 0
directiontime up of p3 1
directiontime down of p3 -1
directiontime (1,1) of p3 0.5
directiontime left of reverse p3 1
direction directiontime (1,2) of p3 of p3 (0.23126,0.46251)
directiontime right of subpath(epsilon,1) of p3 0
directiontime right of subpath(2epsilon,1)of p3 -1
directiontime (1,1) of subpath(epsilon,1) of p3 0.49998
direction epsilon of p3 (0.55226,0)
direction 2epsilon of p3 (0.55229,0.00003)
directiontime dir 30 of p3 0.32925
angle direction 0.32925 of p3 29.99849
angle direction 0.32925+epsilon of p3 30.00081
directionpoint up of p3 (1,1)

Note that directiontime yields ’1 if the speci¬ed direction doesn™t occur. At time
epsilon , path p3 is still traveling right, but at time 2epsilon it has begun to turn
upward. The ˜directionpoint™ operation is analogous to directiontime, but it gives the
point on the path rather than the time of arrival.

You type And the result is
directiontime up of fullcircle 0
directiontime left of fullcircle 2
directiontime right of fullcircle 6
directiontime (-1,1) of fullcircle 1
directiontime (epsilon,infinity) of fullcircle 8
136 Chapter 14: Paths


directiontime right of unitsquare 0 unitsquare
cusp
directiontime up of unitsquare 1 strange
turning numbers
directiontime (1,1) of unitsquare 1
tension
directiontime (-1,1) of unitsquare 2 posttension
pretension
If a path travels in a given direction more than once, directiontime reports only the ¬rst intersection
halfcircle
time. The unitsquare path has sharp turns at the corners; directiontime considers that
all directions between the incoming and outgoing ones are instantaneously present.
It™s possible to construct pathological paths in which unusual things happen.
For example, the path p = (0, 0) . . controls (1, 1) and (0, 1) . . (1, 0) has a
“cusp” at time 0.5, when it comes to a dead stop and turns around. (If you ask
for ˜direction 0.5 of p™, the answer is zero, while direction 0.5 ’ of p is (0, 2 ) and
direction 0.5 + of p is (0, ’2 ).) The directiontime operation assumes that all possible
directions actually occur when a path comes to a standstill, hence ˜directiontime right
of p™ will be 0.5 in this case even though it might be argued that p never turns to the
right. Paths with cusps are numerically unstable, and they might become “strange”
after transformations are applied, because rounding errors might change their turning
numbers. The path p in this example has control points that correspond to tensions of
only 0.28 with respect to the initial and ¬nal directions; since insists that
tensions be at least 0.75, this anomalous path could never have arisen if the control
points hadn™t been given explicitly.
EXERCISE 14.15
Write macros called posttension and pretension that determine the e¬ective
tensions of a path™s control points at integer times t. For example, ˜pretension 1
of (z0 . . tension ± and β . . z1 )™ should be β (approximately). Test your macro by
computing posttension 0 of ((0, 0){right } . . . {up }(1, 10)).
We have now discussed almost all of the things that can do
with paths; but there™s one more important operation to consider, namely
intersection. Given two paths p and q, you can write
p intersectiontimes q
and the result will be a pair of times (t, u) such that point t of p ≈ point u of q. For
example, using the expr routine,
You type And the result is
unitsquare intersectiontimes fullcircle (0.50002,0)
unitsquare intersectiontimes fullcircle rotated 90 (0.50002,6)
reverse unitsquare intersectiontimes fullcircle (0.50002,2)
fullcircle intersectiontimes unitsquare (0,0.50002)
halfcircle rotated 45 intersectiontimes unitsquare (1,3.5)
halfcircle rotated 89 intersectiontimes unitsquare (0.02196,3.5)
halfcircle rotated 90 intersectiontimes unitsquare (0,3.50002)
halfcircle rotated 91 intersectiontimes unitsquare (-1,-1)
halfcircle rotated 45 intersectiontimes fullcircle (0,1)
fullcircle intersectiontimes (-0.5,0) (4,0)
Chapter 14: Paths 137


unitsquare intersectionpoint fullcircle (0.5,0) intersectionpoint
tertiary level
reverse unitsquare intersectionpoint fullcircle (0,0.5) precedence
Quick
Notice that the result is (’1, ’1) if the paths don™t intersect. The last two examples il- shu¬„ed binary
Journal of Algorithms
lustrate the ˜intersectionpoint™ operator, which yields the common point of intersection.
logo
Both intersectiontimes and intersectionpoint apply at the tertiary level of precedence, Knuth, J C
hence parentheses were not needed in these examples.

EXERCISE 14.16
J. H. Quick (a student) wanted to construct a path r that started on some
previously de¬ned path p and proceeded up to the point where it touched another
path q, after which r was supposed to continue on path q. So he wrote

path r; numeric t, u; (t, u) = p intersectiontimes q;
r = subpath (0, t) of p & subpath (u, in¬nity ) of q;

but it didn™t work. Why not?

If the paths intersect more than once, has a somewhat peculiar
way of deciding what times (t, u) should be reported by ˜p intersectiontimes q™.
Suppose p has length m and q has length n. (Paths of length 0 are ¬rst changed into
motionless paths of length 1.) proceeds to examine subpath (k, k + 1) of p
versus subpath (l, l + 1) of q, for k = 0, . . . , m ’ 1 and l = 0, . . . , n ’ 1, with l varying
most rapidly. This reduces the general problem to the special case of paths of length 1,
and the times (t, u) for the ¬rst such intersection found are added to (k, l). But within
paths of length 1 the search for intersection times is somewhat di¬erent: Instead of
reporting the “lexicographically smallest” pair (t, u) that corresponds to an intersection,
¬nds the (t, u) whose “shu¬„ed binary” representation (.t1 u1 t2 u2 . . . )2 is
minimum, where (.t1 t2 . . . )2 and (.u1 u2 . . . )2 are the radix-2 representations of t and u.

EXERCISE 14.17
(A mathematical puzzle.) The path p = (0, 0) . . controls (2, 2) and (0, 1) . .
(1, 0) loops on itself, so there are times t < u such that point t of p ≈ point u of p.
Devise a simple way to compute (t, u) in a program, without using the
subpath operation.

Let™s conclude this chapter by applying what we™ve learned about paths to a
real-life example. The Journal of Algorithms has been published since 1980
by Academic Press, and its cover page carries the following logo, which was designed
by J. C. Knuth to blend with the style of type used elsewhere on that page:




(Figure 14dd will be inserted here; too bad you can™t see it now.)




A program to produce this logo will make it possible for the editors of the
journal to use it on letterheads in their correspondence. Here is one way to do the job,
138 Chapter 14: Paths


without needing to erase anything: superellipse
whatever
beginchar ("A", 29mm #, 25mm #, 0); thick # := 2mm #; thin # := 5/4mm #; rotatedaround
1
re¬‚ectedabout
de¬ne whole blacker pixels(thick , thin );
2
forsu¬xes
forsu¬xes $ = a, b, c: transform $;
3 penstroke
range
forsu¬xes e = l, r: path $e, $ e; numeric t$[ ]e; endfor endfor
4
thru
penpos1 (thick , 0); penpos2 (thick , 90); penpos3 (thick , 180); penpos4 (thick , 270);
5
penpos5 (thick , 0); penpos6 (thick , 90); penpos7 (thick , 180); penpos8 (thick , 270);
6
x2 = x4 = x6 = x8 = .5[x5 , x7 ] = .5w; x1r = w; x3r = 0; x5 ’ x7 = y6 ’ y8 ;
7
y1 = y3 = y5 = y7 = .5[y6 , y8 ] = .5h; y2r = h; y4r = 0; y6r = .75h;
8
forsu¬xes e = l, r: a.e = b e = c e = superellipse (z1e , z2e , z3e , z4e , .75);
9
a e = b.e = c.e = superellipse (z5e , z6e , z7e , z8e , .72); endfor
10
penposa1 (thin , 0); penposa5 (whatever , ’90); penposa9 (thin , 180);
11
xa1l ’ xa9l = 1/3(x5l ’ x7l ); xa5 = .5w; ya1 = ya9 ; ya5r = 4/7h;
12
xa3l = xa1l ; xa3r = xa1r ; xa4r = 1/6[xa3r , x1l ]; x0 = .5w; y0 = .52h;
13
xa6l + xa4l = xa6r + xa4r = xa7l + xa3l = xa7r + xa3r = xa9 + xa1 = w;
14
ya3r = ya4r = ya6r = ya7r = .2[y2l , y0 ]; ya3l = ya4l = ya6l = ya7l = ya3r ’ thin ;
15
za4l = za4r + (thin , 0) rotated(angle(za4r ’ za5r ) + 90)
16
+ whatever — (za4r ’ za5r ); za4l ’ za5l = whatever — (za4r ’ za5r );
17
z = a.r intersectionpoint (z0 - - (w, 0)); ya1 ’ ya5 = length(z ’ z0 );
18
b = identity shifted (0, y0 ’ ya1 ) rotatedaround(z0 , 90 ’ angle(z0 ’ (w, 0)));
19
c = b re¬‚ectedabout (z2 , z4 );
20
for n = 1, 3, 4, 5, 6, 7, 9: forsu¬xes e = l, , r: forsu¬xes $ = b, c:
21
z$[n]e = za[n]e transformed $; endfor endfor endfor
22
forsu¬xes e = l, r: forsu¬xes $ = a, b, c:
23
z$2e = $r intersectionpoint (z$1e - - z$3e );
24
z$8e = $r intersectionpoint (z$9e - - z$7e );
25
t$1e = xpart($e intersectiontimes (z$1l - - z$3l ));
26
t$9e = xpart($e intersectiontimes (z$9l - - z$7l ));
27
t$4e = xpart($ e intersectiontimes (z$5r - - z$4l ));
28
t$6e = xpart($ e intersectiontimes (z$5r - - z$6l )); endfor endfor
29
penstroke subpath(ta9e , tb6e ) of a.e;
30
penstroke subpath(tb4e , tc4e ) of b e;
31
penstroke subpath(tc6e , ta1e + 8) of c e;
32
penstroke subpath(ta6e , tb9e ) of a e;
33
penstroke subpath(tb1e , tc1e ) of b.e;
34
penstroke subpath(tc9e , ta4e + 8) of c.e;
35
forsu¬xes $ = a, b, c: penlabels($1, $2, $3, $4, $5, $6, $7, $8, $9);
36
penstroke z$2e - - z$3e - - z$4e - - z$5e - - z$6e - - z$7e - - z$8e ; endfor
37
penlabels(range 0 thru 8); endchar;
38

Lines 5“10 of this program de¬ne the main superellipses of the ¬gure. The outer
superellipse is eventually drawn as three separate strokes in lines 30“32, and the inner
one is drawn as three strokes in lines 33“35. The rest of the ¬gure consists of three
arrows, whose point labels are prefaced by the respective labels a, b, c. Lines 11“18
de¬ne the ˜a™ arrow; then lines 19“22 transform these points into the ˜b™ and ˜c™ arrows,
anticipating some of the things we shall discuss in Chapter 15. Thirty-six intersections
between arrows and superellipses are computed in lines 23“29, and the arrows are ¬nally
drawn by the penstrokes speci¬ed in lines 36“37.
Chapter 14: Paths 139


El Palo Alto
FONT
Giotto
RUSKIN




(Figure 14e will be inserted here; too bad you can™t see it now.)




The route is indicated by dots,
the days™ journeys are expressed by numbers,
and letters are used to locate notable places and sites.
. . . We arrived at the Arroyo de San Francisco,
beside which stream is the redwood tree I spoke of yesterday;
I measured its height with the Graphometer
and reckoned it to be ¬fty yards high, more or less.
” FRAY PEDRO FONT, Diary (1776)

The practical teaching of the masters of Art was summed by the O of Giotto.
” JOHN RUSKIN, The Cestus of Aglaia (1865)
(page 140)




15
Transformations
Chapter 15: Transformations 141


Points, paths, pens, and pictures can be shifted, scaled, rotated, and revamped transformations
shifted
in a variety of ways. Our aim in this chapter will be to learn all about the built- scaled
in metamorphoses of , because they can make programs simpler and xscaled
yscaled
more versatile. slanted
The basic transformations have already appeared in many examples, but rotated
zscaled
let™s start by reviewing them here: rotatedaround
re¬‚ectedabout
(x, y) shifted (a, b) = (x + a, y + b); transformed
transform
(x, y) scaled s = (sx, sy);
equations
(x, y) xscaled s = (sx, y); identity
(x, y) yscaled s = (x, sy);
(x, y) slanted s = (x + sy, y);
= (x cos θ ’ y sin θ, x sin θ + y cos θ);
(x, y) rotated θ
= (xu ’ yv, xv + yu).
(x, y) zscaled (u, v)
One of the nice things about is that you don™t have to remem-
ber the sine-and-cosine formulas of trigonometry; you just have to know that
˜(x, y) rotated θ™ means ˜the vector (x, y) rotated θ degrees counterclockwise
around (0, 0)™, and the computer does all the necessary calculations by itself.
The operation of zscaling may look a bit strange, but it is simply a combination
of rotating by angle (u, v) and scaling by length (u, v).
Plain provides two more transformations that are commonly
needed: You can say ˜(x, y) rotatedaround (z0 , θ)™ if you want to rotate around
point z0 instead of point (0, 0). And you can say ˜(x, y) re¬‚ectedabout (z1 , z2 )™
if you want to ¬nd the point directly opposite (x, y) on the other side of the
straight line that runs through z1 and z2 .
All of these operations are special manifestations of a single glorious
maneuver that can be written in the general form
(x, y) transformed t.
Here t is a variable (or primary expression) of type transform; it stands for any
desired sequence of shiftings, scalings, slantings, etc., all in one fell swoop.
You can give equations between transforms, just as you can give equa-
tions between other types of things in programs. Thus, for example,
you might say
transform t[ ]; t2 = t1 shifted (2, 2) rotated 30;
then an expression like ˜(x, y) transformed t1 shifted (2, 2) rotated 30™ can be
abbreviated to ˜(x, y) transformed t2 ™, which is simpler and faster.
There™s a special transform variable called identity with the amazing
property that
(x, y) transformed identity = (x, y)
for all x and y. You might think that identity is useless, since it does nothing, but
in fact it™s a natural starting point for building other transforms. For example,
142 Chapter 15: Transformations


line 19 of the program at the end of the previous chapter says show
xpart
b = identity shifted (0, y0 ’ ya1 ) rotatedaround(z0 , theta ); ypart
xypart
yxpart
this de¬nes the transform variable b to be a compound transformation that is yypart
xxpart
used on lines 21 and 22 to construct the lower left arrow as a shifted and rotated
copy of the upper arrow, in the character being drawn.
A transform variable t represents six numbers (tx , ty , txx , txy , tyx , tyy ), in
much the same way as a pair variable represents two numbers (x, y). The
general transformation ˜(x, y) transformed t™ is simply an abbreviation for

(tx + x txx + y txy , ty + x tyx + y tyy );

thus, for example, ˜txy ™ appears in the xpart of the transform as the coe¬cient of y. If
you say ˜show t™ when t is a completely unknown transform, the computer will type

>> (xpart t,ypart t,xxpart t,xypart t,yxpart t,yypart t)

just as it would type ˜>> (xpart u,ypart u)™ for a completely unknown variable u
of type pair. You can access individual components of a transform by referring to
˜xpart t™, ˜ypart t™, ˜xxpart t™, etc.

<< . .

. 17
( : 45)



. . >>