Gleichverteilte Punkte in einem Kreis


Problem: Wie bekommt man eine Gleichverteilung von Punkten in einem Kreis? Die Idee für ein Quadrat ist einfach: Man sucht sich einen zufälligen $x$-Wert und einen zufälligen $y$-Wert, und erhält einen Punkt $(x, y)$.

Gleichverteilung von 10000 Punkten in einem Quadrat
$(x, y)$ = (random(), random())

Eine naive Idee für einen Kreis kann sein, alle Punkte zu ignorieren, die außerhalb des Kreises liegen. Dafür berechnet man $ \sqrt{x^2 * y^2} $.

10000 Punkte in einem Quadrat, alle im Kreis sind eingefärbt
$(x, y)$ = (random(), random()), Kreis eingefärbt

Das ist aber nicht effizient. Man verliert mehr als ein Fünftel aller Punkte!1

Vielleicht hilft ein anderes Koordinatensystem. Beim Polarkoordinatensystem wird ein Punkt durch einen Radius und einen Winkel, $(r, \varphi)$, angegeben.

10000 Punkte in einem Kreis, mehr Punkte beim Ursprung als am Rand
$(r, \varphi)$ = (random(), random() * $0.5 \pi$)

Ein zufälliger Radius und ein zufälliger Winkel bilden aber keine Gleichverteilung ab.

Woran liegt das? Auf allen Strecken, die zwischen dem Mittelpunkt und dem Rand des Kreises liegen, sind gleich viele Punkte, da der Winkel ein Zufallswert ist. Ebenso liegt auf jedem Radius die selbe Anzahl an Punkten, da der Radius ebenfalls zufällig ist.

Das Problem ist, das ein größerer Radius einen größeren Kreis bildet. Auf einem Radius liegt aber immer dieselbe Anzahl von Punkten. Damit wird der Abstand zwischen den Punkten größer und die Dichte der Punkte nimmt mit größerem Radius ab.2

Die Lösung ist, als Radius die Wurzel einer zufälligen Zahl zu nehmen.

10000 gleichverteilte Punkte in einem Kreis
$(r, \varphi)$ = (sqrt(random()), random() * $0.5 \pi$)

Warum funktioniert das? Mit einer Wahrscheinlichkeitsdichtefunktion (WDF) berechnet man, wie wahrscheinlich es ist einen Wert zwischen zwei Punkten zu erhalten. Bisher war unsere WDF konstant, also $f(r) = a$, da jeder Radius $r$ gleich wahrscheinlich war. In jedem gleich großen Intervall waren die Anzahl der Punkte damit ebenfalls konstant.

Da der Umfang eines Kreises aber linear wächst ($2r\pi$), brauchen wir eine WDF, die ebenfalls linear wächst und damit die Dichte (und nicht die Anzahl) der Punkte konstant hält. Die wichtigen Eigenschaften einer WDF sind, das sie nichtnegativ ist und das Integral der Funktion von $-\infty$ bis $+\infty$ 1 ist.

Für unser spezielles Problem wollen wir also eine lineare Funktion, deren Integral zwischen 0 und dem Radius des Kreises $R$ gleich 1 ist. Eine Funktion $f(r) = r$ erfüllt diese Eigenschaften nicht: $ \int_0^R f(r) dr = R^2 / 2 = 0.5$ (mit $R=1$). Die Lösung ist aber naheliegend: $f(r) = 2r/R^2$ und damit $F(x) = \int_0^x f(r) dr = x^2 / R^2$ als Verteilungsfunktion.

Während man mit der Wahrscheinlichkeitsdichtefunktion berechnet, wie wahrscheinlich es ist einen Wert zwischen zwei Punkten zu erhalten, berechnet man mit einer Verteilungsfunktion die Wahrscheinlichkeit, das ein Wert kleiner/gleich einem gegebenen $x$ ist.

Wenn wir diese Funktion nun umkehren, berechnet sie nicht mehr wie wahrscheinlich ein Wert kleiner/gleich $x$ ist, sondern gibt den größtmöglichen Wert für eine gegebene Wahrscheinlichkeit an.

$$ F^{-1}(x): x = \frac{y^2}{R^2} $$ $$ y^2 = R^2 * x $$ $$ y = \sqrt{R^2 * x} $$ $$ F^{-1}(x) = R * \sqrt{x} $$

Die Graphen der genutzten Funktionen
Die Graphen der genutzten Funktionen

Wir können diesen größtmöglichen Wert als unseren tatsächlichen Wert für den Radius wählen. Damit haben wir eine Menge von gleichverteilten Punkten in einem Kreis.

Ein voller Kreis
$(r, \varphi)$ = (sqrt(random()), random() * $2 \pi$)


  1. $$1 - \frac{A_{Kreis}}{A_{Quadrat}} = $$ $$ 1 - \frac{R^2\pi}{(2R)^2} = $$ $$ 1 - \frac{\pi}{4} \approx 0.2146$$ ↩︎

  2. $$ Dichte = \frac{Punkte}{Umfang} = \frac{Punkte}{2r\pi} $$ Wird der Radius größer, wird die Dichte kleiner. ↩︎