Generiere einen zufälligen Punkt innerhalb eines Kreises (gleichmäßig)

Ich muss einen gleichmäßig zufälligen Punkt innerhalb eines Kreises mit dem Radius R erzeugen .

Mir ist klar, dass ich durch Auswahl eines gleichmäßig zufälligen Winkels im Intervall [0 ... 2π) und eines gleichmäßig zufälligen Radius im Intervall (0 ... R ) mehr Punkte in Richtung Zentrum erhalten würde, da für zwei gegeben Radien sind die Punkte im kleineren Radius näher beieinander als bei den Punkten im größeren Radius.

Ich habe hier einen Blogeintrag dazu gefunden, aber ich verstehe seine Argumentation nicht. Ich nehme an, es ist richtig, aber ich würde wirklich gerne verstehen, woher er (2 / R ² ) × r bezieht und wie er die endgültige Lösung herleitet.

Update: 7 Jahre nach dem Posten dieser Frage hatte ich immer noch keine zufriedenstellende Antwort auf die eigentliche Frage bezüglich der Mathematik hinter dem Quadratwurzel-Algorithmus erhalten. Also habe ich einen Tag damit verbracht, selbst eine Antwort zu schreiben. Link zu meiner Antwort .

Gehen wir so vor, wie es Archimedes getan hätte.

Wie können wir einen Punkt gleichmäßig in einem Dreieck ABC erzeugen, wobei | AB | = | BC |? Machen wir dies einfacher, indem wir auf ein Parallelogramm ABCD erweitern. In ABCD ist es einfach, Punkte einheitlich zu generieren. Wir wählen einheitlich einen zufälligen Punkt X auf AB und Y auf BC und wählen Z so, dass XBYZ ein Parallelogramm ist. Um einen einheitlich gewählten Punkt im ursprünglichen Dreieck zu erhalten, falten wir einfach alle Punkte, die im ADC erscheinen, entlang AC wieder nach ABC.

Betrachten Sie nun einen Kreis. Im Grenzfall können wir uns unendlich viele Isozelendreiecke ABC vorstellen, wobei B am Ursprung und A und C am Umfang verschwindend nahe beieinander liegen. Wir können eines dieser Dreiecke einfach durch Auswahl eines Winkels Theta auswählen. Wir müssen jetzt einen Abstand vom Zentrum erzeugen, indem wir einen Punkt im Splitter ABC auswählen. Erweitern Sie erneut ABCD, wo D jetzt doppelt so groß ist wie der Radius vom Kreismittelpunkt.

Das Auswählen eines zufälligen Punkts in ABCD ist mit der obigen Methode einfach. Wählen Sie einen zufälligen Punkt auf AB. Wählen Sie einheitlich einen zufälligen Punkt auf BC. Dh. Wählen Sie ein Paar Zufallszahlen x und y gleichmäßig auf [0, R], um Abstände vom Zentrum zu erhalten. Unser Dreieck ist ein dünnes Band, daher sind AB und BC im Wesentlichen parallel. Der Punkt Z ist also einfach ein Abstand x + y vom Ursprung. Wenn x + y> R, klappen wir zurück.

Hier ist der vollständige Algorithmus für R = 1. Ich hoffe du stimmst zu, dass es ziemlich einfach ist. Es wird trig verwendet, aber Sie können im random()Gegensatz zur Ablehnungsabtastung eine Garantie dafür geben, wie lange es dauern wird und wie viele Anrufe es benötigt.

t = 2*pi*random()
u = random()+random()
r = if u>1 then 2-u else u
[r*cos(t), r*sin(t)]

Hier ist es in Mathematica.

f[] := Block[{u, t, r},
  u = Random[] + Random[];
  t = Random[] 2 Pi;
  r = If[u > 1, 2 - u, u];
  {r Cos[t], r Sin[t]}
]

ListPlot[Table[f[], {10000}], AspectRatio -> Automatic]

So erzeugen Sie einen zufälligen Punkt innerhalb eines Kreises mit dem Radius R :

r = R * sqrt(random())
theta = random() * 2 * PI

(Angenommen, es random()wird einheitlich ein Wert zwischen 0 und 1 angegeben.)

