Drawing Peano Curves

(an investigation in recursion using GSP)


Peano curves are fractal-like structures that are drawn through a recursive process. I will describe the unique challenge that a curve like this presents if you wish to write a GSP script to draw it.

Let us begin by looking at a Peano curve, the curve is actually the border of the figure that you will notice. In this first sketch we see stages 1 and 4 in the construction process.

For a movie that illustrates this development click the movie button:


The challenge is to write a GSP script that will draw the successive stages of the Peano curve. To be able to do so requires a good understanding of how GSP works with recursive scripts.

What we want the script to do is: Given some seed information (A, B, C and D), draw the first stage and then repeat the process on the four corner squares in stage 1 (ie repeat the process performed on A, B, C and D on 1 a, b, c and d, 2 a, b, c and d, 3 a, b, c and d and 4 a, b, c and d) and then repeating again on all the corner squares of stage two etc. At each level of recursion the script must erase the previous stage so that it does not obscure our vision of the next stage. This last requirement - that the script must remove the previous stage is the key to the challenge.

In the words of the developer:

What you need to do is define a more complicated recursive process, in which you teach Sketchpad that each new level of recursion involves hiding the previous level. You have to define a script which fully generates two successive levels of the fractal, rather than one. (If you only generate one level, as your script does, then you only have one state for the polygon: showing or hidden. If you generate TWO levels, then you can manually demonstrate to the recording script that the levels have different visibility: i. e. that the first, or bigger, level is hidden, but the second, or smaller, level is showing.)

What's really going on is that we're exploiting a special feature of Sketchpad's recursive scripts. Normally, if a script requests the construction of a hidden object and that object just so happens to exist in the sketch already, the script won't hide it. (Presumably, if you've constructed it yourself already and left it visible, you want it visible for a reason---and scripts that incidentally construct the same object shouldn't go around hiding it on you!) However, the rules change with recursive scripts. Here, scripts won't hide a previously existing, visible object UNLESS THAT OBJECT WAS CREATED BY A PREVIOUS DEPTH OF PLAYBACK OF RECURSIVE SCRIPT ITSELF. This is precisely the rule that lets one level "hide" objects created at the previous level.

Take a look at the Sierpinski Gasket script that comes with Sketchpad's sample documents: (click here for the discussion).

Nick Jackiw (Designer, Geometer's Sketchpad)

THE PEANO CURVE SCRIPT

The script that I have written now does the following:

1) it constructs the figure shown above and constructs its interior in two stages as shown (I found it useful to fill the polygons in two stages as it helps in the later stages):



2) the script next constructs stage 2 and hides stage 1:


NOTICE, however, that in step one we have four small squares joined by an interior octagon, while in stage 2 we have four squares with points on the corners joined by an interior polygon. This sadly leads to a small irregularity in our script. We could possible overcome this irregularity by treating stage 2 as stage 1 in the construction of the script but this makes the script both very long and too demanding on memory.

THE SCRIPT


The curve after zero recursions.

The curve after three recursions.

Notice the problems of the large internal squares that have not been removed.

Notice also how the "two-stage" script which is essential for the problem introduces the problem that we cannot use it to draw the stage 0 curve.
The script can be accessed by clicking the GSP button

CONCLUSION

I hope that this discussion will help anybody who is interested in using GSP to draw recursive patterns to understand the working of the GSP script tool a little better.
 

 


Return