to see what V itself looks like when its edges have been sorted.) The expression

V+ V rotated 90 shifted 2right

produces an edge structure with both sorted and unsorted edges:

>> Edge structure at line 5:

row 1: 0+ 2- | 0+ 2-

row 0: 0+ 2- 0+ 1- | 0+ 1+ 2--

In general, addition of pictures is accomplished by simply combining the unsorted and

sorted edges of each row separately.

EXERCISE 13.12

Guess what will happen if you type ˜hide(cullit) currentpicture™ now; and

verify your guess by actually doing the experiment.

EXERCISE 13.13

Guess (and verify) what will happen when you type the expression

(V + V + V rotated 90 shifted 2right

- V rotated-90 shifted 2up) rotated 90.

[You must type this monstrous formula all on one line, even though it™s too long to ¬t

on a single line in this book.]

will complain that 45—¦ rotation is

If you ask for ˜V rotated 45™,

too hard. (Try it.) After all, square pixels can™t be rotated unless the angle

of rotation is a multiple of 90—¦ . On the other hand, ˜V scaled-1™ does work; you get

>> Edge structure at line 5:

row -1: 0- -2+ 0- -1+ |

row -2: 0- -2+ |

EXERCISE 13.14

Why is ˜V scaled-1™ di¬erent from ˜-V™ ?

EXERCISE 13.15

Experiment with ˜V shifted (1.5,3.14159)™ and explain what happens.

EXERCISE 13.16

Guess and verify the result of ˜V scaled 2™.

EXERCISE 13.17

Why does the machine always speak of an edge structure ˜at line 5™ ?

That completes our computer experiments. But before you log o¬, you might

want to try typing ˜totalweight V/epsilon™, just to verify that the sum of

all pixel values in V is 5.

118 Chapter 13: Drawing, Filling, and Erasing

The commands we have discussed so far in this chapter”¬ll, draw, ¬lldraw, picture command

addto command

un¬ll, etc.”are not really primitives of ; they are macros of plain

addto

, de¬ned in Appendix B. Let™s look now at the low-level operations on also

pictures that actually performs behind the scenes. Here is the syntax: addto

contour

picture command ’’ addto command | cull command addto

doublepath

addto command ’’ addto picture variable also picture expression with list

| addto picture variable contour path expression with list with clause

withpen

| addto picture variable doublepath path expression with list withweight

with list ’’ empty | with list with clause cull command

with clause ’’ withpen pen expression | withweight numeric expression cull

withweight

cull command ’’ cull picture variable keep or drop pair expression keep or drop

| cull command withweight numeric expression keeping

dropping

keep or drop ’’ keeping | dropping reverse-video

dangerous bend

The picture variable in these commands should contain a known picture; the com- currentpen

mand modi¬es that picture, and assigns the resulting new value to the variable. ¬ll

un¬ll

draw

The ¬rst form of addto command , ˜addto V also P ™, has essentially the

undraw

same meaning as ˜V := V + P ™. But the addto statement is more e¬cient, ¬lldraw

because it destroys the old value of V as it adds P ; this saves both time and space. un¬lldraw

envelope

Earlier in this chapter we discussed the reverse-video dangerous bend, which was said

to have been formed by the statement ˜currentpicture := currentpicture ’dbend ™. That

was a little white lie; the actual command was ˜addto currentpicture also ’dbend ™.

The details of the other forms of ˜addto™ are slightly more complex, but

(informally) they work like this, when V = currentpicture and q = currentpen :

Plain Corresponding primitives

¬ll c addto V contour c

contour c withweight ’1

un¬ll c addto V

draw p addto V doublepath p withpen q

doublepath p withpen q withweight ’1

undraw p addto V

¬lldraw c addto V contour c withpen q

contour c withpen q withweight ’1

un¬lldraw c addto V

The second form of addto command is ˜addto V contour p™, followed by

optional clauses that say either ˜withpen q™ or ˜withweight w™. In this case

p must be a cyclic path; each pen q must be known; and each weight w must be either

’3, ’2, ’1, +1, +2, or +3, when rounded to the nearest integer. If more than one

pen or weight is given, the last speci¬cation overrides all previous ones. If no pen is

given, the pen is assumed to be ˜nullpen™; if no weight is given, the weight is assumed

to be +1. Thus, the second form of addto command basically identi¬es a picture

variable V , a cyclic path p, a pen q, and a weight w; and it has the following meaning,

