hi!

i have to write a gui window, which draws sierpinskys triangle recursively, i have one main class:

package triangleMod;
import java.awt.Dimension;
import java.awt.Frame;
import java.awt.Point;

import javax.swing.JFrame;


public class Main extends Frame{
   
    static Point a;
    static Point b;
    static Point c;
    static Triangle tryAngle;
    static JFrame frame;
   

    private static final long serialVersionUID = 1L;

    //frame setup taken from:
    //http://java.sun.com/docs/books/tutorial/uiswing/examples/components/FrameDemoProject/src/components/FrameDemo.java
    private static void createAndShowGUI() {
        //Create and set up the window.
        frame = new JFrame("Fractal: Sierpinski's Triangle");
        a = new Point(0, 443);
        b = new Point(512, 443);
        c = new Point(256, 0);
        tryAngle = new Triangle(a, b, c);
       
        tryAngle.setPreferredSize(new Dimension(514, 446));
        //frame.add(tryAngle);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        frame.getContentPane().add(tryAngle);

        //Display the window.
        frame.pack();
        frame.setVisible(true);
    }

    public static void main(String[] args) {
           //Schedule a job for the event-dispatching thread:
        //creating and showing this application's GUI.
        javax.swing.SwingUtilities.invokeLater(new Runnable() {
            public void run() {
                createAndShowGUI();
            }
        });
    }
}

AND MORE IMPORTANT: the triangle class with the recursion

package triangleMod;
import java.awt.Component;
import java.awt.Graphics;
import java.awt.Point;

class Triangle extends Component{

    private static final long serialVersionUID = 1L;

    //A, B, C initial triangle-points, assigned in the constructor
    private Point A, B, C;
    //points for the 3 new inner triangles in the current recursive step
    private Point A1, B1, C1, A2, B2, C2, A3, B3, C3;

    public Triangle(Point a, Point b, Point c){
        this.A = a;
        this.B = b;
        this.C = c;
        }
   
    //helper var for recursion termination
    int i= 300;
   
    //draws fractal
    public void drawFractal(Graphics g, Point a, Point b, Point c){
       
        /**
         * draw outer triangle
         **/
       
        //AB
        g.drawLine(a.x, a.y, b.x, b.y);
        //AC
        g.drawLine(a.x, a.y, c.x, c.y);
        //BC
        g.drawLine(b.x, b.y, c.x, c.y);
       
        /**
         * Points of the 3 new triangles get assigned
         **/
       
        //lower left triangle coordinates
        A1 = new Point(A.x, A.y);
        B1 = new Point(c.x, b.y);
        C1 = new Point((a.x+c.x)/2, (c.y+a.y)/2);
       
        //lower right triangle coordinates
        A2 = new Point(c.x, b.y);
        B2 = new Point(B.x, B.y);
        C2 = new Point((c.x+b.x)/2, (c.y+a.y)/2);
       
        //upper triangle coordinates
        A3 =  new Point((a.x+c.x)/2, (c.y+a.y)/2);
        B3 = new Point((c.x+b.x)/2, (c.y+a.y)/2);
        C3 = new Point(C.x, C.y);
       
        /**
         * draw inner reversed triangle
         **/
       
        //AB
        g.drawLine(A3.x, A3.y, B3.x, B3.y);
        //AC
        g.drawLine(A3.x, A3.y, A2.x, A2.y);
        //BC
        g.drawLine(B3.x, B3.y, A2.x, A2.y);
       
        /**
         * rekusive method calls for the three new triangles
         **/
       
    //termination condition not set correctly, helper var i used for testing
        while (i-->0) {           
           
            drawFractal(g, A1, B1, C1);
            //drawFractal(g, A2, B2, C2);
            //drawFractal(g, A3, B3, C3);
           
        }
    }

    public void paint(Graphics g){
        drawFractal(g, A, B, C);
    }
}

THE PROBLEM:

as you see, in the whle loop i commented two of the recursive calls out, if I just have one of the 3 calls (no matter which one of the three), it works, the triangles in that direction are drawn. but if I have two or three of the recursive call, it does not work, it's not drawing the triangles i want. the three recursive calls seem to affect each other in a way i don't want.

