Summary: We consider alternate mechanisms for representing
images, particularly the use of points (and lines between those points)
to represent images.
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 the point
(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:
;;; is-point, a Boolean
;;; Postconditions:
;;; If val seems to have been produced with point, then is-point is
;;; true.
;;; Otherwise, is-point 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 two-element 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-like shape.
(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:
;;; list-of-points?
;;; Parameters:
;;; val, a Scheme value
;;; Purpose:
;;; Determine if val is a list of points.
;;; Produces:
;;; ok, a Boolean
(define list-of-points?
(lambda (val)
(or (null? val)
(and (pair? val)
(point? (car val))
(list-of-points? (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,
(connect-the-dots image points) that does
something similar. That is, it draws a line between the points, using
the current brush and color.
For example, we might draw the tree with
(connect-the-dots img tree)
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 delta-x and delta-y. Let's start
with a pair of procedures that translate points.
;;; Procedure:
;;; htrans
;;; Parameters:
;;; delta-x, a real number
;;; pt, a point
;;; Purpose:
;;; Translates the point horizontally by the specified amount.
;;; Produces:
;;; translated, a point
;;; Postconditions:
;;; (xcoord translated) = (+ (xcoord pt) delta-x)
(define htrans
(lambda (delta-x delta-y pt)
(point (+ (xcoord pt) delta-x) (ycoord pt))))
;;; Procedure:
;;; vtrans
;;; Parameters:
;;; delta-y, a real number
;;; pt, a point
;;; Purpose:
;;; Translates the point vertically by the specified amount.
;;; Produces:
;;; translated, a point
;;; Postconditions:
;;; (ycoord translated) = (+ (xcoord pt) delta-y)
(define vtrans
(lambda (delta-x delta-y pt)
(point (xcoord pt) (+ (ycoord pt) delta-y))))
We might also write a procedure that translates both horizontally
and vertically.
;;; Procedure:
;;; translate
;;; Parameters:
;;; delta-x, a real number
;;; delta-y, a real number
;;; pt, a point
;;; Purpose:
;;; Translates the point by the specified amount.
;;; Produces:
;;; translated, a point
;;; Postconditions:
;;; (xcoord translated) = (+ (xcoord pt) delta-x)
;;; (ycoord translated) = (+ (ycoord pt) delta-y)
(define translate
(lambda (delta-x delta-y pt)
(point (+ (xcoord pt) delta-x) (+ (ycoord pt) delta-y))))
Now, it's fairly simple to translate a sequence of points: We simply
recurse through the list, applying translate at
each position.
;;; Procedure:
;;; translate-points
;;; Parameters:
;;; delta-x, a real number
;;; delta-y, 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)
;;; (list-ref translated i) =
;;; (translate delta-x delta-y (list-ref points i))
(define translate-points
(lambda (delta-x delta-y points)
(if (null? points)
null
(cons (translate delta-x delta-y (car points))
(translate-points delta-x delta-y (cdr points))))))
Once we've defined this procedure, we can draw a sequence of trees.
(define draw-forest
(lambda (image)
(set-brush "Circle (05)")
(set-fgcolor DARK_GREEN)
(connect-the-dots image tree)
(connect-the-dots image (translate-points 20 5 tree))
(set-fgcolor GREEN)
(connect-the-dots image (translate-points 10 3 tree))
(connect-the-dots image (translate-points 30 4 tree))))
Scaling a drawing is not much different than translating. We first
define a procedure, scale, that scales
a point by
a certain amount. To scale a drawing, we apply that procedure to each
point in the drawing.
As in the case of translation, we'll write three procedures: One to
scale horizontally, one to scale vertically, and one to scale in both
directions.
;;; Procedure:
;;; hscale
;;; Parameters:
;;; scale-x, a real number
;;; pt, a point
;;; Purpose:
;;; "Scales" the point horizontally by the specified amount.
;;; Produces:
;;; scaled, a point
;;; Postconditions:
;;; (xcoord scaled) = (* (xcoord pt) scale-x)
(define hscale
(lambda (scale-x pt)
(point (* (xcoord pt) scale-x) (ycoord pt))))
;;; Procedure:
;;; vscale
;;; Parameters:
;;; scale-y, a real number
;;; pt, a point
;;; Purpose:
;;; "Scales" the point horizontally by the specified amount.
;;; Produces:
;;; scaled, a point
;;; Postconditions:
;;; (ycoord scaled) = (* (ycoord pt) scale-y)
(define vscale
(lambda (scale-x pt)
(point (xcoord pt) (* (ycoord pt) scale-y))))
;;; Procedure:
;;; scale
;;; Parameters:
;;; scale-x, a real number
;;; scale-y, a real number
;;; 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) scale-x)
;;; (ycoord scaled) = (* (ycoord pt) scale-y)
(define scale
(lambda (scale-x scale-y pt)
(point (* (xcoord pt) scale-x) (* (ycoord pt) scale-y))))
;;; Procedure:
;;; scales
;;; Parameters:
;;; scale-x, a real number
;;; scale-y, 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)
;;; (list-ref scaled i) = (scale delta-x delta-y (list-ref points i))
(define scale-points
(lambda (delta-x delta-y points)
(if (null? points)
null
(cons (scale delta-x delta-y (car points))
(scale-points delta-x delta-y (cdr points))))))
Once we've defined this procedure, we might define a variant tree with
(define tall-thin-tree (scale-points 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:
;;; vary
;;; 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 vary
(lambda (amt pt)
(point (+ (- (xcoord pt) amt) (random (+ 1 (* 2 amt))))
(+ (- (ycoord pt) amt) (random (+ 1 (* 2 amt)))))))
;;; Procedure:
;;; vary-points
;;; Parameters:
;;; amt, the amount of variance
;;; points, a list of points
;;; Purpose:
;;; Vary each point
;;; Produces:
;;; varied, a sequence of points.
(define vary-points
(lambda (amt points)
(if (null? points)
null
(cons (vary amt (car points))
(vary-points amt (cdr points))))))
We can now define a few variants of our simple tree.
(define trees (list (vary-points 2 tree)
(translate-points 20 10 (vary-points 2 tree))
(translate-points 40 0 (vary-points 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:
;;; spiral-points, 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 zig-zag.
;;; Procedure:
;;; zig-zag
;;; Parameters:
;;; n, the number of lines in the zig zag (at least 2)
;;; Purpose:
;;; Generate a series of lines for an "interesting" zig-zag figure of
;;; width approximately (20 + 2n) and height approximately 4n.
;;; Produces:
;;; zig-zag-points, a list of points
(define zig-zag
(lambda (n)
(if (<= n 0)
null
(cons (point (if (even? n) (- 20 n) (+ 20 n))
(* 4 n))
(zig-zag (- n 1))))))
We don't worry too much about the size or placement of our zig-zags 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:
;;; is-drawing, a Boolean
(define drawing?
(lambda (val)
(or (null? val)
(and (pair? val)
(list-of-points? (car val))
(drawing? (cdr val))))))
We can draw a drawing by connecting-the-dots 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
(connect-the-dots 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-drawing
;;; Parameters:
;;; delta-x, a real
;;; delta-y, 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-drawing
(lambda (delta-x delta-y drawing)
(if (null? drawing) null
(cons (translate-points delta-x delta-y (car drawing))
(translate-drawing delta-x delta-y (cdr drawing))))))
;;; Procedure:
;;; scale-drawing
;;; Parameters:
;;; scale-x, a real
;;; scale-y, 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-drawing
(lambda (scale-x scale-y drawing)
(if (null? drawing) null
(cons (scale-points scale-x scale-y (car drawing))
(scale-drawing scale-x scale-y (cdr drawing))))))
;;; Procedure:
;;; vary-drawing
;;; 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 (vary-points amt (car drawing))
(vary-drawing 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)
base-case
(do-something (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 list-of-points? and
drawing? above have the same basic structure:
(define list-pred?
(lambda (val)
(or (null? val)
(and (pair? val)
(PRED? (car val))
(list-pred? (cdr val))))))
Rather than typing the same code each time, we can write a more
generic list-of? procedure that takes both the predicate
and the list as parameters.
;;; Procedure:
;;; list-of?
;;; 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:
;;; is-list-of, a Boolean
;;; Postconditions:
;;; If val is not a list, is-list-of is #f.
;;; If (type? (list-ref val i)) is #f for some valid i, is-list-of is #f.
;;; Otherwise, is-list-of is true.
(define list-of?
(lambda (type? val)
(or (null? val)
(and (pair? val)
(type? (car val))
(list-of? type? (cdr val))))))
Now, we can define list-of-points? and drawing? in
terms of this procedure.
(define list-of-points?
(lambda (val)
(list-of? point? val)))
(define drawing?
(lambda (val)
(list-of? list-of-points? val)))
In fact, if we remember our friendly left-section procedure, we can even do
without the lambda.
(define list-of-points? (left-section list-of? point?))
(define drawing? (left-section list-of? list-of-points?))
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)
;;; (list-ref newlst i) = (proc (list-ref 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 translate-points
(lambda (delta-x delta-y points)
(map (lambda (pt) (translate delta-x delta-y pt)) points)))
(define scale-points
(lambda (scale-x scale-y points)
(map (lambda (pt) (scale scale-x scale-y pt)) points)))
(define vary-points
(lambda (amt points)
(map (lambda (pt) (vary-point amt pt)) points)))
(define translate-drawing
(lambda (delta-x delta-y drawing)
(map (lambda (points) (translate-points delta-x delta-y points) drawing))))
(define scale-drawing
(lambda (scale-x scale-y drawing)
(map (lambda (points) (scale-points scale-x scale-y points)) drawing)))
(define vary-drawing
(lambda (amt drawing)
(map (lambda (points) (vary-points amt points)) drawing)))
In fact, if we combine map with the sectioning procedures,
we can even more concisely define some procedures. For example, suppose
we want to write a procedure that shifts each point in a sequence of
points right by 3 pixels.
We might start with the following:
(define shift3
(lambda (points)
(map (lambda (pt) (htrans 3 pt)) points)))
An astute programmer might then note that the inner lambda
is just sectioning htrans. That is, it fills in one parameters
of a binary procedure. We can therefore use l-s in its place.
(define shift3
(lambda (points)
(map (l-s htrans 3) points)))
But now the outer lambda looks a whole lot like sectioning, too. In
this case, we're filling in the first parameter of map
with (l-s htrans 3). We can then rewrite the whole
thing to
(define shift3 (l-s map (l-s htrans 3)))
Experience functional programmers start with the final definition,
without going through the intermediate analysis.
The map procedure is certainly useful (in fact, it's so useful
that it's a standard Scheme procedure). For instances in which we're
building compound structures (lists of points from single points, drawings
from lists of points, perhaps even lists of lists of drawings), it may
be useful to write a version that delves more deeply into the structure.
In this case, we also need to decide when we're deep enough for the
base case.
;;; Procedure:
;;; deep-map
;;; Parameters:
;;; simple?, a unary predicate
;;; proc, a unary procedure
;;; struct, a list structure built from simple values
;;; Purpose:
;;; Build a new structure by applying proc to every simple value
;;; in struct.
;;; Produces:
;;; newstruct, a list structure built from the results of proc.
;;; Preconditions:
;;; A list structure built from simple values (LSBFSV) is either
;;; (a) a simple value (a value s.t. (simple? val) holds) or
;;; (b) A list of LSBFSVs.
;;; Postconditions:
;;; newstruct has the same shape as struct.
;;; For every position in struct, if val is the value at that position,
;;; and (simple? val) holds, then then newstruct has the value
;;; (proc val) at the same position.
(define deep-map
(lambda (simple? proc struct)
(if (simple? struct)
(proc struct)
(map (lambda (substruct) (deep-map proc leaf? substruct)) struct))))
We can use this procedure to build a version of translate
that works on points, lists of points, or even drawings.
(define translate
(lambda (delta-x delta-y tree)
(deep-map (lambda (pt)
(point (+ (xcoord pt) delta-x) (+ (ycoord pt) delta-y)))
point?
tree)))
Sunday, 4 February 2007 [Samuel A. Rebelsky]
- Created as a mostly blank document.
Tuesday, 6 February 2007 [Samuel A. Rebelsky]
;
Check with Bobby