assuming that turningcheck is ¤ 0: If q is the null pen, path p is digitized and each

pixel value is increased by (j ’ k)w, where j and k are the respective numbers of

downward and upward path edges lying to the left of the pixel (as explained earlier in

this chapter). If q is not the null pen, the action is basically the same except that p

is converted to another path that “envelopes” p with respect to the shape of q; this

modi¬ed path is digitized and ¬lled as before. (The modi¬ed path may cross itself

Chapter 13: Drawing, Filling, and Erasing 119

in unusual ways, producing strange squirts of ink as illustrated earlier. But it will be convex

turningcheck

well behaved if path p de¬nes a convex region, i.e., if a car that drives counterclockwise

turning number

around p never turns toward the right at any time.) backwards path

strange path

If turningcheck > 0 when an ˜addto . . . contour™ command is being per- ¬lldraw

t

formed, the action is the same as just described, provided that path p has

ENE

a positive turning number. However, if p™s turning number is negative, the action compass directions

depends on whether or not pen q is simple or complex; a complex pen is one whose octants

NNE

boundary contains at least two points. If the turning number is negative and the pen is

NNW

simple, the weight w is changed to ’w. If the turning number is negative and the pen WNW

is complex, you get an error message about a “backwards path.” Finally, if the turning WSW

SSW

number is zero, you get an error message about a “strange path,” unless the pen is

simple and turningcheck <= 1. Plain sets turningcheck := 2; the ¬lldraw

macro in Appendix B avoids the “backwards path” error by explicitly reversing a path

whose turning number is negative.

We mentioned that the command ˜¬ll (0, 2) - - (4, 2) - - (4, 4) - - (2, 4) - -

(2, 0) - - (0, 0) - - cycle™ causes to complain about a strange path;

let™s take a closer look at the error message that you get:

> 0 ENE 1 NNE 2 (NNW WNW) WSW 3 SSW 4 WSW 5 (WNW NNW) NNE 0

! Strange path (turning number is zero).

What does this mean? The numbers represent “time” on the cyclic path, from the

starting point at time 0, to the next key point at time 1, and so on, ¬nally returning

to the starting point. Code names like ˜ENE™ stand for compass directions like “East

by North East”; decides in which of eight “octants” each part of a path

travels, and ENE stands for all directions between the angles 0—¦ and 45—¦ , inclusive. Thus,

this particular strange path starts in octant ENE at time 0, then it turns to octant NNE

after time 1. An octant name is parenthesized when the path turns through that

octant without moving; thus, for example, octants NNW and WNW are bypassed on the

way to octant WSW. It™s possible to compute the turning number from the given sequence

of octants; therefore, if you don™t think your path is really strange, the abbreviated

octant codes should reveal where has decided to take an unexpected turn.

(Chapter 27 explains more about strange paths.)

The third form of addto command is ˜addto V doublepath p™, followed

by optional clauses that de¬ne a pen q and a weight w as in the second case.

If p is not a cyclic path, this case reduces to the second case, with p replaced by the

doubled-up path ˜p & reverse p & cycle™ (unless p consists of only a single point, when

the new path is simply ˜p . . cycle™ ). On the other hand if p is a cyclic path, this

case reduces to two addto commands of the second type, in one of which p is reversed;

turningcheck is ignored during both of those commands.

An anomalous result may occur in the statement ˜draw p™ or, more generally,

in ˜addto V doublepath p withpen q™ when p is a very small cyclic path

and the current pen q is very large: Pixels that would be covered by the pen regardless

of where it is placed on p might retain their original value. If this unusual circumstance

hits you, the cure is simply to include the additional statement ˜draw z™ or ˜addto V

doublepath z withpen q™, where z is any point of p, since this will cover all of the

potentially uncovered pixels.

120 Chapter 13: Drawing, Filling, and Erasing

The cull command transforms a picture variable so that all of its pixel values cull

cullit

are either 0 or a speci¬ed weight w, where w is determined as in an addto

intersection

command. A pair of numbers (a, b) is given, where a must be less than or equal union

to b. To cull “keeping (a, b)” means that each new pixel value is w if and only if the symmetric di¬erence

selective complement

corresponding old pixel value v was included in the range a ¤ v ¤ b; to cull “dropping xor

(a, b)” means that each new pixel value is w if and only if the corresponding old pixel

value v was not in that range. Thus, for example, ˜cullit™ is an abbreviation for

