Qual è il modo ottimale per calcolare un hashcode per un set di punti?

Question

Sto cercando il modo ottimale per calcolare un hashcode per un insieme di punti bidimensionali (in modo da poter memorizzare i poligoni in una tabella hash).

Ci sono alcuni modi ovvi per farlo, come concatenare tutte le coordinate dei punti in una stringa e il suo codice hash, ma questo sarebbe molto lento.

Dall'altra parte dello spettro velocità/collisione, posso anche riassumere tutte le coordinate, il che comporterebbe un codice molto veloce, ma creerebbe anche molte collisioni.

Qual è il modo ottimale per calcolare un hashcode per un set di punti?

La soluzione ottimale è diversa se le coordinate sono integer (vs coordinate reali)?

Modifica: sto usando .net in modo che l'hashcode sia lungo 32 bit.

Answer 1

Non esiste un modo ottimale per questo lavoro. Tutto dipende da quanto grande hash puoi permetterti. Devi fare i tradoff tra velocità e diffusione. Tieni presente che non esiste una soluzione ottimale (se non sai esattamente cosa hai intenzione di fare). In alcuni casi xor può essere abbastanza buono.

Prendete per esempio questo codice

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 */ 

Lei ha detto che agregating punti insieme è quello di rallentare. Se si corregge il codice superiore non è necessario alcun tipo di agregazione appena superato (non molto diverso da quello sommato) E se si utilizzano interi e float probabilmente si correggono i turni (< < e >> sono operazioni di spostamento che insieme funzionano come bit per bit rotazione) per adattarsi al tipo di dati.

Verificare la presenza di altre funzioni hash qui: http://www.partow.net/programming/hashfunctions/

Answer 2

Ottimale dipende dai requisiti del calcolo hash.

Le prestazioni arriveranno al costo di più collisioni di hash.

Avete uno stretto legame su uno dei due? Si tratterà di un'analisi matematica di quanto ogni percentuale di collisioni hash ti costerà in termini di prestazioni.

Answer 3

Se il set di dati è per caso uno dei poligoni che possono avere bordi comuni e non sovrapporsi in caso contrario, avete solo bisogno di hash su tre punti in ogni poligono di evitare collisioni.

Modifica: riconsiderando questo, immaginando possibili collisioni con confini concavi/convessi, è altrettanto bene che i poligoni si sovrappongono. - Sigh

Ahimè: quando il convesso e il concavo si incontrano, mi mettono sempre nei guai. :-P

Answer 4

Partenza questo documento

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

Answer 5

In alternativa, si può semplicemente XOR gli hash dei singoli punti.

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

A seconda dei valori che saranno comunque. Probabilmente potrebbe solo aggiungerli.

Answer 6

Se si desidera che i poligoni siano definiti in senso orario e antiorario, ma in caso contrario uguali, sarà necessario creare una funzione di canonicalizzazione. Una funzione che fornisce punti poligoni a partire da qualsiasi punto e in qualsiasi ordine restituirà i punti in ordine uguale.

Un algoritmo che mi viene in mente è quello di trovare il minimo di tutte le possibili sequenze di punti:

1. Trova l'insieme dei punti top-sinistra (punti con x minimo dei punti con un minimo y), questi sono i punti di partenza.
2. Per ciascun punto di partenza e ogni direzione, aggiungere in modo iterativo i punti collegati nella direzione specificata ed eliminare tutto ciò che non è in alto a sinistra nell'iterazione corrente. Arresta quando è rimasto un solo punto di partenza, coppia di direzione o quando sono completate le iterazioni n-1. Se rimangono più di un punto di partenza e una direzione, scegline uno: sono tutti isomorfi.
3. Riordina i punti a partire dal punto trovato nella direzione trovata.

Questo è O (n^2) il caso peggiore per i poligoni completamente degenerati, ma se i poligoni non hanno punti sovrapposti, questo è O (n), con un fattore costante piuttosto piccolo.

Con l'ordine canonico è possibile confrontare facilmente due poligoni per l'uguaglianza, solo in modo iterativo confrontare i punti per l'uguaglianza. Anche il calcolo del codice hash è banale, usa un metodo di combinazione hash ragionevolmente robusto. Per esempio:

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

Answer 7

Per una molto veloce (per il calcolo) hash con le proprietà desiderate in senso orario/antiorario indipendenza che non vorresti essere dipendente da trovare un ordinamento ben definita dei punti.

Ciò limita le operazioni di combinazione hash a quelle che si spostano. Pertanto desideriamo mantenere separati tutti i dati che sono indipendenti dall'orientamento durante le operazioni di combinazione.

Ecco una soluzione semplice:

Assumendo una mietitrebbia funzione int -> int -> int che è associativa una delle seguenti farà iniziare con:

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

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

Allora possiamo fare la seguente:

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); 
} 

Basandosi su questo per rendere il codice di cui sopra facile

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

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

Questo non sarà l'hash migliore in termini di collisione, ma dovrebbe essere molto veloce da calcolare e potrebbe essere sufficiente per le vostre esigenze.