PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : [JAVA] Rekursion - Pythagorasbaum


Mosher
2010-12-03, 18:14:16
Hi Leute.

Die Aufgabe lautete, mit einer rekusriven Methode einen Pythagorasbaum (http://de.wikipedia.org/wiki/Pythagorasbaum) in ein JApplet zu zeichnen.

Dreiecke, bei denen die Hypotenuse kleiner als 2 Pixel ist, sollten nicht gezeichnet werden.

Quadrate mit Fläche >= 50Pixel^2 sollten braun, alle andere grün gezeichnet werden.

Die Dreiecke, die zu den jeweiligen Quadraten gehören, sollten die gleiche Farbe, wie das Quadrat bekommen.

Mein Ergebnis: http://www.abload.de/img/pythagorasbaumcsjv.png

Man sieht, dass links nicht so weit gezeichnet wurde, wie rechts und dass oben in der Mitte auch irgendwas nicht so ganz hinhaut.
Vielleicht kann mir einer einen Tipp geben, wo ich nach Fehlern suchen sollte, denn mir fällt einfahc nichts mehr ein.
Debuggen bringt leider nichts, denn die Routinge springt einfach zu oft in die rekursive Methode. Das dauert zu lang ;)
Danke für jede Hilfe,
Mosher

Tesseract
2010-12-03, 18:28:36
wie soll dir ohne code jemand helfen? mein tipp ins blaue: je nach dem welche rekursion zuerst aufgerufen wird überzeichnet einmal ein grünes polygon ein braunes oder umgekehrt.
oder verstehe ich gerade etwas komplett falsch? wie soll es denn aussehen?

Mosher
2010-12-03, 18:32:31
import java.awt.Color;
import java.awt.Graphics;

import javax.swing.JApplet;


public class Weihnachtsschmuck extends JApplet{


private static final long serialVersionUID = -6210843273275470411L;

public void zeichneDreieck (Graphics g,int x1, int y1, int x2, int y2, int x3, int y3, Color color) {
int pixelx[] = {x1, x2, x3};
int pixely[] = {y1, y2, y3};
g.setColor(color);
g.fillPolygon(pixelx, pixely, 3); //Polygon mit Farbe füllen
}

public void zeichneViereck(Graphics g, int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, Color color) {
zeichneDreieck(g, x1, y1, x2, y2, x3, y3, color);
zeichneDreieck(g, x1, y1, x3, y3, x4, y4, color);

}

public void zeichneBaum(Graphics g, int x1, int y1, int x2, int y2) {
int xc;
int yc;
int xd;
int yd;
int xe;
int ye;
int delta_x;
int delta_y;
Color color;

delta_x = x2 - x1;
delta_y = -(y2-y1);

xc = (x1-delta_y);
yc = (y1-delta_x);
xd = (int)(xc+0.5*delta_x-0.5*delta_y);
yd = (int)(yc-0.5*delta_x-0.5*delta_y);
xe = (x2-delta_y);
ye = (y2-delta_x);

if (Math.sqrt(delta_x*delta_x+delta_y*delta_y) < 2) {
return;
}

if (delta_x*delta_x+delta_y*delta_y >=50) {
color=new Color(139,69,19);
} else {
color=Color.GREEN;
}

zeichneDreieck(g, xc, yc, xe, ye, xd, yd, color);
zeichneViereck(g, x1, y1, x2, y2, xe, ye, xc, yc, color);

zeichneBaum(g, xd,yd,xe,ye);
zeichneBaum(g, xc,yc,xd,yd);

}

public void init() {
setSize(600, 600); // erstmal beliebig
}

public void paint(Graphics g) {

zeichneBaum(g,275, 350, 325, 350);
/*zeichneDreieck(g, 50, 150, 10, 230, 90, 230, Color.GREEN);
zeichneDreieck(g, 50, 190, 10, 270, 90, 270, Color.GREEN);
zeichneDreieck(g, 50, 230, 10, 310, 90, 310, Color.GREEN);

zeichneDreieck(g, 30, 310, 70, 310, 30, 350, new Color(139,69,19));
zeichneDreieck(g, 70, 350, 70, 310, 30, 350, new Color(139,69,19)); */

zeichneDreieck(g, 130, 10, 120, 40, 140, 40, Color.YELLOW); //Stern
zeichneDreieck(g, 80, 50, 120, 40, 110, 70, Color.YELLOW);
zeichneDreieck(g, 140, 40, 120, 40, 110, 70, Color.YELLOW);
zeichneDreieck(g, 140, 40, 150, 70, 110, 70, Color.YELLOW);
zeichneDreieck(g, 140, 40, 150, 70, 180, 50, Color.YELLOW);
zeichneDreieck(g, 110, 70, 150, 70, 130, 80, Color.YELLOW);
zeichneDreieck(g, 110, 70, 100, 110, 130, 80, Color.YELLOW);
zeichneDreieck(g, 160, 110, 150, 70, 130, 80, Color.YELLOW);

//zeichneViereck(g, 30, 30, 100, 30, 100, 100, 30, 100, Color.GREEN); TESTVIERECK

}

}

