HILBERT CURVE
vkashid.38
April 2017
1 TITLE:
Write C++/Java program to generate Hilbert curve using concept of fractals
2 OBJECTIVE:
Student will be able to generate Hilbert curve using concept of fractals.
3 PROBLEM STATEMENT:
Write a C++or java program to generate hilbert curve
4 SOFTWARE REQUIREMENT:
Fedora ,java.
5 THEORY:
The Hilbert curve is a space filling curve that visits every point in a square grid
with a size of 22, 44, 88, 1616, or any other power of 2. It was first described by
David Hilbert in 1892. Applications of the Hilbert curve are in image processing:
especially image compression and dithering. The basic elements of the Hilbert
curves are what I call cups (a square with one open side) and joins (a vector
that joins two cups).The open side of a cup can be top, bottom, left or right.
In addition, every cup has two end-points, and each of these can be the entry
point or the exit point. So, there are eight possible varieties of cups. In
practice, a Hilbert curve uses only four types of cups. In a similar vein, a join
has a direction: up, down, left or right.
* A first order Hilbert curve is just a single cup.
* The second order Hilbert curve replaces that cup by four (smaller) cups,
which are linked together by three joins (see the figure on the right; the link
between a cup and a join has been marked with a fat dot in the figure).
1
*Every next order repeats the process or replacing each cup by four smaller
cups and three joins.
Let S be the solution perspective of drawing pixel such that S=s, e, i,
o, f, DD, NDD, success, failure s=Initial state. e = End state i= Input of
the system is n order of curve. o=output of the system is curve of n order.
F=curvefunction(n) Input: Plot an order n Hilbert curve Output: Display
Hilbert curve
6 ALGORITHM:
1)Turn in the direction y
2)Draw a Hilbert curve of order n-1, direction y
3)Move one step forward
4)Turn in the direction x
5)Draw a Hilbert curve of order n-1, direction x
6)Move one step forward
7)Draw a Hilbert curve of order n-1, direction x
8)Turn in the direction x
9)Move one step forward
10)Draw a Hilbert curve of order n-1, direction y
7 PSUEDO CODE:
enum
UP,
LEFT,
DOWN,
RIGHT,
;
void hilbert(int level,int direction=UP)
if (level==1)
switch (direction)
case LEFT:
move(RIGHT); /* move() could draw a line in... */
move(DOWN); /* ...the indicated direction */
move(LEFT);
break;
case RIGHT:
move(LEFT);
move(UP);
move(RIGHT);
break;
case UP:
move(DOWN);
2
move(RIGHT);
move(UP);
break;
case DOWN:
move(UP);
move(LEFT);
move(DOWN);
break;
/* switch */
else
switch (direction)
case LEFT:
hilbertl evel(level 1, U P );
move(RIGHT);
hilbertl evel(level 1, LEF T );
move(DOWN);
hilbertl evel(level 1, LEF T );
move(LEFT);
hilbertl evel(level 1, DOW N );
break;
case RIGHT:
hilbertl evel(level 1, DOW N );
move(LEFT);
hilbertl evel(level 1, RIGHT );
move(UP);
hilbertl evel(level 1, RIGHT );
move(RIGHT);
hilbertl evel(level 1, U P );
break;
case UP:
hilbertl evel(level 1, LEF T );
move(DOWN);
hilbertl evel(level 1, U P );
move(RIGHT);
hilbertl evel(level 1, U P );
move(UP);
hilbertl evel(level 1, RIGHT );
break;
case DOWN:
hilbertl evel(level 1, RIGHT );
move(UP);
hilbertl evel(level 1, DOW N );
move(LEFT);
hilbertl evel(level 1, DOW N );
move(DOWN);
hilbertl evel(level 1, LEF T );
3
break;
/* switch */
/* if */
8 Conclusion
The Hilbert curve is easy to generate. When applied over a digitized photograph
or a ray-traced image, it makes better use of the coherence of neighboring pixels
than the traditional scan-line based approach.
