Constructing A 2d Grid From Potentially Incomplete List Of Candidates

Problem I need to construct a 2D grid using a set of candidate positions (values in X and Y). However, there may be false positive candidates that should be filtered out, as well a

Solution 1:

Here is a fairly simple and cheap solution, though I don't know how robust it is.

First of all, here's a way of getting a better estimate for the spacing:

leeway = 1.10XX = X.reshape((1, X.size))
dX = np.abs(XX - XX.T).reshape((1, X.size ** 2))
dxs = dX[np.where(np.logical_and(dX > expected_distance / leeway,
                                 dX < expected_distance * leeway))]
dx = dxs.mean()

YY = Y.reshape((1, Y.size))
dY = np.abs(YY - YY.T).reshape((1, Y.size ** 2))
dys = dY[np.where(np.logical_and(dY > expected_distance / leeway,
                                 dY < expected_distance * leeway))]
dy = dys.mean()

The code computes internal differences in X and Y, and takes the mean of those who are within 10% of the desired spacing.

For the second part, finding the offset of the grid, a similar method can be used:

Ndx = np.array([np.arange(grid_size[0])]) * dx
x_offsets = XX - Ndx.T
x_offset = np.median(x_offsets)

Ndy = np.array([np.arange(grid_size[1])]) * dy
y_offsets = YY - Ndy.T
y_offset = np.median(y_offsets)

Essentially, what this does is to let each position in X "vote" for NX = grid_size[0] positions where the bottom left point might be, based on X - n * dx where n = 0 is a vote for the point itself, n = 1 is a vote for a point one dx to the left etc. This way, the points near the true origin will get the most votes, and the offset can be found using the median.

I think this method is sufficiently symmetric around the desired origin, that the median can be used in most (if not all) cases. If, however, there are many false positives, that make the median not work for some reason, the "true" origin can be found using e.g. a histogram-method.