Wenn Sie dies in kartesische Koordinaten konvertieren möchten, können Sie dies tun

x = centerX + r * cos(theta)
y = centerY + r * sin(theta)

Warum sqrt(random())?

Schauen wir uns die Mathematik an, die dazu führt sqrt(random()). Nehmen wir der Einfachheit halber an, dass wir mit dem Einheitskreis arbeiten, dh R = 1.

Der durchschnittliche Abstand zwischen Punkten sollte gleich sein, unabhängig davon, wie weit wir vom Zentrum entfernt sind. Dies bedeutet zum Beispiel, dass wir beim Betrachten des Umfangs eines Kreises mit Umfang 2 doppelt so viele Punkte finden sollten wie die Anzahl der Punkte am Umfang eines Kreises mit Umfang 1.

Da der Umfang eines Kreises (2π r ) linear mit r wächst , sollte die Anzahl der Zufallspunkte linear mit r wachsen . Mit anderen Worten wächst die gewünschte Wahrscheinlichkeitsdichtefunktion (PDF) linear. Da ein PDF eine Fläche von 1 haben sollte und der maximale Radius 1 ist, haben wir

Wir wissen also, wie die gewünschte Dichte unserer Zufallswerte aussehen soll. Nun: Wie erzeugen wir einen solchen Zufallswert, wenn wir nur einen einheitlichen Zufallswert zwischen 0 und 1 haben?

Wir verwenden einen Trick namens inverse Transformationsabtastung

1. Erstellen Sie aus dem PDF die kumulative Verteilungsfunktion (CDF).
2. Spiegeln Sie dies entlang y = x
3. Wenden Sie die resultierende Funktion auf einen einheitlichen Wert zwischen 0 und 1 an.

Klingt kompliziert? Lassen Sie mich ein Blockzitat mit einer kleinen Nebenspur einfügen, die die Intuition vermittelt:

Angenommen, wir möchten einen zufälligen Punkt mit der folgenden Verteilung generieren:

                

Das ist

• 1/5 der Punkte gleichmäßig zwischen 1 und 2 und
• 4/5 der Punkte gleichmäßig zwischen 2 und 3.

Die CDF ist, wie der Name schon sagt, die kumulative Version der PDF. Intuitiv: Während PDF ( x ) die Anzahl der Zufallswerte bei x beschreibt , beschreibt CDF ( x ) die Anzahl der Zufallswerte unter x .

In diesem Fall würde die CDF folgendermaßen aussehen:

                

Um zu sehen, wie nützlich dies ist, stellen Sie sich vor, wir schießen Kugeln von links nach rechts in gleichmäßig verteilten Höhen. Wenn die Kugeln die Linie treffen, fallen sie zu Boden:

                

Sehen Sie, wie die Dichte der Kugeln auf dem Boden unserer gewünschten Verteilung entspricht! Wir sind fast da!

Das Problem ist, dass für diese Funktion die y- Achse die Ausgabe und die x- Achse die Eingabe ist . Wir können nur "Kugeln vom Boden direkt nach oben schießen"! Wir brauchen die Umkehrfunktion!

Deshalb spiegeln wir das Ganze wider; x wird zu y und y wird zu x :

                

Wir nennen das CDF ^-1 . Um Werte entsprechend der gewünschten Verteilung zu erhalten, verwenden wir CDF ^-1 (random ()).

… Also zurück zur Erzeugung zufälliger Radiuswerte, bei denen unser PDF 2 x entspricht .

Schritt 1: Erstellen der CDF:

Da wir mit Real arbeiten, wird die CDF als Integral der PDF ausgedrückt.

CDF ( x ) = ∫ 2 x = x ²

Schritt 2: Spiegeln Sie die CDF entlang y = x :

Mathematisch kocht diese zu tauschen unten x und y und die Lösung für y :

CDF :      y = x ²
Swap:    x = y ²
Lösung:    y = √ x
CDF ^-1 :   y = √ x

Schritt 3: Wenden Sie die resultierende Funktion auf einen einheitlichen Wert zwischen 0 und 1 an

CDF ^-1 (random ()) = √random ()

Welches ist, was wir ableiten wollten :-)

