Calcul de voisinage - table de hachage spatiale

Bonjour,

J'ai un ensemble de points 3D et pour chaque point j'aimerai construire sa liste de points voisins. Pour ce faire j'utilise une table de hachage spatial, avec une fonction de hachage qui me renvoie un index 1D (je lui passe la position 3D en paramètre). J'utilise ceci pour la construction de ma table.

J'implante en fait la méthode décrite sur ces papiers :
http://image.diku.dk/projects/media/kelager.06.pdf
http://matthias-mueller-fischer.ch/p...rCollision.pdf

Mon problème se situe au niveau de la récupération des voisins : ils disent qu'il faut construire la bounding box de taille h (je connais le h), qui consiste en un point min et un point max (pas de problème jusque là). Et ils disent ensuite qu'il faut itérer sur chaque position discrète à l'intérieur de la boîte. Ainsi si on fait

Code:

---

1 2	liste_resultante = ma_hash_table[hash_function(position_discrète_courante)];

---

Alors on récupère soit une liste vide, soit une liste de voisines (une particule, ou plusieurs si il y a eu collision dans le hachage, ce qui reste peu probable vu ma fonction et la taille de mon map). Le problème est :

Quel pas dois-je utiliser pour intégrer mon parcours de boîte englobante, de telle manière que je retrouve les voisins ? 1/10è ? 1/100è ? etc. Donc en quelque sorte, quel Delta je peux me permettre de manière à ce que ma fonction de hachage retrouve quand même mes voisins ?

Sachant que plus ce pas va être petit, plus mes performances seront mauvaises. Et ce pas n'est aucunement précisé dans les papiers ...

Merci d'avance !

Muska17