repetir - Genera un número aleatorio fuera del rango en Python

muestra aleatoria en python

Question

Actualmente estoy trabajando en un juego de pygame y necesito colocar objetos al azar en la pantalla, excepto que no pueden estar dentro de un rectángulo designado. ¿Hay una manera fácil de hacer esto en lugar de generar continuamente un par de coordenadas al azar hasta que esté fuera del rectángulo?

Aquí hay un ejemplo aproximado de cómo se ven la pantalla y el rectángulo.

 ______________
|      __      |
|     |__|     |
|              |
|              |
|______________|

Donde el tamaño de la pantalla es 1000x800 y el rectángulo es [x: 500, y: 250, ancho: 100, altura: 75]

Una forma más orientada al código de mirarlo sería

x = random_int
0 <= x <= 1000
    and
500 > x or 600 < x

y = random_int
0 <= y <= 800
    and
250 > y or 325 < y

Answer 1

1. Divida la caja en un conjunto de cajas secundarias.
2. Entre los cuadros secundarios válidos, elija en cuál colocar su punto con probabilidad proporcional a sus áreas
3. Elija un punto aleatorio uniformemente al azar desde dentro del cuadro secundario elegido.

Esto generará muestras de la distribución de probabilidad uniforme en la región válida, basada en la regla de la cadena de probabilidad condicional.

Answer 2

Esto ofrece un enfoque O (1) en términos de tiempo y memoria.

Razón fundamental

La respuesta aceptada junto con otras respuestas parecen depender de la necesidad de generar listas de todas las coordenadas posibles, o recalcular hasta que haya una solución aceptable. Ambos enfoques requieren más tiempo y memoria de lo necesario.

Tenga en cuenta que, según los requisitos de uniformidad de generación de coordenadas, existen diferentes soluciones, como se muestra a continuación.

Primer intento

Mi enfoque es elegir aleatoriamente solo las coordenadas válidas alrededor del cuadro designado (piense izquierda / derecha , arriba / abajo ), luego seleccione al azar qué lado elegir:

import random
# set bounding boxes    
maxx=1000
maxy=800
blocked_box = [(500, 250), (100, 75)]
# generate left/right, top/bottom and choose as you like
def gen_rand_limit(p1, dim):
    x1, y1 = p1
    w, h = dim
    x2, y2 = x1 + w, y1 + h
    left = random.randrange(0, x1)
    right = random.randrange(x2+1, maxx-1)
    top = random.randrange(0, y1)
    bottom = random.randrange(y2, maxy-1)
    return random.choice([left, right]), random.choice([top, bottom])
# check boundary conditions are met
def check(x, y, p1, dim):
    x1, y1 = p1
    w, h = dim
    x2, y2 = x1 + w, y1 + h
    assert 0 <= x <= maxx, "0 <= x(%s) <= maxx(%s)" % (x, maxx)
    assert x1 > x or x2 < x, "x1(%s) > x(%s) or x2(%s) < x(%s)" % (x1, x, x2, x)
    assert 0 <= y <= maxy, "0 <= y(%s) <= maxy(%s)" %(y, maxy)
    assert y1 > y or y2 < y, "y1(%s) > y(%s) or y2(%s) < y(%s)" % (y1, y, y2, y)
# sample
points = []
for i in xrange(1000):
    x,y = gen_rand_limit(*blocked_box)
    check(x, y, *blocked_box)
    points.append((x,y))

Resultados

Dadas las restricciones como se indica en el OP, esto en realidad produce coordenadas aleatorias (azul) alrededor del rectángulo designado (rojo) como se desee, sin embargo, deja fuera cualquiera de los puntos válidos que están fuera del rectángulo pero que caen dentro de las respectivas dimensiones x o y de el rectángulo:

# visual proof via matplotlib
import matplotlib
from matplotlib import pyplot as plt
from matplotlib.patches import Rectangle
X,Y = zip(*points)
fig = plt.figure()
ax = plt.scatter(X, Y)
p1 = blocked_box[0]
w,h = blocked_box[1]
rectangle = Rectangle(p1, w, h, fc=''red'', zorder=2)
ax = plt.gca()
plt.axis((0, maxx, 0, maxy))
ax.add_patch(rectangle)

Mejorado

Esto se soluciona fácilmente limitando solo las coordenadas x o y (tenga en cuenta que la check ya no es válida, comente para ejecutar esta parte):

def gen_rand_limit(p1, dim):
    x1, y1 = p1
    w, h = dim
    x2, y2 = x1 + w, y1 + h
    # should we limit x or y?
    limitx = random.choice([0,1])
    limity = not limitx
    # generate x, y O(1)
    if limitx:
        left = random.randrange(0, x1)
        right = random.randrange(x2+1, maxx-1)
        x = random.choice([left, right])
        y = random.randrange(0, maxy)
    else:
        x = random.randrange(0, maxx)
        top = random.randrange(0, y1)
        bottom = random.randrange(y2, maxy-1)
        y = random.choice([top, bottom])
    return x, y 

Ajustando el sesgo aleatorio

Como se señaló en los comentarios, esta solución adolece de un sesgo dado a los puntos fuera de las filas / columnas del rectángulo. Los siguientes arreglos que, en principio, le dan a cada coordenada la misma probabilidad:

def gen_rand_limit(p1, dim):
    x1, y1 = p1Final solution -
    w, h = dim
    x2, y2 = x1 + w, y1 + h
    # generate x, y O(1)
    # --x
    left = random.randrange(0, x1)
    right = random.randrange(x2+1, maxx)
    withinx = random.randrange(x1, x2+1)
    # adjust probability of a point outside the box columns
    # a point outside has probability (1/(maxx-w)) v.s. a point inside has 1/w
    # the same is true for rows. adjupx/y adjust for this probability 
    adjpx = ((maxx - w)/w/2)
    x = random.choice([left, right] * adjpx + [withinx])
    # --y
    top = random.randrange(0, y1)
    bottom = random.randrange(y2+1, maxy)
    withiny = random.randrange(y1, y2+1)
    if x == left or x == right:
        adjpy = ((maxy- h)/h/2)
        y = random.choice([top, bottom] * adjpy + [withiny])
    else:
        y = random.choice([top, bottom])
    return x, y 

La siguiente gráfica tiene 10''000 puntos para ilustrar la colocación uniforme de los puntos (los puntos que se superponen al borde de la caja se deben al tamaño del punto).

Descargo de responsabilidad: Tenga en cuenta que este gráfico coloca el cuadro rojo en el centro, de modo que la top/bottom , left/right tienen la misma probabilidad entre sí. Por lo tanto, el ajuste es relativo al cuadro de bloqueo, pero no para todas las áreas del gráfico. Una solución final requiere ajustar las probabilidades para cada uno de estos por separado.

Solución más simple, pero un problema ligeramente modificado

Resulta que ajustar las probabilidades para diferentes áreas del sistema de coordenadas es bastante complicado. Después de pensar un poco, se me ocurrió un enfoque ligeramente modificado:

Al darse cuenta de que en cualquier sistema de coordenadas 2D, el bloqueo de un rectángulo divide el área en N subáreas (N = 8 en el caso de la pregunta) donde se puede elegir una coordenada válida. Mirándolo de esta manera, podemos definir las subáreas válidas como cuadros de coordenadas. Luego podemos elegir un cuadro al azar y una coordenada al azar dentro de ese cuadro:

def gen_rand_limit(p1, dim):
    x1, y1 = p1
    w, h = dim
    x2, y2 = x1 + w, y1 + h
    # generate x, y O(1)
    boxes = (
       ((0,0),(x1,y1)),   ((x1,0),(x2,y1)),    ((x2,0),(maxx,y1)),
       ((0,y1),(x1,y2)),                       ((x2,y1),(maxx,y2)),
       ((0,y2),(x1,maxy)), ((x1,y2),(x2,maxy)), ((x2,y2),(maxx,maxy)),
    )
    box = boxes[random.randrange(len(boxes))]
    x = random.randrange(box[0][0], box[1][0])
    y = random.randrange(box[0][1], box[1][1])
    return x, y 

Tenga en cuenta que esto no está generalizado ya que la casilla bloqueada puede no estar en el medio, por lo que las boxes verían diferentes. Como esto resulta en cada casilla elegida con la misma probabilidad, obtenemos el mismo número de puntos en cada casilla. Obviamente la densidad es mayor en cajas más pequeñas:

Si el requisito es generar una distribución uniforme entre todas las coordenadas posibles, la solución es calcular boxes modo que cada cuadro tenga aproximadamente el mismo tamaño que el cuadro de bloqueo. YMMV

Answer 3

Requiere un poco de pensamiento para generar un punto aleatoriamente uniforme con estas restricciones. La forma más sencilla de fuerza bruta en la que puedo pensar es generar una lista de todos los puntos válidos y usar random.choice() para seleccionar de esta lista. Esto utiliza unos pocos MB de memoria para la lista, pero generar un punto es muy rápido:

import random

screen_width = 1000
screen_height = 800
rect_x = 500
rect_y = 250
rect_width = 100
rect_height = 75

valid_points = []
for x in range(screen_width):
    if rect_x <= x < (rect_x + rect_width):
        for y in range(rect_y):
            valid_points.append( (x, y) )
        for y in range(rect_y + rect_height, screen_height):
            valid_points.append( (x, y) )
    else:
        for y in range(screen_height):
            valid_points.append( (x, y) )

for i in range(10):
    rand_point = random.choice(valid_points)
    print(rand_point)

Es posible generar un número aleatorio y asignarlo a un punto válido en la pantalla, que usa menos memoria, pero es un poco desordenado y toma más tiempo generar el punto. Puede haber una forma más limpia de hacer esto, pero aquí hay un enfoque que utiliza las mismas variables de tamaño de pantalla:

rand_max = (screen_width * screen_height) - (rect_width * rect_height) 
def rand_point():
    rand_raw = random.randint(0, rand_max-1)
    x = rand_raw % screen_width
    y = rand_raw // screen_width
    if rect_y <= y < rect_y+rect_height and rect_x <= x < rect_x+rect_width:
        rand_raw = rand_max + (y-rect_y) * rect_width + (x-rect_x)
        x = rand_raw % screen_width
        y = rand_raw // screen_width
    return (x, y)

La lógica aquí es similar a la inversa de la forma en que las direcciones de pantalla se calculan a partir de las coordenadas x e y en los microprocesadores antiguos de 8 y 16 bits. La variable rand_max es igual al número de coordenadas de pantalla válidas. Las coordenadas x e y del píxel se calculan, y si está dentro del rectángulo, el píxel se empuja por encima de rand_max , en la región que no se pudo generar con la primera llamada.

Si no le importa demasiado que el punto sea aleatoriamente uniforme, esta solución es fácil de implementar y muy rápida. Los valores de x son aleatorios, pero el valor de Y está restringido si la X elegida está en la columna con el rectángulo, por lo que los píxeles arriba y debajo del rectángulo tendrán una mayor probabilidad de ser elegidos que los pizeles a la izquierda y derecha del rectángulo :

def pseudo_rand_point():        
    x = random.randint(0, screen_width-1)
    if rect_x <= x < rect_x + rect_width: 
        y = random.randint(0, screen_height-rect_height-1)
        if y >= rect_y:
            y += rect_height
    else:
        y = random.randint(0, screen_height-1)
    return (x, y)

Otra respuesta fue calcular la probabilidad de que el píxel se encuentre en ciertas regiones de la pantalla, pero su respuesta aún no es del todo correcta. Aquí hay una versión que usa una idea similar, calcula la probabilidad de que el píxel esté en una región determinada y luego calcula dónde está dentro de esa región:

valid_screen_pixels = screen_width*screen_height - rect_width * rect_height
prob_left = float(rect_x * screen_height) / valid_screen_pixels
prob_right = float((screen_width - rect_x - rect_width) * screen_height) / valid_screen_pixels
prob_above_rect = float(rect_y) / (screen_height-rect_height)
def generate_rand():
    ymin, ymax = 0, screen_height-1
    xrand = random.random()
    if xrand < prob_left:
        xmin, xmax = 0, rect_x-1
    elif xrand > (1-prob_right):
        xmin, xmax = rect_x+rect_width, screen_width-1
    else:
        xmin, xmax = rect_x, rect_x+rect_width-1
        yrand = random.random()
        if yrand < prob_above_rect:
            ymax = rect_y-1
        else:
            ymin=rect_y+rect_height
    x = random.randrange(xmin, xmax)
    y = random.randrange(ymin, ymax)
    return (x, y)

Answer 4

Si lo que quiere evitar es la generación aleatoria, en lugar del bucle, puede hacer lo siguiente:

1. Genera un par de coordenadas aleatorias de punto flotante en [0,1]
2. Escale las coordenadas para dar un punto en el rectángulo exterior.
3. Si su punto está fuera del rectángulo interior, devuélvalo
4. Volver a escalar para asignar el rectángulo interior al rectángulo exterior
5. Goto paso 3

Esto funcionará mejor si el rectángulo interior es pequeño en comparación con el rectángulo exterior. Y probablemente debería limitarse a solo pasar por el bucle un número máximo de veces antes de generar un nuevo aleatorio y volver a intentarlo.

Answer 5

Ya he publicado una respuesta diferente que aún me gusta, ya que es simple y clara, y no necesariamente lenta ... al menos no es exactamente lo que pidió el OP.

Pensé en ello y diseñé un algoritmo para resolver el problema del OP dentro de sus limitaciones:

1. divida la pantalla en 9 rectángulos alrededor y que comprende el "agujero".
2. considerar los 8 rectángulos ("azulejos") alrededor del agujero central "
3. para cada mosaico, calcule el origen (x, y), la altura y el área en píxeles
4. calcular la suma acumulativa de las áreas de las baldosas, así como el área total de las baldosas
5. para cada extracción, elija un número aleatorio entre 0 y el área total de los mosaicos (inclusive y exclusivo)
6. el uso de las sumas acumuladas determina en qué mosaico se encuentra el píxel aleatorio
7. usando divmod determina la columna y la fila (dx, dy) en el mosaico
8. utilizando los orígenes del mosaico en las coordenadas de la pantalla, calcule el píxel aleatorio en las coordenadas de la pantalla.

Para implementar las ideas anteriores, en las que hay una fase de inicialización en la que computamos datos estáticos y una fase en la que usamos repetidamente esos datos, la estructura de datos natural es una clase, y aquí está mi implementación

from random import randrange

class make_a_hole_in_the_screen():

    def __init__(self, screen, hole_orig, hole_sizes):
        xs, ys = screen
        x, y = hole_orig
        wx, wy = hole_sizes
        tiles = [(_y,_x*_y) for _x in [x,wx,xs-x-wx] for _y in [y,wy,ys-y-wy]]
        self.tiles = tiles[:4] + tiles[5:]
        self.pixels = [tile[1] for tile in self.tiles]
        self.total = sum(self.pixels)
        self.boundaries = [sum(self.pixels[:i+1]) for i in range(8)]
        self.x = [0,    0,    0,
                  x,          x,
                  x+wx, x+wx, x+wx]
        self.y = [0,    y,    y+wy,
                  0,          y+wy,
                  0,    y,    y+wy]

    def choose(self):
        n = randrange(self.total)
        for i, tile in enumerate(self.tiles):
            if n < self.boundaries[i]: break
        n1 = n - ([0]+self.boundaries)[i]
        dx, dy = divmod(n1,self.tiles[i][0])
        return self.x[i]+dx, self.y[i]+dy

Para probar la corrección de la implementación, aquí es una comprobación general que corro en python 2.7 ,

drilled_screen = make_a_hole_in_the_screen((200,100),(30,50),(20,30))
for i in range(1000000):
    x, y = drilled_screen.choose()
    if 30<=x<50 and 50<=y<80: print "***", x, y
    if x<0 or x>=200 or y<0 or y>=100: print "+++", x, y

Una posible optimización consiste en usar un algoritmo de bisección para encontrar el mosaico relevante en lugar de la búsqueda lineal más simple que he implementado.