如何在矩形内，随机位置，无重叠地生成点?

Question

我有一个图像，宽度:1980，高度:1080。最终，我想在图像中放置各种形状，但在随机的位置，以这样一种方式，它们不会重叠。图像的0,0坐标在中心

在将形状渲染到图像之前(我不需要帮助)，我需要编写一个算法来生成XY点/位置。我希望能够指定任何给定点到任何其他点的最小距离

怎么能这样呢?

我所能做的就是在等间隔的位置生成点，然后为每个点添加一点随机性。但这并不理想，因为这意味着点只是在网格中的某些"单元格"内变化，如果随机性值过高，它们将出现在矩形之外。下面是我的代码:

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle
from random import randrange
def is_square(integer):
root = np.sqrt(integer)
return integer == int(root + 0.5) ** 2
def perfect_sqr(n):
nextN = np.floor(np.sqrt(n)) + 1
return int(nextN * nextN)
def generate_cells(width = 1920, height = 1080, n = 9, show_plot=False):
# If the number is not a perfect square, we need to find the next number which is
# so that we can get the root N, which will be used to determine the number of rows/columns
if not is_square(n):
n = perfect_sqr(n)
N = np.sqrt(n)
# generate x and y lists, where each represents an array of points evenly spaced between 0 and the width/height
x = np.array(list(range(0, width, int(width/N))))
y = np.array(list(range(0, height, int(height/N))))
# center the points within each 'cell'
x_centered = x+int(width/N)/2
y_centered = y+int(height/N)/2
x_centered = [a+randrange(50) for a in x_centered]
y_centered = [a+randrange(50) for a in y_centered]
# generate a grid with the points
xv, yv = np.meshgrid(x_centered, y_centered)
if(show_plot):
plt.scatter(xv,yv)
plt.gca().add_patch(Rectangle((0,0),width, height,edgecolor='red', facecolor='none', lw=1))
plt.show()
# convert the arrays to 1D
xx = xv.flatten()
yy = yv.flatten()
# Merge them side-by-side
zips = zip(xx, yy)
# convert to set of points/tuples and return
return set(zips)

coords = generate_cells(width=1920, height=1080, n=15, show_plot=True)
print(coords)

Answer 1

假设您只是想在最大图像大小的范围内随机定义不重叠的坐标，而不让图像重叠，这可能是一个很好的解决方案。

import numpy as np 
def locateImages(field_height: int, field_width: int, min_sep: int, points: int)-> np.array:
h_range = np.array(range(min_sep//2, field_height - (min_sep//2), min_sep))
w_range = np.array(range(min_sep//2, field_width-(min_sep//2), min_sep))
mx_len = max(len(h_range), len(w_range))
if len(h_range) < mx_len:
xtra = np.random.choice(h_range, mx_len - len(h_range))
h_range = np.append(h_range, xtra)
if len(w_range) < mx_len:
xtra = np.random.choice(w_range, mx_len - len(w_range))
w_range = np.append(w_range, xtra)
h_points = np.random.choice(h_range, points, replace=False)
w_points = np.random.choice(w_range, points, replace=False)
return np.concatenate((np.vstack(h_points), np.vstack(w_points)), axis= 1)  

然后给出:field_height =图像空间的垂直坐标field_width =图像空间的最大水平坐标Min_sep =图像之间的最小间距点=要选择的座标个数

:locateImages(15, 8, 2, 5)产率:

array([[13,  1],
[ 7,  3],
[ 1,  5],
[ 5,  5],
[11,  5]])

渲染输出:

points = locateImages(1080, 1920, 100, 15)
x,y= zip(*points)
plt.scatter(x,x)
plt.gca().add_patch(Rectangle((0,0),1920, 1080,edgecolor='red', facecolor='none', lw=1))
plt.show()