Hier ist eine schnelle und einfache Lösung.

Wählen Sie zwei Zufallszahlen im Bereich (0, 1), nämlich aund b. Wenn b < aja, tauschen Sie sie aus. Ihr Punkt ist (b*R*cos(2*pi*a/b), b*R*sin(2*pi*a/b)).

Sie können sich diese Lösung wie folgt vorstellen. Wenn Sie den Kreis nehmen, ihn ausschneiden und dann gerade ausrichten, erhalten Sie ein rechtwinkliges Dreieck. Skalieren Sie dieses Dreieck nach unten, und Sie haben ein Dreieck von (0, 0)bis (1, 0)nach (1, 1)und wieder zurück nach (0, 0). Alle diese Transformationen ändern die Dichte gleichmäßig. Sie haben einheitlich einen zufälligen Punkt im Dreieck ausgewählt und den Vorgang umgekehrt, um einen Punkt im Kreis zu erhalten.

Man beachte die Punktdichte in proportional Quadrat des Radius zum inversen daher anstelle das Aufnehmen rvon [0, r_max], von der Abholung [0, r_max^2], dann berechnet die Koordinaten als:

x = sqrt(r) * cos(angle)
y = sqrt(r) * sin(angle)

Dadurch erhalten Sie eine gleichmäßige Punktverteilung auf einer Festplatte.

http://mathworld.wolfram.com/DiskPointPicking.html

Denken Sie so darüber nach. Wenn Sie ein Rechteck haben, bei dem eine Achse der Radius und eine Achse der Winkel ist, und Sie die Punkte innerhalb dieses Rechtecks ​​nehmen, die sich in der Nähe des Radius 0 befinden. Diese fallen alle sehr nahe an den Ursprung (der auf dem Kreis nahe beieinander liegt). Wenn die Punkte in der Nähe des Radius R liegen, fallen diese alle in die Nähe des Kreiskanten (dh weit voneinander entfernt).

Dies könnte Ihnen eine Vorstellung davon geben, warum Sie dieses Verhalten bekommen.

Der Faktor, der von diesem Link abgeleitet wird, gibt an, wie viel entsprechender Bereich im Rechteck angepasst werden muss, um nicht vom Radius abhängig zu sein, sobald er dem Kreis zugeordnet ist.

Bearbeiten: Also schreibt er in den Link, den Sie teilen, "Das ist einfach genug, indem Sie die Umkehrung der kumulativen Verteilung berechnen, und wir erhalten für r:".

Die Grundvoraussetzung ist hier, dass Sie eine Variable mit einer gewünschten Verteilung aus einer Uniform erstellen können, indem Sie die Uniform durch die Umkehrfunktion der kumulativen Verteilungsfunktion der gewünschten Wahrscheinlichkeitsdichtefunktion abbilden. Warum? Nehmen Sie es vorerst für selbstverständlich, aber das ist eine Tatsache.

Hier ist meine etwas intuitive Erklärung der Mathematik. Die Dichtefunktion f (r) in Bezug auf r muss proportional zu r selbst sein. Das Verständnis dieser Tatsache ist Teil aller grundlegenden Kalkülbücher. Siehe Abschnitte zu Polarbereichselementen. Einige andere Plakate haben dies erwähnt.

Also nennen wir es f (r) = C * r;

Dies stellt sich als die meiste Arbeit heraus. Da f (r) eine Wahrscheinlichkeitsdichte sein sollte, können Sie leicht erkennen, dass Sie durch Integration von f (r) über das Intervall (0, R) C = 2 / R ^ 2 erhalten (dies ist eine Übung für den Leser .)

Somit ist f (r) = 2 · r / R · 2

OK, so erhalten Sie die Formel im Link.

Dann geht der letzte Teil von der einheitlichen Zufallsvariablen u in (0,1) aus, die Sie durch die Umkehrfunktion der kumulativen Verteilungsfunktion aus dieser gewünschten Dichte f (r) abbilden müssen. Um zu verstehen, warum dies der Fall ist, müssen Sie wahrscheinlich einen Text mit fortgeschrittener Wahrscheinlichkeit wie Papoulis finden (oder ihn selbst ableiten).