Hast Recht ;)

Neomi
2010-12-03, 18:36:50
An den unteren Zipfeln sieht man ganz gut, daß das Kernproblem nicht im Überzeichnen liegt, links unten (innerer Teil) fehlen auch grüne Polygone vor weißem Hintergrund. Ich vermute eher, daß die errechneten Punkte auf ganzzahlige Pixelkoordinaten gerundet werden, wodurch dann eine Seite kleiner ausfällt als die andere. Eine Lösung dafür wäre, mit Fließkommatypen zu rechnen und alleine beim Zeichnen des Polygons (nicht bei der weiteren Unterteilung) dann umzurechnen. Dann auch gerne mit Subpixelpräzision.

Edit: jep, laut dem geposteten Code trifft meine Vermutung zu. Die Integer-Berechnung ist das Problem.

Mosher
2010-12-03, 18:40:37
An den unteren Zipfeln sieht man ganz gut, daß das Kernproblem nicht im Überzeichnen liegt, links unten (innerer Teil) fehlen auch grüne Polygone vor weißem Hintergrund. Ich vermute eher, daß die errechneten Punkte auf ganzzahlige Pixelkoordinaten gerundet werden, wodurch dann eine Seite kleiner ausfällt als die andere. Eine Lösung dafür wäre, mit Fließkommatypen zu rechnen und alleine beim Zeichnen des Polygons (nicht bei der weiteren Unterteilung) dann umzurechnen. Dann auch gerne mit Subpixelpräzision.


Okay werd ich ausprobieren.
Hatte auch schon an sowas gedacht, den Gedanken aber dann wieder verworfen, da es mir seltsam vorkommt, dass das Ergebnis "unsymmetrisch falsch" war

Tesseract
2010-12-03, 18:42:35
xd = (int)(xc+0.5*delta_x-0.5*delta_y);

so eine zeile ist ganz böse. int*float und dann wieder auf int casten sollte man eigentlich nicht.

wie neomi schon gesagt hat: rechne alles mit floatingpoint und erst direkt vor dem zeichen (korrekt gerundet) auf screenspace-ints um.

ach ja, "Graphics" müsst du auch nicht jeder methode übergeben. da sollte eine klassenvariable reichen.

Mosher
2010-12-03, 18:47:47
hm, komisch.

Habe jetzt alles mit double gerechnet und erst beim Aufruf der Methoden zeichneDreieck, zeichneViereck, zeichneBaum wieder explizit zu (int) gecastet.

Exakt gleiches Ergebnis.

Das mit dem Graphics g werd ich beherzigen, danke

Edit: aah, hab das korrekt gerundet überlesen.

Bedeutet: Math.round(x) oder ? rechnet er dann x.5 auf x+1 oder schneidet er einfach Nachkommastellen ab?

