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.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.