Wenn Sie f (r) integrieren, erhalten Sie F (r) = r ^ 2 / R ^ 2

Um die Umkehrfunktion davon zu finden, setzen Sie u = r ^ 2 / R ^ 2 und lösen dann nach r, was Ihnen r = R * sqrt (u) gibt.

Dies ist auch intuitiv völlig sinnvoll. U = 0 sollte auf r = 0 abgebildet werden. Außerdem sollte u = 1 auf r = R abgebildet werden. Außerdem wird die Quadratwurzelfunktion verwendet, die sinnvoll ist und mit dem Link übereinstimmt.

Der Grund, warum die naive Lösung nicht funktioniert, ist, dass sie den Punkten näher am Kreismittelpunkt eine höhere Wahrscheinlichkeitsdichte verleiht. Mit anderen Worten, der Kreis mit dem Radius r / 2 hat die Wahrscheinlichkeit r / 2, einen Punkt darin auszuwählen, aber er hat die Fläche (Anzahl der Punkte) pi * r ^ 2/4.

Daher möchten wir, dass eine Radiuswahrscheinlichkeitsdichte die folgende Eigenschaft hat:

Die Wahrscheinlichkeit, einen Radius zu wählen, der kleiner oder gleich einem gegebenen r ist, muss proportional zur Fläche des Kreises mit dem Radius r sein. (weil wir eine gleichmäßige Verteilung auf die Punkte haben wollen und größere Flächen mehr Punkte bedeuten)

Mit anderen Worten, wir möchten, dass die Wahrscheinlichkeit, einen Radius zwischen [0, r] zu wählen, gleich seinem Anteil an der Gesamtfläche des Kreises ist. Die gesamte Kreisfläche ist pi * R ^ 2 und die Fläche des Kreises mit dem Radius r ist pi * r ^ 2. Wir möchten daher, dass die Wahrscheinlichkeit, einen Radius zwischen [0, r] zu wählen, (pi * r ^ 2) / (pi * R ^ 2) = r ^ 2 / R ^ 2 ist.

Jetzt kommt die Mathematik:

Die Wahrscheinlichkeit, einen Radius zwischen [0, r] zu wählen, ist das Integral von p (r) dr von 0 bis r (nur weil wir alle Wahrscheinlichkeiten der kleineren Radien addieren). Wir wollen also das Integral (p (r) dr) = r ^ 2 / R ^ 2. Wir können deutlich sehen, dass R ^ 2 eine Konstante ist. Alles, was wir tun müssen, ist herauszufinden, welches p (r), wenn es integriert ist, uns so etwas wie r ^ 2 geben würde. Die Antwort ist eindeutig r * konstant. Integral (r * Konstante dr) = r ^ 2/2 * Konstante. Dies muss gleich r ^ 2 / R ^ 2 sein, daher Konstante = 2 / R ^ 2. Sie haben also die Wahrscheinlichkeitsverteilung p (r) = r * 2 / R ^ 2

Hinweis: Eine andere intuitivere Möglichkeit, über das Problem nachzudenken, besteht darin, sich vorzustellen, dass Sie versuchen, jedem Kreis mit Radius ra Wahrscheinlichkeitsdichte gleich dem Anteil der Anzahl der Punkte auf seinem Umfang zu geben. Somit hat ein Kreis mit dem Radius r 2 * pi * r "Punkte" auf seinem Umfang. Die Gesamtzahl der Punkte beträgt pi * R ^ 2. Daher sollten Sie die Kreis-Ra-Wahrscheinlichkeit gleich (2 * pi * r) / (pi * R ^ 2) = 2 * r / R ^ 2 geben. Dies ist viel einfacher zu verstehen und intuitiver, aber mathematisch nicht ganz so fundiert.

Sei ρ (Radius) und φ (Azimut) zwei Zufallsvariablen, die den Polarkoordinaten eines beliebigen Punktes innerhalb des Kreises entsprechen. Wenn die Punkte gleichmäßig verteilt sind, wie lautet dann die Verteilungsfunktion von ρ und φ?

Für jedes r: 0 <r <R ist die Wahrscheinlichkeit, dass die Radiuskoordinate ρ kleiner als r ist

