Punkt auf Kugel berechnen (programmiert)

22.11.2016, 09:39

iboaz

Auf diesen Beitrag antworten »

Punkt auf Kugel berechnen (programmiert)

Meine Frage:
Hi,
ich möchte einen Punkt auf einer Kugel berechnen. Ich wollte mal fragen, ob meine Berechnungen stimmen oder Sinn machen. Ziel ist es, durch diese Berechnung einen zufälligen Punkt auf der Oberfläche zu erhalten.

Da ich das Ganze ausprogrammiert habe, versuche ich es mal in normale Sprache zu übersetzen..

Meine Ideen:
Gegeben ist der Radius. Gesucht ist ein Vektor.

c1 = Zufallszahl im Intervall von -radius bis radius
c2 = Zufallszahl im Intervall von -(Wurzel(radius²-c1²)) bis Wurzel(radius²-c1²)
c3 = (Wurzel(radius²-c1²-c2²)) * (Zufallszahl im Intervall von (0 oder 1) * 2 - 1) weil c3 ja erstmal nur positiv ist und so positiv oder negativ sein kann

Der Vektor hat die Koordinaten (c1,c2,c3)

Falls jemand die schönere Schreibweise programmiert haben möchte, hier einmal der Code:

Vector3 CalcPoint(float radius)
{
float c1 = Random.Range(-radius, radius);
float c2 = Random.Range(-(Mathf.sqrt(radius²-c1²)), Mathf.sqrt(radius²-c1²));
float c3 = (Mathf.sqrt(radius²-c1²-c2²)) * (Random.Range(0,1) * 2 - 1);
return new Vector3(c1,c2,c3);
}

22.11.2016, 10:09

HAL 9000

Auf diesen Beitrag antworten »

Damit erzeugst du einen zufälligen Punkt $\begin{align*} X \end{align*}$ auf der Kugeloberfläche, ja. Allerdings ist dieser Punkt nicht gleichmäßig stetig auf dieser Oberfläche verteilt.

Letzteres wäre so erreichbar:

$\begin{align*} c_1 \end{align*}$ = Zufallszahl im Intervall von $\begin{align*} [-r,r] \end{align*}$ (d.h. kann wie oben bleiben), anschließend setze man $\begin{align*} \varrho := \sqrt{r^2-c_1^2} \end{align*}$

$\begin{align*} \varphi \end{align*}$ = Zufallszahl im Intervall $\begin{align*} [0,2\pi] \end{align*}$ (Winkel)

$\begin{align*} c_2 = \varrho\cdot \cos(\varphi) \end{align*}$

$\begin{align*} c_3 = \varrho\cdot \sin(\varphi) \end{align*}$ .

-----------------------------

Es gibt auch eine banalere Methode, die aber ebenfalls korrekt gleichmäßig stetig auf der Oberfläche verteilte Punkte liefert:

1) Wiederhole "Zufallszahlen $\begin{align*} t_1,t_2,t_3 \end{align*}$ im Intervall [-1,1] auswürfeln" solange, bis $\begin{align*} t_1^2+t_2^2+t_3^2\leq 1 \end{align*}$ gilt.

2) Setze $\begin{align*} c_k = \lambda t_k \end{align*}$ mit $\begin{align*} \lambda = \frac{r}{\sqrt{t_1^2+t_2^2+t_3^2}} \end{align*}$ .

Diese Methode hat den Nachteil, dass das Auswürfeln in Schritt 1) im Mittel $\begin{align*} \frac{6}{\pi}\approx 1.9 \end{align*}$ -mal durchgeführt werden muss. Dafür sind dann aber auch nur eine Wurzelbildung und keinerlei trigonometrische Funktionen notwendig.

P.S.: $\begin{align*} (t_1,t_2,t_3) \end{align*}$ ist ein gleichmäßig stetig verteilter Punkt im gesamten Kugelvolumen. Durch Operation 3) projeziert man diesen Punkt auf die Kugeloberfläche (Normalisierung).

22.11.2016, 14:33

