sorting - primero - Heurística para ordenar una matriz de puntos 2D/3D según su distancia mutua
primero el mejor inteligencia artificial (2)
Considere una matriz de puntos en 2D, 3D, (4D ...) espacio (por ejemplo, nodos de malla no estructurada ). Inicialmente, el índice de un punto en matriz no está relacionado con su posición en el espacio. En caso simple, supongamos que ya conozco un gráfico de conectividad del vecino más cercano.
Me gustaría algunas heurísticas que aumentan la probabilidad de que dos puntos que están cerca uno del otro en el espacio tendrían un índice similar (estarían cerca en el conjunto).
Entiendo que la solución exacta es muy difícil (tal vez similar al problema del vendedor ambulante ) pero no necesito una solución exacta, solo algo que aumente la probabilidad.
Mis ideas sobre la solución:
alguna solución ingenua sería como:
1. for each point "i" compute fitness E_i given by sum of distances in array (i.e. index-wise) from its spatial neighbors (i.e. space-wise)
E_i = -Sum_k ( abs( index(i)-index(k) ) )
where "k" are spatial nearest neighbors of "i"
2. for pairs of points (i,j) which have low fitness (E_i,E_j)
try to swap them,
if fitness improves, accept
pero la implementación detallada y su optimización del rendimiento no es tan clara.
Otra solución que no necesita vecinos más cercanos precalculados se basaría en algunas locality-sensitive_hashing
Creo que este podría ser un problema bastante común, y puede haber buenas soluciones , no quiero reinventar la rueda.
Solicitud:
- mejorar la ubicación del caché, teniendo en cuenta que el acceso a la memoria a menudo es un cuello de botella de cruce de gráficos
- podría acelerar la interpolación de la cuadrícula no estructurada, más específicamente la búsqueda de nodos que están cerca de la smaple (por ejemplo, centros de función de base radial).
El problema que está tratando de resolver tiene significado si, dado un punto p y su NN q, entonces es cierto que el NN de q es p.
Eso no es trivial, ya que, por ejemplo, los dos puntos pueden representar posiciones en un paisaje, por lo que un punto puede ser alto en una montaña, por lo que ir de abajo a arriba cuesta más que al revés (de la montaña al fondo). Por lo tanto, asegúrese de verificar que ese no sea su caso.
Dado que TilmannZ ya propuso una solución, me gustaría hacer hincapié en LSH que mencionó. No elegiría eso, ya que tus puntos se encuentran en un espacio tridimensional realmente bajo , ni siquiera son 100, entonces, ¿por qué usar LSH?
Me gustaría ir por el algoritmo de CGAL en ese caso, como 2D NNS , o incluso un simple kd-tree . Y si la velocidad es crítica, pero el espacio no lo es, ¿por qué no ir a un quadtree (octree en 3D)? Construí uno, no irá más allá de 10 dimensiones en una RAM de 8GB.
Sin embargo, si crees que tus datos pueden pertenecer a un espacio dimensional superior en el futuro, entonces te sugiero que utilices:
Yo diría que las curvas de relleno de espacio (SPC) son la solución estándar para mapear la proximidad en el espacio a un orden lineal. Los más comunes son Hilbert-curvas y z-curvas (orden de Morton) .
Las curvas de Hilbert tienen el mejor mapeo de proximidad, pero son un tanto caros de calcular. El orden Z todavía tiene un buen mapeo de proximidad, pero es muy fácil de calcular. Para ordenamiento z, es suficiente intercalar los bits de cada dimensión. Suponiendo valores enteros, si tiene un punto 3D de 64 bits (x, y, z), el valor z es $ x_0, y_0, z_0, x_1, y_1, z_1, ... x_63, y_63, z_63 $, es decir, un 192 valor de bit que consiste en el primer bit de cada dimensión, seguido del segundo bit de cada dimensión, y así sucesivamente. Si su matriz se ordena de acuerdo con ese valor z, los puntos que están cerca en el espacio generalmente también están cerca en la matriz.
Aquí hay ejemplos de funciones que intercalan ( merge ) valores en un valor z ( nBitsPerValue suele ser 32 o 64):
public static long[] mergeLong(final int nBitsPerValue, long[] src) {
final int DIM = src.length;
int intArrayLen = (src.length*nBitsPerValue+63) >>> 6;
long[] trg = new long[intArrayLen];
long maskSrc = 1L << (nBitsPerValue-1);
long maskTrg = 0x8000000000000000L;
int srcPos = 0;
int trgPos = 0;
for (int j = 0; j < nBitsPerValue*DIM; j++) {
if ((src[srcPos] & maskSrc) != 0) {
trg[trgPos] |= maskTrg;
} else {
trg[trgPos] &= ~maskTrg;
}
maskTrg >>>= 1;
if (maskTrg == 0) {
maskTrg = 0x8000000000000000L;
trgPos++;
}
if (++srcPos == DIM) {
srcPos = 0;
maskSrc >>>= 1;
}
}
return trg;
}
También puede intercalar los bits de los valores de coma flotante (si están codificados con IEEE 754, como suelen ser en las computadoras estándar), pero esto da como resultado propiedades de distancia no euclidianas. Puede que tenga que transformar los valores negativos primero, vea aquí , sección 2.3.
EDITAR Dos responden las preguntas de los comentarios:
1) Entiendo cómo hacer la curva de relleno de espacio para la cuadrícula rectangular regular. Sin embargo, si tengo puntos flotantes colocados al azar, varios puntos pueden mapearse en una casilla. ¿Funcionaría ese algoritmo en ese caso?
Hay varias formas de usar valores de punto flotante (FP). Lo más simple es convertirlos a valores enteros multiplicándolos por una constante grande. Por ejemplo, multiplique todo por 10 ^ 6 para preservar la precisión de 6 dígitos.
Otra forma es usar la representación de nivel de bits del valor FP para convertirlo en un entero. Esto tiene la ventaja de que no se pierde precisión y no es necesario determinar una constante de multiplicación. La desventaja es que la métrica de distancia euclidiana ya no funciona.
Funciona de la siguiente manera: el truco es que los valores de punto flotante no tienen una precisión infinita, pero están limitados a 64 bits. Por lo tanto, automáticamente forman una cuadrícula. La diferencia con los valores enteros es que los valores de punto flotante no forman una cuadrícula sino una cuadrícula rectangular donde los rectángulos se hacen más grandes a medida que aumenta la distancia desde (0,0). El tamaño de la cuadrícula viene determinado por la cantidad de precisión disponible en un punto determinado. Cerca de (0,0), la precisión (= grid_size) es 10 ^ -28, cerca de (1,1), es 10 ^ -16 ver aquí . Esta cuadrícula distorsionada todavía tiene el mapeo de proximidad, pero las distancias ya no son euclidianas.
Aquí está el código para hacer la transformación (Java, tomado de aquí ; en C ++ simplemente puedes convertir el float a int ):
public static long toSortableLong(double value) {
long r = Double.doubleToRawLongBits(value);
return (r >= 0) ? r : r ^ 0x7FFFFFFFFFFFFFFFL;
}
public static double toDouble(long value) {
return Double.longBitsToDouble(value >= 0.0 ? value : value ^ 0x7FFFFFFFFFFFFFFFL);
}
Estas conversiones conservan el orden de los valores convertidos, es decir, por cada dos valores de FP, los enteros resultantes tienen el mismo orden con respecto a <,>, =. El comportamiento no euclidiano es causado por el exponente que está codificado en la cadena de bits. Como se mencionó anteriormente, esto también se discute aquí , sección 2.3, sin embargo, el código está ligeramente menos optimizado.
2) ¿Hay algún algoritmo de cómo hacer la actualización iterativa de dicha curva de relleno espacial si mis puntos se mueven en el espacio? (es decir, sin reordenar toda la matriz cada vez)
La curva de relleno de espacio impone un orden específico, por lo que para cada conjunto de puntos solo hay un pedido válido. Si se mueve un punto, debe reinsertarse en la nueva posición determinada por su valor z.
La buena noticia es que un movimiento pequeño probablemente significará que un punto a menudo puede permanecer en la misma "área" de su matriz. Entonces, si realmente usa una matriz fija, solo tiene que cambiar pequeñas partes de la misma.
Si tiene muchos objetos en movimiento y la matriz es engorrosa, puede buscar en ''índices de objetos en movimiento'' (MX-CIF-quadtree, etc.). Personalmente puedo recomendar mi propio PH-Tree . Es una especie de quad-radix bit a bit que usa una curva z para ordenamiento interno. Es bastante eficiente para las actualizaciones (y otras operaciones). Sin embargo, normalmente lo recomiendo solo para conjuntos de datos más grandes, para conjuntos de datos pequeños, un quadtree simple suele ser lo suficientemente bueno.