Space Filling Curves

15_03 11/2/2007 by Don Relyea

I have been looking at the space filling curve project again recently. The top 4 new images on this page were createdwith the latest version of the algorithm.

The algorithm I used to make these images is based on the Hilbert space filling curve, discovered by mathematician David Hilbert. This version of my program is new in that it subdivides spaces within the total space to be filled and runs the algorithm to fill the smaller spaces separately. Each smaller space is centered on a point on the curve causing the smaller renderings to intersect the larger one in interesting ways.

This older space filling curve art generator (opens in a new page, shockwave 35k) in particular has been in the works since Summer 2005. I desperately need to update the algorithm in the shockwave version of this program so you can see this in action. I will I promise, hopefully soon.

Exploration of Related Points Along a Space Filling Curve #2 11/2/2007 by Don Relyea

Abstract:
Exploration of Related Points on a Space Filling Curve was created in a custom application written in Director and C++. The result is an archival Lysonic print on a full sheet of arches.
The algorithm used is based on the Hilbert space filling curve. The program recursively draws rectangles along the curve. At certain times during the execution it draws larger concentric rectangles and connects special points with trailed concentric rectangles.

Statement:
I write my own custom software applications to create generative art and video. I have spent some time mildly obsessed with infinite dimensional Euclidean space, also known as Hilbert space.

Exploration of Related Points on a Space Filling Curve was created in an application written in Director and C++. The program can generate these images with relative ease, much easier than I could by hand.

The main program algorithm is based on the Hilbert space filling curve, discovered by mathematician David Hilbert in the early 1900’s. The program recursively draws rectangles along the curve, storing special points in a lookup table. At certain times during the execution it draws larger concentric rectangles and connects the stored special points with trailed concentric rectangles. The program accesses a color theory algorithm that manages the colors used during program execution. It can output very large detailed high resolution images. In fact it can create images that are much larger than I can afford to print.

Technical Brief:
A custom application was created in Adobe Director and C++ to render this image. The algorithm is based on the Hilbert space filling curve. The program recursively draws rectangles along the curve. At certain times during the execution it draws larger concentric rectangles and connects special points along the curve with trailed concentric rectangles.

Included is the main source code below so one can see the code manifestation of the mathematics behind this work. (lingo condensed from the Adobe Shockwave version):

on hilbert_draw(x0, y0, xis, xjs, yis, yjs, n)
–/* n=number of recursions*/
–/* numsteps= number of drawing iterations between two points on the curve*/
–/* x0 and y0 are coordinates of bottom left corner */
–/* xis & xjs are the i & j components of unit x vector */
–/* similarly yis and yjs */
repeat while n > 0
hilbert_draw(x0, y0, yis/2, yjs/2, xis/2, xjs/2, n-1)
draw_from_to_numsteps( point(x0+xis/2, y0+xjs/2), point(x0+(xis+yis)/2, y0+(xjs+yjs)/2), numsteps)
hilbert_draw(x0+xis/2, y0+xjs/2 ,xis/2, xjs/2, yis/2, yjs/2, n-1)
draw_from_to_numsteps( point(x0+xis/2, y0+xjs/2), point(x0+(xis+yis)/2, y0+(xjs+yjs)/2), numsteps)
hilbert_draw(x0+xis/2+yis/2, y0+(xjs/2)+(yjs/2), xis/2, xjs/2, yis/2, yjs/2,n-1)
draw_from_to_numsteps( point(x0+(xis/2)+(yis/2), y0+(xjs/2)+(yjs/2)), point(x0+(xis+yis)/2, y0+(xjs+yjs)/2), numsteps)
hilbert_draw(x0+(xis/2)+yis, y0+(xjs/2)+yjs, -yis/2,-yjs/2, -xis/2, -xjs/2,n-1)
draw_from_to_numsteps( point(x0+xis/2+yis, y0+xjs/2+yjs), point(x0+(xis+yis)/2, y0+(xjs+yjs)/2), numsteps)
n=n-1
if n=0 then exit repeat
end repeat
end

