CSE 382 Algorithms and Data Structures

Barbara Nostrand, Ph.D.

Electrical Engineering and Computer Science


Laboratory 8 - Fractal Stars

Introduction

Fractals were invented by the Polish-French mathematician Benoit Mandelbrot.  Fractals have a number of unusual properties and produce intriguing images.  Fractals are frequently used in computer graphics to produce sythetic landscapes.  This is because there are many objects in nature such as ferms,  trees,  mountains,  and the coast of England which exhibit self-similarity.  Mandelbrot wrote in The Fractal Geometry of Nature that a fractal is "a rough or fragmented geometric shape that can be subdivided in parts, each of which is (at least approximately) a reduced-size copy of the whole". A fractal as a geometric object generally has the following features:

You will develop a program called Fractal which draws fractal stars.  Fractal stars are drawn by drawing and odd pointed star with intersecting lines such as the common five-pointed star.  This large star serves as the base case for our recursive method.  Then,  a smaller star is added to each of the outer points of the star.  Each stage of adding stars smaller stars corresponds to a level of recusrion.  When your program starts,  it will ask the user for:  the number of points on each star,  the number of layers of recursion,  and the ratio between the size of the current star and the adjoinging star in the previous level.  You should display the number of points and the number of layers of recursion at the top of the frame which will hold your drawing of a fractal star.  The program will then recursively display the fractal star for the specified number of layers along with a button labeled New Fractal across the bottom of the frame.  Clicking on the New Fractal button should allow the user to specify and display a new frractal star.  Clicking the close frame button should terminate the program.  The scaling factor is used so that the stars will fit in the display area.  The layers parameter allows computation to complete in finite time.  Ideally,  the levels of the fractal star extend to infinity with smaller and smaller compenent stars.  However,  these will quicly become smaller than a single pixel and will not display. 

Getting Started

Create a new directory for the files of this exercise, and copy in your definition for the Complex class which you implemented in Laboratory 1.  Your Complex class should have the following constructors and accessor methods. 

Constructor Summary
Complex()
          Creates a complex number equal to (0 + 0 i).
Complex(double real)
          Creates a complex number equal to (real + 0 i).
Complex(double real, double imaginary)
          Creates a complex number equal to (real + imaginary i).
 
Method Summary
Complex add(Complex c)
          Returns the result of adding the complex number c.
Complex add(double r)
          Returns the result of adding the real number r.
Complex conjugate()
          Returns the complex conjugate of the complex number by inverting the sign of the imaginary component.
Complex divide(Complex c)
          Returns the result of dividing by the complex number c.
Complex divide(double r)
          Returns the result of dividing by the real number r.
double imaginary()
          Returns the imaginary component of the complex number.
double magnitude()
          Returns the distance in the complex plane from the complex number to the origin.
Complex multiply(Complex c)
          Returns the result of multiplying by the complex number c.
Complex multiply(double r)
          Returns the result of multiplying by the real number r.
double real()
          Returns the real component of the complex number.
Complex subtract(Complex c)
          Returns the result of subtracting the complex number c.
Complex subtract(double r)
          Returns the result of subtracting the real number r.
String toString()
          Returns a String representation such as 3 - 4 i of the complex value.

Representing Points

In addition to complex numbers,  you need to represent points in your program.  The methods for your Point class will roughly correspond to the usual operations for vectors.  Your Point class should have the following constructors and accessor methods. 

Constructor Summary
Point()
          Creates a point at the origin of the Euclidean plane.  The Cartesian coordinates are (0 , 0). 
Point(double x, double y)
          Creates a point in the Euclidean plane at the Cartesian coordinates are (x , y). 
Point(Complex c)
          Creates a point in the Euclidean plane whose x coordinate is equal to the real component and whose y component is equal to the imaginary component of c.
 
Method Summary
Complex add(Complex c)
          Returns the result of adding term-by-term the coefficients of the complex number c.
Complex add(Point p)
          Returns the result of adding term-by-term the coordinates of the point c.
Complex multiply(double r)
          Returns the result of multiplying the coordinates of the point by r.
String toString()
          Returns a String representation such as (3, 4) of the Cartesian coordinates of the point.
double x()
          Returns the x coordinate of the point.
double y()
          Returns the y coordinate of the point.

Design

As usual, we will apply object-centered design to solve this problem.

Behavior. Recursive algorithms work by using a "cookie-cutter" method over and over again.  In our case,  we will write a method which enters a star from one of the vertices,  finds its center,  and then procedes to traverse the edges of the star by finding the next Point,  draws a line to it,  and recursively decorates each new Point with a star.  Please note that we will actually define the Drawing class inside the definition of the Fractal class!  This has the advantage of making the attributes of Fractal available to the methods of Drawing

The Fractal Class

You should define a Fractal class which extends the Frame class. 

Inner Class Summary
protected  class Drawing
          This class extends the Panel class.  This inner class must be declared as non-static so that it can access the data contained in its outer class.
 
Field Summary
protected  Complex angle
          The rotation angle between connected points.
protected  int layers
          The number of layers to draw.
protected  int length
          The size of the current star.
protected  int points
          The number of points in each component star.
protected  double ratio
          The ratio of the size of the current star to the size of its parent star.
 
Constructor Summary
protected Fractal(int points,  int layers,  int length,  double ratio)
          Creates a frame to display the fractal and initializes shared parameters. 
 
Method Summary
Drawing draw()
          Invokes the Drawing constructor.
void main(String[] args)
          Communicates with the user,  creates the Fractal object,  and uses the draw method to add the fractal image to the frame.

The Drawing Class

You should define an inner Drawing class which extends the Panel class. 

Field Summary
private  int HEIGHT
          The height in pixels of the image area.  Initialize this value to 600. 
private  int WIDTH
          The width in pixels of the image area.  Initialize this value to 600. 
 
Constructor Summary
protected Drawing()
          The default constructor creates a Panel to accommodate the recursive drawing method. 
 
Method Summary
void drawLine(Point oldVertex, Point newVertex)
          Draws a line on the graphics panel from oldVertex to newVertex using the standard mathematics coordinate system. This method internally translates standard mathematics coordinates to display coordinates before drawing the line. 
void drawStar(int layer, double radius, Complex entry, Point center)
          
layerinteger value specifying the current layer.
radiusdouble value specifying the distance from the center to the points of the star.
entryComplex value corresponding to the angle of the phasor from the center of the parent star to the entry point of the current star.
centerPoint valuegiving the center of the current star.
Dimension getPreferredSize()
          Invokes the Dimension constructor for an image of HEIGHT and WIDTH
void paint(Graphics graphics)
          Profices the paint method required by the graphics package.  This is the non-recursive entry to star drawing. 

 

Star drawing algorithm

  1. Check for zero layers. 
  2. Reverse the direction of the phasor by multiplying by -1.  Make sure that the phasor remains on the unit circle.  The phasors must remain on the unit circle to function correctly.  You will use scaling factors to control the size of the stars. 
  3. Handle the special case of the first star.  You will need to calculate all of the vertices for the first star including the "entry" vertex.  This means that you will have to apply recursion to this vertex for the first star only.  In all other cases,  a larger star is already attached to the entry vertex. 
  4. Draw the local star on the pane.  You will need to recursively draw a star after you create each new point and link it with a line to its preceding point. 
  5. Add points-1 Points to the local star. 
    1. Step to the next point of the star.  You can accomplish this simply by multiplying phasor by angle.  Recall that the angle is the rotation angle between two connected points on the star. 
    2. Draw a line from the previous point on the star to this new point. 
    3. Find the vertex of the small star to be attached to this new point.  The center lies on a line passing through the center of the parent star and the current vertex.  The distance from the current point to the new center should be the product of ratio and the distance from the current point to the center of the current star. 
    4. Draw a small star centered at the new center beginning with current point.  Be careful to decrement the layer and shrink the radius for this attached star. 
  6. Finish drawing the star on the pane by drawing a line from the current vertex to the entry vertex. 

 

Phrases you should now understand:

Recursion. 

CollaborationYou will complete this project with your lab partner. 
ImplementationYou must implement your system as a Java application.  You may use Jgrasp.  Do not use netbeans or produce a Java applet. 
EnvironmentYour program must execute on the podium computer in our classroom.
Turn inYou must turn in both a report containing complete program sources and an executable electronic version of your program.

Last modified: 2008 MAR 24
bnostran@syr.edu