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.