Tesseract
2010-12-03, 18:49:41
Habe jetzt alles mit double gerechnet und erst beim Aufruf der Methoden zeichneDreieck, zeichneViereck, zeichneBaum wieder explizit zu (int) gecastet.

nein, auch da noch nicht. erst in zeichneDreieck wenn du wirklich das polygon zeichnen lässt.

Mosher
2010-12-03, 18:53:28
Also mit gerundeten Werten zeichnet er einfach links und rechts eine Ebene weiter.
Also wieder asymmetrisches Ergebnis

Mosher
2010-12-03, 18:54:40
nein, auch da noch nicht. erst in zeichneDreieck wenn du wirklich das polygon zeichnen lässt.


ist aber ungünsitg, weil die Methode nach Aufgabenstellung int erwarten soll

Tesseract
2010-12-03, 18:58:38
ist aber ungünsitg, weil die Methode nach Aufgabenstellung int erwarten soll

welche? zeichneDreieck? das kann sein, dann musst du halt beim aufruf vorher umrechnen.

wenn zeichneBaum allerdings auf int bleibt vergrößerst du mit jeder rekursion den fehler. zumindest wenn man die lösung so aufbaut wie du es getan hast.

Mosher
2010-12-03, 19:03:17
hm, zeichneBaum soll leider auch int-Werte erwarten.

Ich habs jetzt trotzdem mal so gemacht, dass zeichneBaum double-paramter übergeben bekommt.
Innerhalb von zeichneBaum ist dann alles double.

zeichneDreieck hab ich dann mit zeichneDreieck((int)x1,......) aufgerufen.

Ergebnis: wie vorher

Mosher
2010-12-03, 19:11:39
Okay, wenn ich zeichneBaum mit doubleParametern definiere und die Werte NICHT runde, erhalte ich einen symmetrischen Baum :)

Einziges Problem ist noch, dass oben in der Mitte Bereiche, die eigentlich grün sein sollten, durch braune Quadrate überdeckt werden. Aber da kann ich besimmt was feilen.

Ich kann halt jetzt nur hoffen, dass der Korrektor nix gegen meine double-Parameter hat.

Aber vielen Dank euch allen für die Hilfe

import java.awt.Color;
import java.awt.Graphics;

import javax.swing.JApplet;


public class Weihnachtsschmuck extends JApplet{


private static final long serialVersionUID = -6210843273275470411L;

public void zeichneDreieck (Graphics g,int x1, int y1, int x2, int y2, int x3, int y3, Color color) {
int pixelx[] = {x1, x2, x3};
int pixely[] = {y1, y2, y3};
g.setColor(color);
g.fillPolygon(pixelx, pixely, 3); //Polygon mit Farbe füllen
}

public void zeichneViereck(Graphics g, int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, Color color) {
zeichneDreieck(g, x1, y1, x2, y2, x3, y3, color);
zeichneDreieck(g, x1, y1, x3, y3, x4, y4, color);

}

public void zeichneBaum(Graphics g, double x1, double y1, double x2, double y2) {
double xc;
double yc;
double xd;
double yd;
double xe;
double ye;
double delta_x;
double delta_y;
Color color;

delta_x = x2 - x1;
delta_y = -(y2-y1);

xc = ((x1-delta_y));
yc = ((y1-delta_x));
xd = ((xc+0.5*delta_x-0.5*delta_y));
yd = ((yc-0.5*delta_x-0.5*delta_y));
xe = ((x2-delta_y));
ye = ((y2-delta_x));

if (Math.sqrt(delta_x*delta_x+delta_y*delta_y) < 2) {
return;
}

if (delta_x*delta_x+delta_y*delta_y >=50) {
color=new Color(139,69,19);
} else {
color=Color.GREEN;
}

zeichneDreieck(g, (int)xc, (int)yc, (int)xe, (int)ye, (int)xd, (int)yd, color);
zeichneViereck(g, (int)x1, (int)y1, (int)x2, (int)y2, (int)xe, (int)ye, (int)xc, (int)yc, color);


zeichneBaum(g, xd,yd,xe,ye);
zeichneBaum(g, xc,yc,xd,yd);

}

public void init() {
setSize(600, 600); // erstmal beliebig
}

public void paint(Graphics g) {

zeichneBaum(g,275, 350, 325, 350);
/*zeichneDreieck(g, 50, 150, 10, 230, 90, 230, Color.GREEN);
zeichneDreieck(g, 50, 190, 10, 270, 90, 270, Color.GREEN);
zeichneDreieck(g, 50, 230, 10, 310, 90, 310, Color.GREEN);

zeichneDreieck(g, 30, 310, 70, 310, 30, 350, new Color(139,69,19));
zeichneDreieck(g, 70, 350, 70, 310, 30, 350, new Color(139,69,19)); */

zeichneDreieck(g, 130, 10, 120, 40, 140, 40, Color.YELLOW); //Stern
zeichneDreieck(g, 80, 50, 120, 40, 110, 70, Color.YELLOW);
zeichneDreieck(g, 140, 40, 120, 40, 110, 70, Color.YELLOW);
zeichneDreieck(g, 140, 40, 150, 70, 110, 70, Color.YELLOW);
zeichneDreieck(g, 140, 40, 150, 70, 180, 50, Color.YELLOW);
zeichneDreieck(g, 110, 70, 150, 70, 130, 80, Color.YELLOW);
zeichneDreieck(g, 110, 70, 100, 110, 130, 80, Color.YELLOW);
zeichneDreieck(g, 160, 110, 150, 70, 130, 80, Color.YELLOW);

//zeichneViereck(g, 30, 30, 100, 30, 100, 100, 30, 100, Color.GREEN); TESTVIERECK

}

}

