Wie berechnet man einen Punkt in einem Rechteck? - Seite 2

Neue Frage »

Jane Doe Auf diesen Beitrag antworten »

Zitat:
Original von riwe
so in etwa Augenzwinkern

Genau so. Freude
riwe Auf diesen Beitrag antworten »

dann folge doch einfach dem Rat von HAL 9000. Augenzwinkern

selbst mein ziemlich rustikales VBA- Programm ( ohne float - Format)
benötigt für 100000 Punkte gerade einmal 0.08 s, für 1000000 0.8 s.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von riwe
selbst mein ziemlich rustikales VBA- Programm ( ohne float - Format)
benötigt für 100000 Punkte gerade einmal 0.08 s, für 1000000 0.8 s.

Ich selbst hab's nicht implementiert, daher freue ich mich über diese Bestätigung, dass ich mit meiner obigen Schätzung nicht so weit danebenlag. smile
Jane Doe Auf diesen Beitrag antworten »

@riwe

Dann versuch es mal anders herum. Lass eine wählbare Anzahl Punkte in einem wählbaren Zeitabschnitt berechnen und schau wie viel FPS Du da noch rauskriegst.
Wenn Du zum Beispiel 1000 Punkte pro 100ms berechnen lässt, dann werden Deine FPS ganz schön in den Keller gehen, denke ich.

Denn das wären 10000 Zufallswinkel + 10000 Bestimmungen der zu schneidenden Strecken + 20000 Schnittpunktberechnungen + 10000 Zufallspunkte auf der errechneten Strecke pro Sekunde.
Wenn Dein Rechner da nicht in die Knie geht, dann hast Du entweder einen Supercomputer, oder ich mache was total falsch. Big Laugh
riwe Auf diesen Beitrag antworten »

Zitat:
Original von Jane Doe
@riwe

Dann versuch es mal anders herum. Lass eine wählbare Anzahl Punkte in einem wählbaren Zeitabschnitt berechnen und schau wie viel FPS Du da noch rauskriegst.
Wenn Du zum Beispiel 1000 Punkte pro 100ms berechnen lässt, dann werden Deine FPS ganz schön in den Keller gehen, denke ich.

Denn das wären 10000 Zufallswinkel + 10000 Bestimmungen der zu schneidenden Strecken + 20000 Schnittpunktberechnungen + 10000 Zufallspunkte auf der errechneten Strecke pro Sekunde.
Wenn Dein Rechner da nicht in die Knie geht, dann hast Du entweder einen Supercomputer, oder ich mache was total falsch. Big Laugh


es scheint mir, das beste an deinen Ausführunden ist dein letzter Satz

das ist doch dein Problem nicht meines.
oben hast du doch geschrieben: genau so!
und mein uralter PC braucht halt die von mir genannten Zeiten.

als pensionierter Fliesenleger oder so habe ich keine Ahnung, was du plötzlich mit FPS und umgekehrt meinst.
aber wenn es dir hilft: mache weiter so unglücklich
Jane Doe Auf diesen Beitrag antworten »

Nicht gleich so negativ, denn das war doch nicht böse gemeint ! Prost

Mit dem 'Genau so' meinte ich das Deine Punkte alle innerhalb der zwei Rechtecke und innerhalb eines Winkelbereichs sind.
FPS bedeutet Frames per second, also Bilder pro Sekunde. 24 FPS braucht der Mensch mindestens um eine Abfolge von Bildern noch als Bewegung und nicht als einzelne Bilder wahrzunehmen.
 
 
HAL 9000 Auf diesen Beitrag antworten »

Nach dem "Gejammer" hab ich das jetzt doch mal in C probiert, mit vollen 64 Bit Floatingpoint "double" und sogar gutem Zufallszahlengenerator (Mersenne-Twister mit 64 Bit Ausgabe) - Ergebnis:

Über 13 Millionen generierte Punkte pro Sekunde im Singlethread-Modus (i7-3770, 3.4GHz), mit 8 Parallelthreads steigt es auf über 70 Millionen Punkte pro Sekunde. Das ganze aber reine Berechnung, d.h., ohne irgendwelche Grafikausgabe.
Jane Doe Auf diesen Beitrag antworten »

Hm. Also bei mir werden die Punkte nicht nur berechnet, sondern auch weiterverarbeitet und grafisch dargestellt. Allerdings sind 13 Millionen Berechnungen schon ein großer Unterschied zu dem was ich bisher rausschlagen konnte, also werde ich mich nochmal an die Optimierung setzen.
HAL 9000 Auf diesen Beitrag antworten »

Die Kernroutine sieht bei mir so aus:

Prozessparameter (Namen hoffentlich selbsterklärend):
halfwidth_inner_rectangle, halfheight_inner_rectangle,
halfwidth_outer_rectangle, halfheight_outer_rectangle,
lower_angle, higher_angle (beide in radiant)

Voraussetzungen:
0 < halfwidth_inner_rectangle < halfwidth_outer_rectangle
0 < halfheight_inner_rectangle < halfheight_outer_rectangle
0 <= lower_angle < higher_angle