Blue Recursive 11/1/2007 for www.nanohedron.com

New! Hilbert program output gallery! A dozen or so large images generated with tweaks of the algorithm.

Additional Background Information and Resources:
German mathematician David Hilbert discovered the curve that bears his name in the early 1900’s. It is an example of a “space-filling” curve: it literally covers every point in a square. Like all good fractals, it is generated in iterations. Hilbert with Ladders(below) is output generated from a modified Hilbert algorithm that also draws other shapes and ladders at points along the Hilbert Curve.

The Hilbert space filling curve is a one dimensional curve which visits every point within a two dimensional space. It may be thought of as the limit of a sequence of curves which are traced through the space.

The basic pattern is a curve which starts near the bottom left corner of a box and terminates near the bottom right corner. It has a kink in it, the kink takes it into the top left and top right of the box.

Professor Cumming of Napier University, Edinburgh, UK was kind enough to provide a sample function on his web site of the basic algorithm(below). With a small amount of effort I was able to get it working well. After adding several of my drawing routines to it and some tweaking I was able to get it to generate fantastic results.

procedure hilbert(x0, y0, xis, xjs, yis, yjs, n)
/* x0 and y0 are the coordinates of the bottom left corner */
/* xis & xjs are the i & j components of the unit x vector this frame */
/* similarly yis and yjs */
if (n<= 0) then
LineTo(x0+(xis+yis)/2, y0+(xjs+yjs)/2);
else
{hilbert(x0, y0, yis/2, yjs/2, xis/2, xjs/2, n-1)
hilbert(x0+xis/2, y0+xjs/2 ,xis/2, xjs/2, yis/2, yjs/2, n-1)
hilbert(x0+xis/2+yis/2, y0+xjs/2+yjs/2, xis/2, xjs/2, yis/2, yjs/2,n-1)
hilbert(x0+xis/2+yis, y0+xjs/2+yjs, -yis/2,-yjs/2, -xis/2, -xjs/2,n-1)}
end procedure;

/* Sample call */
hilbert(0, 0, 300, 0, 0, 300, 4);

References:
Andrew Cumming–School of Computing, Napier University, Edinburgh, UK
Eric W. Weisstein. “Hilbert Curve.” From MathWorld–A Wolfram Web Resource.

interconnected 11/1/2007

Untitled, Space filling curve art project 2007 (click to enlarge) This is a new print on canvas I created for the 2007 500x open show. The wayward youth below the picture is my youngest son. He crawled up to the print to get a closer look. The 500x Open Show 2007 ran May 12 – June 2, 2007 with a reception Friday May 12th 6-9pm. WC68-69 series at the 500x Expo 2007 Juried show I also entered the work below (Generative Exploration of Related Points Along a Space Filling Curve #1) in the 25th Annual 500x Open Show to test the waters. The show ran May 6-27th 2006 with the reception Saturday May 6, 6-9pm.  Generative Exploration of Related Points Along a Space Filling Curve #1 46×35 Iris print

Older 2004 versions of program output….

Hilbert with Ladders 2004 by Don Relyea– Abstract Geometric Art (click to enlarge)

To see a low resolution interactive early prototype of Hilbert with Ladders click here!(requires shockwave plug-in 123k)

Hilbert with Ladders is the first in a series of space filling algorithmic pieces I am working on specifically for giclee print output. Hilbert with Ladders was originally rendered at 33 inches wide and is extremely detailed. It will be available soon as a giclee print in a small limited edition.

Click to enlarge image.

Cityscapes with Ladders and Helipads 2004 (requires shockwave plug-in 123k) is a new Hilbert curve based prototype that generates abstract geometric art.The output of the algorithm is starting to look like a city from above so I decided to name it accordingly. I am focusing on colors right now and doing experiments with different color combinations and geometric patterns with both similar and complimentary colors. Once again, this version is just a temporal prototype. The print version will be the final, the print version is bigger, more detailed and tighter.