Probleme beim Zufalls-Punkte erzeugen [gelöst]

[heinz]

@Lohengrin
Danke nochmals fuer die ausfuehrliche Erklaerung!

Was für drei Radien? Meinst du drei Radien vom Ellipsoid?

rX=2000; rY=1000; rZ=500

Ich hoffe so wird es "klarer" was ich meine...

Ich empfehle immernoch Montecarlo.

Und ein paar Posts vorher:

Kreis ...Du nimmst solange zwei Zufallszahlen z0 und z1 zwischen 0 und 1, bis z0^2+z1^2 < 1
Ellipsoid geht genauso. Da wiederholst du, bis du (z0/a)^2+(z1/b)^2+(z2/c)^2 < 1 hast.

das wollte ich versuchen umzusetzen.
Mein Ziel ist ein Ellipsoid.
Der Kreis scheint mir verstaendlich.
Allerdings scheitere ich daran, zu verstehen was im Zusammenhang mit dem Ellipsoid a,b und c ist.
Sind das die max. Radius-Werte? Also z.B. a=2000; b=1000; c=500;?
Falls ja, muessten die Radien dann nicht auch in der Kreis-Formel auftauchen?
z.B. (z0/a)^2+(z1/b)^2 < 1

Gruss, heinz

[Lohengrin]

Kreis ...Du nimmst solange zwei Zufallszahlen z0 und z1 zwischen 0 und 1, bis z0^2+z1^2 < 1
Ellipsoid geht genauso. Da wiederholst du, bis du (z0/a)^2+(z1/b)^2+(z2/c)^2 < 1 hast.

das wollte ich versuchen umzusetzen.
Mein Ziel ist ein Ellipsoid.
Der Kreis scheint mir verstaendlich.
Allerdings scheitere ich daran, zu verstehen was im Zusammenhang mit dem Ellipsoid a,b und c ist.
Sind das die max. Radius-Werte? Also z.B. a=2000; b=1000; c=500;?

Das habe ich falsch, mindestens verwirrend, erklärt.
Beim Kreis habe ich z0 und z1 aus dem Bereich von 0 bis 1 genommen.
Beim Ellipsoid habe ich z0 aus dem Bereich von -a bis a, z1 aus dem Bereich von -b bis b und z2 aus dem Bereich von -c bis c gemeint.

Du kannst einen Ellipsoid erzeugen, wenn du die Einheits-Kugel streckst. Streckst du in alle drei Richtungen gleich, also a=b und b=c, dann wird es eine Kugel.
Wenn du etwas in den Raum streust, und wissen willst, ob es im Ellipsoid ist, dann machst du die Streckung wieder rückgängig, und schaust, ob das dann in der Einheitskugel ist.

Falls ja, muessten die Radien dann nicht auch in der Kreis-Formel auftauchen?
z.B. (z0/a)^2+(z1/b)^2 < 1

Beim Kreis ist a=b, wird da üblicherweise R genannt. (Das ist jetzt genau der Mathematikerwitz "Beweis durch Verwirrung": Sei a gleich b, wir nennen es c.) Aus (z0/a)^2+(z1/b)^2 < 1 wird dann (z0/R)^2+(z1/R)^2 < 1, mit "mal R^2" äquivalent umgeformt ergibt das z0^2+z1^2 < R^2, also "(z0,z1) liegt in Kugel mit Radius R" gemäß Pythagoras (Beachte das Dreieck mit den Eckpunkten (0,0), (z0,0), (z0,z1). Der rechte Winkel ist bei (z0,0), die lange Seite ist von (0,0) nach (z0,z1), Länge R.).

Um einen gleichmäßig gefüllten Ellipsoid zu bauen, kannst du z0,z1,z2 aus dem Bereich von -1 bis 1 wählen, und mitnehmen, wenn z0^2+z1^2+z2^2 < 1. Dann hast du eine gefüllte Einheitskugel. Das streckst du dann zum Ellipsoid, also (z0,z1,z2) wird zu (a*z0, b*z1, c*z2).

Du kannst aber auch z0 aus dem Bereich von -a bis a, z1 aus dem Bereich von -b bis -b und z2 aus dem Bereich von -c bis c nehmen. Dann hast du erst einmal einen gleichmäßig gefüllten Quader. Du nimmst den Punkt mit, wenn er im Ellipsoid liegt, also wenn (z0/a)^2 + (z1/b)^2 + (z2/c)^2 < 1.

[heinz]

Ich hoffe, ich habe es jetzt kapiert.

Der Code sieht jetzt so aus:
40591
Ist das so wie Du es meintest?
(Ups: > mit < verwechselt...)