i just don't get each of the recursive drawing just the triangles they do draw, when i just have the one recursive call in the while loop. i thought it should work, as i have separated, always newly defined points for A1, B1, C1 and so on...

maybe i am misunderstanding how the java stack recursion works, can anyone maybe test my code and give any help??

would really be cool, thx a lot

btw: i know that the condition in the while loop is not the right recirsive base condition, but i didn't think about the right one yet and just used it like it is there for testing, i want to fix that if my method principally works correct

In public void drawFractal(Graphics g, Point a, Point b, Point c){ use a,b,c as base to set a 3 new (a1,a2,a3) points of division. Use this 6 points to describe 3 new triangles. Post this fragment.

thats what i do in the method, i use the parameter points ro define the points A1, A2... they are not 6, but 9 points, but 3 of them are the old ones, so its them same..

my problem was, that i declared the points A1, A2... as fields... now i declare them inside the method and it works!

but there is a question left: I am useing int i for the termination condition in the while loop, but thats not so good, as its not flexible.

do you know, what would be a good termnination condition for the while loop/for the recursion, maybe something relating to the points??

thanks a lot

Hola, hola.
Are You absolutely sure?
Describe 3 new triangles from attached thumb.
Other things later.

Attachments tri.gif 2.96 KB

but there is a question left: I am useing int i for the termination condition in the while loop, but thats not so good, as its not flexible.

Put i as "level" inside public void drawFractal(int level,Graphics g, Point a, Point b, Point c)

ok, as I am curious about what you want to show me (I always want to learn, especially as recursion is really tough!) I'll try and heres the method which just describes the 3 new triangles from the parameter triangles:

public void drawFractal(Graphics g, Point a, Point b, Point c){

		//first triangle
		Point A1 = new Point(a);
		Point B1 = new Point((b.x-a.x)/2, b.y);
		Point C1 = new Point((a.x+c.x)/2, (c.y+a.y)/2);

		g.drawLine(A1.x, A1.y, B1.x, B1.y);
		g.drawLine(A1.x, A1.y, C1.x, C1.y);
		g.drawLine(B1.x, B1.y, C1.x, C1.y);
		
		//second triangle
		Point A2 = new Point(c.x, b.y);
		Point B2 = new Point(b.x, b.y);
		Point C2 = new Point((c.x+b.x)/2, (c.y+a.y)/2);

		g.drawLine(A2.x, A2.y, B2.x, B2.y);
		g.drawLine(A2.x, A2.y, C2.x, C2.y);
		g.drawLine(B2.x, B2.y, C2.x, C2.y);
		
		//third triangle
		Point A3 = new Point((a.x+c.x)/2, (c.y+a.y)/2);
		Point B3 = new Point((c.x+b.x)/2, (c.y+a.y)/2);
		Point C3 = new Point(c.x, c.y);

		g.drawLine(A3.x, A3.y, B3.x, B3.y);
		g.drawLine(A3.x, A3.y, C3.x, C3.y);
		g.drawLine(B3.x, B3.y, C3.x, C3.y);
	}

besides: after I changed the class variable points to local method variables my code drew the fractal correctly thats why I am sure.

but I wrote this fragment as you wished, because I would like to know what you were going to explain, cause I stil don't feel to have really understood recursion and I don't know how to determine the termination condition.

thanks a lot for your help :)

Put i as "level" inside public void drawFractal(int level,Graphics g, Point a, Point b, Point c)

ah, ok. so using a level seems to the right way. i was thinking the bascase (or termination condition) must be defined in relation to the decreasing elements (in this case the length of the triangle lines..). for example in the while loop:

while(b.x-a.x>5){
...
}

but it seemed to produce an infinite loop...

ok. we divides triangles recursively, but we put on screen triangles, for whos level==1. Try apply for

public void drawFractal(int level,Graphics g, Point a, Point b, Point c){
 if (level == 1) {
             /**
         * draw inner reversed triangle
         **/
        //AB
        g.drawLine(a.x, a.y, b.x, b.y);
        //AC
        g.drawLine(a.x, a.y, c.x, c.y);
        //BC
        g.drawLine(b.x, b.y, c.x, c.y);
        } else {
/// calculation of new points


         drawFractal(level-1,g, A1, B1, C1);
         drawFractal(level-1,g, A2, B2, C2);
         drawFractal(level-1,g, A3, B3, C3);
   }
}

uhh, I do not completely understand your approach..
I implemented the class with your suggestion as follows:

package triangleMod;

import java.awt.Color;
import java.awt.Component;
import java.awt.Graphics;
import java.awt.Point;

class TriangleQuu extends Component{

	private static final long serialVersionUID = 1L;

	//A, B, C initial triangle-points, assigned in the constructor
	private Point A, B, C;
	
	public TriangleQuu(Point a, Point b, Point c){
		this.A = a; 
		this.B = b; 
		this.C = c;
		}
	
       public void drawFractal(int level,Graphics g, Point a, Point b, Point c){
		if (level == 1) {
			/**
			 * draw inner reversed triangle
			 **/
			//AB
			g.drawLine(a.x, a.y, b.x, b.y);
			//AC
			g.drawLine(a.x, a.y, c.x, c.y);
			//BC
			g.drawLine(b.x, b.y, c.x, c.y);
		} else {

			//lower left triangle coordinates
			Point A1 = new Point(a.x, a.y);
			Point B1 = new Point(c.x, b.y);
			Point C1 = new Point((a.x+c.x)/2, (c.y+a.y)/2);

			//lower right triangle coordinates
			Point A2 = new Point(c.x, b.y);
			Point B2 = new Point(b.x, b.y);
			Point C2 = new Point((c.x+b.x)/2, (c.y+a.y)/2);

			//upper triangle coordinates
			Point A3 =  new Point((a.x+c.x)/2, (c.y+a.y)/2);
			Point B3 = new Point((c.x+b.x)/2, (c.y+a.y)/2);
			Point C3 = new Point(c.x, c.y);


			drawFractal(level-1,g, A1, B1, C1);
			drawFractal(level-1,g, A2, B2, C2);
			drawFractal(level-1,g, A3, B3, C3);
		}
	}


	public void paint(Graphics g){
		drawFractal(100, g, A, B, C);
	}
}

I called it with 100 for level in the paint, because I didn't know how to choose a good value for it, how can I?

if the lengst of the hypothenuse of the first triangle (the distance AB) always splits with every recursive step, can I call the method with something logarithmic relating to the width of the gui window? maybe(pseudocode:) level = log2(frameWidth); ??

or how do I determine, how many levels of recursion I actually need???

It doesn't draw anything with this implementation, I probably missed something in the recursive method, maybe didn't see how you really wanted me to program it...

sorry for so many beginer questions..

I invoked with level=8[ & i recived this thumb
it is why i want from You once more write new coordinates of triangle. Remark new points are in half of triangle edge. Write external function

Point midPoint(Point a,Point b){
//..
return new Point(....);
}
Attachments screen.png 15.16 KB

Hello, jrobw.
You asked:

or how do I determine, how many levels of recursion I actually need???

You can offer to user to enter this. And then pass it as a parameter into method.:)

youre not right in your last post, because I invoked it now with 8 for level too, and voila, it perfectly worked...

I have setup a new project for your approach in eclipse with 2 classes, I will post them both, so you can see, that it works, and that I assigned the points A1, A2, A3, B1, B2, B3, C1, C2, C3 correctly...

Here they are, first the main class:

import java.awt.Dimension;
import java.awt.Frame;
import java.awt.Point;

import javax.swing.JFrame;


public class MainQuu extends Frame{
	
	static Point a;
	static Point b;
	static Point c;
	static TriangleQuu tryAngle;
	static JFrame frame;
	

	private static final long serialVersionUID = 1L;

	//frame setup taken from:
	//http://java.sun.com/docs/books/tutorial/uiswing/examples/components/FrameDemoProject/src/components/FrameDemo.java
    private static void createAndShowGUI() {
    	//Create and set up the window.
        frame = new JFrame("Fractal: Sierpinski's Triangle");
    	a = new Point(0, 443);
    	b = new Point(512, 443);
    	c = new Point(256, 0);
    	tryAngle = new TriangleQuu(a, b, c);
        
        tryAngle.setPreferredSize(new Dimension(514, 446));
        //frame.add(tryAngle);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        frame.getContentPane().add(tryAngle);

        //Display the window.
        frame.pack();
        frame.setVisible(true);
    }

