recursion sierpinskys triangle - HELP!!

Please support our Java advertiser: Programming Forums - DaniWeb Sister Site
Reply

Join Date: Nov 2008
Posts: 249
Reputation: Antenka has a spectacular aura about Antenka has a spectacular aura about Antenka has a spectacular aura about 
Solved Threads: 65
Antenka's Avatar
Antenka Antenka is offline Offline
Posting Whiz in Training

Re: recursion sierpinskys triangle - HELP!!

 
0
  #11
Dec 8th, 2008
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.
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
Reply With Quote Quick reply to this message  
Join Date: Dec 2008
Posts: 13
Reputation: jrobw is an unknown quantity at this point 
Solved Threads: 0
jrobw jrobw is offline Offline
Newbie Poster

Re: recursion sierpinskys triangle - HELP!!

 
0
  #12
Dec 8th, 2008
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:


  1. import java.awt.Dimension;
  2. import java.awt.Frame;
  3. import java.awt.Point;
  4.  
  5. import javax.swing.JFrame;
  6.  
  7.  
  8. public class MainQuu extends Frame{
  9.  
  10. static Point a;
  11. static Point b;
  12. static Point c;
  13. static TriangleQuu tryAngle;
  14. static JFrame frame;
  15.  
  16.  
  17. private static final long serialVersionUID = 1L;
  18.  
  19. //frame setup taken from:
  20. //http://java.sun.com/docs/books/tutorial/uiswing/examples/components/FrameDemoProject/src/components/FrameDemo.java
  21. private static void createAndShowGUI() {
  22. //Create and set up the window.
  23. frame = new JFrame("Fractal: Sierpinski's Triangle");
  24. a = new Point(0, 443);
  25. b = new Point(512, 443);
  26. c = new Point(256, 0);
  27. tryAngle = new TriangleQuu(a, b, c);
  28.  
  29. tryAngle.setPreferredSize(new Dimension(514, 446));
  30. //frame.add(tryAngle);
  31. frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  32.  
  33. frame.getContentPane().add(tryAngle);
  34.  
  35. //Display the window.
  36. frame.pack();
  37. frame.setVisible(true);
  38. }
  39.  
  40. public static void main(String[] args) {
  41. //Schedule a job for the event-dispatching thread:
  42. //creating and showing this application's GUI.
  43. javax.swing.SwingUtilities.invokeLater(new Runnable() {
  44. public void run() {
  45. createAndShowGUI();
  46. }
  47. });
  48. }
  49. }

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

  1. import java.awt.Component;
  2. import java.awt.Graphics;
  3. import java.awt.Point;
  4.  
  5. class TriangleQuu extends Component{
  6.  
  7. private static final long serialVersionUID = 1L;
  8.  
  9. //A, B, C initial triangle-points, assigned in the constructor
  10. private Point A, B, C;
  11.  
  12. public TriangleQuu(Point a, Point b, Point c){
  13. this.A = a;
  14. this.B = b;
  15. this.C = c;
  16. }
  17.  
  18.  
  19. public void drawFractal(int level, Graphics g, Point a, Point b, Point c){
  20. if (level == 1) {
  21. /**
  22. * draw inner reversed triangle
  23. **/
  24. //AB
  25. g.drawLine(a.x, a.y, b.x, b.y);
  26. //AC
  27. g.drawLine(a.x, a.y, c.x, c.y);
  28. //BC
  29. g.drawLine(b.x, b.y, c.x, c.y);
  30. } else {
  31.  
  32. //lower left triangle coordinates
  33. Point A1 = new Point(a.x, a.y);
  34. Point B1 = new Point(c.x, b.y);
  35. Point C1 = new Point((a.x+c.x)/2, (c.y+a.y)/2);
  36.  
  37. //lower right triangle coordinates
  38. Point A2 = new Point(c.x, b.y);
  39. Point B2 = new Point(b.x, b.y);
  40. Point C2 = new Point((c.x+b.x)/2, (c.y+a.y)/2);
  41.  
  42. //upper triangle coordinates
  43. Point A3 = new Point((a.x+c.x)/2, (c.y+a.y)/2);
  44. Point B3 = new Point((c.x+b.x)/2, (c.y+a.y)/2);
  45. Point C3 = new Point(c.x, c.y);
  46.  
  47.  
  48. drawFractal(level-1,g, A1, B1, C1);
  49. drawFractal(level-1,g, A2, B2, C2);
  50. drawFractal(level-1,g, A3, B3, C3);
  51. }
  52. }
  53.  
  54.  
  55. public void paint(Graphics g){
  56. drawFractal(8, g, A, B, C);
  57. }
  58. }

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?
Reply With Quote Quick reply to this message  
Join Date: Dec 2008
Posts: 13
Reputation: jrobw is an unknown quantity at this point 
Solved Threads: 0
jrobw jrobw is offline Offline
Newbie Poster

Re: recursion sierpinskys triangle - HELP!!

 
0
  #13
Dec 8th, 2008
@Antenka:
  1. 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
Reply With Quote Quick reply to this message  
Join Date: Nov 2008
Posts: 249
Reputation: Antenka has a spectacular aura about Antenka has a spectacular aura about Antenka has a spectacular aura about 
Solved Threads: 65
Antenka's Avatar
Antenka Antenka is offline Offline
Posting Whiz in Training

Re: recursion sierpinskys triangle - HELP!!

 
0
  #14
Dec 8th, 2008
You can add this condition to this:
for example
  1. 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
Reply With Quote Quick reply to this message  
Join Date: Dec 2008
Posts: 13
Reputation: jrobw is an unknown quantity at this point 
Solved Threads: 0
jrobw jrobw is offline Offline
Newbie Poster

Re: recursion sierpinskys triangle - HELP!!

 
0
  #15
Dec 8th, 2008
@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
Reply With Quote Quick reply to this message  
Join Date: Nov 2008
Posts: 249
Reputation: Antenka has a spectacular aura about Antenka has a spectacular aura about Antenka has a spectacular aura about 
Solved Threads: 65
Antenka's Avatar
Antenka Antenka is offline Offline
Posting Whiz in Training

Re: recursion sierpinskys triangle - HELP!!

 
0
  #16
Dec 8th, 2008
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:
  1. if ((level == 1) ||(minLineLength < 12))
  2. {
  3. //here
  4. }
It value will mean a count of levels, which were remained after doing one branch of your recursion ... here what I mean:
  1. //you call your method with 8 length
  2. drawFractal(8,g, A, B, C);
  3. ....
  4. //if we reach the condition (because our screen resolution doesn't allow us to draw more triangles - as you specify) for example level=2
  5. if ((level == 1) ||(minLineLength < 12))
  6. {
  7. //here we set the value, that will remember the leves remained to do
  8. }
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
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
Reply With Quote Quick reply to this message  
Join Date: Nov 2008
Posts: 332
Reputation: quuba is on a distinguished road 
Solved Threads: 53
quuba quuba is offline Offline
Posting Whiz

Re: recursion sierpinskys triangle - HELP!!

 
0
  #17
Dec 8th, 2008
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?
Reply With Quote Quick reply to this message  
Join Date: Dec 2008
Posts: 13
Reputation: jrobw is an unknown quantity at this point 
Solved Threads: 0
jrobw jrobw is offline Offline
Newbie Poster

Re: recursion sierpinskys triangle - HELP!!

 
0
  #18
Dec 8th, 2008
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
Reply With Quote Quick reply to this message  
Join Date: Dec 2008
Posts: 13
Reputation: jrobw is an unknown quantity at this point 
Solved Threads: 0
jrobw jrobw is offline Offline
Newbie Poster

Re: recursion sierpinskys triangle - HELP!!

 
0
  #19
Dec 8th, 2008
sorry, i did not mean O(n^3), i meant O(3^n)...
Reply With Quote Quick reply to this message  
Join Date: Dec 2008
Posts: 13
Reputation: jrobw is an unknown quantity at this point 
Solved Threads: 0
jrobw jrobw is offline Offline
Newbie Poster

Re: recursion sierpinskys triangle - HELP!!

 
0
  #20
Dec 8th, 2008
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)...
Reply With Quote Quick reply to this message  
Reply

This thread is more than three months old.
Perhaps start a new thread instead?
Message:



Other Threads in the Java Forum
Thread Tools Search this Thread



About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC