Je cherche le moyen optimal de calculer un hashcode pour un ensemble de points bi-dimensionnels (afin que je puisse stocker des polygones dans une haquetable).
Il existe des moyens évidents de le faire, tels que la concaténation de tous les points de coordonnées dans une chaîne et son hachemode, mais ce serait très lent.
À l'autre extrémité du spectre de vitesse / collision, je peux également résumer toutes les coordonnées, ce qui entraînerait un code très rapide, mais créerait également beaucoup de collisions.
Quel est le moyen optimal de calculer un hashcode pour un ensemble de points ?
est la solution optimale différente si les coordonnées sont entier (vs véritables coordonnées)?
EDIT: J'utilise .NET afin que le hashcode doit être de 32 bits de long.
7 Réponses :
optimal dépend de vos exigences du calcul de hachage.
performance viendra au coût des collisions de hachage plus.
Avez-vous une liaison difficile sur l'un ou l'autre? Cela va se passer d'une analyse mathématique de la manière dont chaque pourcentage de collisions de hachage vous coûtera en termes de performance.
Pas de limites dures. Maintenant que j'ai précisé que la taille de hachage est de 32 bits, "optimal" signifie quelque chose, non?
Il n'y a pas de manière optimale pour ce travail. Tout dépend de la taille de la haquee. Vous devez faire des marchandises entre la vitesse et la diffusion. Gardez à l'esprit qu'il n'y a pas de solution optimale (si vous ne savez pas exactement ce que vous allez à Hash) dans certains cas, XOR peut être suffisamment bon.
Prendre par exemple ce code P>
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 */
Si votre jeu de données est par hasard l'un des polygones pouvant avoir des bords communs, mais ne pas se chevaucher autrement, vous n'avez besoin que de hachage sur trois points dans chaque polygone pour éviter les collisions.
EDIT: Réexamener cela, photographier des collisions possibles avec des limites concave / convexe, il s'agit aussi bien de vos polygones se chevauchent. - soupir
Hélas: lorsque le convexe et la rencontre concave, cela me rend toujours en difficulté. :-P
Découvrez ce papier
Alternativement, vous pouvez simplement Xor les hachages des points individuels.
return p1.GetHashCode() ^ p2.GetHashCode()
Si vous voulez des polygones définis dans le sens des aiguilles d'une montre et dans le sens des aiguilles d'une montre, mais sinon égaux, pour être égaux, vous devrez créer une fonction de canonicalisation. Fonction qui compte tenu des points de polygones à partir de n'importe quel point et dans n'importe quel ordre retournera les points dans un ordre égal.
Un algorithme que je peux penser est de trouver le minimum de toutes les séquences possibles de points: < ol>
Ceci est le pire cas o (n ^ 2) pour des polygones entièrement dégénèrent, mais si vos polygones n'ont pas de points de chevauchement, ceci est O (n), avec un facteur constant assez petit.
avec l'ordre canonicalisé, vous pouvez facilement comparer deux polygones pour l'égalité, il suffit de comparer itérativement des points pour l'égalité. Le calcul de HashCode est également trivial, utilisez toute méthode de combinaison de hachage raisonnablement robuste. Par exemple:
pour un hachage très rapide (à calculer) avec les propriétés souhaitées sur l'indépendance des aiguilles d'une montre / dans le sens des aiguilles d'une montre, vous ne voudrez pas dépendre de la recherche d'un ordre bien défini des points.
Cela limite votre hachage combinant des opérations à des opérations qui font la navette. Par conséquent, nous souhaitons conserver toutes les données indépendantes de l'orientation séparées lors des opérations de combinaison. P>
Voici une solution simple: p>
supposant une fonction de combinaison INT -> INT -> int qui est associatif
L'un des éléments suivants fera pour commencer par: p> alors nous pouvons faire ce qui suit: p> comptez sur cette Pour rendre le code ci-dessus EASY P> public unsafe uint ReinterpretInt32ToUInt32(int i)
{
return *((uint*) (void*) &i);
}
public unsafe int ReinterpretUInt32ToInt32(uint u)
{
return *((int*) (void*) &u);
}
Peut-être que parce que vous identifiez que ce n'est pas le meilleur lors de l'évitement de collision et, en tant que tel, ne convient pas à l'utilisation d'une clé dans une haquetable? Compte tenu du coût des collisions sur les recherches, je pense que le questionneur voudrait comme disperser un hachage que possible
Des restrictions sur la façon dont vos polygones peuvent se chevaucher dans l'espace?
Anon: ils peuvent se chevaucher; Mais tu me fais curieux: quelle différence cela ferait-il?
Posté ma réponse à ce sujet avant de voir votre commentaire de réponse. Demandait par commentaire depuis que je pensais que vous permettais probablement de chevaucher.