P [ρ <r] = P [Punkt liegt innerhalb eines Kreises mit dem Radius r] = S1 / S0 = (r / R) ²

Wobei S1 und S0 die Kreisflächen mit dem Radius r bzw. R sind. Die CDF kann also wie folgt angegeben werden:

          0          if r<=0
  CDF =   (r/R)**2   if 0 < r <= R
          1          if r > R

Und PDF:

PDF = d/dr(CDF) = 2 * (r/R**2) (0 < r <= R).

Beachten Sie, dass für R = 1 die Zufallsvariable sqrt (X), wobei X auf [0, 1) einheitlich ist, genau diese CDF hat (weil P [sqrt (X) <y] = P [x <y ** 2] = y * * 2 für 0 <y <= 1).

Die Verteilung von φ ist offensichtlich gleichmäßig von 0 bis 2 * π. Jetzt können Sie zufällige Polarkoordinaten erstellen und diese mithilfe trigonometrischer Gleichungen in kartesische konvertieren:

x = ρ * cos(φ)
y = ρ * sin(φ)

Ich kann nicht widerstehen, Python-Code für R = 1 zu posten.

from matplotlib import pyplot as plt
import numpy as np

rho = np.sqrt(np.random.uniform(0, 1, 5000))
phi = np.random.uniform(0, 2*np.pi, 5000)

x = rho * np.cos(phi)
y = rho * np.sin(phi)

plt.scatter(x, y, s = 4)

Sie erhalten

Es hängt wirklich davon ab, was Sie unter "einheitlich zufällig" verstehen. Dies ist ein subtiler Punkt, und Sie können mehr darüber auf der Wiki-Seite hier lesen: http://en.wikipedia.org/wiki/Bertrand_paradox_%28probability%29 , wo das gleiche Problem, das "einheitlich zufällig" unterschiedlich interpretiert, auftritt verschiedene Antworten!

Abhängig davon, wie Sie die Punkte auswählen, kann die Verteilung variieren, obwohl sie in gewissem Sinne einheitlich zufällig sind .

Es scheint, als würde der Blogeintrag versuchen, ihn im folgenden Sinne einheitlich zufällig zu machen: Wenn Sie einen Unterkreis des Kreises mit demselben Mittelpunkt nehmen, ist die Wahrscheinlichkeit, dass der Punkt in diese Region fällt, proportional zur Fläche von die Region. Ich glaube, das versucht, der jetzt üblichen Interpretation von "einheitlich zufällig" für 2D-Regionen mit darauf definierten Bereichen zu folgen : Die Wahrscheinlichkeit, dass ein Punkt in eine Region fällt (wobei die Fläche gut definiert ist), ist proportional zur Fläche dieser Region.

Hier ist mein Python-Code zum Generieren von numzufälligen Punkten aus einem Radiuskreis rad:

import matplotlib.pyplot as plt
import numpy as np
rad = 10
num = 1000

t = np.random.uniform(0.0, 2.0*np.pi, num)
r = rad * np.sqrt(np.random.uniform(0.0, 1.0, num))
x = r * np.cos(t)
y = r * np.sin(t)

plt.plot(x, y, "ro", ms=1)
plt.axis([-15, 15, -15, 15])
plt.show()

Ich denke, dass in diesem Fall die Verwendung von Polarkoordinaten das Problem kompliziert. Es wäre viel einfacher, wenn Sie zufällige Punkte in ein Quadrat mit Seiten der Länge 2R auswählen und dann die Punkte (x,y)so auswählen, dass x^2+y^2<=R^2.

Lösung in Java und das Verteilungsbeispiel (2000 Punkte)

public void getRandomPointInCircle() {
    double t = 2 * Math.PI * Math.random();
    double r = Math.sqrt(Math.random());
    double x = r * Math.cos(t);
    double y = r * Math.sin(t);
    System.out.println(x);
    System.out.println(y);
}

basierend auf der vorherigen Lösung https://stackoverflow.com/a/5838055/5224246 von @sigfpe

Zuerst generieren wir ein cdf [x], das ist

Die Wahrscheinlichkeit, dass ein Punkt kleiner als der Abstand x vom Mittelpunkt des Kreises ist. Angenommen, der Kreis hat einen Radius von R.

