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:

• displaySegments (g, order, p1, p2)
• displaySegments (g, order, p2, p3)
• displaySegments (g, order, p3, p1)

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.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();
jtfOrder.setHorizontalAlignment(SwingConstants.RIGHT);

//Register Listener
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.