Fundamentals of Computer Science I (CS151.01 2006F)
[Skip to Body]
Primary:
[Front Door]
[Syllabus]
[Glance]
[Search]

[Academic Honesty]
[Instructions]
Current:
[Outline]
[EBoard]
[Reading]
[Lab]
[Homework]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Projects]
[Readings]
Reference:
[Scheme Report (R5RS)]
[Scheme Reference]
[DrScheme Manual]
Related Courses:
[CSC151.02 2006F (Davis)]
[CSCS151 2005S (Stone)]
[CSC151 2003F (Rebelsky)]
[CSC153 2004S (Rebelsky)]
This reading is also available in PDF.
Summary: We consider some new techniques for making and modifying simple drawings.
Code: You can find most of the procedures discussed herein
in drawing.scm
.
Contents:
As you may have noted, it is a bit difficult to make drawings in DrScheme that we can replicate, scale, and place at different positions in the image. We have experimented with parameterized drawings, in which we can set certain parameters and get different versions of the drawings. However, such drawings required significant effort on our part to compute the various points.
Since Scheme is so good at calculation, we should be able to use Scheme to help make different versions of images. How? We'll work in two steps: First, we'll think of a way to represent simple drawings and then we'll look at ways to manipulate those simple drawings.
If you think about how we normally draw on paper, we typically put the pen down, draw from place on the paper to place on the paper to place on the appear, pick the pen up, put it down somewhere else, draw from place to place to place again, and so on and so forth.
Let's focus on one line in that drawing. We might represent that
line as a sequence of (x,y) points. How do we represent a point?
One easy way is as a pair. For example, we might represent (10,15)
by (cons 10 15)
. We might then write some helper procedures
to go with that description.
;;; Procedure: ;;; point ;;; Parameters: ;;; x, a real number ;;; y, a real number ;;; Purpose: ;;; Build the point (x,y) ;;; Produces: ;;; pt, a point ;;; Postconditions: ;;; (xcoord pt) = x ;;; (ycoord pt) = y (define point cons) ;;; Procedure: ;;; xcoord ;;; Parameters: ;;; pt, a point ;;; Purpose: ;;; Extracts the x coordinate of a point. ;;; Produces: ;;; x, a real number ;;; Preconditions: ;;; pt was created with point. ;;; Postconditions: ;;; (xcoord (point x y)) = x (define xcoord car) ;;; Procedure: ;;; ycoord ;;; Parameters: ;;; pt, a point ;;; Purpose: ;;; Extracts the y coordinate of a point. ;;; Produces: ;;; y, a real number ;;; Preconditions: ;;; pt was created with point. ;;; Postconditions: ;;; (ycoord (point x y)) = y (define ycoord cdr) ;;; Procedure: ;;; point? ;;; Parameters: ;;; val, a Scheme value ;;; Purpose: ;;; Determine if val is a point, using our current representation. ;;; Produces: ;;; ispoint, a Boolean ;;; Postconditions: ;;; If val seems to have been produced with point, then ispoint is ;;; true. ;;; Otherwise, ispoint is false. (define point? (lambda (val) (and (pair? val) (real? (car val)) (real? (cdr val)))))
Why do we bother to define point
, xcoord
,
and ycoord
? So that if we decide to change the representation
(e.g., to use a twoelement list rather than a pair), the only code we need
to change is these three procedures. (Of course, that assumes that we only
use these procedures elsewhere, and don't rely on the underlying
representation.)
Now that we can represent individual points, we need to figure out how to represent sequences of points. The natural representation of a sequence is a list.
For example, the following defines the sequence of points for a simple, somewhat inelegant, tree.
(define tree (list (point 15 30) (point 18 14) (point 5 18) (point 8 8) (point 20 0) (point 30 2) (point 35 19) (point 23 16) (point 23 30)))
How did I decide on those points? I sketched the tree on grid paper and then found the places on the grid. You could also sketch something in the GIMP, zoom in, pick key points, and list those points. Some very talented people can just visualize points.
We won't write something that builds such lists, but we will write a predicate for such lists.
;;; Procedure: ;;; listofpoints? ;;; Parameters: ;;; val, a Scheme value ;;; Purpose: ;;; Determine if val is a list of points. ;;; Produces: ;;; ok, a Boolean (define listofpoints? (lambda (val) (or (null? val) (and (pair? val) (point? (car val)) (listofpoints? (cdr val))))))
Now, what can we do with a list of points? We could write a procedure that
takes each neighboring pair and draws a line between them. However, that
isn't necessary, as gimp.scm
contains a procedure,
(connectthedots image points)
that does
something similar. That is, it draws a line between the points, using
the current brush and color.
Now that we know how to make one drawing, what can we do with it? One possibility is to make another copy of the drawing somewhere else. It turns out that it's fairly straightforward to move a drawing: We simply move each point by the same deltax and deltay. Let's start with a procedure that translates points.
;;; Procedure: ;;; translatepoint ;;; Parameters: ;;; deltax, an integer ;;; deltay, an integer ;;; pt, a point ;;; Purpose: ;;; Translates the point by the specified amount. ;;; Produces: ;;; translated, a point ;;; Postconditions: ;;; (xcoord translated) = (+ (xcoord pt) deltax) ;;; (ycoord translated) = (+ (ycoord pt) deltay) (define translatepoint (lambda (deltax deltay pt) (point (+ (xcoord pt) deltax) (+ (ycoord pt) deltay))))
Now, it's fairly simple to translate a sequence of points: We simply
recurse through the list, applying translatepoint
at
each position.
;;; Procedure: ;;; translatepoints ;;; Parameters: ;;; deltax, a real number ;;; deltay, a real number ;;; points, a list of points ;;; Purpose: ;;; Translate all of the points by the specified amount. ;;; Produces: ;;; translated, a list of points ;;; Postconditions: ;;; For each i, 0 <= i < (length points) ;;; (listref translated i) = ;;; (translatepoint deltax deltay (listref points i)) (define translatepoints (lambda (deltax deltay points) (if (null? points) null (cons (translatepoint deltax deltay (car points)) (translatepoints deltax deltay (cdr points))))))
Once we've defined this procedure, we can draw a sequence of trees.
(define drawforest (lambda (image) (setbrush "Circle (05)") (setfgcolor DARK_GREEN) (connectthedots image tree) (connectthedots image (translatepoints 20 5 tree)) (setfgcolor GREEN) (connectthedots image (translatepoints 10 3 tree)) (connectthedots image (translatepoints 30 4 tree))))
Scaling a drawing is not much different than translating. We first
define a procedure, scalepoint
, that scales
a point by a certain amount. We then apply that procedure to each
point in the drawing.
;;; Procedure: ;;; scalepoint ;;; Parameters: ;;; scalex, an integer ;;; scaley, an integer ;;; pt, a point ;;; Purpose: ;;; "Scales" the point by the specified amount. Think of a point as ;;; representing a vector from the origin to the point; that vector ;;; has been scaled. ;;; Produces: ;;; scaled, a point ;;; Postconditions: ;;; (xcoord scaled) = (* (xcoord pt) scalex) ;;; (ycoord scaled) = (* (ycoord pt) scaley) (define scalepoint (lambda (scalex scaley pt) (point (* (xcoord pt) scalex) (* (ycoord pt) scaley)))) ;;; Procedure: ;;; scalepoints ;;; Parameters: ;;; scalex, a real number ;;; scaley, a real number ;;; points, a list of points ;;; Purpose: ;;; Scale all of the points by the specified amount. ;;; Produces: ;;; scaled , a list of points ;;; Postconditions: ;;; For each i, 0 <= i < (length points) ;;; (listref scaled i) = (scalepoint deltax deltay (listref points i)) (define scalepoints (lambda (deltax deltay points) (if (null? points) null (cons (scalepoint deltax deltay (car points)) (scalepoints deltax deltay (cdr points))))))
Once we've defined this procedure, we might define a variant tree with
(define tallthintree (scalepoints 2 5 tree))
Of course, the images made by scale and translate are nearly identical
to the original images, differing only in size or position. Can we
make more interesting changes, so that the copies are not quite the
same? Certainly, we can change the x and y coordinate of each point
by a random
amount, giving a similar but different drawing.
Here's a procedure that does just that for one point.
;;; Procedure: ;;; varypoint ;;; Parameters: ;;; amt, the amount of variance ;;; pt, a point ;;; Purpose: ;;; Vary the x and y coordinate of pt by a random amount. ;;; Produces: ;;; varied, a point ;;; Postconditions: ;;; (<= ( (xcoord pt) amt) (xcoord varied) (+ (xcoord pt) amt)) ;;; (<= ( (ycoord pt) amt) (ycoord varied) (+ (ycoord pt) amt)) ;;; Each point that meets those requirements is equally likely. (define varypoint (lambda (amt pt) (point (+ ( (xcoord pt) amt) (random (+ 1 (* 2 amt)))) (+ ( (ycoord pt) amt) (random (+ 1 (* 2 amt))))))) ;;; Procedure: ;;; varypoints ;;; Parameters: ;;; amt, the amount of variance ;;; points, a list of points ;;; Purpose: ;;; Vary each point ;;; Produces: ;;; varied, a sequence of points. (define varypoints (lambda (amt points) (if (null? points) null (cons (varypoint amt (car points)) (varypoints amt (cdr points))))))
We can now define a few variants of our simple tree.
(define trees (list (varypoints 2 tree) (translatepoints 20 10 (varypoints 2 tree)) (translatepoints 40 0 (varypoints 2 tree))))
We can also generate some of our drawings (or lists of points) algorithmically. For example, here's a simple procedure that draws n points on a simple spiral.
;;; Procedure: ;;; spiral ;;; Parameters: ;;; n, the number of points to draw in the spiral (90 points are needed ;;; for one loop). ;;; Purpose: ;;; Generate a list of points for a spiral ;;; Produces: ;;; spiralpoints, a list of points (define spiral (let ((scale (/ 3.14 45))) (lambda (n) (if (<= n 0) null (cons (point (* n (sin (* scale n))) (* n (cos (* scale n)))) (spiral ( n 1)))))))
We can use a similar process to draw an expanding zigzab.
;;; Procedure: ;;; zigzag ;;; Parameters: ;;; n, the number of lines in the zig zag (at least 2) ;;; Purpose: ;;; Generate a series of lines for an "interesting" zigzag figure of ;;; width approximately (20 + 2n) and height approximately 4n. ;;; Produces: ;;; zigzagpoints, a list of points (define zigzag (lambda (n) (if (<= n 0) null (cons (point (if (even? n) ( 20 n) (+ 20 n)) (* 4 n)) (zigzag ( n 1))))))
We don't worry too much about the size or placement of our zigzags and spirals, since we can always translate them or scale them.
In the sections above, we've focused on one sequence of points in a drawing. However, as we noted in the beginning, a drawing is really a sequence of sequences. That is, you draw the first sequence, move the pen somewhere else, draw another sequence, move the pen somewhere else, draw another sequence, and so on and so forth. Hence, we should really represent each drawing as a list of lists of points. We'll begin with the predicate.
;;; Procedure: ;;; drawing? ;;; Parameters: ;;; val, a Scheme value ;;; Purpose: ;;; Determine if val is a drawing. ;;; Produces: ;;; isdrawing, a Boolean (define drawing? (lambda (val) (or (null? val) (and (pair? val) (listofpoints? (car val)) (drawing? (cdr val))))))
We can draw a drawing by connectingthedots for each line.
;;; Procedure: ;;; draw ;;; Parameters: ;;; image, an image ;;; drawing, a drawing ;;; Purpose: ;;; Draws the drawing. ;;; Produces: ;;; (nothing) ;;; Preconditions: ;;; (none) ;;; Postconditions: ;;; The drawing has been done in the current brush and color (define draw (lambda (image drawing) (if (not (null? drawing)) (begin (connectthedots image (car drawing)) (draw image (cdr drawing))))))
Now, we can do the same things with a drawing that we do with a sequence of points (or with a point): translate it or scale it (or both).
;;; Procedure: ;;; translate ;;; Parameters: ;;; deltax, a real ;;; deltay, a real ;;; drawing, a drawing (a list of lists of points) ;;; Purpose: ;;; Translate the drawing by the specified amount. ;;; Produces: ;;; translated, a translated version of the drawing (define translate (lambda (deltax deltay drawing) (if (null? drawing) null (cons (translatepoints deltax deltay (car drawing)) (translate deltax deltay (cdr drawing)))))) ;;; Procedure: ;;; scale ;;; Parameters: ;;; scalex, a real ;;; scaley, a real ;;; drawing, a drawing (a list of lists of points) ;;; Purpose: ;;; Scale the drawing by the specified amount. ;;; Produces: ;;; scaled, a scaled version of the drawing (define scale (lambda (scalex scaley drawing) (if (null? drawing) null (cons (scalepoints scalex scaley (car drawing)) (scale scalex scaley (cdr drawing)))))) ;;; Procedure: ;;; vary ;;; Parameters: ;;; amt, an integer ;;; drawing, a drawing (a list of lists of points) ;;; Purpose: ;;; Vary the drawing by the specified amount. ;;; Produces: ;;; varied, a randomly modified version of the drawing. (define vary (lambda (amt drawing) (if (null? drawing) null (cons (varypoints amt (car drawing)) (vary amt (cdr drawing))))))
One mark of successful programmers is that they identify and remember common techniques for solving problems. Such abstractions of common structures for solving problems are often called patterns or design patterns. You should already have begun to identify some patterns. For example, you know that procedures almost always have the form
(define procname (lambda (parameters) body))
You may also have a pattern in mind for the typical recursive procedure over lists:
(define procname (lambda (lst) (if (null? lst) basecase (dosomething (car lst) (procname (cdr lst))))))
In some languages, these patterns are simply guides to programmers as they design new solutions. In other languages, such as Scheme, you can often encode a design pattern in a separate procedure.
Here's one common pattern. Often, we want to check a list to make sure that
all of the elements of the list are of a certain type (or otherwise meet a
particular predicate). For example, both listofpoints?
and
drawing?
above have the same basic structure:
(define listpred? (lambda (val) (or (null? val) (and (pair? val) (PRED? (car val)) (listpred? (cdr val))))))
Rather than typing the same code each time, we can write a more
generic listof?
procedure that takes both the predicate
and the list as parameters.
;;; Procedure: ;;; listof? ;;; Parameters: ;;; type?, a predicate ;;; val, a Scheme value ;;; Purpose: ;;; Verify that val is a list of values and that type? holds for each ;;; value in the list. ;;; Produces: ;;; islistof, a Boolean ;;; Postconditions: ;;; If val is not a list, islistof is #f. ;;; If (type? (listref val i)) is #f for some valid i, islistof is #f. ;;; Otherwise, islistof is true. (define listof? (lambda (type? val) (or (null? val) (and (pair? val) (type? (car val)) (listof? type? (cdr val))))))
Now, we can define listofpoints?
and drawing?
in
terms of this procedure.
(define listofpoints? (lambda (val) (listof? point? val))) (define drawing? (lambda (val) (listof? listofpoints? val)))
In fact, if we remember our friendly leftsection procedure, we can even do without the lambda.
(define listofpoints? (leftsection listof? point?)) (define drawing? (leftsection listof? listofpoints?))
Here's another common pattern. Let's consider the procedures we've defined above. Do some of them have a common form? Yes. Most of the procedures (except the point procedures) recurse over a list, building a new list by applying a procedure to each value in the original list. If we ignore the other parameters, we can write this as
(define procname (lambda (lst) (if (null? lst) null (cons (modify (car lst)) (procname (cdr lst))))))
Now, if we make modify a parameter to this pattern, we can
define the pattern as a procedure. This pattern is typically called
map
;;; Procedure: ;;; map ;;; Parameters: ;;; proc, a procedure that takes one parameter and returns one value ;;; lst, a list of values ;;; Purpose: ;;; Builds a list by applying proc to each value in lst. ;;; Produces: ;;; newlst, a list of values. ;;; Preconditions: ;;; proc can be applied ot each value in lst. ;;; Postconditions: ;;; (length newlst) = (length lst) ;;; For each i, 0 <= i < (length lst) ;;; (listref newlst i) = (proc (listref lst i )) (define map (lambda (proc lst) (if (null? lst) null (cons (proc (car lst)) (map proc (cdr lst))))))
Once we've defined map
, we can define each of the preceding
recursive procedures using map
(define translatepoints (lambda (deltax deltay points) (map (lambda (pt) (translatepoint deltax deltay pt)) points))) (define scalepoints (lambda (scalex scaley points) (map (lambda (pt) (scalepoint scalex scaley pt)) points))) (define varypoints (lambda (amt points) (map (lambda (pt) (varypoint amt pt)) points))) (define translate (lambda (deltax deltay drawing) (map (lambda (points) (translatepoints deltax deltay points) drawing)))) (define scale (lambda (scalex scaley drawing) (map (lambda (points) (scalepoints scalex scaley points)) drawing))) (define vary (lambda (amt drawing) (map (lambda (points) (varypoints amt points)) drawing)))
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/History/Readings/drawing.html
.
[Skip to Body]
Primary:
[Front Door]
[Syllabus]
[Glance]
[Search]

[Academic Honesty]
[Instructions]
Current:
[Outline]
[EBoard]
[Reading]
[Lab]
[Homework]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Projects]
[Readings]
Reference:
[Scheme Report (R5RS)]
[Scheme Reference]
[DrScheme Manual]
Related Courses:
[CSC151.02 2006F (Davis)]
[CSCS151 2005S (Stone)]
[CSC151 2003F (Rebelsky)]
[CSC153 2004S (Rebelsky)]
Disclaimer:
I usually create these pages on the fly
, which means that I rarely
proofread them and they may contain bad grammar and incorrect details.
It also means that I tend to update them regularly (see the history for
more details). Feel free to contact me with any suggestions for changes.
This document was generated by
Siteweaver on Thu Nov 30 21:43:44 2006.
The source to the document was last modified on Tue Oct 31 17:10:26 2006.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2006F/Readings/drawing.html
.
You may wish to validate this document's HTML ; ;
Samuel A. Rebelsky, rebelsky@grinnell.eduhttp://creativecommons.org/licenses/bync/2.5/
or send a letter to Creative Commons, 543 Howard Street, 5th Floor,
San Francisco, California, 94105, USA.