zorg

Auf diesen Beitrag antworten »

.
Habe mir mal einen Account zugelegt smile

smile

Du meinst mit gleichmäßiger Verteilung, dass 100 Punkte gleichmäßig auf der Kugel liegen?

Das wäre nicht das Ziel, nachdem der Zufallspunkt berechnet wurde, soll ein neuer zufälliger berechnet werden, unabhängig davon, wo der vorherige Punkt gelegen hat.

Leider verstehe ich deinen Post nicht ganz, also wenn ich meine Methode zu deiner abändere, bräuchte ich noch ein paar Antworten.

ϱ:= ...

Das ist einfach eine Variable mit einer Zuweisung? Also könnte da auch "Haus = .." stehen?

Gleiches für

Æ = ...

Dann wäre deine Berechnung ja sehr verkürzt und übersichtlicher, aber ich würde gerne vorher die Antwort zu meiner 1. Frage wissen smile

smile

Wenn alles Random sein soll, ist der Satz

"Allerdings ist dieser Punkt nicht gleichmäßig stetig auf dieser Oberfläche verteilt."

hinfällig oder meinst du damit etwas anderes =?

22.11.2016, 14:45

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von zorg
Du meinst mit gleichmäßiger Verteilung, dass 100 Punkte gleichmäßig auf der Kugel liegen?

Streng nach Definition: Ist $\begin{eqnarray*} A \end{eqnarray*}$ eine beliebige Teilfläche der Gesamtoberfläche $\begin{eqnarray*} O \end{eqnarray*}$ der Kugel, dann ist die Wahrscheinlichkeit dafür, dass ein gleichmäßig stetig auf der Oberfläche verteilter Punkt $\begin{eqnarray*} X \end{eqnarray*}$ in $\begin{eqnarray*} A \end{eqnarray*}$ liegt gleich $\begin{eqnarray*} \frac{|A|}{|O|} = \frac{|A|}{4\pi r^2} \end{eqnarray*}$ , dabei ist $\begin{eqnarray*} |A| \end{eqnarray*}$ der Flächeninhalt von $\begin{eqnarray*} A \end{eqnarray*}$ .

D.h., diese Wahrscheinlichkeit hängt nur vom Flächeninhalt, nicht aber von der konkreten Lage der Teilfläche $\begin{eqnarray*} A \end{eqnarray*}$ auf $\begin{eqnarray*} O \end{eqnarray*}$ ab.

Bei deiner Simulation ist das leider nicht der Fall, da werden bestimmte Zonen der Oberfläche bevorzugt und andere vernachlässigt. Es sind zwar alle Gebiete der Oberfläche irgendwie erreichbar, aber eben mit unterschiedlicher Intensität (=Dichte), und damit ist es keine stetige Gleichverteilung - dessen solltest du dir bewusst sein!

22.11.2016, 15:26

zorg

Auf diesen Beitrag antworten »

Ok, ich habe noch nicht genau verstanden, WARUM manche Gebiete bevorzugt werden.

Weil Zufall für den Computer nicht Zufall bedeutet? Also weil es kein wirkliches random in der Rechnung gibt?

22.11.2016, 15:29

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von zorg
Ok, ich habe noch nicht genau verstanden, WARUM manche Gebiete bevorzugt werden.

Weil man das ausrechnen kann, streng gemäß der stochastischen Verteilung. Ich habe irgendwie den Eindruck, dass du da nicht so richtig fit bist auf dem Gebiet - kann das sein?

--------------------------

Ok, beleuchten wir mal dein Verfahren:

Nehmen wir $\begin{align*} c_1 \end{align*}$ beliebig, und $\begin{align*} c_2 \end{align*}$ so, dass wir genau die "mittlere Hälfte" von $\begin{align*} -\sqrt{r^2-c_1^2} \leq c_2 \leq \sqrt{r^2-c_1^2} \end{align*}$ betrachten, also $\begin{align*} -\frac{1}{2}\sqrt{r^2-c_1^2} \leq c_2 \leq \frac{1}{2}\sqrt{r^2-c_1^2} \end{align*}$ . Und $\begin{align*} c_3 \end{align*}$ darf dann wieder beliebig sein (also in dem Kontext hier positiv oder negativ, der Betrag steht ja vorab fest).

