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.
Eventuali restrizioni su come i poligoni possono sovrapporsi nello spazio? – Anon
Anon: possono sovrapporsi; ma mi fai incuriosire: che differenza farebbe? – Brann
Ho pubblicato la mia risposta a riguardo prima di vedere il vostro commento di risposta. Stavo chiedendo tramite commento dato che pensavo che probabilmente stavi permettendo le sovrapposizioni. – Anon