Zufällige Punkte innerhalb einer Ellipse erzeugen

maxpayne80 · 24.06.2009

Hi zusammen

Hat vielleicht jemand eine Idee für einen Algorithmus, der (pseudo-)zufällig Punkte innerhalb einer Ellipse (gegeben sind Mittelpunkt und die 2 Radien) verteilen kann?
Die Punkte (also auch der Mittelpunkt) haben jeweils eine X-, Y- und Z-Koordinate.
Die Verteilung selber muss nur 2-dimensional sein, also es soll quasi nur eine der Koordinaten variiert werden (am besten X).

Muss nich gerade in C++ sein (darin mache ich das), Pseudocode oder eine Seite im Internet würden mir auch schon sehr weiterhelfen.

Vielen Dank
max

Andromedar · 24.06.2009

Gibt es keine RND Funktion? *noahnung*

maxpayne80 · 24.06.2009

Andromedar schrieb:
Gibt es keine RND Funktion?

Ja, aber das reicht nicht

Die Punkte sollen ja auf einer vorgegebenen Fläche liegen und nicht sonstwo verteilt.

Nachtschicht · 24.06.2009

Zufallspunkte erzeugen und dann testen, ob sie innerhalb der Ellipse liegen, im Link ist eine entsprechende Formel:

http://www.klamm.de/forum/archive/index.php/t-6352.html

maxpayne80 · 24.06.2009

Nachtschicht schrieb:
Zufallspunkte erzeugen und dann testen, ob sie innerhalb der Ellipse liegen, im Link ist eine entsprechende Formel:

http://www.klamm.de/forum/archive/index.php/t-6352.html

Ok ich werde mir das morgen mal zu Gemüte führen, für heute bin ich matsche. Danke

Für nen Kreis habe ich mir das eben gebastelt, das ging einigermaßen.

Devastators · 24.06.2009

maxpayne80 schrieb:
Ok ich werde mir das morgen mal zu Gemüte führen, für heute bin ich matsche. Danke
Für nen Kreis habe ich mir das eben gebastelt, das ging einigermaßen.

dann haste doch schon 90% vom Ergebnis?

Die Definition einer Ellipse ist doch nur unwesentlich schwieriger als bei einem Kreis.
Es muss also nur die Abfrage angepasst werden.

maxpayne80 · 24.06.2009

Devastators schrieb:
dann haste doch schon 90% vom Ergebnis?

Die Definition einer Ellipse ist doch nur unwesentlich schwieriger als bei einem Kreis.
Es muss also nur die Abfrage angepasst werden.

Wenn ich dir meine Methode zur Kreiserzeugung zeige wirst du das anders sehen

Das ganze ist in etwas Größeres integriert, daher mögen die Namen / Datenstrukturen evtl. etwas verwirrend klingen (außerdem bin ich kein super erfahrener Coder *buck*

).

Folgendes gibt eine Referenz auf ein Objekt (Typ "Vec") mit 3 Werten für x, y, z zurück, welches Koordinaten auf eine "Scheibe" hat; centerPosition ist natürlich der Mittelpunkt des Kreises:

Code:

Vec &SphereDomain::getRandomPositionInDomain() const
{

    Vec rand = randomVec();
    //This lets the vector be within a 1.0 radius sphere
    rand.normalize();
    // "Scheibe" in x-z dimension
    rand.xValue = centerPosition.xValue + rand.xValue * sphereRadius;
    rand.zValue = centerPosition.zValue + rand.zValue * sphereRadius;
    //Return a random position within this sphere
    return rand;
}

Hier die Methode randomVec()

Code:

Vec randomVec()
{
   return Vec((-(float)rand() / RAND_MAX) + ((float)rand() / RAND_MAX),(-(float)rand() / RAND_MAX) + ((float)rand() / RAND_MAX),(-(float)rand() / RAND_MAX) + ((float)rand() / RAND_MAX));
}

Und "normalize()":

Code:

void Vec::normalize()
{
    float normfactor = 1.0f / sqrtf(xValue*xValue+yValue*yValue+zValue*zValue);
    xValue *= normfactor;
    yValue *= normfactor;
    zValue *= normfactor;
}

Vielleicht ist dieser etwas "unkonventionelle" Ansatz verständlich, jedenfalls erzeugt das genau nen Kreis, ich wüsste aber nicht, wie ich das auf ne Ellipse umbauen sollte

Devastators · 24.06.2009

wenn ich nicht wüsste was Du da programmieren wolltest, hätte ich es auch nie erkannt *lol*

meine Idee:

http://www.htlortwein-graz.ac.at/edu/ras/kegelschnitte/ellipse/ellipse.htm

und dann der Teil:

a 2 – b 2 = e 2

Heißt quasie 2 Werte per Random und den Dritten dann ausrechnen, damit es passt.

Es gibt aber AFAIK auch andere Definitionen für eine Ellipse, ist mir aber nun zu spät.

Edit:
Ohne jetzt alles zu verraten

Beim Kreis hätte ich es wie folgt gemacht:
Radius per Zufall bestimmen (zwischen 0 und dem Radius des Begrenzungskreises)
Winkel per Zufall bestimmen. (beliebig 0-360!)

Beides dann zu einem Punkt ausgehend vom Mittelpunkt zusammenfügen.
2 Zufallszahlen hast Du dann gebraucht.

Mit einer Ellipse verhält es sich ähnlich einfach, müsstest nur die Mehrinformationen einer Ellipse verarbeiten

maxpayne80 · 25.06.2009

