| | Name binding, Recursion, Iteration, and Continuations |
In this chapter we will give examples of recursive curves. The examples are taken from the ECIU material on recursion [eciu-recursion] which we have mentioned earlier on.
The primary value of this chapter is the animations, which show the building of the Hilbert Curves. These animations must be approached in the web version of the material.
12.1. Hilbert Curves
Contents Up Previous Next Slide Subject index Program index Exercise index
|
| Figure 12.1 A hilbert curve of order 5 which is traversed repeatedly to emphasize the maze. The view enforced on you through this picture is an iterative one: We traverse the curve one edge after the other. Needless to tell, this gives a very confusing and complicated understanding of the curve. Below, we will explain the curve in recursive terms. It turns out that this will be key to understanding the curve. Relative to the Scheme program shown later, this curve is produced by the call (hilbert 5 'up) . |
The path taken by a Hilbert Curve appears as a sequence - or a certain iteration - of up, down, left, and right.
|
12.2. Building Hilbert Curves of order 1
Contents Up Previous Next Slide Subject index Program index Exercise index
A Hilbert Curve of order 1 is composed of four Hilbert Curves of order 0 connected by three connector lines. A Hilbert Curve of order 0 is empty |
| Figure 12.2 In the starting point we have a Hilbert Curve of order 0 - that is nothing. It is empty. For illustrative purpose, the empty Hilbert Curve of order 0 is shown as a small circle. We see how four instances (which in the starting point are overlapping in the middle of the picture) are moved to the four corners. Finally the four Curves of order 0 are connected by three connector lines. This makes up a Hilbert Curve of order 1. Relative to the Scheme program shown later, this curve can be produced by the call (hilbert 1 'up) . |
12.3. Building Hilbert Curves of order 2
Contents Up Previous Next Slide Subject index Program index Exercise index
A Hilbert Curve of order 2 is composed of four Hilbert Curves of order 1 connected by three connector lines. |
| Figure 12.3 In the starting point we have a Hilbert Curve of order 1, as constructed above. We see how four instances (which in the starting point are overlapping in the middle of the picture) are moved to the four corners. Two of them are rotated. Finally the four Curves of order 1 are connected by three connector lines. This makes up a Hilbert Curve of order 2. Relative to the Scheme program shown later, this curve is produced by the call (hilbert 2 'up) . |
12.4. Building Hilbert Curves of order 3
Contents Up Previous Next Slide Subject index Program index Exercise index
A Hilbert Curve of order 3 is composed of four Hilbert Curves of order 2 connected by three connector lines. |
| Figure 12.4 In the starting point we have a Hilbert Curve of order 2, as constructed above. We see how four instances (which in the starting point are overlapping in the middle of the picture) are moved to the four corners. Two of them are rotated. Finally the four Curves of order 2 are connected by three connector lines. This makes up a Hilbert Curve of order 3. Relative to the Scheme program shown later, this curve can be produced by the call (hilbert 3 'up) . |
12.5. Building Hilbert Curves of order 4
Contents Up Previous Next Slide Subject index Program index Exercise index
A Hilbert Curve of order 4 is composed of four Hilbert Curves of order 3 connected by three connector lines. |
| Figure 12.5 In the starting point we have a Hilbert Curve of order 3, as constructed above. We see how four instances (which in the starting point are overlapping in the middle of the picture) are moved to the four corners. Two of them are rotated. Finally the four Curves of order 3 are connected by three connector lines. This makes up a Hilbert Curve of order 4. Relative to the Scheme program shown later, this curve is produced by the call (hilbert 4 'up) . |
12.6. A program making Hilbert Curves
Contents Up Previous Next Slide Subject index Program index Exercise index
We will here discuss a concrete program which draws Hilbert Curves of order n |
The program below, Program 12.1 shows the hilbert function, which returns a rendering of Hilbert Curves.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | (define (hilbert n turn)
(cond ((= n 0) (empty-hilbert-curve))
((> n 0)
(cond
((eq? turn 'up)
(concat-path
(hilbert (- n 1) 'right)
(up-line)
(hilbert (- n 1) 'up)
(right-line)
(hilbert (- n 1) 'up)
(down-line)
(hilbert (- n 1) 'left) ))
((eq? turn 'left)
(concat-path
(hilbert (- n 1) 'down)
(left-line)
(hilbert (- n 1) 'left)
(down-line)
(hilbert (- n 1) 'left)
(right-line)
(hilbert (- n 1) 'up)))
((eq? turn 'right)
(concat-path
(hilbert (- n 1) 'up)
(right-line)
(hilbert (- n 1) 'right)
(up-line)
(hilbert (- n 1) 'right)
(left-line)
(hilbert (- n 1) 'down)))
((eq? turn 'down)
(concat-path
(hilbert (- n 1) 'left)
(down-line)
(hilbert (- n 1) 'down)
(left-line)
(hilbert (- n 1) 'down)
(up-line)
(hilbert (- n 1) 'right)))
)))) | |||
|
The actual rendering of a Hilbert Curve is done by use of SVG stuff [svg]. SVG is a W3C standard for Scalable Vector Graphics. In case you want to get started with SVG we will recommend that you start with an excellent tutorial made by Ivan Herman, F.R.A. Hopgood, and D.A. Duce [svg-tutorial].
In the web version of the material - in slide or annotated slide view - you will have access to the additional implementation details of the primitives used in Program 12.1.
| Generated: Tuesday July 2, 2013, 09:15:17 | |