Vorberechnet (kann man auch innerhalb der Prozedur über zwei zusätzliche Multiplikationen erledigen)
inner_tanangle = halfheight_inner_rectangle / halfwidth_inner_rectangle;
outer_tanangle = halfheight_outer_rectangle / halfwidth_outer_rectangle;

Benutzte Prozeduren:
frandom() ... double Zufallszahl im Intervall [0,1)

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
#ifndef M_PI
#define M_PI  3.14159265358979323846
#endif

void GenerateRandomPoint (double *x, double *y)
{
    double tanangle, randvalue;
    double xin, yin, xout, yout;
    int sx = 1;
    int sy = 1;
    double angle = lower_angle + frandom() * (higher_angle - lower_angle);
    // Winkel in ersten Quadranten bringen: durch Spiegelungen
    while (angle >= M_PI)
    {
        sx = -sx;
        sy = -sy;
        angle -= M_PI;
    }
    if (angle >= M_PI/2)
    {
        sx = -sx;
        angle = M_PI-angle;
    }
    // Jetzt ist Winkel im Bereich 0..pi/2 und sx,sy enthalten Spiegelungsfaktoren
    tanangle = tan(angle);
    if (tanangle < inner_tanangle)
    {
        // rechte Kante inneres Rechteck
        xin = halfwidth_inner_rectangle;
        yin = halfwidth_inner_rectangle*tanangle;
    }
    else
    {
        // obere Kante inneres Rechteck
        xin = halfheight_inner_rectangle/tanangle;
        yin = halfheight_inner_rectangle;
    }
    if (tanangle < outer_tanangle)
    {
        // rechte Kante äußeres Rechteck
        xout = halfwidth_outer_rectangle;
        yout = halfwidth_outer_rectangle*tanangle;
    }
    else
    {
        // obere Kante äußeres Rechteck
        xout = halfheight_outer_rectangle/tanangle;
        yout = halfheight_outer_rectangle;
    }
    randvalue = frandom();
    // Punktberechnung auf Schnittstrecke + nötige Spiegelungen
    *x = sx * (randvalue * xin + (1-randvalue)* xout);
    *y = sy * (randvalue * yin + (1-randvalue)* yout);
}
Hierbei ist natürlich der Ursprung (0,0) einfach das Zentrum der beiden Rechtecke, aber additive Verschiebungen in einen anderen Punkt sollten ja kein Problem sein.
Jane Doe Auf diesen Beitrag antworten »

Danke für das Beispiel, aber wo genau berechnest Du denn die Schnittpunkte ? :O
HAL 9000 Auf diesen Beitrag antworten »

Die Schnittpunkte mit dem Rechteck? Na das sind (xin,yin) und (xout,yout) - ist doch ersichtlich, wo die berechnet werden.
riwe Auf diesen Beitrag antworten »

Zitat:
Original von Jane Doe
Danke für das Beispiel, aber wo genau berechnest Du denn die Schnittpunkte ? :O


nicht "jammern" nur Augenzwinkern

ein schöner Code, die Spiegelung ist sehr elegant Gott
Jane Doe Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Die Schnittpunkte mit dem Rechteck? Na das sind (xin,yin) und (xout,yout) - ist doch ersichtlich, wo die berechnet werden.

Ich glaube ich habe gerade einen Knoten im Gehirn. Kannst Du bitte kurz erklären wie Du damit auf die Schnittpunkte zweier Strecken kommst ?

Meine Routine dafür sieht folgendermaßen aus:
code:
1:
	denom = (y2e-y2s) * (x1e-x1s) - (x2e-x2s) * (y1e-y1s)	IF (ABS(denom) < 1.E-008) THEN RETURN FALSE    ua = ((x2e - x2s) * (y1s - y2s) - (y2e - y2s) * (x1s - x2s)) / denom    ub = ((x1e - x1s) * (y1s - y2s) - (y1e - y1s) * (x1s - x2s)) / denom	IF ua >= 0 AND ua <= 1 AND ub >= 0 AND ub <= 1		xpoint = x1s + ua * (x1e - x1s)		ypoint = y1s + ua * (y1e - y1s)		RETURN TRUE	ELSE		RETURN FALSE	ENDIF


Wobei x1,y1 die Punkte der ersten Strecke und x2,y2 die der zweiten sind.
Jane Doe Auf diesen Beitrag antworten »

Ach Mist...Jetzt hats die Formatierung meines Codes zerpflückt.
HAL 9000 Auf diesen Beitrag antworten »

Wir haben hier bei den Rechteckseiten doch den Sonderfall von achsenparallelen Strecken (d.h. zur x- oder y-Achse) - da kann man doch die Schnittpunktrechnung drastisch vereinfachen - was ich dann auch getan habe. Augenzwinkern
Jane Doe Auf diesen Beitrag antworten »

Stimmt, Du hast Recht. Das hatte ich nicht bedacht, sondern bin von einer allgemeinen Schnittpunktberechnung ausgegangen. Kein Wunder daß das bei Dir um einiges schneller läuft. Freude
URL Auf diesen Beitrag antworten »

Das habe ich dir hier

schon gesagt geschockt
Jane Doe Auf diesen Beitrag antworten »

Das mag sein, aber nicht jeder kann etwas mit dieser Formelschreibweise anfangen. Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »