¿Cuál es la forma óptima de calcular un código hash para un conjunto de puntos?

Question

Estoy buscando la forma óptima de calcular un código hash para un conjunto de puntos bi-dimensionales (para poder almacenar polígonos en una tabla hash).

Existen algunas formas obvias de hacerlo, como concatenar todas las coordenadas de puntos en una cadena y su código hash, pero esto sería muy lento.

En el otro extremo del espectro de velocidad/colisión, también puedo, por ejemplo, resumir todas las coordenadas, lo que daría como resultado un código muy rápido, pero también crearía muchas colisiones.

¿Cuál es la forma óptima de calcular un código hash para un conjunto de puntos?

¿Es la solución óptima diferente si las coordenadas son enteras (frente a coordenadas reales)?

Editar: Estoy usando .net por lo que el hashcode debe tener 32 bits de longitud.

Answer 1

No hay una manera óptima para este trabajo. Todo depende de qué tan grande hash puedas pagar. Tienes que hacer tradoffs entre velocidad y difusión. Tenga en cuenta que no existe una solución óptima (si no sabe exactamente qué es lo que va a hacer hash) En algunos casos, xor puede ser lo suficientemente bueno.

Tomemos por ejemplo el código

unsigned int JSHash(char* str, unsigned int len) 
{ 
    unsigned int hash = 1315423911; 
    unsigned int i = 0; 

    for(i = 0; i < len; str++, i++) 
    { 
     hash ^= ((hash << 5) + (*str) + (hash >> 2)); 
    } 

    return hash; 
} 
/* End Of JS Hash Function */ 

Se dice que agregating puntos juntos es reducir la velocidad. Si arreglas el código superior no necesita ningún tipo de agregación simplemente pasa a través (no es muy diferente que sumas) Y si estás usando integeres y flotadores probablemente corregirías los cambios (< < y >> son operaciones de cambio que juntas funcionan como bits rotación) para adaptarse a su tipo de datos.

Compruebe si hay otras funciones hash aquí: http://www.partow.net/programming/hashfunctions/

Answer 2

Optimal depende de sus requisitos del cálculo hash.

El rendimiento vendrá a costa de más colisiones hash.

¿Tiene un límite en cualquiera de los dos? Se reducirá a un análisis matemático de cuánto le va a costar cada porcentaje de colisiones hash en términos de rendimiento.

Answer 3

Si el conjunto de datos es por casualidad uno de los polígonos que pueden tener bordes comunes pero no se superponen por lo demás, sólo es necesario para discutir a fondo en tres puntos en cada polígono a evitar colisiones

Editar: Reconsiderando esto, imaginando posibles colisiones con límites cóncavos/convexos, es igual de bien la superposición de sus polígonos. - Suspiro

Alas: Cuando el convexo y el cóncavo se encuentran, siempre me mete en problemas. :-P

Answer 4

Salida este documento

Lamdan and Wolfson. Geometric hashing: A general and efficient model-based recognition scheme. Computer Vision. (1988)

Answer 5

Alternativamente, puede simplemente XOR los hashes de los puntos individuales.

return p1.GetHashCode()^p2.GetHashCode() 

Según los valores que vayan a ser de todos modos. Probablemente podría simplemente agregarlos.

Answer 6

Si desea que los polígonos definidos en el sentido de las agujas del reloj y en el sentido contrario a las agujas del reloj, pero iguales, sean iguales, entonces deberá crear una función de canonización. Una función que da un punto de polígono comenzando desde cualquier punto y en cualquier orden devolverá los puntos en el mismo orden.

Un algoritmo que se me ocurre es encontrar el mínimo de todas las posibles secuencias de puntos:

1. encontrar el conjunto de puntos de recarga más a la izquierda (puntos con x mínimos de los puntos con y mínima), estos son los puntos de partida.
2. Para cada punto de inicio y cada dirección, agregue iterativamente puntos conectados en la dirección dada y elimine todos los que no están en la esquina superior izquierda de la iteración actual. Detener cuando solo queda un punto inicial, par de dirección o cuando se completan n-1 iteraciones. Si queda más de un punto de partida y una dirección, elija cualquiera; todos son isomórficos.
3. Reordenar los puntos comenzando desde el punto encontrado en la dirección encontrada.

Este es O (n^2) el peor caso para polígonos totalmente degenerados, pero si sus polígonos no tienen puntos superpuestos, este es O (n), con un factor constante bastante pequeño.

Con el pedido canonicalizado puede comparar fácilmente dos polígonos para la igualdad, solo compare puntos de forma iterativa para la igualdad. El cálculo de Hashcode también es trivial, use cualquier método de combinación de hash razonablemente robusto. Por ejemplo:

int result = 0; 
foreach (var point in this.points) { 
    result = (result * 31 + point.X.GetHashCode()) * 31 + point.Y.GetHashCode(); 
} 

Answer 7

para un muy rápido (para calcular) hash con las propiedades deseadas de las agujas del reloj la independencia/hacia la izquierda que no le gustaría ser dependiente de la búsqueda de un orden bien definido de los puntos.

Esto limita sus operaciones de combinación de hash a las que conmutan. Por lo tanto, deseamos mantener todos y cada uno de los datos que son independientes de la orientación por separado durante las operaciones de combinación.

Aquí es una solución simple:

Suponiendo una función int combinar -> int -> int que es asociativo cualquiera de las siguientes va a hacer para comenzar con:

public static int combine(int h, int x) 
{ 
    return h * 31 + x; 
} 

public static int combine(int h, int x) 
{ 
    return h^x; 
} 

Entonces podemos hacer lo siguiente:

public override int GetHashCode() 
{ 
    int x = 0; 
    int y = 0; 
    uint h = 0;  
    foreach (var point p in polgon) 
    { 
     x = combine(x, p.X); 
     y = combine(y, p.Y); 
     h++; 
    } 
    // simplified, unrolled Murmur2 hash for end stage 
    const uint m = 0x5bd1e995; 
    const int r = 24; 
    uint h = count; 
    uint k = ReinterpretInt32ToUInt32(x); 
    k *= m; 
    k ^= k >> r; 
    k *= m; 
    h *= m; 
    h ^= k; 
    k = ReinterpretInt32ToUInt32(y); 
    k *= m; 
    k ^= k >> r; 
    k *= m; 
    h *= m; 
    h ^= k; 
    // avalanche 
    h ^= h >> 13; 
    h *= m; 
    h ^= h >> 15; 
    return ReinterpretUInt32ToInt32(h); 
} 

Basándose en esto para hacer que el código anterior fácil

public unsafe uint ReinterpretInt32ToUInt32(int i) 
{ 
    return *((uint*) (void*) &i); 
} 

public unsafe int ReinterpretUInt32ToInt32(uint u) 
{ 
    return *((int*) (void*) &u); 
} 

Este no será el mejor hash en términos de prevención de colisiones, pero debe ser muy rápido de calcular y puede que sea suficiente para sus necesidades.