cull currentpicture keeping (1, in¬nity )

or for

cull currentpicture dropping (’in¬nity , 0)

(which both mean the same thing). A more complicated example is

cull V5 dropping (’3, 2) withweight ’2;

this changes the pixel values of V5 to ’2 if they were ’4 or less, or if they were 3

or more; pixel values between ’3 and +2, inclusive, are zeroed.

A cull command must not change pixel values from zero to nonzero. For

example, doesn™t let you say ˜cull V1 keeping (0, 0)™, since that

would give a value of 1 to in¬nitely many pixels.

EXERCISE 13.18

What is the e¬ect of the following sequence of commands?

picture V [ ];

V1 = V2 = currentpicture ;

cull V1 dropping (0, 0);

cull V2 dropping (’1, 1);

currentpicture := V1 ’ V2 ;

EXERCISE 13.19

Given two picture variables V1 and V2 , all of whose pixel values are known to

be either 0 or 1, explain how to replace V1 by (a) V1 © V2 ; (b) V1 ∪ V2 ; (c) V1 • V2 .

[The intersection V1 © V2 has 1™s where V1 and V2 both are 1; the union V1 ∪ V2 has 0™s

where V1 and V2 both are 0; the symmetric di¬erence or selective complement V1 • V2

has 1™s where V1 and V2 are unequal.]

EXERCISE 13.20

Explain how to test whether or not two picture variables are equal.

EXERCISE 13.21

Look at the de¬nitions of ¬ll, draw, etc., in Appendix B and determine the

e¬ect of the following statements:

a) draw p withpen q;

b) draw p withweight 3;

c) undraw p withweight w;

¬ll c withweight ’2 withpen q;

d)

erase ¬ll c withweight 2 withpen currentpen ;

e)

f) cullit withweight 2.

Chapter 13: Drawing, Filling, and Erasing 121

EXERCISE 13.22 safe¬ll

strange path

Devise a safe¬ll macro such that ˜safe¬ll c™ increases the pixel values of

outline

currentpicture by 1 in all pixels whose value would be changed by the command ˜¬ll c™. Conway

(Unlike ¬ll, the safe¬ll command never stops with a “strange path” error; furthermore, Life

SWIFT

it never increases a pixel value by more than 1, nor does it decrease any pixel values, SUTHERLAND

even when the cycle c is quite wild.)

EXERCISE 13.23

Explain how to replace a character by its “outline”: All black pixels whose

four closest neighbors are also black should be changed to white, because they are in

the interior. (Diagonally adjacent neighbors don™t count.)

EXERCISE 13.24

In John Conway™s “Game of Life,” pixels are said to be either alive or dead.

Each pixel is in contact with eight neighbors. The live pixels in the (n + 1)st generation

are those who were dead and had exactly three live neighbors in the nth generation, or

those who were alive and had exactly two or three live neighbors in the nth generation.

Write a short program that displays successive generations on your screen.

Blot out, correct, insert, re¬ne,

Enlarge, diminish, interline;

Be mindful, when Invention fails,

To scratch your Head, and bite your Nails.

” JONATHAN SWIFT, On Poetry: A Rapsody (1733)

The understanding that can be gained from computer drawings

is more valuable than mere production.

” IVAN E. SUTHERLAND, Sketchpad (1963)

(page 122)

14

Paths

Chapter 14: Paths 123

The boundaries of regions to be ¬lled, and the trajectories of moving pens, are boundaries

trajectories

“paths” that can be speci¬ed by the general methods introduced in Chapter 3. paths

allows variables and expressions to be of type path, so that a de- quartercircle

circle

signer can build new paths from old ones in many ways. Our purpose in this halfcircle

chapter will be to complete what Chapter 3 began; we shall look ¬rst at some fullcircle

ellipse

special features of plain that facilitate the creation of paths, then we

shall go into the details of everything that knows about pathmaking.

A few handy paths have been prede¬ned in Appendix B as part of plain

, because they turn out to be useful in a variety of applications.

For example, quartercircle is a path that represents one-fourth of a circle of

diameter 1; it runs from point (0.5, 0) to point (0, 0.5). The program

