(不完全な) グリッドを形成する 2D 空間内のポイントのリストがあります。
x x x x
x x x x
x
x x x
x x x x
これらを固定グリッドに合わせる最良の方法は何ですか (つまり、2 次元配列を作成し、各点がその配列のどこに収まるかを調べます)?
グリッドに穴はありませんが、その寸法が事前にわかりません。
EDIT：グリッドは必ずしも規則的ではありません（行/列間の間隔でさえありません）
私が思いついた最善の方法は、点とその最も近いグリッド交点の間のユークリッド距離の 2 乗の誤差を最小化するグリッド寸法を計算する力ずくのソリューションです。
これは、点の数 p が列の数に行の数を掛けたものに正確に等しく、各グリッド交点に正確に 1 つの点があることを前提としています。また、任意のポイントの最小 x/y 値がゼロであると想定しています。最小値がゼロより大きい場合は、各ポイントの x 座標から最小 x 値を減算し、各ポイントの y 座標から最小 y 値を減算します。
考えられるのは、与えられたポイント数で可能なすべてのグリッド ディメンションを作成することです。上記の 16 ポイントの例では、寸法 1x16、2x8、4x4、8x2、および 16x1 のグリッドを作成します。これらの各グリッドについて、ポイントの最大幅を列数から 1 を引いた数で割り、ポイントの最大高さを行数から 1 を引いた数で割ることによって、グリッドの交点がどこにあるかを計算します。次に、各ポイントを次のように適合させます。その最も近いグリッド交点と、点と交点の間の誤差 (距離の 2 乗) を見つけます。(これは、各ポイントが他の交点よりも意図したグリッド交点に近い場合にのみ機能することに注意してください。)
各グリッド構成のエラーを個別に合計した後 (たとえば、1x16 構成で 1 つのエラー値を取得し、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;
列の数 (および行の数) を取得したら、各ポイントの正規化された値を再計算し、それらを丸めて、それらが属するグリッドの交点を取得できます。
最後に、ビーカーに触発されたこのアルゴリズムを使用しました。