Wenn x Null ist, ist cdf [0] = 0

Wenn x R ist, ist natürlich cdf [R] = 1

offensichtlich, wenn x = r, dann ist cdf [r] = (Pi r ^ 2) / (Pi R ^ 2)

Dies liegt daran, dass jeder "kleine Bereich" auf dem Kreis die gleiche Wahrscheinlichkeit hat, ausgewählt zu werden. Die Wahrscheinlichkeit ist also proportional zum betreffenden Bereich. Und die Fläche, die einen Abstand x vom Mittelpunkt des Kreises hat, ist Pi r ^ 2

also cdf [x] = x ^ 2 / R ^ 2, weil sich die Pi gegenseitig aufheben

wir haben cdf [x] = x ^ 2 / R ^ 2, wobei x von 0 nach R geht

Also lösen wir nach x

R^2 cdf[x] = x^2

x = R Sqrt[ cdf[x] ]

Wir können jetzt cdf durch eine Zufallszahl von 0 bis 1 ersetzen

x = R Sqrt[ RandomReal[{0,1}] ]

Schließlich

r = R Sqrt[  RandomReal[{0,1}] ];
theta = 360 deg * RandomReal[{0,1}];
{r,theta}

wir erhalten die Polarkoordinaten {0,601168 R, 311,915 Grad}

Es gibt eine lineare Beziehung zwischen dem Radius und der Anzahl der Punkte "in der Nähe" dieses Radius, daher muss er eine Radiusverteilung verwenden, die auch die Anzahl der Datenpunkte in der Nähe eines Radius rproportional macht r.

Ich habe diese Methode einmal verwendet: Diese Methode ist möglicherweise nicht optimiert (dh sie verwendet ein Punktarray, sodass sie für große Kreise unbrauchbar ist), bietet jedoch eine ausreichende Zufallsverteilung. Sie können die Erstellung der Matrix überspringen und direkt zeichnen, wenn Sie möchten. Die Methode besteht darin, alle Punkte in einem Rechteck, die in den Kreis fallen, zufällig zu sortieren.

bool[,] getMatrix(System.Drawing.Rectangle r) {
    bool[,] matrix = new bool[r.Width, r.Height];
    return matrix;
}

void fillMatrix(ref bool[,] matrix, Vector center) {
    double radius = center.X;
    Random r = new Random();
    for (int y = 0; y < matrix.GetLength(0); y++) {
        for (int x = 0; x < matrix.GetLength(1); x++)
        {
            double distance = (center - new Vector(x, y)).Length;
            if (distance < radius) {
                matrix[x, y] = r.NextDouble() > 0.5;
            }
        }
    }

}

private void drawMatrix(Vector centerPoint, double radius, bool[,] matrix) {
    var g = this.CreateGraphics();

    Bitmap pixel = new Bitmap(1,1);
    pixel.SetPixel(0, 0, Color.Black);

    for (int y = 0; y < matrix.GetLength(0); y++)
    {
        for (int x = 0; x < matrix.GetLength(1); x++)
        {
            if (matrix[x, y]) {
                g.DrawImage(pixel, new PointF((float)(centerPoint.X - radius + x), (float)(centerPoint.Y - radius + y)));
            }
        }
    }

    g.Dispose();
}

private void button1_Click(object sender, EventArgs e)
{
    System.Drawing.Rectangle r = new System.Drawing.Rectangle(100,100,200,200);
    double radius = r.Width / 2;
    Vector center = new Vector(r.Left + radius, r.Top + radius);
    Vector normalizedCenter = new Vector(radius, radius);
    bool[,] matrix = getMatrix(r);
    fillMatrix(ref matrix, normalizedCenter);
    drawMatrix(center, radius, matrix);
}

Das Flächenelement in einem Kreis ist dA = rdr * dphi. Dieser zusätzliche Faktor r hat Ihre Idee zerstört, ar und phi zufällig auszuwählen. Während Phi flach verteilt ist, ist r nicht, sondern flach in 1 / r (dh Sie treffen eher die Grenze als "das Bullauge").