Die Werte, die dabei entstehen:
40590

Und aussehen tut es jetzt so:

(Ist wieder ein animiertes .gif Rotiert um die x- und y-Achse
Die x-, y- und z-Radius-Werte sind alle gleich damit eine Kugel entsteht.
Die Kamera blickt von oben drauf.)

Ersetze ich:

Code: Alles auswählen

while(rX*rX + rY*rY + rZ*rZ > 1.0);

durch

Code: Alles auswählen

while(rX*rX + rY*rY + rZ*rZ < 1.0);

Sieht es so aus:



Es ist zum Maeusemelken...

Gruss, heinz

[Lohengrin]

Warum die Winkel? Lass das weg!

Code: Alles auswählen

do
        {
                rX=(double)(rand()%20000000 - 10000000)/10000000.0;
                rY=(double)(rand()%20000000 - 10000000)/10000000.0;
                rZ=(double)(rand()%20000000 - 10000000)/10000000.0;
        }
        while(rX*rX + rY*rY + rZ*rZ > 1.0);

macht solange einen Punkt (rX,rY,rZ) in den Würfel [-1,1]x[-1,1]x[-1,1], bis (rX,rY,rZ) in der Einheitskugel liegt.
Das steckst du dann.

Code: Alles auswählen

XX=radX*rX;
YY=radY*rY;
ZZ=radZ*rZ;

Das Ergebnis ist ein Punkt (XX,YY,ZZ) im Ellipsoid

[heinz]

Lieber Lohengrin ,

ES FUNKTIONIERT!

Warum die Winkel? Lass das weg!

Sorry, das ich so lange gebraucht habe um es zu kapieren...

Vielen herzlichen Dank fuer Deine Geduld und Deine ausdauernde Hilfe!

Auch nochmals vielen Dank an alle anderen, die sich damit beschaeftigt haben.

Gruss, heinz

Falls es sonst noch jemanden interessiert, hier ist die endgueltige Loesung:
40592

[reox]

Warum die Winkel? Lass das weg!

Ja die Lösung hatten wir ja auch schon für 2D. Interessant wäre es jetzt so eine Lösung zu machen ohne das man Werte wegwirft

[heinz]

Interessant wäre es jetzt so eine Lösung zu machen ohne das man Werte wegwirft

Interessieren wuerde mich das natuerlich auch, allerdings befuerchte ich, dass ich keine
Ahnung davon haette, warum es am Ende funktioniert...
Ich muss gestehen, etwas neidisch auf Euer mathematisches Verstaendnis zu sein...
Auf jeden Fall bin ich sehr Dankbar, hier (wie schon oft) eine Loesung fuer mein Problem gefunden zu haben.
Falls Ihr Euch hier weiterhin mathematische Formeln um die Ohren hauen moechtet, werde ich natuerlich
mit Begeisterung mitlesen und versuchen etwas daraus zu lernen...


Mit der derzeitigen Version habe ich mal etwas herumgespielt:
Das Programm ist in C geschrieben.
Startbedingung ist:
20000 Stellen in einer ca. 2 MB. grossen .txt Datei, durch die berechneten Werte zu ersetzen.

Code: Alles auswählen