    public static void main(String[] args) {
           //Schedule a job for the event-dispatching thread:
        //creating and showing this application's GUI.
        javax.swing.SwingUtilities.invokeLater(new Runnable() {
            public void run() {
                createAndShowGUI();
            }
        });
    }
}

and now the triangle class, no difference to my last post:

import java.awt.Component;
import java.awt.Graphics;
import java.awt.Point;

class TriangleQuu extends Component{

	private static final long serialVersionUID = 1L;

	//A, B, C initial triangle-points, assigned in the constructor
	private Point A, B, C;
	
	public TriangleQuu(Point a, Point b, Point c){
		this.A = a; 
		this.B = b; 
		this.C = c;
		}
	
	
	public void drawFractal(int level, Graphics g, Point a, Point b, Point c){
		if (level == 1) {
			/**
			 * draw inner reversed triangle
			 **/
			//AB
			g.drawLine(a.x, a.y, b.x, b.y);
			//AC
			g.drawLine(a.x, a.y, c.x, c.y);
			//BC
			g.drawLine(b.x, b.y, c.x, c.y);
		} else {

			//lower left triangle coordinates
			Point A1 = new Point(a.x, a.y);
			Point B1 = new Point(c.x, b.y);
			Point C1 = new Point((a.x+c.x)/2, (c.y+a.y)/2);

			//lower right triangle coordinates
			Point A2 = new Point(c.x, b.y);
			Point B2 = new Point(b.x, b.y);
			Point C2 = new Point((c.x+b.x)/2, (c.y+a.y)/2);

			//upper triangle coordinates
			Point A3 =  new Point((a.x+c.x)/2, (c.y+a.y)/2);
			Point B3 = new Point((c.x+b.x)/2, (c.y+a.y)/2);
			Point C3 = new Point(c.x, c.y);


			drawFractal(level-1,g, A1, B1, C1);
			drawFractal(level-1,g, A2, B2, C2);
			drawFractal(level-1,g, A3, B3, C3);
		}
	}


	public void paint(Graphics g){
		drawFractal(8, g, A, B, C);
	}
}

so maybe you have not used the same code when you tested, i don't know... I tried to attach a screeenshot, hope it works..

but could you still tell me something about how I can determine or calculate how many levels of recursion i will have?

@Antenka:

You can offer to user to enter this. And then pass it as a parameter into method.

thanks for your reply! I mean, if I resize the window for example and take a fix number for the recursive levels, than maybe its not good anymore, thats why I wanted to have a determination of the level or another way to set the termination condition relating to the decreasing element - the distance of the points in the triangle (correlating to the frameWidth, which is the distance in the first triangle...)

I also ask this, because I will have to determine the complexity of the algorithm I implement for my exercise, and I don't really see how many levels I get, when I programm it this or the other way..

maybe you have any more hints, thanks

@antenka

huh? thats easily said if you don't write what you exactly mean with minLineLength (almost as easy as just handing over the problem to the user ;) ). would it be the distance between two points, lets say a and b?

I already tried that with the distance of the x-values (minLineLength would then be b.x-a.x, but doesn't work), i also tried to use the distance formula fot points in a cartesian system but it also woudln't work.

besides that, if I have a well choice for a termination condition I won't need level anymore, thats what i am talking about.

and if I have to use level anyway, the second condition is obsolte, AND: if I still have level in it, my actual question remains, how I can make a good choice for level - how can I (maybe mathematically) determine the depth of the recursion und thereby the complexity O(?) of the algorithm

As minLineLength I mean minimal line legngs (you should specify it yourself - the "12" it is an example) ... not only by x or y coordinates.
Using this additional condition you can specify wittingly big depth of the recursion and It is stops, when you reach the minimal triangle, that you specify.
Also I can't give advice about determining the depth of the recursion mathematically ... as you say it depends on screen resolution.
To count the levels, you can create variable in your class ... and then specify it, when you will go out from recursion:

if ((level == 1) ||(minLineLength < 12))
{
//here
}

It value will mean a count of levels, which were remained after doing one branch of your recursion ... here what I mean:

//you call your method with 8 length
drawFractal(8,g, A, B, C);
....
//if we reach the condition (because our screen resolution doesn't allow us to draw more triangles - as you specify) for example level=2
if ((level == 1) ||(minLineLength < 12))
{
//here we set the value, that will remember the leves remained to do
}

What we have: 8 - 2 is a depth of one branch ... also each branch creates 3 new branches ... here is your solution.
Maybe there is a better way to describe that - but It is my variant :)

