如何在中心为原点的矩形图像内生成无重叠随机坐标点？

我有一张宽度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):

    # 如果输入的数量不是完全平方数，就找下一个完全平方数
    # 这样就能得到平方根N，用来确定行列数
    if not is_square(n):
        n = perfect_sqr(n)
    N = np.sqrt(n)

    # 生成x和y列表，分别是在0到宽/高之间均匀分布的点数组
    x = np.array(list(range(0, width, int(width/N))))
    y = np.array(list(range(0, height, int(height/N))))

    # 将点居中到每个单元格内
    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]

    # 生成点网格
    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()

    # 将数组转为一维
    xx = xv.flatten()
    yy = yv.flatten()

    # 合并为坐标对
    zips = zip(xx, yy)

    # 转为坐标点元组的集合并返回
    return set(zips)


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

内容的提问来源于stack exchange，提问作者pookie