Esta es la contestación más acertada que encomtrarás brindar, pero primero estúdiala pausadamente y analiza si es compatible a tu trabajo.
Solución:
Lo mejor que se me ocurrió es una solución de fuerza bruta que calcula las dimensiones de la cuadrícula que minimizan el error en el cuadrado de la distancia euclidiana entre el punto y su intersección de cuadrícula más cercana.
Esto supone que el número de puntos p es exactamente igual al número de columnas multiplicado por el número de filas, y que cada intersección de la cuadrícula tiene exactamente un punto. También asume que el valor mínimo de x/y para cualquier punto es cero. Si el mínimo es mayor que cero, simplemente reste el valor mínimo de x de la coordenada x de cada punto y el valor mínimo de la coordenada y de cada punto.
La idea es crear todas las dimensiones posibles de la cuadrícula dada la cantidad de puntos. En el ejemplo anterior con 16 puntos, haríamos cuadrículas con dimensiones 1×16, 2×8, 4×4, 8×2 y 16×1. Para cada una de estas cuadrículas, calculamos dónde estarían las intersecciones de la cuadrícula dividiendo el ancho máximo de los puntos por el número de columnas menos 1, y la altura máxima de los puntos por el número de filas menos 1. Luego ajustamos cada punto para su intersección de cuadrícula más cercana y encuentre el error (cuadrado de la distancia) entre el punto y la intersección. (Tenga en cuenta que esto solo funciona si cada punto está más cerca de su intersección de cuadrícula prevista que de cualquier otra intersección).
Después de sumar los errores de cada configuración de cuadrícula individualmente (por ejemplo, obtener un valor de error para la configuración 1×16, otro para la configuración 2×8, etc.), seleccionamos la configuración con el error más bajo.
Inicialización:
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
Algoritmo:
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;
Una vez que tenga la cantidad de columnas (y, por lo tanto, la cantidad de filas), puede volver a calcular los valores normalizados para cada punto y redondearlos para obtener la intersección de la cuadrícula a la que pertenecen.
Un poco de un enfoque de procesamiento de imágenes: si piensa en lo que tiene como una imagen binaria donde la X es 1 y el resto es 0, puede sumar filas y columnas, y usar un algoritmo de búsqueda de picos para identificar picos que corresponden a las líneas x e y de la cuadrícula:
Sus puntos como una imagen binaria:
Sumas de filas/columnas
Ahora aplique alguna técnica de suavizado a la señal (por ejemplo, lowess):
Seguro que te haces una idea 🙂
Buena suerte
Al final utilicé este algoritmo, inspirado en el de beaker:
- Calcular todas las dimensiones posibles de la cuadrícula, dado el número total de puntos
- Para cada dimensión posible, ajuste los puntos a esa dimensión y calcule la variación en la alineación:
- Ordenar los puntos por valor de x
- Agrupe los puntos en columnas: los primeros r puntos forman la primera columna, donde r es el número de filas
- Dentro de cada columna, ordene los puntos por valor y para determinar en qué fila están
- Para cada fila/columna, calcule el rango de valores de y/valores de x
- La variación en la alineación es el rango máximo encontrado
- Elija la dimensión con la menor variación en la alineación
Comentarios y valoraciones
Al final de la página puedes encontrar las explicaciones de otros programadores, tú asimismo tienes el poder insertar el tuyo si lo deseas.