Um Punkte zu erzeugen, die gleichmäßig über den Kreis verteilt sind, wählen Sie Phi aus einer flachen Verteilung und r aus einer 1 / r-Verteilung.

Alternativ können Sie die von Mehrdad vorgeschlagene Monte-Carlo-Methode verwenden.

BEARBEITEN

Um eine zufällige r-Ebene in 1 / r auszuwählen, können Sie ein zufälliges x aus dem Intervall [1 / R, unendlich] auswählen und r = 1 / x berechnen. r wird dann flach in 1 / r verteilt.

Um ein zufälliges Phi zu berechnen, wählen Sie ein zufälliges x aus dem Intervall [0, 1] und berechnen Sie das Phi = 2 * pi * x.

Ich weiß nicht, ob diese Frage noch offen ist für eine neue Lösung mit all den bereits gegebenen Antworten, aber ich habe mich zufällig genau der gleichen Frage gestellt. Ich habe versucht, mit mir selbst eine Lösung zu finden, und ich habe eine gefunden. Es könnte dasselbe sein, wie einige hier bereits vorgeschlagen haben, aber hier ist es trotzdem:

Damit zwei Elemente der Kreisoberfläche unter der Annahme gleicher dr gleich sind, müssen wir dtheta1 / dtheta2 = r2 / r1 haben. Schreiben des Ausdrucks der Wahrscheinlichkeit für dieses Element als P (r, Theta) = P {r1 <r <r1 + dr, Theta1 <Theta <Theta + dtheta1} = f (r, Theta) * dr * dtheta1 und Setzen der beiden Wahrscheinlichkeiten (für r1 und r2) gleich, kommen wir zu (unter der Annahme, dass r und Theta unabhängig sind) f (r1) / r1 = f (r2) / r2 = Konstante, was f (r) = c * r ergibt. Und der Rest, der die Konstante c bestimmt, folgt aus der Bedingung, dass f (r) ein PDF ist.

Eine Programmiererlösung:

• Erstellen Sie eine Bitmap (eine Matrix aus Booleschen Werten). Es kann so groß sein, wie Sie möchten.
• Zeichnen Sie einen Kreis in diese Bitmap.
• Erstellen Sie eine Nachschlagetabelle mit den Punkten des Kreises.
• Wählen Sie einen zufälligen Index in dieser Nachschlagetabelle.

const int RADIUS = 64;
const int MATRIX_SIZE = RADIUS * 2;

bool matrix[MATRIX_SIZE][MATRIX_SIZE] = {0};

struct Point { int x; int y; };

Point lookupTable[MATRIX_SIZE * MATRIX_SIZE];

void init()
{
  int numberOfOnBits = 0;

  for (int x = 0 ; x < MATRIX_SIZE ; ++x)
  {
    for (int y = 0 ; y < MATRIX_SIZE ; ++y)
    {
      if (x * x + y * y < RADIUS * RADIUS) 
      {
        matrix[x][y] = true;

        loopUpTable[numberOfOnBits].x = x;
        loopUpTable[numberOfOnBits].y = y;

        ++numberOfOnBits;

      } // if
    } // for
  } // for
} // ()

Point choose()
{
  int randomIndex = randomInt(numberOfBits);

  return loopUpTable[randomIndex];
} // ()

Die Bitmap wird nur zur Erläuterung der Logik benötigt. Dies ist der Code ohne die Bitmap:

const int RADIUS = 64;
const int MATRIX_SIZE = RADIUS * 2;

struct Point { int x; int y; };

Point lookupTable[MATRIX_SIZE * MATRIX_SIZE];

void init()
{
  int numberOfOnBits = 0;

  for (int x = 0 ; x < MATRIX_SIZE ; ++x)
  {
    for (int y = 0 ; y < MATRIX_SIZE ; ++y)
    {
      if (x * x + y * y < RADIUS * RADIUS) 
      {
        loopUpTable[numberOfOnBits].x = x;
        loopUpTable[numberOfOnBits].y = y;

        ++numberOfOnBits;
      } // if
    } // for
  } // for
} // ()

Point choose()
{
  int randomIndex = randomInt(numberOfBits);

  return loopUpTable[randomIndex];
} // ()

