Most efficient way to remove x,y coordinates in a specified area

Question

I have two arrays of x and y coordinates:

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

I'm using these arrays to randomly plot squares of .65 width/height within the specified range, which represents an area on the left side of a quadrant. The values indicate distance from 0 in visual degrees, and an x,y pair is what the square is centered on. Here is how I'm picking the coordinates at random:

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

The problem is that sometimes there are multiple squares to be plotted, and they cannot overlap. A minimum distance of 2 degrees (center to center) must be maintained between squares within the defined area.

I thought about creating an array containing all of the possible coordinate pairs within that area:

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

I could then randomly pick a pair from that array, produce another array of all the coordinate points in the square area centered on that pair, and remove them from coords. This would ensure that no other square can be plotted within 2 degrees of that square. I suppose that this could be done for multiple squares.

This produces some massive arrays. This code is being run within PsychoPy (experiment builder), so its important that assigning those coordinates to squares happens quickly. What is the most efficient way to accomplish this task? Perhaps there is a more obvious method that I am missing?

Answer 1

You could use a grid map to be able to do a quick check.

When you select a point first check looking only a nearby cells in the grid if there's any other point that is too close, otherwise you accept the point and also add the point to the grid:

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