在指定区域内删除x,y坐标的最有效方法

Question

我有两个数组，分别存储了x和y坐标：

x = np.round(np.arange(-4.67,-1.32,0.01),2)
y = np.round(np.arange(-3.32,3.32,0.01),2)

我用这些数组在指定的范围内随机绘制宽高为0.65的正方形，这个范围代表了象限左侧的一个区域。数值表示从0开始的视觉角度距离，而x,y的配对就是正方形的中心位置。下面是我随机选择坐标的方式：

x1, y1 = random.choice(x), random.choice(y)
position1 = np.append(x1,y1)

问题是，有时候需要绘制多个正方形，而它们不能重叠。正方形之间的中心距离必须保持至少2度的间隔。

我考虑过创建一个数组，里面包含该区域内所有可能的坐标配对：

coords = np.array(list(itertools.product(x,y))

然后我可以从这个数组中随机挑选一对坐标，生成另一个数组，包含以这对坐标为中心的正方形区域内的所有坐标点，并把这些点从coords中移除。这样就能确保其他正方形在这个正方形的2度范围内无法绘制。我想这可以适用于多个正方形。

这样会产生一些非常大的数组。这个代码是在PsychoPy（实验构建工具）中运行的，所以快速分配这些坐标给正方形是很重要的。有没有更高效的方法来完成这个任务？也许我遗漏了更明显的解决方案？

Answer 1

你可以使用一个网格地图来快速检查。

当你选择一个点时，首先只查看网格中附近的单元格，看看有没有其他点离得太近。如果没有太近的点，那就可以接受这个点，并把它也添加到网格中：

grid = {}
points = []

def addPoint(x, y):
    # returns True if the point was accepted

    # compute the cell of the point
    ix = int(math.floor(x / dist))
    iy = int(math.floor(y / dist))

    # check cell and all neighbors
    for nhcell in ((ix-1, iy-1), (ix, iy-1), (ix+1, iy-1),
                   (ix-1,  iy ), (ix,  iy ), (ix+1,  iy ),
                   (ix-1, iy+1), (ix, iy+1), (ix+1, iy+1)):
        if nhcell in grid:
            for xx, yy in grid[nhcell]:
                if (x - xx)**2 + (y - yy)**2 < dist2:
                    # anoter existing point is too close
                    return False

    # the new point is fine
    points.add((x, y))

    # we should also add it to the grid for future checks
    if (ix, iy) in grid:
        grid[(ix, iy)].append((x, y))
    else:
        grid[(ix, iy)] = [(x, y)]

    return True