Recursion - Koch snowflake - top of Musings page

By: Nicholas Duchon


A little math:

First - it will work better if the recursive part takes two points as its input and computes the 1/3 and 2/3 points between them. This means that the program will start with 3 calls to this method to get started: 

Second, the body of the method will need to compute the third point of the equilateral triangle with base 1/3 and 2/3, and make sure it points in the right direction - outward. This is quite a bit more challenging than I had first thought. I had to do quite a bit of thinking, math, looking at the web, and finally experimenting with my own code before I got a solution. Here it is:

static PointND getApex (PointND pa, PointND pb) {
  double pvx   = (pa.x + pb.x)/2; // init to something sort of simple
  double pvy   = (pa.y + pb.y)/2; // used during code development
  double dy    = pb.y - pa.y;
  double dx    = pb.x - pa.x;
  double len   = Math.sqrt (dx*dx + dy*dy);
  double alpha = Math.atan (dy/dx); // return angle (-pi/2, pi/2)
  double beta  = Math.PI / 3; // 60 degrees
  if (pa.x > pb.x) alpha = alpha + Math.PI; // angle in (pi/2, 3pi/2) range
  pvx = pa.x + len * Math.cos (alpha + beta);
  pvy = pa.y + len * Math.sin (alpha + beta);
     // System.out.printf ("pa: %s, pb: %s, a: %.2f, b: %.2f, dx: %2f, dy: %2f\n", pa, pb, alpha*180/Math.PI, beta*180/Math.PI, dx, dy);
  return new PointND (pvx, pvy);
} // end method getApex

The PointND class - uses double rather than int for more precision:

class PointND {
  public double x, y;
  public PointND (double a, double b) {x=a; y=b;}
} // end class PointND

This really needs a drawing to explain it. 

Also, since beta is 60 degrees, sin beta and cos beta can be simplified - perhaps the entire atan, cos, sin methods can be replaced by appropriate ratios, eliminating the need for trig functions.

More math:

Results:

  

  

After I worked out the implications of the angle addition formulas and simplified the code, I came up with the following, where pa and bp are 1/3 and 2/3 of the segment that is getting an equilateral triangle pushed into it - see the diagram above.

private static double SIN60 = Math.sqrt (3)/2; // sin 60 degrees

// ND: getting apex of equilateral triangle with trig formulas resolved
// to coordinates
static PointND getApex2 (PointND pa, PointND pb) {
  double cx = (pa.x + pb.x) / 2;
  double cy = (pa.y + pb.y) / 2;
  double dx = (pa.y - pb.y) * SIN60;
  double dy = (pb.x - pa.x) * SIN60;
  return new PointND (cx + dx, cy + dy);
} // end method getApex

Entire program:

// File: KochSnowflakeFractalND.java
 // Author: Neptune, modified by Nicholas Duchon
 // Date: Oct 13, 2010
 // Reference: Liang, 8th, Problem 20.27, pg 704
       
    import javax.swing.*;
    import java.awt.*;
    import java.awt.event.*;
       
    public class KochSnowflakeFractalND extends JApplet {
       private JTextField jtfOrder = new JTextField("0",5);
       private KochSnowflakeTriangleND trianglePanel = new KochSnowflakeTriangleND ();
    
       
       public static void main(String[]args){
          JFrame frame = new JFrame("Koch Snowflake Fractal");
          KochSnowflakeFractalND applet = new KochSnowflakeFractalND ();
          frame.add(applet);
          frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
          frame.setSize(400, 400);
          frame.setVisible(true);
       } // end main
       
       public KochSnowflakeFractalND () {
       //Panel to hold: label, text field
          JPanel panel = new JPanel();
          panel.add(new JLabel("Enter an order: "));
          panel.add(jtfOrder);
          jtfOrder.setHorizontalAlignment(SwingConstants.RIGHT);
       
       //Add KochSnowflakeTriangle panel to applet
          add(trianglePanel);
          add(panel, BorderLayout.SOUTH);
       
       //Register Listener
          jtfOrder.addActionListener(
                new ActionListener() {
                    public void actionPerformed(ActionEvent e){
                       trianglePanel.setOrder(Integer.parseInt(jtfOrder.getText()));
                   }
                });
       } // end constructor
    
       static class KochSnowflakeTriangleND extends JPanel {
          private int order = 0;
          private static double SIN60 = Math.sqrt (3)/2; // sin 60 degrees
       
          public void setOrder(int order){
             this.order = order;
             repaint();
          } // end setOrder
       
          protected void paintComponent(Graphics g){
             super.paintComponent(g);
          
          //select 3 pts
             double space = 0.20 * getWidth();
              PointND p1 = new PointND  (space           ,  getHeight()-space);
              PointND p2 = new PointND (getWidth()-space, getHeight()-space);
             PointND p3 = getApex2 (p2, p1);
          
             displaySegments (g, order, p1, p2);
             displaySegments (g, order, p2, p3);
             displaySegments (g, order, p3, p1);
          } // end paintComponent
          
          private static void  displaySegments (Graphics g, int order, PointND p1, PointND p2) {
             if (order == 0) {
                 g.drawLine ((int) (p1.x + 0.5), (int)(p1.y + 0.5), (int)(p2.x + 0.5),  (int)(p2.y + 0.5));
             } 
             else {
                double pax = (2*p1.x + p2.x)/3;
                double pay = (2*p1.y + p2.y)/3;
                PointND pa = new PointND (pax, pay);
                displaySegments (g, order - 1, p1, pa);
             
                double pbx = (p1.x + 2*p2.x)/3;
                double pby = (p1.y + 2*p2.y)/3;
                PointND pb = new PointND (pbx, pby);
                displaySegments (g, order - 1, pb, p2);
             
                PointND c = getApex2 (pa, pb);
                displaySegments (g, order - 1, pa, c );
                 displaySegments (g, order - 1, c ,  pb);         
             }
          } // end display segments
          
          // ND: getting apex of equilateral triangle with trig formulas resolved
          //  to coordinates
          static PointND getApex2 (PointND pa, PointND pb) {
             double cx   = (pa.x + pb.x) / 2;
             double cy   = (pa.y + pb.y) / 2;
             double dx   = (pa.y - pb.y) * SIN60;
             double dy   = (pb.x - pa.x) * SIN60;
             return new PointND (cx + dx, cy + dy);
          } // end method getApex
          
       } // end static inner class KochSnowflakeTriangleND
    } // end KochSnowflakeFractalND
       
    class PointND {
       public double x, y;
       public PointND (double a, double b) {
          x=a; y=b;
} // end double double constructor    } // end class PointND

ND.