http://www.abload.de/img/pythagorasbaum2rmjo.png

Das Graphics g hab ich jetzt mal dringelassen, weil ich nicht allzuweit von den vorgegebenen Methodenrümpfen abweichen wollte

Tesseract
2010-12-03, 19:20:11
Okay, wenn ich zeichneBaum mit doubleParametern definiere und die Werte NICHT runde, erhalte ich einen symmetrischen Baum :)
genau. ;)

casten ist btw. nicht runden, zumindest nicht das was man normalerweise unter runden versteht.

im prinzip ist das aber sekundär. wenn du beim runden (und/oder casten) beim aufruf von zeichneDreieck was falsch machst, kann das ergebnis höchstens 1 pixel falsch sein. gefährlich ist das aber bei den parametern, die du der rekursion übergibst, weil sich da die rundungsfehler aufsummieren/multiplizieren. da darf man natürlich nix runden und nicht mit int arbeiten.

und wegen der sichtbarkeit: da müsstest du z.B. eine parallele rekursion machen, also immer alle polygone einer tiefe zeichnen und dann erst in der rekursion tiefer gehen. da gäbe es aber noch viele andere (mehr oder weniger komplexe) möglichkeiten.

Mosher
2010-12-03, 19:29:03
genau. ;)

casten ist btw. nicht runden, zumindest nicht das was man normalerweise unter runden versteht.

im prinzip ist das aber sekundär. wenn du beim runden (und/oder casten) beim aufruf von zeichneDreieck was falsch machst, kann das ergebnis höchstens 1 pixel falsch sein. gefährlich ist das aber bei den parametern, die du der rekursion übergibst, weil sich da die rundungsfehler aufsummieren/multiplizieren. da darf man natürlich nix runden und nicht mit int arbeiten.

und wegen der sichtbarkeit: da müsstest du z.B. eine parallele rekursion machen, also immer alle polygone einer tiefe zeichnen und dann erst in der rekursion tiefer gehen. da gäbe es aber noch viele andere (mehr oder weniger komplexe) möglichkeiten.

Ich glaub ich lass mir einfach erst nur die braunen, dann nur die grünen Pixel zeichnen. Sollte eigtl gehen. Danke für die vielen Hinweise.

Programmieren macht echt Spaß, beinhaltet halt viele Tücken, aber die werd ich schon noch meistern