Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!orca!mesa!rthomson
From: rthomson@mesa.dsd.es.com (Rich Thomson)
Newsgroups: comp.graphics
Subject: Re: Need info on Peano curves
Message-ID: <1991Mar12.011131.24091@dsd.es.com>
Date: 12 Mar 91 01:11:31 GMT
References: <1991Mar11.202541.2292@ms.uky.edu>
Sender: usenet@dsd.es.com
Reply-To: rthomson@dsd.es.com (Rich Thomson)
Organization: Design Systems Division, Evans & Sutherland, SLC, UT
Lines: 93
Nntp-Posting-Host: 130.187.85.21

In article <1991Mar11.202541.2292@ms.uky.edu>
	hucaby@mri.uky.edu (David Hucaby) writes:
>Does anybody have references on how to generate Peano curves
>via computer? I've found the original Peano paper, where he derives
>his space-filling curve theoretically, but haven't come across
>any modern papers so far.

L-systems can be used to generate Peano space-filling curves.
L-systems work by using a string-rewriting system.  The construction
starts with an "initiator" that is modified according to the rewrite
rules (the "generators").  Using the rules, each successive rewrite
of the string (when interpreted graphically) results in a closer
approximation to the desired Peano curve (a true rendering of the
curve would be impossible because the curve has infinite length, which
is why it fills space).

Although Przemyslaw Prusinkiewicz/Aristid Lindenmayer's book
[PL90] on L-systems discusses the fundamentals of those systems for
modelling plants, an earlier publication by Prusinkiewicz [PH89] digresses
briefly into modelling other types of structures via the same method.

Here are some "classic" space-filling curves in the notation of that
text:

    a) Peano (1890) curve

    delta=90 degrees

    Generator:	X

    Rules:	X -> XFYFX+F+YFXFY-F-XFYFX
		Y -> YFXFY-F-XFYFX+F+YFXFY

    b) Hilbert (1891) curve

    delta=90 degrees

    Generator:	X

    Rules:	X -> -YF+XFX+FY-
		Y -> +XF-YFY-FX+

    c) A square grid approximation of the Sierpinski (1912) curve

    delta=90 degrees

    Generator:	F+XF+F+XF

    Rule:	X -> XF-F+F-XF+f+XF-F+F-X

    d) Quadratic Gosper curve (Dekking 1982)

    delta=90 degrees

    Generator:	-YF

    Rules:	X -> XFX-YF-YF+FX+GX-YF-YFFX
		     +YF+FXFXYF-FX+YF+FXFX+
		     YF-FXYF-YF-FX+FX+YFYF-
		Y -> +FXFX-YF-YF+FX+FXYF+FX
		     -YFYF-FX-YF+FXYFYF-FX-
		     YFFX+FX+YF-YF-FX+FX+YFY

    [I may have made some typos on that last one ;-]

The symbols are graphically interpreted using a turtle-graphics approach
in the following way:

    F => move forward one unit.
    + => add delta to the turtle's current heading, i.e. turn
	counter-clockwise.
    - => subtract delta from the turtle's current heading, i.e. turn
	clockwise.

More details on L-systems can be found in various articles in the
literature over the years and the newly published book ``The Algorithmic
Beauty of Plants'' is the most up-to-date and detailed reference.

						-- Rich

References:

[PH89]	Przemyslaw Prusinkiewicz, James Hanan  ``Lindenmayer Systems,
    Fractals, and Plants'', Lecture Notes in Biomathematics #79,
    Springer-Verlag 1989.

[PL90]	Przemyslaw Prusinkiewicz, Aristid Lindenmayer, ``The
    Algorithmic Beauty of Plants'', Springer-Verlag 1990.
-- 
  ``Read my MIPS -- no new VAXes!!'' -- George Bush after sniffing freon
	    Disclaimer: I speak for myself, except as noted.
UUCP: ...!uunet!dsd.es.com!rthomson		Rich Thomson
ARPA: rthomson@dsd.es.com			PEXt Programmer