For this laboratory problem, you are to implement a language similar to Henderson's, except based on triangles rather than squares. We begin by describing the implementation, and listing the procedures which should be used for this problem.

The implementation of the language is very similar to the Square-Limit language.

Points and segments

Points (vectors) are represented as pairs of numbers, and segments are represented as pairs of points, just as in the Square-Limit language. Here are the constructors and accessors for vectors and segments.

(define make-vect cons)
(define xcor car)
(define ycor cdr)
(define zero-vector (make-vect 0 0))
(define make-segment cons)
(define seg-start car)
(define seg-end cdr)

We will use the operations of vector addition, subtraction, and scaling a vector by a number.

(define (+vect v1 v2)
  (make-vect (+ (xcor v1) (xcor v2))
             (+ (ycor v1) (ycor v2))))

(define (-vect v1 v2)
  (+vect v1 (scale -1 v2)))

(define (scale x v)
  (make-vect (* x (xcor v))
             (* x (ycor v))))

(define (shift v o1 o2)
  (-vect (+vect v o1) o2))

(define (drawline start end)
  (pos-pen (xcor start) (ycor start))
  (draw-line-to (xcor end) (ycor end)))

Figure 1. Shifting a vector from one origin to another.

Triangles

(define make-triangle list)
(define origin car)
(define side1 cadr)
(define side2 caddr)

As shown in Figure 3, we can express the points of a triangle in terms of so-called triangular coordinates, which are pairs x, y such that x + y 1. Another way to say this is that each point of the triangle can be expressed as a vector

x * Side₁(Tri) + y * Side₂(Tri)

where x + y 1 and Side₁ and Side ₂ are vectors. Still another way to express this is that mapping the point in the plane whose coordinates are x, y to the point given by

Origin(Tri) + x * Side₁ (Tri) + y * Side₂ (Tri)

maps one-half of the unit square onto the given triangle.

(define (coord-map triangle)
  (lambda (point)
    (+vect
     (+vect (scale (xcor point)
                   (side1 triangle))
            (scale (ycor point)
                   (side2 triangle)))
     (origin triangle))))

Figure 2. A triangle represented as origin and two sides; triangular coordinates.

Finally, we define a standard screen-triangle, which is an isosceles triangle whose base and height are the edges of the screen:

(define screen-lower-left (make-vect east south))
(define screen-lower-right (make-vect west south))
(define screen-upper-left (make-vect  east north))

(define screen-lower-edge
  (-vect screen-lower-right screen-lower-left))

(define screen-left-edge
  (-vect screen-upper-left screen-lower-left))

(define screen-triangle
  (make-triangle screen-lower-left
                 screen-lower-edge
                 (+vect screen-left-edge
                        (scale 0.5 screen-lower-edge))))

Pictures

As in the square-limit language, a picture is a procedure, this time a procedure on triangles, which draws inside the given triangle. make-picture constructs a picture from a list of segments:

(define (make-picture seglist)
  (lambda (triangle)
    (for-eac
     (lambda (segment)
       (drawline ((coord-map triangle) (seg-start segment))
                 ((coord-map triangle) (seg-end segment))))
     seglist)))

(define (draw pict)
  (clear-graphics)
  (pict screen-triangle))

