CSC151.01 2009F Functional Problem Solving : Readings
Primary: [Front Door] [Syllabus] - [Academic Honesty] [Instructions]
Current: [Outline] [EBoard] [Reading] [Lab] [Assignment]
Groupings: [Assignments] [EBoards] [Examples] [Exams] [Handouts] [Labs] [Outlines] [Projects] [Readings]
References: [Primary] [A-Z] - [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [CSC151.02 2009F (Weinman)] [CSC151.02 2009S (Davis)] [CSC151 2008S (Rebelsky)]
Misc: [SamR] [MediaScript] [GIMP]
Summary: We consider a very different representation of images, in which we think of an image as a drawing that can be built from other drawings.
Instead of thinking about images in terms of how we make them, we might also think of images in terms of the kinds of things that we are able to draw. For example, we might agree that a unit circle (a circle with diameter 1) is something we can draw, as is a unit square (a square with edge length 1). Why start with those two things? We have to start somewhere.
It might help to visualize these two simple drawings.
In these images, you see the unit circle and unit square (respectively) superimposed upon a simple grid. The greyish area of the grid represents the part of the coordinate system we normally use (non-negative columns, non-negative rows). The grid and greyish area are there only to provide context; they are not part of the “drawing”.
You can certainly imagine a few other simple things that one might draw.
Suppose we have something that everyone agrees can be drawn, such as the unit circle. Could we draw the same thing in a different color? Certainly. Can we draw a bigger or smaller version of the same thing? It seems like we should be able to do so.
To help us discuss these things, let's call something that can be drawn a “drawing”. So far, we know that
For example, a blue unit square is drawing, as is a unit circle scaled by a factor of 5. (The rendering intentionally cuts off part of the scaled circle , because it is so far outside of the normal image area.)
Is a red circle of diameter 4 centered at (0,0) a drawing? Yes. We can start with a unit circle centered at (0,0), scale it by 4, and recolor it red.
If we rely on the four definitions above, is a a purple circle of diameter 4 centered at (2,3) a drawing? How about a green oval centered at (0,0)? In each case of these cases, we probably have to say “No”, because we can't build either starting with the basic shapes (unit circle, unit square) and using the two operations mentioned above (recolor, scale).
At this point, you may be asking yourself, “Why are we going into such detail about these simple drawings?” You may also be asking yourself, “Why aren't things that are obviously easy to draw, like the purple circle and green oval, considered drawings?”
We are going into this detail because it's a common practice in computer science (and in many other related disciplines, such as mathematics) to formally specify the kinds of data you work with. That is, in formalizing a group of values, we often specify some basic values (such as squares and circles) and then ways they modify those basic values to create new values (recolor, scale). Our mathematician friends often describe the natural numbers (the non-negative integers) in a similar way: “Zero is a natural number. If you add one to a natural number, you get a natural number.”
There are many benefits to such formal definitions, some of which we will explore in this course. One natural benefit is it helps to ensure that everyone talking about a kind of data agrees about the form of those data.
So, why are purple circles (not centered at (0,0)) and green ovals not drawings, even though they are obviously easy to draw? Because our definition does not currently admit them. The inability to specify these natural drawings may suggest a flaw in our definition. Of course, it may also suggest a difference of opinion on what is easy to draw. (Many people can draw squares and circles on graph paper, particularly if given a straight edge and a compass. Fewer can draw ellipses and ovals.)
Since our definition is still relatively simple, let's think of ways to extend it. Our preliminary of those questions dealt with a single drawing. Suppose we had two (or more) drawings and superimposed them. Would the result be a drawing? (Looking at it another way, if someone can draw each of two separate things, can they draw one and then the other on the same sheet of paper?) Yes, it seems so.
You may be able to think of other ways we can decide whether we can draw something. For example, if we can draw something centered at one position, we can probably draw it at another position.
However, computer scientists (and some mathematicians) often find it useful to describe things in this way.
In the remainder of this reading, we'll consider how we might describe
drawings using a similar technique, using Scheme to formalize the
values and operations. That is, we'll start with some basic drawing
values and provide operations that build new drawings from old.
In particular, we'll design a drawing
data type.
(For now, the implementation of the procedures on this data type will
be concealed. As the semester progresses, we'll think about ways to
implement those procedures.)
For our initial exploration of drawings as values, we'll start with two simple drawing values: the unit circle and the unit square, both centered at (0,0), and drawn in black. Why start with these two values? They're easy to think about, easy to draw, and relatively straightforward to think about.
In Scheme, we'll represent these two values as
drawing-unit-circle
and
drawing-unit-square
. Note, these are
values, not procedures. That is, you will
not place them immediately after an open parenthesis. Rather, you will
use them in various procedures that take drawings as parameters.
drawing-unit-circle
drawing-unit-square
Could we have other basic values in addition to the unit circle and the unit square? Certainly. We might want lines, other kinds of polygons, more complex curves, and so on and so forth. However, for now, our exercises in design will involve only variations of these two values.
If all that we can draw are the unit circle and unit square, and can only
draw them in one position, we're in a bit of trouble. So let's think
of how we might vary them. Well ... both are fairly small, so we might
want to scale them. Hence, we should provide a
procedure that scales drawings. (It will scale the two basic drawings,
but as we come up with other drawings, it will scale those, too.)
That procedure will be called (drawing-scale
drawing
factor
), and, given
a drawing, will return a scaled version of the drawing.
When we scale the unit circle by 5, we can envision getting something like
(drawing-scale drawing-unit-circle 5)
Note that
does not change
the underlying drawing. Rather, it builds a new one, just like those
machines they advertise on television.
drawing-scale
To mix things up a bit, let's say that in addition to scaling drawings
in both directions (horizontally and vertically),
we can also scale them in a single direction (horizontally
or vertically). We'll call the procedures
to do so drawing-hscale
and
drawing-vscale
.
(drawing-hscale drawing-unit-circle 6)
(drawing-vscale drawing-unit-circle 4)
But we don't just want our images centered at (0,0). Hence,
we should also be able to shift them
around. We'll use (
to shift the drawing to the right (or to the
left, if drawing-hshift
drawing
amt
)amt
is negative)
and (
to
shift the drawing downward (or upward, if drawing-vshift
drawing
amt
)amt
is
negative). Once again, these don't really shift the original drawing.
Rather, they make new copies of the drawing.
We can envision shifting our unit circle right, left, up, or down.
(drawing-hshift drawing-unit-circle 1)
(drawing-hshift drawing-unit-circle 2)
(drawing-hshift drawing-unit-circle 0.5)
(drawing-hshift drawing-unit-circle -0.5)
(drawing-vshift drawing-unit-circle -0.25)
(drawing-vshift drawing-unit-circle 1.5)
We can also work with previously-created drawings. Suppose we've
defined circ
with
(define circ (drawing-scale drawing-unit-circle 5))
We can then build variants centered at (4,0) and at (0,3).
(define circ-right (drawing-hshift circ 4)) (define circ-down (drawing-vshift circ 3))
circ
circ-right
circ-down
Note that the images suggest that the first call
to drawing-hshift
on circ
does not affect the position of big-circ
. (Otherwise,
circ-down
would have been both horizontally and
vertically shifted.) Once a drawing is centered at (0,0),
it is forever centered at (0,0). To get a similar image
in another place, we must shift it.
By combining the operations we've seen so far, we can now describe drawings that consists of a single black square, a single black rectangle, a single black circle, or a single black ellipse that falls anywhere on the canvas. How do we get rectangles and ellipses? By using different horizontal and vertical scales. For example, a black ellipse of width 5 and height 3, centered at (2,1) can be built from the unit circle as follows:
>
(define sample-ellipse (drawing-vshift (drawing-hshift (drawing-vscale (drawing-hscale drawing-unit-circle 5) 3) 2) 1))
sample-ellipse
Yes, that code is a bit long. However, one of the intellectual challenges of algorithm design (and of programming) is finding creative ways to use the basic operations you've been given. A consequence is that you'll sometimes write long code. And, as you'll see in a few days, if you find you're regularly writing similar long code, there are elegant ways to combine a group of small operations into a single big operation.
Although we can describe a variety of drawings, the drawings we
can describe are still black. Let's make them a bit more lively.
In particular, let's add a procedure that recolors drawings.
(That is, makes a copy of the drawing in another color.) We'll
call that procedure (
.
drawing-recolor
drawing
newcolor
)
Our ellipse, recolored in purple, might then be rendered as follows.
(drawing-recolor sample-ellipse "purple")
Our repertoire for describing drawings has expanded significantly.
We've can now describe circles, squares, rectangles, and ellipses
in a variety of colors and at any size and any location. But a
single shape rarely makes a compelling drawing. Hence, we'll
want to combine drawings into new drawings. The procedure
(
combines drawings for us.
drawing-group
drawing1
drawing2
)
(drawing-group circ-right (drawing-recolor circ-down "red"))
Now, here's the another fun part. If we agree that a group of superimposed drawings is also a drawing, then we can do anything to that group that we did to the simpler drawings: We can recolor it, scale it, shift it, and combine it with other groups. Together, those different features will allow us to create some fairly interesting drawings. For example, once we've described a single face, we might make new copies of the face in different colors, at different locations, stretched in various ways, and so on and so forth. You'll explore these capabilities in the corresponding and subsequent labs.
As you might guess, one of the reasons we've looked at drawings in terms of operations that build new drawings from old is to encourage you to think in this new way about data. (Just as our mathematician friends think of integers in terms of a basic value and the operation that creates new integers, you can now think of drawings as basic values and operations that create new drawings.)
However, there's another reason that we like this way of describing drawings: All of the operations are pure: They do not modify the underlying value they are applied to. Rather they build new values. Contrast this to the various image operations you've learned. If you tell GIMP to switch the foreground color, GIMP's “state” changes, and the old foreground color is lost. In contrast, if you recolor a drawing, the original drawing is still in the old color. There are both advantages and disadvantages to working with pure operations, but, like working with a small set of operations, it's a useful intellectual challenge.
By the way, here's one great advantage of working with pure operations: Since the original values are still around somewhere, you never need to undo an action.
At the beginning of this reading, we noted that we often specify data types by providing the basic data values and operations that build new values from other values. Let's review the ones that we've come up with.
We have two basic drawing values.
drawing-unit-circle
is a drawing. It represents
the unit circle (diameter 1, centered at (0,0)). drawing-unit-square
is a drawing. It represents
the unit square (edge length 1, centered at (0,0)). We have a variety of procedures that operated on drawings.
d
is a drawing and
factor
is a real number, then
(drawing-scale
d
factor
)
is a drawing that represents
a scaled version of d
.
d
is a drawing and
factor
is a real number, then
(drawing-hscale
d
factor
)
is a drawing that represents
a horizontally scaled version of d
.
d
is a drawing and
factor
is a real number, then
(drawing-vscale
d
factor
)
is a drawing that represents
a vertically scaled version of d
.
d
is a drawing and
offset
is a real number, then
(drawing-hshift
d
offset
)
is a drawing that represents
d
shifted right by
offset
.
d
is a drawing and
offset
is a real number, then
(drawing-vshift
d
offset
)
is a drawing that represents
d
shifted down by
offset
.
d
is a drawing and
c
is a color, then
(drawing-recolor
d
c
)
is a drawing that represents
c
redrawn in color
c
.
d1
is a drawing and
d2
is a drawing, then
(drawing-group
d1
d2
)
is a drawing that represents
the overlay of d2
over d1
.
The procedures described above constitute a basic library for describing simple drawings composed of circles, squares, ellipses, and rectangles.
Why don't we have other procedures, such as a procedure to draw
a circle? Because we are trying to keep the set of procedures
minimal. For example, we don't have a procedure to draw a circle
because we already have a way to draw any circle: We start with
the unit circle, recolor it, shift it, and scale it. Would a
procedure make it easier to
draw circles? Certainly. However, there are may procedures that could
make drawing easier.
drawing-circle
When creating a library, a designer must balance utility, concision
of expression, and size of the library. In this particular case, we've
tried to avoid adding procedures that duplicate existing functionality.
For example, we don't need a
procedure because
anything we could do with that procedure, we can do with other procedures
(just more of them). In contrast, we need
drawing-circle
and
drawing-hshift
because no other
procedure provides the ability to shift drawings. (We've violated
the “don't duplicate functionality” principle once.
Can you tell how?)
drawing-vshift
We've chosen this minimal design because of the audience: The procedures are designed for beginning CS students. Since one of our goals for this point in your career is to help you think about combining procedures (and, soon, designing your own procedures), it makes sense to keep the library small. If we were designing the library for, say, an artist, we would provide a richer library, even if we duplicated functionality.
We now know how to describe drawings. But what
if we want to see the drawings we've described?
The procedure (
will convert a drawing to an
image that we can display. For example, we could show the simplest
circle drawing on a 100x50 canvas with
drawing->image
drawing
width
height
)
>
(image-show (drawing->image drawing-unit-circle 100 50))
Of course, the unit circle is relatively small (diameter 1), so its rendering on the 100x50 canvas is essentially invisible, even when we zoom in.
Hence, in practice, we are likely to scale drawings before rendering. Often, we start with larger building blocks, made by scaling the original images. For example, here's a circle with radius of 50.
>
(define big-circle (drawing-scale drawing-unit-circle 100))
We could easily build an image for that circle.
>
(image-show (drawing->image big-circle 100 50))
In the GIMP, we would then see something like the following.
To make a rectangle that is 50 wide and 25 high, we might write
>
(define rect (drawing-vscale (drawing-hscale drawing-unit-square 50) 25))
>
(image-show (drawing->image rect 100 50))
We can also shift the big objects we create.
In the following, low-circle
will be centered at (0,25)
and right-circle
will be centered at (60,0).
>
(define low-circle (drawing-vshift big-circle 25))
>
(define right-circle (drawing-hshift big-circle 60))
>
(image-show (drawing->image (drawing-group low-circle (drawing-recolor right-circle "red")) 100 100))
We can also build bigger ellipses. For example, here we've built an ellipse of width 50 and height 25, centered at (30,10).
>
(define new-ellipse (drawing-vshift (drawing-hshift (drawing-vscale (drawing-hscale drawing-unit-circle 50) 25) 30) 10))
>
(image-show new-ellipse 100 50)
You can also do most of the work at a small scale, and then scale everything just before rendering. In fact, that's how we generated the figures for most of this reading: We built them at the scale suggested by the code, overlaid the drawings on a simple grid, scaled the overlaid drawing, and then rendered it.
So, how does MediaScheme represent drawings internally? Usually, you shouldn't be able to tell much about how programs represent their values. However, because of a quirk in the design of MediaScheme, you can see a bit about that representation. Let's see what happens when we just ask for the unit values, but don't display them.
>
drawing-unit-circle
(drawing ellipse 0 "" -0.5 -0.5 1 1)
>
drawing-unit-square
(drawing rectangle 0 "" -0.5 -0.5 1 1)
So, we see
The parentheses make it look like a procedure call (perhaps to the
procedure drawing
). However, in this case, they are
Scheme's way of indicating that the values are grouped in a
list, a simple ordered collection of values.
You don't yet know how to work with lists, but that's okay, because
you're not intended to. It is, however, potentially useful for you
to understand the values in the lists that are used to represent
drawings. You can find that out experimentally.
Let's see what happens when we shift the unit square.
>
(drawing-hshift drawing-unit-square 5)
(drawing rectangle 0 "" 4.5 -0.5 1 1)
>
(drawing-vshift drawing-unit-square 3)
(drawing rectangle 0 "" -0.5 2.5 1 1)
Okay, it seems like the first number after the string has something to do with the horizontal position of the square and the second number after the string has something to do with the vertical position. (What particular thing it represents we'll leave as an exercise for the reader.)
Next, let's see what happens when we enlarge the unit circle.
>
(drawing-hscale drawing-unit-circle 5)
(drawing ellipse 0 "" -2.5 -0.5 5 1)
>
(drawing-vscale drawing-unit-circle 6)
(drawing ellipse 0 "" -0.5 -3.0 1 6)
>
(drawing-scale drawing-unit-circle 10)
(drawing ellipse 0 "" -5.0 -5.0 10 10)
Interesting. Scaling the circle horizontally also affects the value that has to do with the horizontal position, and it also affects the third value after the string. Scaling the circle vertically affects the value that has to do with the vertical position, and also affects the fourth value after the string. In particular, it looks like the third value after the string is the width and the fourth value is the height.
Now, what about that 0 and the empty string? What else can we do with drawings? The only other thing we know how to do is to recolor them, so perhaps one has to do with the color. Let's see ...
>
(drawing-recolor drawing-unit-square "red")
(drawing rectangle 16711680 "" -0.5 -0.5 1 1)
>
(drawing-recolor drawing-unit-square "blue")
(drawing rectangle 255 "" -0.5 -0.5 1 1)
>
(drawing-recolor drawing-unit-circle "purple")
(drawing ellipse 8388736 "" -0.5 -0.5 1 1)
Okay, that first number seems to represent the color, but using some very strange numbering system.
What about that string? Well, it turns out the string is used in procedures that we have not yet taught you, so let's just leave it alone for now.
Why look at these internal issues? One key reason is that it's sometimes easier to understand what the transformations do by looking at the representation, rather than trying to understand the displayed image.
Primary: [Front Door] [Syllabus] - [Academic Honesty] [Instructions]
Current: [Outline] [EBoard] [Reading] [Lab] [Assignment]
Groupings: [Assignments] [EBoards] [Examples] [Exams] [Handouts] [Labs] [Outlines] [Projects] [Readings]
References: [Primary] [A-Z] - [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [CSC151.02 2009F (Weinman)] [CSC151.02 2009S (Davis)] [CSC151 2008S (Rebelsky)]
Misc: [SamR] [MediaScript] [GIMP]
Copyright (c) 2007-9 Janet Davis, Matthew Kluber, Samuel A. Rebelsky, and Jerod Weinman. (Selected materials copyright by John David Stone and Henry Walker and used by permission.)
This material is based upon work partially supported by the National Science Foundation under Grant No. CCLI-0633090. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
This work is licensed under a Creative Commons
Attribution-NonCommercial 2.5 License. To view a copy of this
license, visit http://creativecommons.org/licenses/by-nc/2.5/
or send a letter to Creative Commons, 543 Howard Street, 5th Floor,
San Francisco, California, 94105, USA.