C      ALGORITHM 781, COLLECTED ALGORITHMS FROM ACM.
C      THIS WORK PUBLISHED IN TRANSACTIONS ON MATHEMATICAL SOFTWARE,
C      VOL. 24,NO. 2,      June, 1998, P.  184--189.
#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create the files:
#	Src/
#	Src/C/
#	Src/C/Sp/
#	Src/C/Sp/Res
#	Src/C/Sp/data
#	Src/C/Sp/src.c
# This archive created: Tue Jan 19 19:10:45 1999
export PATH; PATH=/bin:$PATH
if test ! -d 'Src'
then
	mkdir 'Src'
fi
cd 'Src'
if test ! -d 'C'
then
	mkdir 'C'
fi
cd 'C'
if test ! -d 'Sp'
then
	mkdir 'Sp'
fi
cd 'Sp'
if test -f 'Res'
then
	echo shar: will not over-write existing file "'Res'"
else
cat << SHAR_EOF > 'Res'
Enter the Hilbert curve width.
Enter the plotting resolution (1 = points only, 3 = aesthetic curve plotting).

0,0
1,0
1,1
0,1
0,2
0,3
1,3
1,2
2,2
2,3
3,3
3,2
3,1
2,1
2,0
3,0
4,0
4,1
5,1
5,0
6,0
7,0
7,1
6,1
6,2
7,2
7,3
6,3
5,3
5,2
4,2
4,3
4,4
4,5
5,5
5,4
6,4
7,4
7,5
6,5
6,6
7,6
7,7
6,7
5,7
5,6
4,6
4,7
3,7
2,7
2,6
3,6
3,5
3,4
2,4
2,5
1,5
1,4
0,4
0,5
0,6
1,6
1,7
0,7
0,8
0,9
1,9
1,8
2,8
3,8
3,9
2,9
2,10
3,10
3,11
2,11
1,11
1,10
0,10
0,11
0,12
1,12
1,13
0,13
0,14
0,15
1,15
1,14
2,14
2,15
3,15
3,14
3,13
2,13
2,12
3,12
4,12
5,12
5,13
4,13
4,14
4,15
5,15
5,14
6,14
6,15
7,15
7,14
7,13
6,13
6,12
7,12
7,11
7,10
6,10
6,11
5,11
4,11
4,10
5,10
5,9
4,9
4,8
5,8
6,8
6,9
7,9
7,8
8,8
8,9
9,9
9,8
10,8
11,8
11,9
10,9
10,10
11,10
11,11
10,11
9,11
9,10
8,10
8,11
8,12
9,12
9,13
8,13
8,14
8,15
9,15
9,14
10,14
10,15
11,15
11,14
11,13
10,13
10,12
11,12
12,12
13,12
13,13
12,13
12,14
12,15
13,15
13,14
14,14
14,15
15,15
15,14
15,13
14,13
14,12
15,12
15,11
15,10
14,10
14,11
13,11
12,11
12,10
13,10
13,9
12,9
12,8
13,8
14,8
14,9
15,9
15,8
15,7
14,7
14,6
15,6
15,5
15,4
14,4
14,5
13,5
13,4
12,4
12,5
12,6
13,6
13,7
12,7
11,7
11,6
10,6
10,7
9,7
8,7
8,6
9,6
9,5
8,5
8,4
9,4
10,4
10,5
11,5
11,4
11,3
11,2
10,2
10,3
9,3
8,3
8,2
9,2
9,1
8,1
8,0
9,0
10,0
10,1
11,1
11,0
12,0
13,0
13,1
12,1
12,2
12,3
13,3
13,2
14,2
14,3
15,3
15,2
15,1
14,1
14,0
15,0


Enter the Hilbert curve width.
SHAR_EOF
fi # end of overwriting check
if test -f 'data'
then
	echo shar: will not over-write existing file "'data'"
else
cat << SHAR_EOF > 'data'
16
1
-1
SHAR_EOF
fi # end of overwriting check
if test -f 'src.c'
then
	echo shar: will not over-write existing file "'src.c'"
else
cat << SHAR_EOF > 'src.c'
/*
	Hilbert.c
	
	Generate the points of the Hilbert curve by recursion.
	
	Greg Breinholt, ETHZ, 1997.
	
	email: 	breinholt@computer.org
	
	Compiles with standard ANSI C.
	
*/




#include <stdio.h>
#include <math.h>

void Hilbert(int x, int y, int lg, int i1, int i2);

int resolution = -1;




void main(void) {
	int width = -1;
	float p = 0.0;
	
	while (1) { 												/* Repeat forever */
		while (width < 2) {  										/* Check valid width */
			printf("Enter the Hilbert curve width.\n");
			scanf("%d", &width);

			if (width<0){
			  exit(0);
			}
			
			p = (log10(width)/ log10(2));								/* Check width is result of 2^m*/
			if (p != ((int)p)) {								
				printf("Curve width must be >= 2, and the result of 2^m (m = 1,2,3,4...).\n\n");
				width = -1;
			}
		}
		
		while (resolution < 0) {										/* Check valid resolution */
			printf("Enter the plotting resolution (1 = points only, 3 = aesthetic curve plotting).\n");
			scanf("%d", &resolution);
		}
		
		printf("\n");
		Hilbert(0,0,width,0,0);										/* Start recursion */
		printf("\n\n");
		
		width = -1; 
		resolution = -1;
	}		
}


void Hilbert(int x, int y, int lg, int i1, int i2){
			/* 	 x:	initial x co-ordinate, 
				 y:	initial y co-ordinate, 
				lg:	curve width (2^m), 
				i1:	starting point of the unit shape, 
				i2:	end point of the unit shape.  
			*/

	if (lg==1) {													/* Unit shape reached */
			printf("%d%c%d\n",x*resolution,',',y*resolution);							/* Output co-ordinates to console */
			return;												/* Exit recusion*/
	}
		
	lg >>= 1;														/* Divide by 2 */
	Hilbert(x + i1*lg, 	y + i1*lg, 	lg,	 i1,	1-i2);
	Hilbert(x + i2*lg, 	y + (1- i2)*lg,	lg,	 i1,	i2);
	Hilbert(x + (1-i1)*lg, 	y + (1-i1)*lg,	lg,	 i1,	i2);
	Hilbert(x + (1-i2)*lg, 	y + i2*lg, 	lg,	 1-i1,	i2);
}



/* Note
			Use: 	printf("%d%c%d\n",x * resolution,',',y * resolution);
					to output the points needed to plot a line curve.
		
			Use: 	LineTo(x * resolution, y * resolution); 
					to draw the curve.
					
			Use resolution 	= 1 to give just the points, 
							= 3 to space the points aesthetically,
*/
SHAR_EOF
fi # end of overwriting check
cd ..
cd ..
cd ..
#       End of shell archive
exit 0