translate <[>

wird zu

Code: Alles auswählen

translate <-91.9506 , -9.98181 , -20.8027>

Bei der Berechnung in 2D werden im Schnitt 5470 erzeugte Werte (rX, rY) verworfen.
Bei der Berechnung in 3D werden im Schnitt 18200 erzeugte Werte (rX, rY, rZ) verworfen.
Die Laufzeit des Programms liegt im Schnitt zwischen 0.08 bis 0.1 sek.
Das Ergebnis sieht immer perfekt gleichverteilt aus.

Gruss, heinz

[Lohengrin]

20000 Stellen
...
Bei der Berechnung in 2D werden im Schnitt 5470 erzeugte Werte (rX, rY) verworfen.
Bei der Berechnung in 3D werden im Schnitt 18200 erzeugte Werte (rX, rY, rZ) verworfen.

Für 2D:
Der Kreis mit Radius 1 hat die Fläche pi*1^2=pi. Das Quadrat [-1,1]x[-1,1] hat die Fläche 2*2=4. Es werden die weggeworfen, die nicht im Kreis sind. Für 20000 im Kreis braucht man 4/pi mal so viele Schüsse ins Quadrat, also etwa 25500, macht etwa 5500 zu erwartende Verworfene. 5470 passt.
Für 3D:
Die Kugel mit Radius 1 hat Volumen 4/3*pi*1^3=4/3*pi (Achtung! Gerechnet wird von links nach rechts. (4/3)*pi und 4/(3*pi) ist nicht dasselbe.). Der Würfel [-1,1]x[-1,1]x[-1,1] hat Volumen 2^3=8. Es werden die weggeworfen, die nicht in der Kugel sind. Für 20000 in der Kugel braucht man 8/(4/3*pi) Schüsse in den Würfel, also etwa 38200, macht etwa 18200 zu erwartende Verworfene. 18200 passt.

Wozu will hier jemand eine Lösung haben, wo man keine Werte verliert? Es geht bei 3D um "die Hälfte wirft man weg". Dafür würde ich keinen Tamtam machen.
Früher, als man noch nicht mal so einfach ein paar Millionen mal schießen konnte, hat man solche Probleme umgeformt, und kam dann oft nur bis zu etwas, über das es Tabellen gab. Dabei hatte man dann oft immernoch einen Approximationsfehler. Das ist heute gar nicht mehr nötig, und bei Approximationsfehler ist Montecarlo sogar besser.
Ich verstehe ja, dass das die Leute ärgert, die noch gelernt haben, wie man das umformen muss, um die Tabelle benutzen zu können. Die Generation, die noch keine Computer hatte, ist heute schon lange im Ruhestand. Es ist jetzt die nächste Generation, die noch etwas gegen Montecarlo hat, weil deren Lehrer ihnen erzählt haben, dass das Banausentum sei.
Mir hat mal ein uralter Mathematiker erzählt, dass die Banausen bevor es Computer gab mit 80g-Papier, Schere und Feinwaage integriert hätten.

[reox]

Wozu will hier jemand eine Lösung haben, wo man keine Werte verliert?

Weil es vielleicht interessant ist genau dieses Problem zu lösen

[hikaru]

Wozu will hier jemand eine Lösung haben, wo man keine Werte verliert? Es geht bei 3D um "die Hälfte wirft man weg". Dafür würde ich keinen Tamtam machen.

Weil Montecarlo "Brute Force", also unelegant ist, wie mein (natürlich hinkender) Vergleich mit dem Paintballgewehr und der Zielscheibe zeigen sollte.
Den Algorithmus nutzt du nur, weil er mit moderner Rechentechnik vermeintlich billig ist. Das mag isoliert betrachtet richtig sein, aber weil alle so denken haben wir heute haufenweise Software-Bloat für den wir gigabyteweise RAM brauchen, nur um Briefe zu schreiben.
Ich hatte Spaß am Suchen nach einer Lösung, die nicht auf Quadrate schießt, wenn man Kreise treffen will. U.a. dank deiner Erklärungen habe ich auch verstanden, wo die Probleme der vorgestellten Implementierungen liegen. Ich glaube qualitativ verstanden zu haben, was man tun müsste, um den ursprünglichen Winkelansatz zum Ziel zu führen. Leider kann ich keine Lösung präsentieren, da ich mich seit jeher mit der mathematischen Formulierung von Lösungen schwer tue.

@heinz:
Mich würde abschließend noch interessieren, wozu du das brauchst. Als es noch um Kreise und Ellipsen ging, dachte ich, du willst Galaxien für dein Weltraumspiel erzeugen. Aber wozu sind die Kugeln? Kugelsternhaufen?

[reox]

Als es noch um Kreise und Ellipsen ging, dachte ich, du willst Galaxien für dein Weltraumspiel erzeugen.

Da ist aber die frage, ob eine Galaxie eine isotrope Verteilung hat. Ich würde jetzt ad-hoc sagen die Verteilung ist zur mitte hin dichter.
Schon wieder eine Baustelle

[MSfree]

Ich würde jetzt ad-hoc sagen die Verteilung ist zur mitte hin dichter.

Und die zur Mitte stürzenden Massen stürzen ja nicht geradewegs auf das Zentrum zu sondern folgen der Raumkrümmung, was letztlich zu einem Drehimpuls der Galaxie führt. Am Ende hat man durch den Drehimpuls und die resultierenden Zentripedalkräfte eine hübsche Scheibenform. Und selbst in so einer Scheibe kommt es zu anisotropen Massenverdichtungen, was zur Bildung von gekrümmten "Speichen" führt, den Spiralarmen....

OK, genug Physik für heute.

[heinz]

@heinz:
Mich würde abschließend noch interessieren, wozu du das brauchst.

Die Entstehungsgeschichte:

Ich habe zu Weihnachten einen Nikolaus in Pov erstellt der in einem Wald stehen sollte.
Also musste ich die Baeume so um ihn herum verteilen das keiner zwischen Kamera und Nikolaus steht und sich alle innerhalb eines kreisfoermigen Horizontes befinden.
Von Hand, eine Sisyphusaufgabe...

Da ich Computer mag und gerne Programmiere schrieb ich mir also ein Programm mit dem ich in der POV-Datei einzelne Zeichen durch Zufallswerte ersetzen konnte.
Das hab ich dann einfach so oft laufenlassen bis es gepasst hat.

Als ich dann spaeter im Bett lag, (im Bett hab ich immer gute Ideen...) dachte ich mir, es waere doch praktisch ein Programm zu haben welches
die Koordinaten gleich Kreisfoermig korrekt verteilen kann und das man auf alle Arten von ASCI-Dateien "loslassen" kann.
Sowas wie >tr<, nur mit Zufallszahlen...
Und daraus entstand dann die Idee es auch gleich in 3D zu machen, da ich bis jetzt nur "2D-Sachen" Programmiert hatte.

Als es noch um Kreise und Ellipsen ging, dachte ich, du willst Galaxien für dein Weltraumspiel erzeugen. Aber wozu sind die Kugeln? Kugelsternhaufen?

Mein Weltraumspiel ruht z.Z. etwas... Aber ich habe auch schon einiges geschafft.
Man kann z.B. schon in der Galaxis "rumfliegen" (65536 * 65536 = 4294967296 Sektoren. Davon ca. 20000000 Sternsysteme mit bis zu 10 Planeten.)
Es gibt einen Pilot der Luft, Nahrung und normale Temperaturen braucht.
Man kann schon Materialien auf den Planeten mittels einer Sonde abbauen, das Schiff an Gasplaneten auftanken, aus den Rohstoffen "Dinge herstellen",
die Energieverteilung einstellen, das Schiff reparieren und noch einiges mehr.
Es fehlt aber auch noch sehr viel. Der Aufwand ist "ziemlich Riesig".
Alle Animationen sind mit POV erstellt, Grafiken meist mit Gimp oder Inkscape. Die gesamte Vertonung fehlt noch komplett, usw. usf.
Der Code ist eine Mischung aus C und C++, fuer die Garfik nutze ich SDL.
Es war irgendwie schon immer eine Art "Traum" von mir mal ein Weltraumspiel zu machen.
Ich hoffe ich bekomme es irgendwann fertig...

Gruss, heinz

[Lohengrin]

Den Algorithmus nutzt du nur, weil er mit moderner Rechentechnik vermeintlich billig ist.

Der andere Weg ist mit Rechnerei verbunden.
Wenn man Radius vom Raumwinkel abtrennt, muss man, um den Radius zu wählen, dritte Wurzel ziehen. Wenn man dann noch den Raumwinkel in phi und theta zerlegt, muss man, um theta zu wählen, asin rechnen. Und dann nochmal sin und cos, um das wieder in kartesischen Koordinaten zu haben, die man dann plotten kann.

Ich weiß nicht, wie aufwendig das Erzeugen von Zufallszahlen ist. Wenn ich besonders zufällige Zufallszahlen haben will, würde ich die Rechnerei in Kauf nehmen, um die Anzahl der Schüsse nicht zu verdoppeln.

Ich glaube qualitativ verstanden zu haben, was man tun müsste, um den ursprünglichen Winkelansatz zum Ziel zu führen.

Ich halte den Winkelansatz für unnötig kompliziert. Das wäre sinnvoll, wenn der Radius vom Raumwinkel getrennt sein soll, und wenn es eine bevorzugte Achse gibt, zB weil das Ding um die Polachse rotiert.
Es sollen kartesische Koordinaten geplottet werden, also erzeuge ich möglichst einfach kartesische Koordinaten.

Ein Hau-Ruck-Verfahren zur Erzeugung einer Gleichverteilung in der Einheitskugel, ohne daneben schießen zu müssen, wäre, erst x, dann y und dann z zu wählen.
Für x brauche ich einen Zufallsgenerator, der etwas zwischen -1 und 1 ausgibt, und dessen Dichte proportional zur Fläche des Schnittes der Einheitskugel bei x ist, also Dichte proportional zu 1-x^2. Die Dichte muss man integrieren und die Konstanten so wählen, dass es die Verteilungsfunktion eines Wahrscheinlichkeitsmaßes wird. Die Umkehrfunktion der Verteilungsfunktion ist das Passende, was aus auf 0 bis 1 gleichverteilten Zufallszahlen x macht.
Dann kommt die y-Koordinate des Punktes, der in dieser Schnittfläche der Einheitskugel liegt (ein Kreis mit Radius 1-x^2). Die Dichte muss in der Mitte proportional zu Wurzel(1-x^2-y^2) sein, davor und dahinter 0. Integriert wird das irgendwas Wildes mit asin. Und umkehren muss man das dann auch noch.
Dann kommt die z-Koordinate dran. Das ist dann gleichverteilt zwischen minus und plus Wurzel(1-x^2-y^2).

[hikaru]

Ich habe zu Weihnachten einen Nikolaus in Pov erstellt der in einem Wald stehen sollte.
Also musste ich die Baeume so um ihn herum verteilen das keiner zwischen Kamera und Nikolaus steht und sich alle innerhalb eines kreisfoermigen Horizontes befinden.
Von Hand, eine Sisyphusaufgabe...

Ich glaube, ich hätte den Nikolaus auf ein Feld gestellt.
Schön, dass du da etwas hartnäckiger warst!

Mein Weltraumspiel ruht z.Z. etwas... Aber ich habe auch schon einiges geschafft.
Man kann z.B. schon in der Galaxis "rumfliegen" (65536 * 65536 = 4294967296 Sektoren. Davon ca. 20000000 Sternsysteme mit bis zu 10 Planeten.)
Es gibt einen Pilot der Luft, Nahrung und normale Temperaturen braucht.
Man kann schon Materialien auf den Planeten mittels einer Sonde abbauen, das Schiff an Gasplaneten auftanken, aus den Rohstoffen "Dinge herstellen",
die Energieverteilung einstellen, das Schiff reparieren und noch einiges mehr.
Es fehlt aber auch noch sehr viel. Der Aufwand ist "ziemlich Riesig".

Klingt ein wenig nach "Elite". Dass der Aufwand riesig ist kann ich mir vorstellen.
Wahrscheinlich wirst du nie wirklich "fertg" werden, weil dir in einer offenen Spielwelt immer noch mehr einfallen wird.

Der andere Weg ist mit Rechnerei verbunden.
Wenn man Radius vom Raumwinkel abtrennt, muss man, um den Radius zu wählen, dritte Wurzel ziehen. Wenn man dann noch den Raumwinkel in phi und theta zerlegt, muss man, um theta zu wählen, asin rechnen. Und dann nochmal sin und cos, um das wieder in kartesischen Koordinaten zu haben, die man dann plotten kann.

Ich weiß nicht, wie aufwendig das Erzeugen von Zufallszahlen ist. Wenn ich besonders zufällige Zufallszahlen haben will, würde ich die Rechnerei in Kauf nehmen, um die Anzahl der Schüsse nicht zu verdoppeln.

Da hast du natürlich recht. Rechnen muss man bei beiden Varianten und den Aufwand müsste man dann gegeneinander abwägen. Ich finde es nur konzeptuell hässlich, Punkte zu erzeugen, von denen man von Anfang an weiß, dass man sie man gar nicht braucht.
Ich glaube, ein Grund warum mir der Montecarlo-Ansatz nicht gefällt ist, dass er mit steigender Dimensionszahl immer ineffizienter wird, weil das n-Volumen der n-Kugel im Vergleich zum n-Volumen des n-Kubus immer kleiner wird.

Es sollen kartesische Koordinaten geplottet werden, also erzeuge ich möglichst einfach kartesische Koordinaten.

Das und der Umstand, dass wir dazu nun eine funktionierende Lösung haben ist eigentlich das Einzige, was mich von dem Ansatz überzeugt: "It gets the job done."
Da stellt sich mir im Anschluss aber gleich die Frage, ob eine Kugel hier wirklich gebraucht wird, oder ob es nicht auch ein Kubus täte. Ich vermute, den Unterschied würde heinz in der letztendlich generierten Szene gar nicht sehen.

[heinz]

Schön, dass du da etwas hartnäckiger warst!

Naja, die wirklich hartnaeckigen wart eigentlich Ihr.
Ohne Eure Hilfe waere daraus wohl nicht viel geworden...

Klingt ein wenig nach "Elite".

*lach*... Der Unterschied zwischen meinem Spiel und Elite ist ungefaehr so wie Streichholz zu Supernova. Elite ist schon Kult...

Ich vermute, den Unterschied würde heinz in der letztendlich generierten Szene gar nicht sehen.

Leider doch. Zuerst hatte ich es ja auch mit einem Kubus/Quadrat gemacht.
Allerdings hatte ich da das Problem, am Horizont (eine grosse Kugel) immer wieder "abgeschnittene" Baeume zu haben.
Auch wenn man die Werte klein genug gewaehlt hat, damit die Ecken in die Kugel passten, sah es nicht so richtig gut aus.
Ausserdem lassen sich damit ja auch andere "lustige Sachen" anstellen...


Gruss, heinz