Ich bin mir immer noch nicht sicher über das genaue '(2 / R2) × r', aber was offensichtlich ist, ist die Anzahl der Punkte, die in der gegebenen Einheit 'dr' verteilt werden müssen, dh die Zunahme von r ist proportional zu r2 und nicht zu r.

Überprüfen Sie dies auf diese Weise ... Anzahl der Punkte in einem Winkel Theta und zwischen r (0,1r bis 0,2r), dh Bruchteil des r und Anzahl der Punkte zwischen r (0,6r bis 0,7r) wäre gleich, wenn Sie die Standardgenerierung verwenden. da der Unterschied zwischen zwei Intervallen nur 0,1r beträgt. Da jedoch die zwischen Punkten (0,6r bis 0,7r) abgedeckte Fläche viel größer ist als die zwischen 0,1r bis 0,2r abgedeckte Fläche, wird die gleiche Anzahl von Punkten in größeren Bereichen nur spärlich beabstandet sein. Ich gehe davon aus, dass Sie dies bereits wissen Die Erzeugung der Zufallspunkte darf nicht linear, sondern quadratisch sein (da die Anzahl der Punkte, die in der gegebenen Einheit 'dr' verteilt werden müssen, dh die Zunahme von r proportional zu r2 und nicht r ist), ist sie in diesem Fall umgekehrt zu quadratisch, seit dem Delta haben wir (0.

So ein lustiges Problem.
Die Gründe für die Wahrscheinlichkeit, dass ein Punkt mit zunehmendem Abstand vom Achsenursprung abnimmt, werden oben mehrfach erläutert. Wir berücksichtigen dies, indem wir die Wurzel von U [0,1] ziehen. Hier ist eine allgemeine Lösung für ein positives r in Python 3.

import numpy
import math
import matplotlib.pyplot as plt

def sq_point_in_circle(r):
    """
    Generate a random point in an r radius circle 
    centered around the start of the axis
    """

    t = 2*math.pi*numpy.random.uniform()
    R = (numpy.random.uniform(0,1) ** 0.5) * r

    return(R*math.cos(t), R*math.sin(t))

R = 200 # Radius
N = 1000 # Samples

points = numpy.array([sq_point_in_circle(R) for i in range(N)])
plt.scatter(points[:, 0], points[:,1])

Sie können auch Ihre Intuition verwenden.

Die Fläche eines Kreises ist pi*r^2

Zum r=1

Dies gibt uns einen Bereich von pi. Nehmen wir an, wir haben eine Funktion f, die N=10Punkte innerhalb eines Kreises gleichmäßig verteilt . Das Verhältnis hier ist10 / pi

Jetzt verdoppeln wir die Fläche und die Anzahl der Punkte

Für r=2undN=20

Dies ergibt eine Fläche von 4piund das Verhältnis ist jetzt 20/4pioder 10/2pi. Das Verhältnis wird immer kleiner, je größer der Radius ist, da sein Wachstum quadratisch ist und die NSkalen linear sind.

Um dies zu beheben, können wir einfach sagen

x = r^2
sqrt(x) = r

Wenn Sie einen Vektor in Polarkoordinaten wie diesen erzeugen würden

length = random_0_1();
angle = random_0_2pi();

Weitere Punkte würden um das Zentrum landen.

length = sqrt(random_0_1());
angle = random_0_2pi();

length ist nicht mehr gleichmäßig verteilt, aber der Vektor wird jetzt gleichmäßig verteilt.

1) Wählen Sie ein zufälliges X zwischen -1 und 1.

var X:Number = Math.random() * 2 - 1;

2) Berechnen Sie unter Verwendung der Kreisformel die Maximal- und Minimalwerte von Y unter der Annahme, dass X und ein Radius von 1:

var YMin:Number = -Math.sqrt(1 - X * X);
var YMax:Number = Math.sqrt(1 - X * X);

3) Wählen Sie ein zufälliges Y zwischen diesen Extremen:

var Y:Number = Math.random() * (YMax - YMin) + YMin;

4) Integrieren Sie Ihre Standort- und Radiuswerte in den Endwert:

var finalX:Number = X * radius + pos.x;
var finalY:Number = Y * radois + pos.y;