Dann wird diese Konfiguration "mittlere Hälfte bzgl. $\begin{align*} c_2 \end{align*}$ " mit deinem Verfahren in 50% der Fälle ausgewürfelt, repräsentiert aber nur zwei Kugelzweiecke ("Apfelsinenstücke") mit einer Gesamtoberfläche, die nur einem Drittel der Kugeloberfläche entspricht. D.h. diese Kugelzweiecke werden mit deinem Verfahren öfter bedient, als ihnen laut Fläche zusteht.

Anzeige

22.11.2016, 15:44

zorg

Auf diesen Beitrag antworten »

Danke für die Erklärung.

Ja du hast Recht, ich bin da absolut nicht mehr fit. Mein Abi ist 4 Jahre her, habe dazwischen gar nichts mehr mit Mathe zu tun gehabt und natürlich ist Mathe beim programmieren sehr wichtig, aber mein zu programmierendes Problem ist auch sehr speziell.

22.11.2016, 15:46

HAL 9000

Auf diesen Beitrag antworten »

Naja, vielleicht ist dir ja die Gleichverteilung nicht wichtig (obwohl es mir danach klang), sondern nur, dass alle Gebiete der Kugeloberfläche irgendwann mal erreicht werden. Dann kannst du natürlich so vorgehen, wie du es wolltest.

22.11.2016, 15:56

zorg

Auf diesen Beitrag antworten »

Also ich habe einen Planeten mit einer Spielfigur. Und man bewegt sich auf dieser Kugel. Jetzt habe ich gespawnte NPCs mit einer künstlichen Intelligenz. Diese sollen sich zufällig hin und her bewegen, und sich dementsprechend Wegpunkte erstellen.

Dafür brauche ich diese Punkte und wollte wissen, ob meine Berechnung Sinn macht smile

smile

22.11.2016, 16:05

HAL 9000

Auf diesen Beitrag antworten »

Machen wir ohne große theoretische Rechnung einen ganz einfachen Test: Führe deine Simulation 10000mal durch und zähle dabei die Punkte $\begin{align*} (c_1,c_2,c_3) \end{align*}$

a) mit $\begin{align*} |c_2|<0.1r \end{align*}$
b) mit $\begin{align*} |c_3|<0.1r \end{align*}$

Jede Wette, dass die Zahl von a) mindestens dreimal so groß ist wie die von b). Ersetzt man 0.1 durch einen noch kleineren Wert (und erhöht im gleichen Zug die Simulationszahl, damit es auch noch was zu zählen gibt), dann wird das (Miss-)Verhältnis der Anzahlen immer krasser.

Wenn dich das nicht stört, dann bleib bei deinem Verfahren. Falls doch, dann rate ich dir zur echten Gleichverteilung zu wechseln.

22.11.2016, 16:52

zorg

Auf diesen Beitrag antworten »

Ja, du hast Recht, die Verteilung war schon unverhältnismäßig unterschiedlich ..

Vielen Dank für deine Hilfe smile

smile

23.11.2016, 11:17

HAL 9000

Auf diesen Beitrag antworten »

Ich hab nochmal nachgedacht, und eine Synthese der beiden oben von mir genannten Methoden erstellt, besser hinsichtlich Effizienz:

1) $\begin{align*} c_1 \end{align*}$ = Zufallszahl im Intervall von $\begin{align*} [-r,r] \end{align*}$ .

2) Wiederhole "Zufallszahlen $\begin{align*} t_2,t_3 \end{align*}$ im Intervall [-1,1] auswürfeln" solange, bis $\begin{align*} t_2^2+t_3^2\leq 1 \end{align*}$ gilt.

