Fractals

Fractals play an important role in computational geometry. Flake (The Computational Beauty of Nature, The MIT Press, 1998) says that ``geometry can be extended to account for objects with a fractional dimension. Such objects, known as fractals, come very close to capturing the richness and variety of forms found in nature. Fractals possess structural self-similarity on multiple ...\ scales, meaning that a piece of a fractal will often look like the whole.''

Figure: The Sierpinski triangle

Figure  displays an example of a fractal, widely known as the Sierpinski triangle. The basic shape is an (equilateral) triangle, as shown in the left-most picture. In the right-most example we see that the triangle is repated many times and in many sizes inside of the outermost triangle. The picture in the middle is a snapshot from the middle of the drawing process.

The middle picture also suggests what the generative step might look like. Given the three endpoints of a triangle, we draw the triangle and then compute the midpoint of each side. If we were to connect these midpoints to each other, we would divide the given triangle into four triangles. The middle picture illustrates this idea. The Sierpinski triangle is the result of repeating the process for the three outer triangles and leaving the inner one alone.

A function that draws this nest of triangles must mirror this process. Its input data must represent the triangle that we start with. The process stops when the input data specifies a triangle that is too small to be drawn. Since all of our drawing functions produce true when they are done, we agree that our Sierpinski function should also produce true.

If the given triangle is still large enough, the function must draw the triangle and possibly some nested ones. The trick is to translate the partitioning of the triangle into Scheme. Let us summarize our discussion with a skeletal Scheme definition:

;; sierpinski : posn posn posn -> true
;; to draw a Sierpinski triangle down at a, b, and c,  
;; assuming it is large enough 
(define (sierpinski a b c) 
  (cond 
    [(too-small? a b c) true] 
    [else ... (draw-triangle a b c) ... ])) 

The partitioning step requires the function to determine the three mid-points between the three end-points. Let us call these new mid-points a-b, b-c, and c-a. Together with the given endpoints, a, b, and c, they determine four triangles: a, a-b, c-a; b, a-b, b-c; c, c-a, b-c; a-b, b-c, c-a. Thus, if we wanted to create the Sierpinski triangle for, say, the first listed triangle, we would use (sierpinski a a-b c-a).

Since each midpoint is used twice, we use a local-expression to translate the generative step into Scheme. The local-expression introduces the three new midpoints. Its body contains three recursive applications of sierpinski and the draw-triangle application mentioned earlier. To combine the solutions of the three problems, we use an and-expression, which ensures that all three recursions must succeed. Figure  collects all the relevant definitions, including two small functions based on domain knowledge from geometry.

;; sierpinski : posn posn posn -> true ;; to draw a Sierpinski triangle down at a, b, and c, ;; assuming it is large enough (define (sierpinski a b c) (cond [(too-small? a b c) true] [else (local ((define a-b (mid-point a b)) (define b-c (mid-point b c)) (define c-a (mid-point a c))) (and (draw-triangle a b c) (sierpinski a a-b c-a) (sierpinski b a-b b-c) (sierpinski c c-a b-c)))])) ;; mid-point : posn posn -> posn ;; to compute the mid-point between a-posn and b-posn (define (mid-point a-posn b-posn) (make-posn (mid (posn-x a-posn) (posn-x b-posn)) (mid (posn-y a-posn) (posn-y b-posn)))) ;; mid : number number -> number ;; to compute the average of x and y (define (mid x y) (/ (+ x y) 2)) Figure: The Sierpinski algorithm

Since sierpinski is based on generative recursion, collecting the code and testing it is not the last step. We must also consider why the algorithm terminates for any given legal input. The inputs of sierpinski are three positions. The algorithm terminates if the corresponding triangle is too small. But, each recursive step subdivides the triangle so that the sum of its sides is only half of the given triangle. Hence the size of the triangles indeed decreases and sierpinski is bound to produce true.

Develop the functions

1. ;; draw-triangle : posn posn posn -> true
2. ;; too-small? : posn posn posn -> bool

Use the teachpack draw.ss to test the code. For a first test of the complete function, use the following definitions:

(define A (make-posn 200 0))
(define B (make-posn 27 300)) 
(define C (make-posn 373 300) 

Exercise 27.1.2

The process of drawing a Sierpinski triangle usually starts from an equilateral shape. To compute the endpoints of an equilateral Sierpinski triangle, we can pick a large circle and three points on the circle that are 120 degrees apart. For example, they could be at 0, 120, 240:

(define CENTER (make-posn 200 200))

(define RADIUS 200)

;; cicrcl-pt : number -> posn 
;; to compute a position on the circle with CENTER 
;; and RADIUS as defined above  
(define (circle-pt factor) ...)

(define A (circle-pt 120/360)) 
(define B (circle-pt 240/360)) 
(define C (circle-pt 360/360)) 

Hints: Recall that DrScheme's sin and cos compute the sine and cosine in terms of radians, not degrees. Also keep in mind that on-screen positions grow downwards not upwards. Solution

Exercise 27.1.3

Rewrite the function in figure  to use structures for the representation of triangles. Then apply the new function to a list of triangles and observe the effect. Solution

Exercise 27.1.4

Take a look at the following two pictures:

The left one is the basic step for the generation of the ``Savannah'' tree on the right. It is analogous to the middle picture on page . Develop a function that draws trees like the one in the right picture.

Hint: Think of the problem as drawing a straight line, given its starting point and an angle in, say, radians. Then, the generative step divides a single straight line into three pieces and uses the two intermediate points as new starting points for straight lines. The angle changes at each step in a regular manner. Solution

Exercise 27.1.5

In mathematics and computer graphics, people must often connect some given points with a smooth curve. One popular method for this purpose is due to Bezier. Here is a sequence of pictures that illustrate the idea:

For simplicity, we start with three points: p1, p2, and p3. They form the outermost triangle in all three pictures, with p1 being the left-most and p3 the right-most point.

If the triangle is small enough, draw it. It appears as a large point. If not, generate two smaller triangles as illustrated in the center picture. The outermost points, p1 and p3, remain the end points. The new center points, r2 and q2, are the midpoints between p1 and p2 and between p3 and p2, respectively. The new left-most and right-most endpoints, respectively, is the midpoint between r2 and q2.

To test the function, use the teachpack draw.ss. Here is some good test data:

(define p1 (make-posn 50 50))
(define p2 (make-posn 150 150)) 
(define p3 (make-posn 250 100))