Devastators schrieb:
Beim Kreis hätte ich es wie folgt gemacht:
Radius per Zufall bestimmen (zwischen 0 und dem Radius des Begrenzungskreises)
Winkel per Zufall bestimmen. (beliebig 0-360!)

Beides dann zu einem Punkt ausgehend vom Mittelpunkt zusammenfügen.
2 Zufallszahlen hast Du dann gebraucht.

Mit einer Ellipse verhält es sich ähnlich einfach, müsstest nur die Mehrinformationen einer Ellipse verarbeiten

Ah ok macht Sinn

Ich wollte mich nur um die Winkelberechnungen drücken, da ich ehrlich gesagt in Sachen Mathe ne ziemliche Niete bin

Rones · 25.06.2009

Hier auch noch eine Variante in keiner konkreten Programmiersprache:

Code:

foreach punkt
	zufall = zufallszahl(0,10000) # je größer der Maximalwert desto besser

	temp1 = sinus(potenz(zufall,2))
	temp2 = cosinus(potenz(zufall,2))

	xfactor = zufall(0, maxradiusx)
	yfactor = zufall(0, maxradiusy)
	
	x = temp1 * xfactor + mittelpunktx
	y = temp2 * yfactor + mittelpunkty

	zeichnepunkt(x,y)

Das Resultat sind zufällige Punkte innerhalb der Ellipse, allerdings sind sie nicht gleichverteilt sondern häufen sich bedingt durch die Sinus- und Cosinus-Funktion zu der senkrechten und waagerechten Mittellinie hin. Schau' es Dir mal an, das Ergebnis nett

Insbesondere interessant sind die Ergebnisse bei wachsenden einstelligen Maximalgrößen für den Zufallswert in der Variable "zufall" - also die Zufallszahlen von 0-1, 0-2, 0-3 usw.

Viel Spaß beim Ausprobieren!

flybyray · 25.06.2009

Also ich denke wenn man sich an Geometrische Algorithmen traut, dann sollte man Mathematik vor allem Analytische Geometrie beherrschen.
Für diese Probleme die hier beschrieben werden gibt es mit Sicherheit vorgefertigte Bibliotheken.
Ich verweise hier zu erst einmal auf Wikipedia ( conic section / Kegelschnitt ). Wie fast immer ist der deutsche Beitrag unzureichend und ich kann einfach nur den englischen empfehlen.

Letztendlich sollte einem die Gleichung

Code:

Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0

ins Auge fallen. Deren Parameter untersucht werden. Hieraus ergeben sich dann Fälle für Ellipsen ( Kreise sind spezialfälle ).
Damit gibt es also schon mal einen Ansatz wie man ein Funktion und nicht mehrere für verschiedene Fälle schreibt.

Bibliotheken verwenden häufig intern Matrizen für all die Funktionen und Tests auf geometrischen Objekten. Im Englischen Wikipedia gibt es hier noch eine extra Seite über die Darstellung und Behandlung von Matrizen für Kegelschnitte ( Matrix representation of conic sections ).

Einige der vorher genannten links sind nicht gerade optimal. Meist behandeln sie nur achsensysmetrische Ellipsen. Mit den Gleichungen der Analytischen Geometrie befasst man sich sofort mit allen Freiheitsgraden (A,B,C,D,E,F) wobei F meist nicht dazu gezählt wird.

maxpayne80 · 25.06.2009

Rones schrieb:
Hier auch noch eine Variante in keiner konkreten Programmiersprache:

Code:

foreach punkt zufall = zufallszahl(0,10000) # je größer der Maximalwert desto besser temp1 = sinus(potenz(zufall,2)) temp2 = cosinus(potenz(zufall,2)) xfactor = zufall(0, maxradiusx) yfactor = zufall(0, maxradiusy) x = temp1 * xfactor + mittelpunktx y = temp2 * yfactor + mittelpunkty zeichnepunkt(x,y)

Das Resultat sind zufällige Punkte innerhalb der Ellipse, allerdings sind sie nicht gleichverteilt sondern häufen sich bedingt durch die Sinus- und Cosinus-Funktion zu der senkrechten und waagerechten Mittellinie hin. Schau' es Dir mal an, das Ergebnis nett

Insbesondere interessant sind die Ergebnisse bei wachsenden einstelligen Maximalgrößen für den Zufallswert in der Variable "zufall" - also die Zufallszahlen von 0-1, 0-2, 0-3 usw.

Viel Spaß beim Ausprobieren!

Ah danke, das hat mir tatsächlich gut geholfen denke ich. Nachdem ich meine Zufallsfunktion im Griff hatte *buck*

kam dann das hier raus (1000 Punkte jeweils als Anfangspunkt einer Linie):

Die Ellipse soll die Radien 5.0f und 10.0f vom Mittelpunkt aus haben, das scheint noch nicht so ganz zu passen

// Edit

Meine nächste Aufgabe ist nun, pro "Tiefenebene" eine Triangulierung zwischen je einem Partikel pro Ebene und "Faser" durchzuführen, und sozusagen ein 2D-Mesh zu erzeugen. Hui ... spaßig *buck*

Zufällige Punkte innerhalb einer Ellipse erzeugen

maxpayne80

Admiral Special

Andromedar

Cadet

maxpayne80

Admiral Special

Nachtschicht

Admiral Special

maxpayne80

Admiral Special

Devastators

Grand Admiral Special

maxpayne80

Admiral Special

Devastators

Grand Admiral Special

maxpayne80

Admiral Special

Rones

Vice Admiral Special

flybyray

Vice Admiral Special

maxpayne80

Admiral Special

Ähnliche Themen