En primer lugar, agradeceré si alguien me da un término apropiado para "anillo con un agujero desplazado", vea exactamente a qué tipo de forma me refiero en una imagen a continuación.

Volver a la pregunta principal: Quiero elegir un punto aleatorio en el área naranja, no se requiere una distribución uniforme. Para un caso de un anillo habitual, habría elegido un punto aleatorio en el rango (r: R) y un ángulo aleatorio, luego los transformaría en x, y y listo. Pero para esta forma inusual ... ¿hay incluso una fórmula "simple" para eso, o debería abordarla haciendo algún tipo de aproximación poligonal de una forma?

Estoy interesado en un enfoque general, pero apreciaré un ejemplo en python, javascript o cualquier lenguaje de codificación de su elección.

shifted annulus

3
Max Yari 30 oct. 2017 a las 01:25

4 respuestas

La mejor respuesta

Aquí hay un método simple que proporciona una distribución uniforme sin remuestreo.

Para simplificar, suponga que el centro del círculo del límite exterior (radio r_outer) está en (0, 0) y que el centro del límite circular interno (radio r_inner) se encuentra en (x_inner, y_inner) .

Escriba D para el disco externo, H1 para el subconjunto del plano dado por el agujero interno descentrado y H2 para el disco de radio central r_inner, centrado en (0, 0).

Ahora suponga que ignoramos el hecho de que el círculo interno no es central, y en lugar de tomar muestras de D-H1 tomamos muestras de D-H2 (que es fácil de hacer de manera uniforme). Entonces hemos cometido dos errores:

  • hay una región A = H1 - H2 de la que podríamos tomar muestras, a pesar de que esas muestras no deberían estar en el resultado.
  • hay una región B = H2 - H1 de la que nunca tomamos muestras, aunque deberíamos

Pero aquí está la cosa: las regiones A y B son congruentes: dado cualquier punto (x, y) en el plano, (x, y) está en {{X4 }} si y solo si (x_inner - x, y_inner - y) está en H1, y se deduce que (x, y) está en A si y solo si (x_inner - x, y_inner - y) está en {{X10} }! El mapa (x, y) -> (x_inner - x, y_inner - y) representa una rotación de 180 grados alrededor del punto (0.5*x_inner, 0.5*y_inner). Entonces, hay un truco simple: generar desde D - H2, y si terminamos con algo en H1 - H2, gire para obtener el punto correspondiente de H2 - H1 en su lugar.

Aquí está el código. Tenga en cuenta el uso de la raíz cuadrada de una distribución uniforme para elegir el radio: este es un truco estándar. Consulte este artículo, por ejemplo.

import math
import random

def sample(r_outer, r_inner, x_inner, y_inner):
    """
    Sample uniformly from (x, y) satisfiying:

       x**2 + y**2 <= r_outer**2

       (x-x_inner)**2 + (y-y_inner)**2 > r_inner**2

    Assumes that the inner circle lies inside the outer circle;
    i.e., that hypot(x_inner, y_inner) <= r_outer - r_inner.
    """
    # Sample from a normal annulus with radii r_inner and r_outer.
    rad = math.sqrt(random.uniform(r_inner**2, r_outer**2))
    angle = random.uniform(-math.pi, math.pi)
    x, y = rad*math.cos(angle),rad*math.sin(angle)

    # If we're inside the forbidden hole, reflect.
    if math.hypot(x - x_inner, y - y_inner) < r_inner:
        x, y = x_inner - x, y_inner - y

    return x, y

Y un diagrama de ejemplo, generado por lo siguiente:

import matplotlib.pyplot as plt
samples = [sample(5, 2, 1.0, 2.0) for _ in range(10000)]
xs, ys = zip(*samples)

plt.scatter(xs, ys, s=0.1)
plt.axis("equal")
plt.show()

uniform samples from annulus with off-center hole

3
Mark Dickinson 30 oct. 2017 a las 11:58

Como no ha mostrado ninguna ecuación, algoritmo o código propio, sino solo un esquema de un algoritmo para círculos alineados al centro, también daré el esquema de un algoritmo aquí para el caso más general.