beginchar ("a", 5pt #, 5pt #, 0);

pickup pencircle scaled (.4pt + blacker );

draw quartercircle scaled 10pt ; endchar;

therefore produces the character ˜ ™ in position ˜a™ of a font.

EXERCISE 14.1

Write a program that puts a ¬lled quarter-circle ˜ ™ into font position ˜b™.

EXERCISE 14.2

Why are the ˜ ™ and ˜ ™ characters of these examples only 5 pt wide and 5 pt

high, although they are made with the path ˜quartercircle scaled 10pt ™ ?

EXERCISE 14.3

Use a rotated quarter-circle to produce ˜ ™ in font position ˜c™.

EXERCISE 14.4

Use quartercircle to produce ˜ ™ in font position ˜d™.

Plain also provides a path called halfcircle that gives you

˜ ™; this path is actually made from two quarter-circles, by de¬ning

halfcircle = quartercircle & quartercircle rotated 90.

And of course there™s also fullcircle , a complete circle of unit diameter:

fullcircle = halfcircle & halfcircle rotated 180 & cycle.

You can draw a circle of diameter D centered at (x, y) by saying

draw fullcircle scaled D shifted (x, y);

similarly, ˜draw fullcircle xscaled A yscaled B™ yields an ellipse with axes A and B.

Besides circles and parts of circles, there™s also a standard square path

called unitsquare ; this is a cycle that runs from (0, 0) to (1, 0) to (1, 1) to (0, 1)

and back to (0, 0). For example, the command ˜¬ll unitsquare ™ adds 1 to a single

pixel value, as discussed in the previous chapter.

124 Chapter 14: Paths

EXERCISE 14.5

Use fullcircle and unitsquare to produce the characters ˜ ™ and ˜ ™ in font

positions ˜e™ and ˜f™, respectively. These characters should be 10 pt wide and

10 pt tall, and their centers should be 2.5 pt above the baseline.

path branch [ ], trunk ;

branch 1 = ¬‚ex ((0, 660), (’9, 633), (’22, 610))

& ¬‚ex ((’22, 610), (’3, 622), (17, 617))

& ¬‚ex ((17, 617), (7, 637), (0, 660)) & cycle;

branch 2 = ¬‚ex ((30, 570), (10, 590), (’1, 616))

& ¬‚ex ((’1, 616), (’11, 592), (’29, 576), (’32, 562))

& ¬‚ex ((’32, 562), (’10, 577), (30, 570)) & cycle;

branch 3 = ¬‚ex ((’1, 570), (’17, 550), (’40, 535))

& ¬‚ex ((’40, 535), (’45, 510), (’60, 477))

& ¬‚ex ((’60, 477), (’20, 510), (40, 512))

& ¬‚ex ((40, 512), (31, 532), (8, 550), (’1, 570)) & cycle;

branch 4 = ¬‚ex ((0, 509), (’14, 492), (’32, 481))

& ¬‚ex ((’32, 481), (’42, 455), (’62, 430))

& ¬‚ex ((’62, 430), (’20, 450), (42, 448))

& ¬‚ex ((42, 448), (38, 465), (4, 493), (0, 509)) & cycle;

branch 5 = ¬‚ex ((’22, 470), (’23, 435), (’44, 410))

& ¬‚ex ((’44, 410), (’10, 421), (35, 420))

& ¬‚ex ((35, 420), (15, 455), (’22, 470)) & cycle;

branch 6 = ¬‚ex ((18, 375), (9, 396), (5, 420))

& ¬‚ex ((5, 420), (’5, 410), (’50, 375), (’50, 350))

& ¬‚ex ((’50, 350), (’25, 375), (18, 375)) & cycle;

branch 7 = ¬‚ex ((0, 400), (’13, 373), (’30, 350))

& ¬‚ex ((’30, 350), (0, 358), (30, 350))

& ¬‚ex ((30, 350), (13, 373), (0, 400)) & cycle;

branch 8 = ¬‚ex ((50, 275), (45, 310), (3, 360))

& ¬‚ex ((3, 360), (’20, 330), (’70, 300), (’100, 266))

& ¬‚ex ((’100, 266), (’75, 278), (’60, 266))

& ¬‚ex ((’60, 266), (0, 310), (50, 275)) & cycle;

branch 9 = ¬‚ex ((10, 333), (’15, 290), (’43, 256))

& ¬‚ex ((’43, 256), (8, 262), (58, 245))

& ¬‚ex ((58, 245), (34, 275), (10, 333)) & cycle;

branch 10 = ¬‚ex ((8, 262), (’21, 249), (’55, 240))

(Figure 14a will be inserted here;

too bad you can™t see it now.)

& ¬‚ex ((’55, 240), (’51, 232), (’53, 220))

& ¬‚ex ((’53, 220), (’28, 229), (27, 235))

& ¬‚ex ((27, 235), (16, 246), (8, 262)) & cycle;

branch 11 = ¬‚ex ((0, 250), (’25, 220), (’70, 195))

& ¬‚ex ((’70, 195), (’78, 180), (’90, 170))

& ¬‚ex ((’90, 170), (’5, 188), (74, 183))

& ¬‚ex ((74, 183), (34, 214), (0, 250)) & cycle;

branch 12 = ¬‚ex ((8, 215), (’35, 175), (’72, 155))

& ¬‚ex ((’72, 155), (’75, 130), (’92, 110), (’95, 88))

& ¬‚ex ((’95, 88), (’65, 117), (’54, 104))

& ¬‚ex ((’54, 104), (10, 151), (35, 142))

. . ¬‚ex ((42, 130), (60, 123), (76, 124))

& ¬‚ex ((76, 124), (62, 146), (26, 180), (8, 215)) & cycle;

trunk = (0, 660) - - - (’12, 70) . . {curl 5}(’28, ’8)

& ¬‚ex ((’28, ’8), (’16, ’4), (’10, ’11))

& ¬‚ex ((’10, ’11), (0, ’5), (14, ’10))

& ¬‚ex ((14, ’10), (20, ’6), (29, ’11))

& (29, ’11){curl 4} . . (10, 100) - - - cycle;

Chapter 14: Paths 125

Sometimes it™s necessary to draw rather complicated curves, and plain ¬‚ex

El Palo Alto

provides a ˜¬‚ex ™ operation that can simplify this task. The construc- Stanford University

tion ˜¬‚ex (z1 , z2 , z3 )™ stands for the path ˜z1 . . z2 {z3 ’ z1 } . . z3 ™, and similarly

˜¬‚ex (z1 , z2 , z3 , z4 )™ stands for ˜z1 . . z2 {z4 ’ z1 } . . z3 {z4 ’ z1 } . . z4 ™; in general

¬‚ex (z1 , z2 , . . . , zn’1 , zn )

is an abbreviation for the path

z1 . . z2 {zn ’ z1 } . . · · · . . zn’1 {zn ’ z1 } . . zn .

The idea is to specify two endpoints, z1 and zn , together with one or more

intermediate points where the path is traveling in the same direction as the

straight line from z1 to zn ; these intermediate points are easy to see on a typical

curve, so they are natural candidates for key points.

For example, the command

¬ll ¬‚ex (z1 , z2 , z3 ) & ¬‚ex (z3 , z4 , z5 )

& ¬‚ex (z5 , z6 , z7 ) & ¬‚ex (z7 , z8 , z9 , z1 ) & cycle

will ¬ll the shape

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

after the points z1 , . . . , z9 have been suitably de¬ned. This shape occurs as

the fourth branch from the top of “El Palo Alto,” a tree that is often used to

symbolize Stanford University. The thirteen paths on the opposite page were

de¬ned by simply sketching the tree on a piece of graph paper, then reading o¬

approximate values of key points “by eye” while typing the code into a computer.

(A good radio or television program helps to stave o¬ boredom when you™re

typing a bunch of data like this.) The entire ¬gure involves a total of 47 ¬‚exes,

most of which are pretty mundane; but branch 12 does contain an interesting

subpath of the form

¬‚ex (z1 , z2 , z3 ) . . ¬‚ex (z4 , z5 , z6 ),

which is an abbreviation for

z1 . . z2 {z3 ’ z1 } . . z3 . . z4 . . z5 {z6 ’ z4 } . . z6 .

Since z3 = z4 in this example, a smooth curve runs through all six points,

although two di¬erent ¬‚exes are involved.

126 Chapter 14: Paths

Once the paths have been de¬ned, it™s easy to use them un¬ll

superellipse

to make symbols like the white-on-black medallion shown here: ellipse

superness

beginchar ("T", .5in #, 1.25in #, 0); Lam´ e

De¬ne the thirteen paths on the preceding pages ; Hein

(Figure

14aa will Gardner

¬ll superellipse ((w, .5h), (.5w, h), (0, .5h), (.5w, 0), .8); be inserted

fullcircle

here; too

branch 0 = trunk ; bad you

can™t see it

for n = 0 upto 12: now.)

un¬ll branch [n] shifted (150, 50) scaled (w/300);