Drawing space-filling curves in logo
Vladimir Batagelj
Department of mathematics, FMF,
University of Ljubljana
Jadranska 19, 1000 Ljubljana, Slovenia
email: vladimir.batagelj@uni-lj.si
Abstract
Several space-filling and related curves are described by means of "simultaneous grammars". From these descriptions it is very easy to obtain short procedures in logo for drawing the curves.
Keywords
Space-filling curves, recursion, simultaneous grammar, logo, PostScript
1 Introduction
Several procedures for drawing particular space-filiing curves have been proposed in the literature [2, 7, 10, 12, 15, 16, 13]. In this paper we propose to describe space-filling and related curves by means of "simultaneous (nonlinear) grammars". By nonlinear we mean that objects described by the grammar are not linear strings but spatial (planar) configurations; and by simultaneous we mean that at each derivation step we choose a rule and apply it simultaneously to all "nonterminal parts" of the object. For our purposes this intuitive, informal notion of simultaneous grammars is sufficient. The rules governing the growth of a considered curve reflect the recursive patterns that can be observed in the examples of the curve. From this grammatical description of the curve it is very easy to obtain the corresponding drawing procedure.
Let us work out an example in details.
2 Hilbert curve
The nonterminals are represented by an arrow and the terminals by heavy lines which remain a permanent part of the objects. The axiom AH and the rules RH1 and RH2 should be understood as embedded in the plane.
AH. | RH1. | RH2. |
We start with AH | by RH1 we obtain | and by RH2 we obtain H1 | ,but by RH1 |
and by RH2 we obtain H2 | etc. |
It is evident that we use the rule RH2 only once - at the last step of a derivation. Let hi(n) be the procedure to draw the n-th Hilbert curve Hn and ih(n) the procedure to draw Hn in the opposite direction. Then we can easily translate our description into the following logo commands:
TO Hi :n
IF :n = 0 [ STOP ]
RT 90 Ih :n - 1 FD :h LT 90 Hi :n - 1 FD :h
Hi :n - 1 LT 90 FD :h Ih :n - 1 RT 90
END
TO Ih :n
IF :n = 0 [ STOP ]
LT 90 Hi :n - 1 FD :h RT 90 Ih :n - 1 FD :h
Ih :n - 1 RT 90 FD :h Hi :n - 1 LT 90
END
Because RT a = LT -a we can, introducing another parameter :d and denoting H 1 º Hi and H -1 º Ih, combine these two commands into a single command:
TO H :d :n
IF :n = 0 [ STOP ]
RT :d*90 H (-:d) :n - 1 FD :h LT :d*90 H :d :n - 1 FD :h
H :d :n - 1 LT :d*90 FD :h H (-:d) :n - 1 RT :d*90
END
Figure 1 Hilbert curve and Peano curve
or finally, to avoid multiplication
TO Hilb :n :a :h
IF :n = 0 [ STOP ]
RT :a Hilb :n - 1 (-:a) :h FD :h LT :a Hilb :n - 1 :a :h
FD :h
Hilb :n - 1 :a :h LT :a FD :h Hilb :n - 1 (-:a) :h RT :a
END
TO Hilbert
PU SETPOS [-150 -150] PD SETPC [000 000 255]
Hilb 5 90 10
END
In a similar way we can develop drawing procedures also for the following curves. In the examples MicroSoft Windows Logo [11] is used. The PostScript pictures of space-filling curves, presented in figures, were produced by Logo2PS [1].
3 Peano curve
AP. | RP1. | RP2. | |||
RP3. | RP4. |
TO Pean :n :a :h
IF :n = 0 [STOP]
RT :a Pean :n - 1 (-:a) :h FD :h Pean :n - 1 :a :h
FD :h Pean :n - 1 (-:a) :h LT :a
END
TO Peano
PU SETPOS [ -150 -160 ] PD SETPC [255 000 000]
SetScreenColor [000 255 000] Pean 6 90 12
END
4 Grate curve
AG. | RG1. | RG2. | |||
RG3. | RG4. |
TO TWO :a :c :w
IF :c < 1 [ STOP ]
RT :a FD 1 RT :a FD :w LT :a IF :c > 1 [FD 1]
LT :a FD :w TWO :a :c - 2 :w
END
TO Square :a :h :w
FD :w TWO :a :h - 1 :w
END
TO Cag :n :a :w :h
IF :n = 0 [ Square :a :h :w STOP ]
RT :a Cag :n - 1 (-:a) :h/4 :w FD :h/8
Cag :n - 1 :a :h/4 :w FD :h/8
Cag :n - 1 (-:a) :h/4 :w LT :a
END
TO Cage
PU SETPOS [ -160 -160 ] PD SETPC [0 0 0]
SetScreenColor [255 100 100] Cag 4 90 320 320
END
Figure 2 Grate curve and Sierpinski curve.
5 Sierpinski curve
AS. | RS1. | RS2. |
TO Sierp :n :a :h :k
IF :n = 0 [ FD :k STOP ]
RT :a Sierp :n - 1 (-:a) :h :k LT :a FD :h
LT :a Sierp :n - 1 (-:a) :h :k RT :a
END
TO Sierpinski
PU SETPOS [ -160 -170 ] PD MAKE "h 12/sqrt 2
SETPC [200 000 200] SetScreenColor [255 255 000]
REPEAT 4 [ Sierp 7 45 :h 10 RT 45 FD :h RT 45 ]
SetFloodColor [000 255 000] PU SetPos [-155 -170] PD FILL
END
Figure 3 Wirth curve and Dragon curve.
6 Wirth curve
AW. | RW1. | RW2. | RW3. |
TO wi :n :a :h :k
IF :n = 0 [ FD :h STOP ]
RT :a iw :n (-:a) :h :k LT :a FD :h
LT :a iw :n (-:a) :h :k RT :a
END
TO iw :n :a :h :k
RT :a wi :n - 1 (-:a) :h :k FD :k LT 2 * :a
FD :k wi :n - 1 (-:a) :h :k RT :a
END
TO Wirth
PU SETPOS [ -155 -153 ] PD
SETPC [0 0 0] SetScreenColor [150 150 255]
REPEAT 4 [ wi 4 45 7 3 FD 3 RT 90 FD 3 ] PU
SetFloodColor [255 255 0] PU SetPos [-150 -150] PD FILL
END
7 Dragon curve
AD. | RD1. | RD2. |
TO Drag :n :a :h
IF :n < 1 [ FD :h STOP ]
Drag :n - 1 90 :h RT :a Drag :n - 1 -90 :h
END
TO Dragon
PU SETPOS [ -60 -100 ] PD LT 90
SETPC [255 000 000] SetPenSize [2 2]
Drag 11 90 7
END
8 Knuth curve
AK. | RK1. | RK2. | |||
RK3. | RK4. |
TO Knu :n :a :t :h
IF :n = 0 [ RT 45 + :t FD :h LT 45 + :t STOP ]
RT 2 * :t + :a Knu :n - 1 2 * :t (-:t) :h
RT 45 - 3 * :t - :a FD :h LT 45 - :t + :a
Knu :n - 1 0 (-:t) :h RT :a
END
TO Knuth
PU SETPOS [ 250 -130 ] PD LT 90
SETPC [255 255 255] SetScreenColor [000 000 000]
Knu 9 -90 45 8
END
Figure 4 Knuth curve and Antenna tree.
9 Antenna tree
AT. | RT1. | RT2. |
TO Tr :n :h :q
IF :n = 0 [ STOP ]
FD :h LT 90 Tr :n - 1 :q * :h :q LT 90 FD 2 * :h LT 90
Tr :n - 1 :q * :h :q LT 90 FD :h
END
TO Tree
HOME RT 90 SETPC [0 0 0] SetScreenColor [255 255 000]
Tr 10 120 1 / sqrt 2
END
A MSWLogo source file for space-filling curves is available on:
http://vlado.fmf.uni-lj.si/educa/logo/ex/mix/recurves.lgo
References