El círculo más pequeño es la imagen del círculo más grande bajo una transformación de similitud. Es decir. hay un punto fijo en el círculo más grande y una relación (que es R / r, mayor que uno) de modo que puede tomar cualquier punto en el círculo más pequeño, examinar el vector desde el punto fijo hasta ese punto y multiplicar ese vector por la relación, entonces el final de ese vector cuando comienza desde el punto fijo es un punto en el círculo más grande. Esta transformación es uno a uno.

Por lo tanto, puede elegir un punto aleatorio en el círculo más pequeño (elija el ángulo al azar entre 0 y dos pi) y elegir una relación aleatoria entre 1 y la relación de proporcionalidad R / r entre los círculos. Luego use esa transformación de similitud con el mismo punto fijo pero usando la relación aleatoria para obtener el punto de imagen del punto recién elegido en el círculo más pequeño. Este es un punto aleatorio en su región deseada.

Este método es bastante simple. De hecho, la parte matemática más difícil es encontrar el punto fijo de la transformación de similitud. Pero esto es bastante fácil, dados los centros y radios de los dos círculos. Sugerencia: la transformación lleva el centro del círculo más pequeño al centro del círculo más grande.

Pregunte si necesita más detalles. Mi algoritmo no produce una distribución uniforme: los puntos estarán más apretados donde los círculos están más juntos y menos apretados donde los círculos están más separados.


Aquí hay un código Python 3.6.2 no probado que hace lo anterior. Lo probaré y mostraré un gráfico cuando pueda.

import math
import random

def rand_pt_between_circles(x_inner, 
                            y_inner,
                            r_inner, 
                            x_outer,
                            y_outer,
                            r_outer):
    """Return a random floating-point 2D point located between the 
    inner and the outer circles given by their center coordinates and 
    radii. No error checking is done on the parameters."""
    # Find the fixed point of the similarity transformation from the
    #   inner circle to the outer circle.
    x_fixed = x_inner - (x_outer - x_inner) / (r_outer - r_inner) * r_inner 
    y_fixed = y_inner - (y_outer - y_inner) / (r_outer - r_inner) * r_inner 

    # Find a a random transformation ratio between 1 and r_outer / r_inner
    #   and a random point on the inner circle
    ratio = 1 + (r_outer - r_inner) * random.random()
    theta = 2 * math.pi * random.random()
    x_start = x_inner + r_inner * math.cos(theta)
    y_start = y_inner + r_inner * math.sin(theta)

    # Apply the similarity transformation to the random point.
    x_result = x_fixed + (x_start - x_fixed) * ratio
    y_result = y_fixed + (y_start - y_fixed) * ratio

    return x_result, y_result
2
Rory Daulton 30 oct. 2017 a las 00:09

¿Realmente necesitas un muestreo exacto? Porque con aceptación / rechazo debería funcionar bien. Supongo que el gran círculo naranja se encuentra en (0,0)

import math
import random

def sample_2_circles(xr, yr, r, R):
    """
    R - big radius
    r, xr, yr - small radius and its position
    """
    x = xr
    y = yr
    cnd = True
    while cnd:
        # sample uniformly in whole orange circle
        phi = 2.0 * math.pi * random.random()
        rad = R * math.sqrt(random.random())
        x = rad * math.cos(phi)
        y = rad * math.sin(phi)

        # check condition - if True we continue in the loop with sampling
        cnd = ( (x-xr)**2 + (y-yr)**2 < r*r )

    return (x,y)
3
Severin Pappadeux 30 oct. 2017 a las 00:21

El método de aceptación / rechazo descrito por Severin Pappadeux es probablemente el más simple.

Para un enfoque directo, también puede trabajar en coordenadas polares, con el centro del agujero como el poste.

La ecuación polar (Θ, σ) (perdón, no rho) del círculo externo será

(σ cosΘ - xc)² + (σ sinΘ - yc)² = σ² - 2(cosΘ xc + sinΘ yc)σ + xc² + yc² = R²

Esta es una ecuación cuadrática en σ, que puedes resolver fácilmente en términos de Θ. Luego puede dibujar un ángulo en 0, 2π y dibujar un radio entre r y σ.

Esto no le dará una distribución uniforme, porque el rango de σ es una función de Θ y debido al sesgo polar. Esto podría solucionarse calculando una función de transferencia adecuada, pero esto es un poco técnico y probablemente no sea manejable analíticamente.

1
Yves Daoust 30 oct. 2017 a las 08:34