Discussion :

[r0d]

Bonjour à tous,

ben voilà, je suis en train d'halluciner sur la complexité de cet algo. Je pensais que ça me prendrais 2mn, mais là j'y suis dessus depuis ce matin et je n'en reviens pas comme c'est compliqué. Le truc, c'est que j'en ai trouvé un qui fonctionne, mais c'est affreux (tellement affreux que je n'ose pas le poster ).

Alors voilà. J'ai une grille hexagonale comme cela:

les petits chiffres correspondent aux coordonnées de chaque case. Je ne les ai pas toutes écrites, mais suffisamment pour comprendre le principe.

Donc voilà, je cherche un algo qui prend 2 cases (qui connais donc les coordonnées i et j de chacune d'entre elles), et qui me renvoie la distance entre ces deux cases.

Par exemple:
-> entre (0,0) et (2,0), la distance est 2
-> entre (3,0) et (0,0), la distance est 3
-> entre (3,1) et (0,0), la distance est 3
etc...

je vous aurais prévenu, c'est nettement plus difficile qu'il n'y parait

[souviron34]

un bel arrondi sur une distance directe marchera, non ??

(d'ailleurs, d'après ton schéma, je mettrais plutôt les distances à 1,2,2)

[r0d]

un bel arrondi sur une distance directe marchera, non ??

Le truc c'est que je ne connais pas les dimensions des cases. Je ne connais vraiment que leurs coordonnées.

(d'ailleurs, d'après ton schéma, je mettrais plutôt les distances à 1,2,2)

Ben non c'est bien ça: pour aller de la case (0,0) à la case (2,0), je dois "sauter" 2 fois de case. Mais bon, ça reviens au même, c'est juste la façon de compter (il suffit d'ajouter/soustraire 1 pour passer de l'une à l'autre).

[souviron34]

(0,0) (2,0) : sqrt( (2-0)*(2-0) + (0-0)*(0-0) ) = 2
(0,0) (3,0) : sqrt( (3-0)*(3-0) + (0-0)*(0-0) ) = 3
(0,0) (3,1) : sqrt( (3-0)*(3-0) + (1-0)*(1-0) ) = sqrt(10) = 3.16..

donc dist = (int)(0.5+sqrt())




(0,0) (3,2) : sqrt( (3-0)*(3-0) + (2-0)*(2-0) ) = sqrt(13) = 3.6
(int)(3.6+0.5) = 4

[Zavonen]

Il y aurait bien une définition récursive:
1) Définir pour toute case C l'ensemble V(C) de ses 'voisins' immédiats. Ça c'est pas trop dur.
Ensuite dire:
Si C1 et C2 sont deux cases:
Si C1=C2 alors d(C1,C2)=0
Si C2 appartient à V(C1) alors d(C1,C2)=1
Sinon
d(C1,C2)=Inf(X dans V(C1),d(X,C2))+1
Mais pour éviter de partir dans toutes les directions on se limite la recherche à un rectangle englobant C1 et C2.

[r0d]

Il y aurait bien une définition récursive:
1) Définir pour toute case C l'ensemble V(C) de ses 'voisins' immédiats. Ça c'est pas trop dur.
Ensuite dire:
Si C1 et C2 sont deux cases:
Si C1=C2 alors d(C1,C2)=0
Si C2 appartient à V(C1) alors d(C1,C2)=1
Sinon
d(C1,C2)=Inf(X dans V(C1),d(X,C2))+1
Mais pour éviter de partir dans toutes les directions on limite la recherche à un rectangle englobant C1 et C2.

Effectivement j'avais pensé à un algo récursif (bien que différent du tiens), mais pour des raisons de rapidité d'exécution, j'aurais aimé trouver un calcul direct. J'ai vraiment besoin que cet algo soit super rapide, car il fait partie d'un autre algo et sera donc appelé beaucoup beacoup de fois.

L'algo auquel j'avais pensé consiste à calculer, à chaque itération, la direction de la case à atteindre, et d'aller dans cette direction jusqu'à ce qu'on l'atteigne.

[r0d]

dist = (int)(0.5+sqrt())

Je ne saurais pas te dire pourquoi, mais ça ne marche pas à tous les coups.
Par exemple:
(5,4) -> (8,6), ça devrait donner 3
or (int) ( 0.5 + sqrt( (8-5 )*(8-5) + (6-4)*(6-4) ) ) = 4

[souviron34]

Je ne saurais pas te dire pourquoi, mais ça ne marche pas à tous les coups.
Par exemple:
(5,4) -> (8,6), ça devrait donner 3
or (int) ( 0.5 + sqrt( (8-5 )*(8-5) + (6-4)*(6-4) ) ) = 4

Mais au fond, vu tes problèmes, et que tes hexagones ne sont pas réguliers, cela veut dire que ta grille a des trous...

Cela voudrait donc dire qu'il faudrait que tu superposes à ta grille irrégulière une grille régulière, et que tu interpoles à partir de là (comme on fait quand on veut tourner une image : on part du pixel résultat, pour calculer là ou on tombe en rotation inverse, sinon ça provoque du moiré).