3) Setze $\begin{align*} c_k = \lambda t_k \end{align*}$ für $\begin{align*} k=2,3 \end{align*}$ mit $\begin{align*} \lambda := \sqrt{\frac{r^2-c_1^2}{t_2^2+t_3^2}} \end{align*}$ .

Hier muss das Auswürfeln in Schritt 2) im Mittel nur noch $\begin{align*} \frac{4}{\pi}\approx 1.27 \end{align*}$ -mal durchgeführt werden muss.

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

Vector3 CalcPoint(float radius)
{
  float c1 = Random.Range(-radius, radius);
  float t2, t3, tq;
  do
  {
     t2 = Random.Range(-1,1);
     t3 = Random.Range(-1,1);
     tq = t2*t2+t3*t3;
  }
  while (tq > 1);
  float lambda = Mathf.sqrt((radius*radius-c1*c1)/tq);
  return new Vector3(c1,lambda*t2,lambda*t3);
}

24.11.2016, 13:41

zorg

Auf diesen Beitrag antworten »

Cool, vielen Dank für deine Mühe.

Ich finde echt nicht so einfach ... Also du hast jetzt den Code, der so glaube ich mal bestimmt auch funktioniert, aber jetzt hast du ja gar keinen Cosinus etc. mehr drin ;D

Also interessant wie sich die Berechnungen so wandeln :P

24.11.2016, 15:23

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von zorg
aber jetzt hast du ja gar keinen Cosinus etc. mehr drin

Das ist ja der Clou hinsichtlich Geschwindigkeit. Den man sich aber erkaufen muss durch die evtl. nötigen Wiederholungen in der do {} while-Schleife.

24.11.2016, 19:08

zorg

Auf diesen Beitrag antworten »

Ich habe mal deine neueste Berechnung getestet, leider kommen bei mir viele Werte mit "NaN" raus, meistens die 2. oder ganz oft die 3. Koordinate.

Deine 2. Rechnung scheint gut zu sein smile

smile

Die Werte sind sehr klein, meistens 0,0.. Wenn diese Punkte von der Kugel entfernt liegen sollen, reicht es, diese mit der Distanz zu multiplizieren?

Also wenn ich diese Berechnung nicht nur für die Kugel nutzen möchte, sondern die Punkte auch "um z.B. 100 Einheiten wegziehen" möchte.

Oder muss man dann den Vektor zum Mittelpunkt spiegeln? Also gucken wo der Vektor am Mittelpunkt liegt und diese Distanz verlängern.

24.11.2016, 22:30

zorg

Auf diesen Beitrag antworten »

Kleiner Nachtrag,
die Methode war sehr sehr rechenaufwändig, ich habe mal durch Formeln gestöbert, und konnte das hier mit viel Hilfe basteln

code:

1:

public Vector3 CalcSpawnPoint(float distanceToPlanet) { float pan = Random.Range(0, 2 * Mathf.PI); float tilt = Random.Range(0, 2 * Mathf.PI); float yr = Mathf.Cos(tilt) * (planetRadius + distanceToPlanet); float x = Mathf.Sin(pan) * (yr); float y = Mathf.Sin(tilt) * (planetRadius + distanceToPlanet); float z = Mathf.Cos(pan) * (yr); return new Vector3(x,y,z); }

Dadurch wird das Ganze ordentlich verteilt, glaube ich, also zumindest schön über die Kugel verteilt smile

smile

24.11.2016, 23:37

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von zorg
Ich habe mal deine neueste Berechnung getestet, leider kommen bei mir viele Werte mit "NaN" raus, meistens die 2. oder ganz oft die 3. Koordinate.

Kann ich jetzt nicht nachvollziehen, wieso das passieren kann. Die entsprechende Variante in C funktioniert tadellos.

Also entweder passiert das wegen tq=0, dazu müssten sowohl t2=0 als auch t3=0 sein (-> barbarisch schlechtes Random), oder aber wegen |c1|>radius, was auch nur passieren kann, wenn das Random nicht wie gedacht funktioniert. verwirrt

verwirrt

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »