Generar un punto aleatorio dentro de un círculo (uniformemente)

212

Necesito generar un punto uniformemente aleatorio dentro de un círculo de radio R .

Me doy cuenta de que simplemente seleccionando un ángulo uniformemente aleatorio en el intervalo [0 ... 2π) y un radio uniformemente aleatorio en el intervalo (0 ... R ) terminaría con más puntos hacia el centro, ya que para dos dados radios, los puntos en el radio más pequeño estarán más cerca uno del otro que para los puntos en el radio más grande.

Encontré una entrada de blog sobre esto aquí, pero no entiendo su razonamiento. Supongo que es correcto, pero realmente me gustaría entender de dónde obtiene (2 / R 2 ) × r y cómo deriva la solución final.


Actualización: 7 años después de publicar esta pregunta, todavía no había recibido una respuesta satisfactoria sobre la pregunta real sobre las matemáticas detrás del algoritmo de raíz cuadrada. Así que me pasé un día escribiendo una respuesta yo mismo. Enlace a mi respuesta .

aioobe
fuente
18
¿El inconveniente del rechazo de muestreo es realmente un gran problema? El número esperado de intentos requeridos es 4 / π ≈ 1.27, y la probabilidad de que necesite más de k intentos es (1-π / 4) ^ k. Para k = 20 , esto es ≈ .00000000000004 y para k = 50 está en el orden de 10 ^ {- 34}. Puedes tomar esas probabilidades cualquier día; Lo harás bien.
ShreevatsaR
3
En realidad, el muestreo de rechazo proporciona una garantía de terminación. Las probabilidades son infinitamente bajas (para ser precisos, cero) de que su algoritmo nunca terminará.
Jared Nielsen
2
En mi opinión, la importancia del inconveniente del muestreo de rechazo es proporcional a la facilidad de usar un método de muestreo que evite el rechazo. En este caso, el inconveniente es importante porque el muestreo sin rechazo es simple.
spex
44
@spex En la práctica, la técnica de rechazo es más rápida porque evita la necesidad de evaluaciones de funciones trascendentales.
pjs
2
(cont) rechazo: 0.52s Todos dieron medias idénticas y desviaciones estándar (a 3 sig. fig). Como se esperaba, el muestreo de rechazo falló el 27% del tiempo (4 / pi-1), por lo que necesitó un 27% más de números aleatorios que btilly pero un 15% menos que sigfpe. Esto confirma los comentarios hechos por pjs y otros que el muestreo de rechazo es probablemente el mejor enfoque, a menos que los randoms sean muy caros de generar.
Peter Davidson

Respuestas:

189

Abordemos esto como lo haría Arquímedes.

¿Cómo podemos generar un punto uniformemente en un triángulo ABC, donde | AB | = | BC |? Hagamos esto más fácil extendiéndonos a un paralelogramo ABCD. Es fácil generar puntos de manera uniforme en ABCD. Elegimos uniformemente un punto aleatorio X en AB e Y en BC y elegimos Z de modo que XBYZ sea un paralelogramo. Para obtener un punto elegido uniformemente en el triángulo original, simplemente doblamos los puntos que aparecen en ADC hacia ABC a lo largo de AC.

Ahora considere un círculo. En el límite podemos pensar en él como infinitos triángulos isoceles ABC con B en el origen y A y C en la circunferencia que se desvanecen uno cerca del otro. Podemos elegir uno de estos triángulos simplemente eligiendo un ángulo theta. Entonces ahora necesitamos generar una distancia desde el centro seleccionando un punto en la astilla ABC. Nuevamente, extienda a ABCD, donde D ahora es dos veces el radio desde el centro del círculo.

Elegir un punto aleatorio en ABCD es fácil usando el método anterior. Elija un punto aleatorio en AB. Elija uniformemente un punto aleatorio en BC. Es decir. escoja un par de números aleatorios x e y uniformemente en [0, R] dando distancias desde el centro. Nuestro triángulo es una astilla delgada, por lo que AB y BC son esencialmente paralelos. Entonces, el punto Z es simplemente una distancia x + y desde el origen. Si x + y> R volvemos a doblar.

Aquí está el algoritmo completo para R = 1. Espero que estés de acuerdo, es bastante simple. Utiliza trigonometría, pero puede brindar una garantía sobre cuánto tiempo llevará y cuántas random()llamadas necesita, a diferencia del muestreo de rechazo.

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

Aquí está en 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]

ingrese la descripción de la imagen aquí

sigfpe
fuente
66
@Karelzarath Me gusta la noción contraintuitiva de un triángulo infinitamente delgado que todavía es más ancho en un extremo que en el otro :-) Obtiene la respuesta correcta.
sigfpe
2
@hammar No estoy seguro de que se generalice bien en n dimensiones. ¡Pero para 3d puedes usar otro resultado de Arquímedes! Use el teorema "hat-box" para generar un punto en el cilindro (¡fácil!) Y luego vuelva a mapearlo en la esfera. Eso da una dirección. Ahora se usa random()+random()+random()con algunos pliegues más complejos (es decir, un pliegue de 6 vías de un paralelepípedo infinitesimalmente delgado a un teraedro). Sin embargo, no estoy convencido de que este sea un buen método.
sigfpe
2
Pensé 1 minuto para descubrir la diferencia entre random () + random () y 2 * random () ... Soy tan estúpido: /
JiminP
3
@Tharwen Observe cómo en un círculo hay más puntos en el radio 0.9-1.0 que en el radio 0.0-0.1. random () + random () genera radios con mayor probabilidad de estar alrededor de 1.0 pero se encuentran en el rango 0.0-2.0. Cuando se pliegan, es más probable que estén alrededor de 1.0 y siempre en el rango de 0.0-1.0. Además, es exactamente la proporción necesaria en la primera oración de este comentario. Simplemente dividir a la mitad produce más números alrededor de la marca 0.5 y eso estaría mal.
sigfpe
2
@Tharwen Intenta usar ambos esquemas para generar números aleatorios y ver qué obtienes. 2 * random () da números distribuidos uniformemente en el rango de 0 a 2. random () + random () le da números en el rango de 0 a 2 pero (generalmente) habrá más números cerca de 1.0 que cerca de 0.0 o 2.0. Es como tirar dos dados y sumar es más probable que dé 7 que cualquier otro número.
sigfpe
134

Cómo generar un punto aleatorio dentro de un círculo de radio R :

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

(Suponiendo que random()da un valor entre 0 y 1 de manera uniforme)

Si desea convertir esto a coordenadas cartesianas, puede hacer

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


¿Por qué sqrt(random())?

Veamos las matemáticas que conducen a sqrt(random()). Supongamos por simplicidad que estamos trabajando con el círculo unitario, es decir, R = 1.

La distancia promedio entre puntos debe ser la misma independientemente de cuán lejos del centro miremos. Esto significa, por ejemplo, que mirando el perímetro de un círculo con circunferencia 2 deberíamos encontrar el doble de puntos que el número de puntos en el perímetro de un círculo con circunferencia 1.


                

Como la circunferencia de un círculo (2π r ) crece linealmente con r , se deduce que el número de puntos aleatorios debería crecer linealmente con r . En otras palabras, la función de densidad de probabilidad deseada (PDF) crece linealmente. Como un PDF debe tener un área igual a 1 y el radio máximo es 1, tenemos


                

Entonces sabemos cómo debería ser la densidad deseada de nuestros valores aleatorios. Ahora: ¿Cómo generamos un valor aleatorio cuando todo lo que tenemos es un valor aleatorio uniforme entre 0 y 1?

Usamos un truco llamado muestreo de transformación inversa

  1. Desde el PDF, cree la función de distribución acumulativa (CDF)
  2. Refleje esto a lo largo de y = x
  3. Aplique la función resultante a un valor uniforme entre 0 y 1.

¿Suena complicado? Permítanme insertar una cita en bloque con una pequeña pista lateral que transmite la intuición:

Supongamos que queremos generar un punto aleatorio con la siguiente distribución:

                

Es decir

  • 1/5 de los puntos uniformemente entre 1 y 2, y
  • 4/5 de los puntos uniformemente entre 2 y 3.

El CDF es, como su nombre indica, la versión acumulativa del PDF. Intuitivamente: mientras PDF ( x ) describe el número de valores aleatorios en x , CDF ( x ) describe el número de valores aleatorios menores que x .

En este caso, el CDF se vería así:

                

Para ver cómo esto es útil, imagine que disparamos balas de izquierda a derecha a alturas distribuidas uniformemente. Cuando las balas golpean la línea, caen al suelo:

                

¡Vea cómo la densidad de las balas en el suelo corresponde a nuestra distribución deseada! ¡Casi estámos allí!

El problema es que para esta función, el eje y es la salida y el eje x es la entrada . ¡Solo podemos "disparar balas desde el suelo hacia arriba"! ¡Necesitamos la función inversa!

Es por eso que reflejamos todo el asunto; x se convierte en y e y se convierte en x :

                

Llamamos a esto CDF -1 . Para obtener valores de acuerdo con la distribución deseada, usamos CDF -1 (random ()).

... entonces, volviendo a generar valores de radio aleatorios donde nuestro PDF es igual a 2 x .

Paso 1: Cree el CDF:

dado que estamos trabajando con reales, el CDF se expresa como la integral del PDF.

CDF ( x ) = ∫ 2 x = x 2

Paso 2: Descarga el CDF a lo largo de y = x :

Matemáticamente, esto se reduce a intercambiar x e y resolver por y :

CDF :      y = x 2
Intercambio:    x = y 2
Resolver:    y = √ x
CDF -1 :   y = √ x

Paso 3: aplique la función resultante a un valor uniforme entre 0 y 1

CDF -1 (aleatorio ()) = √ aleatorio ()

Que es lo que nos propusimos derivar :-)

aioobe
fuente
Este algoritmo se puede usar para generar puntos de manera eficiente en el anillo.
Ivan Kovtun
En el ring? ¿Como con un radio fijo? No estoy seguro si entiendo su pregunta, pero si tiene un radio fijo, solo necesita aleatorizar el ángulo.
aioobe
2
Traté de usar la palabra más simple "Anillo" en lugar de Annulus - región limitada por dos círculos concéntricos. En este caso, el algoritmo de rechazo deja de ser efectivo y el primer algoritmo superior es difícil de generalizar. Y el caso de la esquina con un radio también está cubierto con su algoritmo. Siempre generamos radio como sqrt (aleatorio (min_radius ^ 2, max_radius ^ 2)) incluso cuando min_radius == max_radius.
Ivan Kovtun
1
¡Oh bien! Para ser claros, cuando dices random(min_radius², max_radius²), ¿quieres decir algo equivalente a random() * (max_radius² - min_radius²) + min_radius², donde random()devuelve un valor uniforme entre 0 y 1?
aioobe
sí, eso es exactamente lo que quiero decir: radio = sqrt (random () * (max_radius² - min_radius²) + min_radius²).
Ivan Kovtun
27

Aquí hay una solución rápida y simple.

Elija dos números aleatorios en el rango (0, 1), a saber, ay b. Si b < a, intercambiarlos. Su punto es (b*R*cos(2*pi*a/b), b*R*sin(2*pi*a/b)).

Puede pensar en esta solución de la siguiente manera. Si tomas el círculo, lo cortas y lo enderezas, obtendrás un triángulo rectángulo. Escalar ese triángulo hacia abajo, y que tendría un triángulo a partir (0, 0)de (1, 0)a (1, 1)y volver de nuevo a (0, 0). Todas estas transformaciones cambian la densidad de manera uniforme. Lo que has hecho es elegir uniformemente un punto aleatorio en el triángulo e invertir el proceso para obtener un punto en el círculo.

btilly
fuente
Esto, por alguna razón, me da una distribución mucho más uniforme que la respuesta aceptada, aunque necesitaba dividir la coordenada por el radio, de lo contrario está dentro de un círculo de R ^ 2
Greg Zaal
3
Gracias, este es su código en Java, tal vez alguien lo encuentre útil: float random1 = MathUtils.random (); float random2 = MathUtils.random (); flotante randomXPoint = random2 * radio MathUtils.cos (MathUtils.PI2 * random1 / random2); flotante randomYPoint = random2 * radio MathUtils.sin (MathUtils.PI2 * random1 / random2);
Tony Ceralva
¡muy bien! Me gusta la idea de una mayor probabilidad para centralizar los puntos, ¡así que si no intercambiamos cuándo b < apodemos lograr esto! por ejemplo, en javascript jsfiddle.net/b0sb5ogL/1
Guilherme el
Creo que tu solución es mala. No está dando resultados uniformes. Mira esta captura de pantalla prntscr.com/fizxgc
bolec_kolec
44
¿Puedes explicar un poco más cómo cortar el círculo y enderezarlo?
kec
21

Tenga en cuenta la densidad de puntos en proporcional al inverso cuadrado del radio, por lo tanto, en lugar de escoger rentre [0, r_max], elegir [0, r_max^2], a continuación, calcular sus coordenadas como:

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

Esto le dará una distribución de puntos uniforme en un disco.

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

Libor
fuente
12

Piensa en ello de esta manera. Si tiene un rectángulo donde un eje es radio y uno es ángulo, y toma los puntos dentro de este rectángulo que están cerca del radio 0. Todos estos caerán muy cerca del origen (que están muy juntos en el círculo). Sin embargo, los puntos cercanos al radio R, todos caerán cerca del borde del círculo (es decir, muy separados entre sí).

Esto podría darle una idea de por qué está teniendo este comportamiento.

El factor que se deriva en ese enlace le indica la cantidad de área correspondiente en el rectángulo que debe ajustarse para no depender del radio una vez que se asigna al círculo.

Editar: Entonces, lo que escribe en el enlace que comparte es: "Eso es bastante fácil de hacer calculando el inverso de la distribución acumulativa, y obtenemos para r:".

La premisa básica es que puede crear una variable con una distribución deseada de un uniforme mapeando el uniforme mediante la función inversa de la función de distribución acumulativa de la función de densidad de probabilidad deseada. ¿Por qué? Simplemente dé por sentado por ahora, pero esto es un hecho.

Aquí está mi explicación intuitiva somehwat de las matemáticas. La función de densidad f (r) con respecto a r tiene que ser proporcional a r misma. Comprender este hecho es parte de cualquier libro de cálculo básico. Ver secciones sobre elementos del área polar. Algunos otros carteles han mencionado esto.

Entonces lo llamaremos f (r) = C * r;

Esto resulta ser la mayor parte del trabajo. Ahora, dado que f (r) debería ser una densidad de probabilidad, puede ver fácilmente que integrando f (r) en el intervalo (0, R) obtiene C = 2 / R ^ 2 (este es un ejercicio para el lector .)

Por lo tanto, f (r) = 2 * r / R ^ 2

OK, así es como obtienes la fórmula en el enlace.

Luego, la parte final va desde la variable aleatoria uniforme u en (0,1) que debe mapear por la función inversa de la función de distribución acumulativa de esta densidad deseada f (r). Para comprender por qué este es el caso, debe encontrar un texto de probabilidad avanzado como Papoulis probablemente (o derivarlo usted mismo).

Integrando f (r) obtienes F (r) = r ^ 2 / R ^ 2

Para encontrar la función inversa de esto, establezca u = r ^ 2 / R ^ 2 y luego resuelva para r, que le da r = R * sqrt (u)

Esto también tiene un sentido intuitivo, u = 0 debería correlacionarse con r = 0. Además, u = 1 debería correlacionarse con r = R. Además, sigue la función de raíz cuadrada, que tiene sentido y coincide con el enlace.

Chris A.
fuente
10

La razón por la cual la solución ingenua no funciona es que da una mayor densidad de probabilidad a los puntos más cercanos al centro del círculo. En otras palabras, el círculo que tiene radio r / 2 tiene probabilidad r / 2 de obtener un punto seleccionado en él, pero tiene área (número de puntos) pi * r ^ 2/4.

Por lo tanto, queremos que una densidad de probabilidad de radio tenga la siguiente propiedad:

La probabilidad de elegir un radio menor o igual a una r dada tiene que ser proporcional al área del círculo con radio r. (porque queremos tener una distribución uniforme en los puntos y áreas más grandes significan más puntos)

En otras palabras, queremos que la probabilidad de elegir un radio entre [0, r] sea igual a su parte del área general del círculo. El área total del círculo es pi * R ^ 2, y el área del círculo con radio r es pi * r ^ 2. Por lo tanto, nos gustaría que la probabilidad de elegir un radio entre [0, r] sea (pi * r ^ 2) / (pi * R ^ 2) = r ^ 2 / R ^ 2.

Ahora viene la matemática:

La probabilidad de elegir un radio entre [0, r] es la integral de p (r) dr de 0 a r (eso es solo porque sumamos todas las probabilidades de los radios más pequeños). Por lo tanto, queremos integral (p (r) dr) = r ^ 2 / R ^ 2. Podemos ver claramente que R ^ 2 es una constante, por lo que todo lo que tenemos que hacer es descubrir qué p (r), cuando se integra, nos daría algo así como r ^ 2. La respuesta es claramente r * constante. integral (r * constante dr) = r ^ 2/2 * constante. Esto tiene que ser igual a r ^ 2 / R ^ 2, por lo tanto constante = 2 / R ^ 2. Por lo tanto, tiene la distribución de probabilidad p (r) = r * 2 / R ^ 2

Nota: Otra forma más intuitiva de pensar sobre el problema es imaginar que está tratando de dar a cada círculo de radio una densidad de probabilidad igual a la proporción del número de puntos que tiene en su circunferencia. Por lo tanto, un círculo que tiene radio r tendrá 2 * pi * r "puntos" en su circunferencia. El número total de puntos es pi * R ^ 2. Por lo tanto, debe dar al círculo una probabilidad de ra igual a (2 * pi * r) / (pi * R ^ 2) = 2 * r / R ^ 2. Esto es mucho más fácil de entender y más intuitivo, pero no es tan matemáticamente sólido.

usuario502248
fuente
9

Deje ρ (radio) y φ (acimut) ser dos variables aleatorias correspondientes a coordenadas polares de un punto arbitrario dentro del círculo. Si los puntos están distribuidos uniformemente, ¿cuál es la función de distribución de ρ y φ?

Para cualquier r: 0 <r <R, la probabilidad de que la coordenada del radio ρ sea menor que r es

P [ρ <r] = P [el punto está dentro de un círculo de radio r] = S1 / S0 = (r / R) 2

Donde S1 y S0 son las áreas de círculo de radio r y R respectivamente. Entonces el CDF se puede dar como:

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

Y PDF:

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

Tenga en cuenta que para R = 1 variable aleatoria sqrt (X) donde X es uniforme en [0, 1) tiene este CDF exacto (porque P [sqrt (X) <y] = P [x <y ** 2] = y * * 2 para 0 <y <= 1).

La distribución de φ es obviamente uniforme de 0 a 2 * π. Ahora puede crear coordenadas polares aleatorias y convertirlas a cartesianas utilizando ecuaciones trigonométricas:

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

No puedo resistirme a publicar código python para R = 1.

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)

Conseguirás

ingrese la descripción de la imagen aquí

Inglés
fuente
7

Realmente depende de lo que quieras decir con "uniformemente aleatorio". Este es un punto sutil y puede leer más al respecto en la página wiki aquí: http://en.wikipedia.org/wiki/Bertrand_paradox_%28probability%29 , donde el mismo problema, dando diferentes interpretaciones a 'uniformemente aleatorio' da diferentes respuestas!

Dependiendo de cómo elija los puntos, la distribución podría variar, aunque en algún sentido sean uniformemente aleatorios .

Parece que la entrada del blog está tratando de hacerlo uniformemente aleatorio en el siguiente sentido: si toma un sub-círculo del círculo, con el mismo centro, entonces la probabilidad de que el punto caiga en esa región es proporcional al área de la región. Creo que está intentando seguir la interpretación ahora estándar de 'uniformemente aleatorio' para regiones 2D con áreas definidas en ellas : la probabilidad de que un punto caiga en cualquier región (con un área bien definida) es proporcional al área de esa región.


fuente
55
O más bien, la probabilidad de que el punto caiga en cualquier región arbitraria es proporcional al área de la región, suponiendo que la región tenga un área .
ShreevatsaR
@Shree: Correcto, que es lo que quise decir con mi declaración entre paréntesis. Lo aclararé, gracias. Por cierto, sobre el blog, no había pruebas reales de que las áreas arbitrarias dieran probabilidades proporcionales, por lo tanto, elegí expresarlo de esa manera.
6

Aquí está mi código de Python para generar numpuntos aleatorios a partir de un círculo de radio 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()
krishnab
fuente
1
¿Por qué no solo r = np.sqrt(np.random.uniform(0.0, rad**2, num))?
4

Creo que en este caso el uso de coordenadas polares es una forma de complicar el problema, sería mucho más fácil si selecciona puntos aleatorios en un cuadrado con lados de longitud 2R y luego selecciona los puntos de (x,y)tal manera x^2+y^2<=R^2.

ascanio
fuente
Te refieres a x ^ 2 + y ^ 2 <= R ^ 2, creo.
sigfpe
1
Esta es una muestra de rechazo. Está bien, pero significa que el tiempo de cálculo varía un poco, lo que podría ser un problema.
Steve Bennett
Todos los cuadrados son de 4 lados.
xaxxon
Este algoritmo es más eficiente que cualquier cosa que implique raíces cuadradas o cálculos sin / cos. Rechaza menos del 21.5% de puntos del cuadrado.
Ivan Kovtun
3

Solución en Java y el ejemplo de distribución (2000 puntos)

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);
}

Distribución 2000 puntos

basado en la solución anterior https://stackoverflow.com/a/5838055/5224246 de @sigfpe

bolec_kolec
fuente
2

Primero generamos un cdf [x] que es

La probabilidad de que un punto sea menor que la distancia x desde el centro del círculo. Suponga que el círculo tiene un radio de R.

obviamente si x es cero, entonces cdf [0] = 0

obviamente si x es R entonces el cdf [R] = 1

obviamente si x = r entonces el cdf [r] = (Pi r ^ 2) / (Pi R ^ 2)

Esto se debe a que cada "área pequeña" en el círculo tiene la misma probabilidad de ser recogida, por lo que la probabilidad es proporcional al área en cuestión. Y el área dada una distancia x desde el centro del círculo es Pi r ^ 2

entonces cdf [x] = x ^ 2 / R ^ 2 porque el Pi se cancela entre sí

tenemos cdf [x] = x ^ 2 / R ^ 2 donde x va de 0 a R

Entonces resolvemos para x

R^2 cdf[x] = x^2

x = R Sqrt[ cdf[x] ]

Ahora podemos reemplazar cdf con un número aleatorio de 0 a 1

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

Finalmente

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

obtenemos las coordenadas polares {0.601168 R, 311.915 grados}

Steven Siew
fuente
1

Existe una relación lineal entre el radio y el número de puntos "cerca" de ese radio, por lo que necesita usar una distribución de radio que también haga que el número de puntos de datos cerca de un radio sea rproporcional r.

recursivo
fuente
1

Una vez utilicé este método: esto puede no ser optimizado por completo (es decir, utiliza una matriz de puntos, por lo que no se puede usar para círculos grandes), pero proporciona una distribución aleatoria suficiente. Puede omitir la creación de la matriz y dibujar directamente si lo desea. El método consiste en aleatorizar todos los puntos en un rectángulo que caen dentro del círculo.

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);
}

ingrese la descripción de la imagen aquí

Marino Šimić
fuente
3
Las distribuciones no son "lo suficientemente aleatorias". Son o no aleatorios para una definición dada de aleatorio. Su respuesta es oblicua: no comenta su código ni explica cómo llega a él. Las respuestas oblicuas son difíciles de seguir y más difíciles de confiar.
Richard
1

El elemento de área en un círculo es dA = rdr * dphi. Ese factor adicional r destruyó su idea de elegir aleatoriamente ar y phi. Mientras que phi se distribuye plano, r no lo es, pero plano en 1 / r (es decir, es más probable que llegue al límite que "el blanco").

Entonces, para generar puntos distribuidos uniformemente sobre el círculo, elija phi de una distribución plana y r de una distribución 1 / r.

Alternativamente, use el método Monte Carlo propuesto por Mehrdad.

EDITAR

Para elegir una r plana aleatoria en 1 / r, puede elegir una x aleatoria del intervalo [1 / R, infinito] y calcular r = 1 / x. r luego se distribuye plano en 1 / r.

Para calcular un phi aleatorio, elija una x aleatoria del intervalo [0, 1] y calcule phi = 2 * pi * x.

Benjamin Bannier
fuente
¿Cómo elijo exactamente una r de "una distribución 1 / r" ?
aioobe
0

No sé si esta pregunta todavía está abierta para una nueva solución con todas las respuestas ya dadas, pero resultó que me enfrenté exactamente a la misma pregunta. Traté de "razonar" conmigo mismo para encontrar una solución, y encontré una. Puede ser lo mismo que algunos ya han sugerido aquí, pero de todos modos aquí está:

Para que dos elementos de la superficie del círculo sean iguales, suponiendo dr iguales, debemos tener dtheta1 / dtheta2 = r2 / r1. Escribir la expresión de la probabilidad de ese elemento como P (r, theta) = P {r1 <r <r1 + dr, theta1 <theta <theta + dtheta1} = f (r, theta) * dr * dtheta1, y establecer los dos probabilidades (para r1 y r2) iguales, llegamos a (suponiendo que r y theta son independientes) f (r1) / r1 = f (r2) / r2 = constante, lo que da f (r) = c * r. Y el resto, determinar la constante c se deduce de la condición de que f (r) sea un PDF.

arsaKasra
fuente
Enfoque interesante para comenzar con dtheta1 / dtheta2 = r2 / r1. ¿Podría explicar cómo se le ocurrió esa ecuación?
aioobe
Como otros han mencionado (bocinazo, por ejemplo), un elemento diferencial de la superficie de un círculo se da como r dr dtheta, por lo que si asumimos que r1 = r2, tendremos dr1 * dtheta1 = dr2 * dtheta2 y el resto sigue .
arsaKasra
0

Una solución de programador:

  • Cree un mapa de bits (una matriz de valores booleanos). Puede ser tan grande como quieras.
  • Dibuja un círculo en ese mapa de bits.
  • Crea una tabla de búsqueda de los puntos del círculo.
  • Elija un índice aleatorio en esta tabla de búsqueda.
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];
} // ()

El mapa de bits solo es necesario para la explicación de la lógica. Este es el código sin el mapa de bits:

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];
} // ()
sellador
fuente
0

Todavía no estoy seguro sobre el '(2 / R2) × r' exacto, pero lo que es evidente es el número de puntos necesarios para distribuir en la unidad dada 'dr', es decir, el aumento en r será proporcional a r2 y no a r.

verifique de esta manera ... el número de puntos en algún ángulo theta y entre r (0.1r a 0.2r), es decir, la fracción de r y el número de puntos entre r (0.6r a 0.7r) sería igual si usa la generación estándar, ya que la diferencia es solo 0.1r entre dos intervalos. pero dado que el área cubierta entre puntos (0.6r a 0.7r) será mucho más grande que el área cubierta entre 0.1r a 0.2r, el mismo número de puntos estará escasamente espaciado en un área más grande, supongo que ya lo sabe, así que la función para generar los puntos aleatorios no debe ser lineal sino cuadrático (ya que el número de puntos que se deben distribuir en la unidad dada 'dr', es decir, el aumento de r será proporcional a r2 y no r), por lo que en este caso será inverso a cuadrático, desde el delta tenemos (0.

fiesta de queso
fuente
Eres el primero en hacer referencia al teorema de Pitágoras aquí. Me encantaría que pudieras ampliar esto con una figura o dos, apoyando tu explicación. Me cuesta
seguirlo
@aioobe He intentado reformular la respuesta, puedo agregar diagramas si es necesario :)
cheesefest
Entiendo por qué no puedo extenderlo linealmente. Lo que no entiendo aquí es la conexión con Pitágoras o sin / cos. Tal vez los diagramas podrían ayudarme aquí.
aioobe
Pitágoras es mi error, olvídalo, pero espero que hayas entendido la naturaleza cuadrática de la función, el exacto (2 / R2) × r necesita prueba y no puedo encontrar ninguna prueba para esto
cheesefest
0

Un problema tan divertido.
La razón de la probabilidad de que un punto sea elegido bajando a medida que aumenta la distancia desde el origen del eje se explica varias veces más arriba. Nos damos cuenta de eso tomando la raíz de U [0,1]. Aquí hay una solución general para una r positiva en 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])

ingrese la descripción de la imagen aquí

AChervony
fuente
0

También puedes usar tu intuición.

El área de un círculo es pi*r^2

por r=1

Esto nos da un área de pi. Supongamos que tenemos algún tipo de función fque distribuiría N=10puntos uniformemente dentro de un círculo. La relación aquí es10 / pi

Ahora duplicamos el área y la cantidad de puntos

Para r=2yN=20

Esto da un área de 4piy la relación es ahora 20/4pio 10/2pi. La relación se hará cada vez más pequeña cuanto mayor sea el radio, porque su crecimiento es cuadrático y elN escalas linealmente.

Para arreglar esto solo podemos decir

x = r^2
sqrt(x) = r

Si generas un vector en coordenadas polares como esta

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

Más puntos aterrizarían alrededor del centro.

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

length ya no se distribuye uniformemente, pero el vector ahora se distribuirá uniformemente.

Maik Klein
fuente
-1

1) Elija una X aleatoria entre -1 y 1.

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

2) Usando la fórmula del círculo, calcule los valores máximos y mínimos de Y dado que X y un radio de 1:

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

3) Elija una Y aleatoria entre esos extremos:

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

4) Incorpore sus valores de ubicación y radio en el valor final:

var finalX:Number = X * radius + pos.x;
var finalY:Number = Y * radois + pos.y;
xytor
fuente
2
No uniforme: la probabilidad de [-1, 0] es mucho mayor que para [0, 0], dado que p ([- 1, Y]) = p ([0, Y]), y solo hay un elección para [-1, Y] y muchas opciones para [0, Y].
Amadan
Esta solución favorece los puntos hacia los lados izquierdo y derecho del círculo. Los puntos con x cerca de cero están subrepresentados. No es una distribución uniforme en absoluto.
Dawood ibn Kareem