I inserted a counter inside drawFractal:

level	if (level == 1)
1	1
2	4
3	13
4	40
5	121
6	364
7	1093
8	3280
9	9841
10	29524
11	88573
12	265720
13	797161
14	2391484
15	7174453
16	21523360
17	64570081

Second column shows how many triangles is to paint.
for level=100 i can't try.
What equation is needed?

ok, i try a third time to make clearer what i mean: you have minLineLength as an additional condition for the case, that level has not an appropriate value. screenresolution would make no sense here, because it java automatically deals with that point and wouldn't draw something wrgon and i am calculating with integers only and deal with pixals, so this problem can never occur anyway.
so just using level alone is much better than your workaround here.

if you cant tell how to mathematically look at the recursive strcuture of a method with 3 recursive calls thats ok, someone will. I just think that it would be a much more flexible code, if I would not have to call the method whith an arbitrary value for level and then decrease it.

i think it would be much nicer to call the method with a value, which relates to what happens in recursion, as in all standard examples like hanoi, fibonacci, quicksort or something. it would maybe be possible here to leave the level parameter out in the method call and construct a condition similar to your minLineLength-suggestion in the if-condition of the method. i am tired now, but i am sure to figure something out tomorrow, if you want, i'll post it here, so you can see it.

and please don't misunderstand, but i would recommend you to look at the previous posts, and go into the topic, before y<ou post before of the following reason:

screen resolution is not problem in java awt as we are dealing with integer and pixels. so what would be the minimal line lenght between to points anyway?? it would be 1 pixel!!! so minLineLength would be 1, no matter what resolution your screen has, because 1 pixels stays 1 pixel in every resolution. and level, which we already had, is set to 1 in the condition. so your siggestion is not good, because it adds complexity and does nothing good. you don't only have another condition, you also need another variable to count the levels. if you just use level, you don't have to xount, because you know the beginning value of level and in the and its one, so you now how many levels.

just to go sure, you don't misunderstand. I was not looking for a way to count levels after the algorithm terminates, but

1) a way to estimate the complexity of recursive methods with several recursive calls, and

2) a condition for the termination of the recursion, which is related to the decreasing element.

I) try to explain it further, when i figured it out, goodnight so far and thank you very much for your very nice help and time, you spend on this, antenka and quuba :)

the last post went to antenka...

@ quuba:

that looks good! would you say the complexity is in the range of O(n^3)?? it looks bigger than O(n^2)...

strange, i see my last little post in the wrong order...

ok, lets look at it close: for 1 ir is of course only 1 triangle, because the recurive calls are not executed, for 2 its 3 + 1, for 3 it's 3*3 + 1, for 4 its ((4*3)+1)*3 +1hm.... i don't se it, maybe too tired...

i think O(n^3) or O(3^n), but 3^n would even grow faster I think, maybe It's a bit smaller than than n^3, maybe still something logarithmic, because the line are split in hals... but i can only gues right now...

a = new Point(0, 443);
     b = new Point(512, 443);
     c = new Point(256, 0);
     tryAngle = new TriangleQuu(a, b, c);

try tryAngle = new TriangleQuu(c, a, b); to see later

i think it would be much nicer to call the method with a value, which relates to what happens in recursion,

sure you are right!!!

and please don't misunderstand, but i would recommend you to look at the previous posts, and go into the topic, before y<ou post before

I have read all post in this thread. But misunderstood ... I thought you want have as smallest triangle - the smallest visible triangle (or direct set depth of recursion).
In this case, the variant with 1 condition is the best :)

This article has been dead for over six months. Start a new discussion instead.