hucaby@mri.uky.edu (David Hucaby) (03/12/91)
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.
Thanks!
--
_________ David Hucaby University of Kentucky MRI Center
/ \ _ ____ 800 Rose Street, HM103
/ / /_\ \ / /___ Lexington, Kentucky 40536-0084
_____/_____/ / \ \/ /___ (606)-258-4307 hucaby@mri.uky.eduspencer@eecs.umich.edu (Spencer W. Thomas) (03/12/91)
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? A. R. Butz, "Alternative algorithm for Hilbert's space-filling curve," IEEE Trans. Comput., vol C-20, pp. 424-426, Apr. 1971. Actually, this is not quite the Peano curve, as it isn't closed. It starts in one corner of the square and ends in another. But it's pretty close. I have code that implements this in N dimensions (with the constraint that N * (the number of bits of resolution) is <= 32.) It's pretty short, I could post it if there is interest. -- =Spencer W. Thomas EECS Dept, U of Michigan, Ann Arbor, MI 48109 spencer@eecs.umich.edu 313-936-2616 (8-6 E[SD]T M-F)
stam@dgp.toronto.edu (Jos Stam) (03/12/91)
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. You can generate finer and finer approximations of the Peano curve recursively as follows: start with any segment: -------------------------- At each step recursively replace each segment by: -------- | | | | | | -------- -------- -------- | | | | | | -------- From this construction it is also easy to show that the fractal dimension of the curve is 2. (Think I've seen this construction in the "Science of Fractals", Springer-Verlag) To draw the limit curve just fill the whole screen :-) It can be shown that such curves cannot be bijective and continuous at the same time, hence a line is not homeomorphic to a plane. This intuitive sound result is however extremely hard to prove... Jos
rthomson@mesa.dsd.es.com (Rich Thomson) (03/12/91)
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
ianh@bhpmrl.oz.au (Ian Hoyle) (03/12/91)
spencer@eecs.umich.edu (Spencer W. Thomas) writes: >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? >A. R. Butz, "Alternative algorithm for Hilbert's space-filling curve," >IEEE Trans. Comput., vol C-20, pp. 424-426, Apr. 1971. >Actually, this is not quite the Peano curve, as it isn't closed. It >starts in one corner of the square and ends in another. But it's >pretty close. I have code that implements this in N dimensions (with >the constraint that N * (the number of bits of resolution) is <= 32.) >It's pretty short, I could post it if there is interest. There are a few others of interest that I know of (having also implemented Butz's algorithm as well - it is pretty quick as it uses bit operations to do it's work). Butz, A.R. "Space filling curves and mathematical programming", Information and Control, 12, 314-330 (1968) Butz, A.R. "Convergence with Hilbert's space filling curve" Journal of Computing and Systems Science, 3, 128-146 (1969) Cole, A.J. "A note on space-filling curves", Software - Practices and Experience, 13, 1181-1189 (1983) Cole, A.J. "Compaction techniques for raster scan graphics using space-filling curves", The Computer Journal, 30, 87-92 (1987) Whitten, I.H. and Wyvill, B "On the generation and use of space-filling curves", Software - practices and Experience, 6, 519-525, (1983) I am sure there are lots of others, but these might be a start for locating them. ian -- Ian Hoyle /\/\ Image Processing & Data Analysis Group / / /\ BHP Research - Melbourne Laboratories / / / \ 245 Wellington Rd, Mulgrave, 3170 / / / /\ \ AUSTRALIA \ \/ / / / \ / / / Phone : +61-3-560-7066 \/\/\/ FAX : +61-3-561-6709 E-mail : ianh@bhpmrl.oz.au