我有一个二维空间中形成（不完美）网格的点列表：
x x x x
x x x x
x
x x x
x x x x
将这些拟合到刚性网格的最佳方法是什么（即创建一个二维数组并计算出每个点在该数组中的位置）？
网格中没有孔，但我事先不知道它的尺寸是多少。
编辑：网格不一定是规则的（甚至行/列之间的间距）
一点图像处理方法：如果您将所拥有的图像视为 X 为 1 其余为 0 的二进制图像，您可以总结行和列，并使用峰值查找算法来识别峰值对应于网格的 x 和 y 线：
您作为二进制图像的点：
行/列的总和
现在对信号应用一些平滑技术（例如lowess）：
我相信你明白了:-)
祝你好运
我能想到的最好的方法是计算网格尺寸的蛮力解决方案，以最小化点与其最近网格交点之间的欧几里得距离的平方误差。
这假设点的数量 p 正好等于列数乘以行数，并且每个网格交叉点上正好有一个点。它还假设任何点的最小 x/y 值为零。如果最小值大于零，只需从每个点的 x 坐标减去最小 x 值，从每个点的 y 坐标减去最小 y 值。
这个想法是在给定点数的情况下创建所有可能的网格尺寸。在上面有 16 个点的示例中，我们将制作尺寸为 1x16、2x8、4x4、8x2 和 16x1 的网格。对于这些网格中的每一个，我们通过将点的最大宽度除以列数减 1 并将点的最大高度除以行数减 1 来计算网格交叉点的位置。然后我们将每个点拟合到它最近的网格交点并找到该点和交点之间的误差（距离的平方）。（请注意，这仅在每个点更接近其预期的网格交叉点而不是任何其他交叉点时才有效。）
在分别对每个网格配置的误差求和后（例如，为 1x16 配置获取一个误差值，为 2x8 配置获取另一个误差值等等），我们选择具有最低误差的配置。
初始化：
P is the set of points such that P[i][0] is the x-coordinate and
P[i][1] is the y-coordinate
Let p = |P| or the number of points in P
Let max_x = the maximum x-coordinate in P
Let max_y = the maximum y-coordinate in P
(minimum values are assumed to be zero)
Initialize min_error_dist = +infinity
Initialize min_error_cols = -1
算法：
for (col_count = 1; col_count <= n; col_count++) {
// only compute for integer # of rows and cols
if ((p % col_count) == 0) {
row_count = n/col_count;
// Compute the width of the columns and height of the rows
// If the number of columns is 1, let the column width be max_x
// (and similarly for rows)
if (col_count > 1) col_width = max_x/(col_count-1);
else col_width=max_x;
if (row_count > 1) row_height = max_y/(row_count-1);
else row_height=max_y;
// reset the error for the new configuration
error_dist = 0.0;
for (i = 0; i < n; i++) {
// For the current point, normalize the x- and y-coordinates
// so that it's in the range 0..(col_count-1)
// and 0..(row_count-1)
normalized_x = P[i][0]/col_width;
normalized_y = P[i][1]/row_height;
// Error is the sum of the squares of the distances between
// the current point and the nearest grid point
// (in both the x and y direction)
error_dist += (normalized_x - round(normalized_x))^2 +
(normalized_y - round(normalized_y))^2;
}
if (error_dist < min_error_dist) {
min_error_dist = error_dist;
min_error_cols = col_count;
}
}
}
return min_error_cols;
一旦获得了列数（以及行数），您就可以重新计算每个点的归一化值并将它们四舍五入以获得它们所属的网格交点。
最后我使用了这个算法，灵感来自烧杯：
我写了这个算法来解释丢失的坐标以及有错误的坐标。
# Input [x, y] coordinates of a 'sparse' grid with errors
xys = [[103,101],
[198,103],
[300, 99],
[ 97,205],
[304,202],
[102,295],
[200,303],
[104,405],
[205,394],
[298,401]]
def row_col_avgs(num_list, ratio):
# Finds the average of each row and column. Coordinates are
# assigned to a row and column by specifying an error ratio.
last_num = 0
sum_nums = 0
count_nums = 0
avgs = []
num_list.sort()
for num in num_list:
if num > (1 + ratio) * last_num and count_nums != 0:
avgs.append(int(round(sum_nums/count_nums,0)))
sum_nums = num
count_nums = 1
else:
sum_nums = sum_nums + num
count_nums = count_nums + 1
last_num = num
avgs.append(int(round(sum_nums/count_nums,0)))
return avgs
# Split coordinates into two lists of x's and y's
xs, ys = map(list, zip(*xys))
# Find averages of each row and column within a specified error.
x_avgs = row_col_avgs(xs, 0.1)
y_avgs = row_col_avgs(ys, 0.1)
# Return Completed Averaged Grid
avg_grid = []
for y_avg in y_avgs:
avg_row = []
for x_avg in x_avgs:
avg_row.append([int(x_avg), int(y_avg)])
avg_grid.append(avg_row)
print(avg_grid)
[[[102, 101], [201, 101], [301, 101]],
[[102, 204], [201, 204], [301, 204]],
[[102, 299], [201, 299], [301, 299]],
[[102, 400], [201, 400], [301, 400]]]
我也在寻找使用线性代数的另一种解决方案。在这里查看我的问题。