| | |
recursion sierpinskys triangle - HELP!!
Please support our Java advertiser: Programming Forums - DaniWeb Sister Site
![]() |
Hello, jrobw.
You asked:
You can offer to user to enter this. And then pass it as a parameter into method.
You asked:
•
•
•
•
or how do I determine, how many levels of recursion I actually need???
So what if you can see the darkest side of me?
No one would ever change this animal I have become
Help me believe it's not the real me
Somebody help me tame this animal
No one would ever change this animal I have become
Help me believe it's not the real me
Somebody help me tame this animal
•
•
Join Date: Dec 2008
Posts: 13
Reputation:
Solved Threads: 0
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:
and now the triangle class, no difference to my last post:
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?
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:
Java Syntax (Toggle Plain Text)
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:
Java Syntax (Toggle Plain Text)
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?
•
•
Join Date: Dec 2008
Posts: 13
Reputation:
Solved Threads: 0
@Antenka:
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
Java Syntax (Toggle Plain Text)
You can offer to user to enter this. And then pass it as a parameter into method.
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
You can add this condition to this:
for example
for example
java Syntax (Toggle Plain Text)
if ((level == 1) ||(minLineLength < 12))
Last edited by Antenka; Dec 8th, 2008 at 8:43 pm.
So what if you can see the darkest side of me?
No one would ever change this animal I have become
Help me believe it's not the real me
Somebody help me tame this animal
No one would ever change this animal I have become
Help me believe it's not the real me
Somebody help me tame this animal
•
•
Join Date: Dec 2008
Posts: 13
Reputation:
Solved Threads: 0
@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
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:
It value will mean a count of levels, which were remained after doing one branch of your recursion ... here what I mean:
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
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:
java Syntax (Toggle Plain Text)
if ((level == 1) ||(minLineLength < 12)) { //here }
java Syntax (Toggle Plain Text)
//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 }
Maybe there is a better way to describe that - but It is my variant
Last edited by Antenka; Dec 8th, 2008 at 9:29 pm. Reason: Mistake :(
So what if you can see the darkest side of me?
No one would ever change this animal I have become
Help me believe it's not the real me
Somebody help me tame this animal
No one would ever change this animal I have become
Help me believe it's not the real me
Somebody help me tame this animal
•
•
Join Date: Nov 2008
Posts: 332
Reputation:
Solved Threads: 53
I inserted a counter inside drawFractal:
Second column shows how many triangles is to paint.
for level=100 i can't try.
What equation is needed?
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
for level=100 i can't try.
What equation is needed?
•
•
Join Date: Dec 2008
Posts: 13
Reputation:
Solved Threads: 0
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
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
![]() |
Other Threads in the Java Forum
- Previous Thread: Help on arrays!! Progress Made!!
- Next Thread: Loan repayment calculator
| Thread Tools | Search this Thread |
2dgraphics android api apple applet application arguments array arrays automation banking binary binarytree bluetooth capture chat chatprogramusingobjects class classes client code color component count database derby design eclipse eclipsedevelopment encryption error exception fractal game givemetehcodez graphics gridlayout gui html ide if_statement image input integer interface j2me java javadesktopapplications javaprojects jlabel jni jpanel julia keyword linux list loop macintosh map method methods midlethttpconnection mobile netbeans newbie nullpointerexception object os print printing problem producer program programming project projectideas read recursion reference replaysolutions ria scanner screen server set size sms sort sourcelabs sql stop string swing threads transforms tree ui unicode validation windows