(define empty-picture (make-picture '()))

(define outline-picture
  (let ((v1 (make-vect 0 0))
        (v2 (make-vect 0 1))
        (v3 (make-vect 1 0)))
    (make-picture (list (make-segment v1 v2)
                        (make-segment v2 v3)
                        (make-segment v3 v1)))))

(define midpoints
  (let ((center (make-vect (/ 1 3) (/ 1 3)))
        (m1 (make-vect (/ 1 2) 0))
        (m2 (make-vect 0 (/ 1 2)))
        (m3 (make-vect (/ 1 2) (/ 1 2))))
    (make-picture (list (make-segment m1 center)
                        (make-segment m2 center)
                        (make-segment m3 center)))))

(define band
  (let ((a1 (make-vect .4 0))
        (a2 (make-vect .6 0))
        (b1 (make-vect 0 .4))
        (b2 (make-vect 0 .6)))
    (make-picture (list (make-segment a1 b1)
                        (make-segment a2 b2)))))

(define v-shape
  (let ((m1 (make-vect (/ 2 9) (/ 2 9)))
        (m2 (make-vect (/ 4 9) (/ 4 9)))
        (a1 (make-vect (/ 1 3) 0))
        (a2 (make-vect (/ 2 3) 0))
        (b1 (make-vect 0 (/ 1 3)))
        (b2 (make-vect 0 (/ 2 3))))
    (make-picture (list (make-segment a1 m1)
                        (make-segment m1 b1)
                        (make-segment a2 m2)
                        (make-segment m2 b2)))))

Figure 3. Sample pictures, specified using triangular coordinates.

Means of combination

We define a means of combination, called split, which takes as arguments two pictures and a ratio between 0 and 1. When given a triangle as argument, the split picture first splits the triangle by dividing side1 of the triangle as specified by the ratio . Then it draws one picture in each subtriangle, as shown in Figure 4.

Figure 4. The split combination of two pictures.

The procedure for split must compute the new origin and sides for each of the two component triangles.

(define (split pict1 pict2 ratio)
  (lambda (triangle)
    (define p (scale ratio (side1 triangle)))
    (define oa (origin triangle))
    (define ob (shift p oa zero-vector))
    (pict1 (make-triangle oa p (side2 triangle)))
    (pict2 (make-triangle ob
                 (shift (side1 triangle) oa ob)
                 (shift (side2 triangle) oa ob)))))

The second subtriangle has an origin ob at the point designated by p, and the other two vertices at the same points as the original triangle. However, according to our representation of triangles, we must express the origin in external (screen) coordinates, and express the other two vertices as offsets from the origin of the triangle. This is where shift comes in handy: With respect to the origin oa of the original triangle, the origin of our second subtriangle is given by the vector p. So to find the coordinates or ob, we shift p from the origin oa to an origin at the zero-vector. Similarly, we can find the correct side1 and side2 for the second subtriangle by using the fact that these are the vectors running from ob the the endpoints of the sides of the original triangle: With respect to the old origin oa, these are just the vectors side1 and side2 . So to find the offsets from the new origin ob, we shift side1 and side2 from oa to ob .

split illustrates a useful general method for specifying new triangles: Find the vertices of the triangle with respect to some fixed coordinate system (such as the triangle that is being decomposed); then use shift to express points in the external coordinate system (this is required when specifying an origin for a new triangle), or as offsets from a new origin (this is required when specifying the sides of a new triangle).

To do in this laboratory problem

Begin by entering all of the code listed above. You will not need to edit or modify any of it.

Part 1

Draw some pictures to test the procedures. Use split to make various combinations of the pre-defined elementary pictures.

Part 2

Use split to define an operation called push which is analogous to right-push of the square-limit language. Test your procedure by trying it out on some of the simple figures provided. Turn in a listing of the procedure.

Part 3

For this part, you are to define a rotate operator on pictures. The rotation of a picture draws the picture in the specified triangle, but rotated so that a different vertex of the triangle is taken as the origin. See Figure 5.

Here is one way to go about defining rotate: The origin of the new triangle is at the point specified by side2 of the original triangle (assuming we are rotating clockwise). So we compute this new origin by shifting side2 from the old origin to the zero vector. (Compare the above explanation of shift.) The side1 of the new triangle ends where the side2 of the original triangle ended. So we can compute the new side1 by shifting the vector side2 from the old origin to the new origin. The side2 of the new triangle ends at the origin of the old triangle. With respect to the old origin, this is the endpoint of the zero vector. So we can find the new side2 by shifting the zero vector from the old origin to the new origin. Note that in the case of an equilateral triangle, this operation simply reduces to rotating the picture about the center of the enclosing triangle. If the triangle is no equilateral, then not only does the origin change, but the picture will be compressed or stretched, depending on the difference in the lengths of the sides of the triangle.

Implement the rotate operation by competing the following definition:

(define (rotate pict)
  (lambda (triangle)
    (let ((new-origin (shift ?? ?? ??)))
      (pict (make-triangle ??
                           ??
                           ??)))))

Test rotate on some simple pictures. Note that outline-picture and midpoints won't look any different when rotated, so you should use v-shape or band to test your procedure.

Observe that, using rotate, you can also rotate a picture in the opposite direction by applying rotate twice, using repeated. (Compare the rotation operators in the square-limit language.) Turn in a listing of the rotate procedure.

Part 4

Define an operator three-fold which, given a picture, produces the superposition of three pictures - the original picture, the picture rotated once, and the picture rotated twice. (See figure 5.) Test your procedure by defining 3v and 3band to be the three-fold superpositions, respectively, of v-shape and band.

Part 5

Figure 6. illustrates a means of combination called 3split , which takes as its arguments three pictures and two numbers r and s, such that r + s 1. It combines the pictures as shown in the figure. (The orientation of the small triangles is unspecified - in implementing 3split you can choose whichever orientation you wish.)

For this part, you are to implement 3split and turn in a listing of your procedure.

This procedure can be rather tricky, especially if you are not used to expressing points in terms of vectors, so think about it carefully before you start coding. A good way to proceed is to take the central point indicated in Figure 6. as (r,s) to be the common origin of the three new triangles. Note that this point can be computed by vector-adding together the origin of the (original) triangle, the side1 scaled by r, and the side2 scaled by s. You must now determine the two sides of each of the three small triangles relative to this origin.

In writing your procedure, you can make good use of the shift procedure, as in the implementations of split and rotate discussed above. Also, a good way to test your procedure is to run it with all pictures as the outline-picture, and to draw the results.

Part 6

The following equal-split procedure uses 3split to replicate a single picture 3 times, splitting the original triangle at the point where the medians intersect (i.e., the point who triangular coordinates are (1/3, 1/3).

(define (equal-split pict)
  (3split pict pict pict (/ 1/3) (/ 1 3)))

We could imagine a generalization of equal-split, which uses the same picture three times, but with each of the small triangles rotated by applying rotate 0, 1, or 2 times, as specified. One way to do this is to define a procedure similar to equal-split, but which takes as arguments a picture, and also three numbers - each of which is 0, 1, or 2 - that specify the number of times to repeat the rotate operation in generating each picture in the small triangles. (You can use repeated to accomplish the repetitions.)

An alternative method is to use a higher-order procedure, which, given the three rotation numbers, will generate a procedure that takes a picture as argument. In other words, if we call this higher-order procedure make-splitter, then writing

(define equal-split (make-splitter  0 0 0))

should be an equivalent way to define equal-split , and

should produce a procedure that is like equal-split
, but which rotates the first and third small picture before drawing them.


For this part, you are to implement and turn in a listing of
the make-splitter procedure.  As a hint, notice the make-splitter
 will have the following form:

(define (make=splitter  r1  r2  r3)

(lambda (pict)
...))

As a test, try drawing

(define mesh   ((make-splitter  0 1 2) band))


Turn in a listing of make-splitter.

Part 7

Suppose we use 3split recursively:  split a picture
which is itself a split, and so on.  Here is an extended version of the 
equal-split procedure given above, which performs this splitting to a
specified number of levels:

(define (rec-equal-split pict levels)

(if (= levels 0)
pict
(let ((p (rec-equal-split pict (-1+ levels))))

(3split p p p (/ 1 3) (/ 1 3)))))


Now suppose we want to generalize this procedure as in 
Part 6, that is to have a higher-order procedure that will create
things like rec-equal-split, except where the splitting ratios of the
sides can be other than one-third.  We want a procedure make-rec-splitter
, such that rec-equal-split could be defined as

(define rec-equal-split (make-rec-splitter
(/ 1 3) (/ 1 3)))

Test your procedure by drawing some figures, and turn in a listing.


Part 8

The procedures of the previous parts on splitting
subdivided a triangle by choosing a central point as a common vertex for three
sub-triangles, each of which shared a common edge with the original triangle. 
Another way of subdividing a triangle is shown in Figure 7.  Here, we can 
imbed one triangle inside a second by determining vertices along each
of the three sides of the outer triangle, and adjusting the coordinates of the
inner triangle to fit those vertices.  The boundaries of two triangles will
thus share in common only the three vertices of the inner triangle.  The
resulting procedure should draw two pictures, one imbedded within the other.



Figure 7.  Using imbed to combine 2 pictures.


Write a procedure called imbed, which takes five
arguments, three parameters q, r, s,  each between 0 and 1, which
describe the ratio along the edge at which to place the vertex (see Figure 8)
and two pictures p1,  p2.  The function should have the
following form

(define (imbed q r s p1 p2)

  (lambda (tri)
     ...))

As was the case in Part 7, you should be able to
recursively apply the procedure imbed to a picture.

Turn in a listing of your procedure imbed.

Part 9

Suppose we apply procedures such as 3split, which
were written to be applied to triangular pictures, instead to pictures created
for the square limit language?  Will the procedures still work?  Why or why not?


Part 10

Suppose we decide to change the representation of vectors so
that make-vect is now defined as:

(define make-vect list)

What are the corresponding new definitions of xcor
 and ycor?  What other procedures in the triangle-drawing system
must be changed as a consequence of making this change in the representation
for vectors?

Part 11

The procedures you have implemented give you a wide choice of
things to experiment with.  For example, even if you restrict yourself to a
single picture element, and perform only 3split to three levels using
a fixed splitting point (r,s), there are still a tremendous number of
variations, since for each 3split you can choose to rotate each of
the component pictures.  Thus, each level gives you 27 choices (three
orientations for each of three pictures) and all three levels thus produces 93
possibilities, although many of these will be the same, due to symmetry of the
component figures.

There is nothing to turn in for this part of the assignment,
but we hope you will spend some time experimenting.  The patterns in Fgure 8.
were produced in just this way, using picture elements similar to the ones you
have here.  Perhaps you can discover a new kind of pattern?







Figure 8.  Tiling patterns.

Lab 27 Scheme Code