Quelle est la meilleure façon de calculer une hashcode pour un ensemble de points?

Question

Je cherche la meilleure façon de calculer une hashcode pour un ensemble de points bidimensionnels (pour que je puisse stocker des polygones dans un Hashtable).

Il y a des façons évidentes de le faire, comme concaténer tous les points de coordonnées dans une chaîne et son hashcode, mais ce serait très lent.

À l'autre extrémité du spectre de vitesse / collision, je peux aussi, par exemple résumer toutes les coordonnées, ce qui se traduirait par un code très rapide, mais créerait aussi un grand nombre de collisions.

Quelle est la meilleure façon de calculer une hashcode pour un ensemble de points ?

est la solution optimale différente si les coordonnées sont des nombres entiers (vs coordonnées réelles)?

Edit: J'utilise donc le .net hashcode doit être long 32 bits

.

Answer 1

Il n'y a pas de façon optimale pour ce travail. Tout dépend de la taille de hachage peut vous permettre. Vous devez faire tradoffs entre la vitesse et la diffusion. Gardez à l'esprit qu'il n'y a pas une telle chose comme solution (si vous ne savez pas exactement ce que vous allez hash) Dans certains cas, XOR peut être assez bon.

Prenons par exemple le code

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

Vous avez dit que les points agregating ensemble est de ralentir. Si vous fixez le code supérieur, il ne passe pas besoin de tout type de trought juste agregation (pas très différent que les sommes) Et si vous utilisez integeres et flotteurs vous probablement fixer des changements (<< et >> sont des opérations de changement qui fonctionne ensemble comme bitwise rotation) pour adapter le type de données.

Vérifiez les autres fonctions de hachage ici: http://www.partow.net/programming/hashfunctions/

Answer 2

Optimal dépend de vos besoins du calcul de hachage.

Performance viendra au prix de plus de collisions de hachage.

Avez-vous un disque lié sur l'un? Il va se réduire à une analyse mathématique de combien chaque pour cent des collisions de hachage va vous coûter cher en termes de performance.

Answer 3

Si votre ensemble de données est par hasard l'un des polygones qui peuvent avoir des bords communs, mais ne se chevauchent pas autrement, il vous suffit de hachage sur trois points dans chaque polygone pour éviter les collisions.

Edit: Reconsidérer cela, imaginer toute collision avec des limites concaves / convexes, il est tout aussi bien vos polygones se chevauchent. - Sigh

Hélas: Lorsque le convexe et concave la rencontre, il me fait toujours des ennuis. :-P

Answer 4

Consultez ce document

Lamdan et Wolfson. hash géométrique: Un système de reconnaissance basé sur un modèle général et efficace. Vision par ordinateur. (1988)

Answer 5

Vous pouvez simplement XOR les hash des points individuels.

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

En fonction de ce que les valeurs vont être de toute façon. Probablement pourrait simplement les ajouter.

Answer 6

Si vous voulez des polygones qui sont définis droite et à gauche, mais égales par ailleurs, être égaux, alors vous devrez créer une fonction canonicalisation. Une fonction qui a donné polygones points de départ d'un point quelconque et dans un ordre quelconque renverra les points dans l'ordre égal.

Un algorithme que je peux penser est de trouver le minimum de toutes les séquences possibles de points:

1. Trouvez l'ensemble des points haut (points avec plus à gauche minimum x des points avec y minimum), ce sont les points de départ.
2. Pour chaque point de départ et chaque direction, itérativement ajouter des points connectés dans la direction donnée et d'éliminer tout ce qui ne sont pas top dans l'itération extrême gauche actuelle. L'arrêt quand un seul point de départ, la paire de direction est vers la gauche ou lors des itérations n-1 sont terminées. Si plus d'un point de départ et la direction est restante, choisir tout -. Ils sont tous isomorphes
3. Réorganiser les points de départ du point trouvé dans la direction trouvée.

est O (n ^ 2) cas le plus défavorable pour les polygones complètement dégénérés, mais si vos polygones ne sont pas des points qui se chevauchent, c'est O (n), avec un facteur constant assez faible.

Avec l'ordre canonisé, vous pouvez facilement comparer deux polygones pour l'égalité, juste itérativement comparer les points pour l'égalité. calcul de Hashcode est également trivial, utiliser toute méthode de combinaison de hachage raisonnablement robustes. Par exemple:

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

Answer 7

Pour un hachage très rapide (pour le calcul) avec les propriétés désirées sur droite / indépendance dans le sens horaire vous ne voudriez pas dépendre de la recherche d'un ordre bien défini des points.

Cela limite votre hachage combinant les opérations à ceux qui commutent. Par conséquent, nous voulons garder tout et toutes les données qui est indépendante de l'orientation séparée au cours des opérations de combinaison.

Voici une solution simple:

En supposant une fonction de combinaison int -> int -> int qui est associative une des conditions suivantes vont faire pour commencer:

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

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

Ensuite, nous pouvons faire ce qui suit:

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

En se fondant sur ce pour rendre le code ci-dessus facile

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

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

Ce ne sera pas le meilleur hachage en termes d'évitement de collision, mais devrait être très rapide pour calculer et vous pouvez le trouver suffisant pour vos besoins.