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]

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

[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.

[Zavonen]

J'ai modifié ta citation, parce que j'ai corrigé entre-deux la formule de récurrence.

[Zavonen]

Si tu considères les centres de gravité de tes cellules, ils forment un réseau de pas horizontal 1.5 et de pas vertical racine(3)/2. On peut supposer que l'origine est toujours (0,0).
Le problème est donc de calculer la distance de (0,0) à (m*racine(3)/2,n) où m et n sont entiers l'unité de distance étant racine(3).
Je dirais donc racine((m*3/4+n²)/racine(3)

[r0d]

En fait je viens de capter un truc: mes hexagones ne sont pas forcément réguliers (6 côtés de même longueur). En fait, il ne le sont jamais, et pis, les dimensions changent (selon plein de paramètres) et leurs proportions aussi. Donc les pas ne seront jamais identiques, non?

[FR119492]

Salut!

les petits chiffres correspondent aux coordonnées de chaque case

Premièrement, la notion de coordonnées d'une surface, en l'occurrence un hexagone, n'a pas de sens; ne s'agit-il pas plutôt des coordonnées des centres de gravité.
Secondement, tu donnes tes coordonnées sous la forme de paires de nombres entiers, alors que, si tes hexagones sont réguliers, le décalage horizontal entre deux cases voisines est de 1,5 et le décalage vertical de sqrt(3), en prenant la longueur d'un côté comme unité de longueur.
Dans tous les cas, le théorème de Pythagore devrait suffire pour calculer la distance séparant deux centres de gravité.
Jean-Marc Blanc

[r0d]

Premièrement, la notion de coordonnées d'une surface, en l'occurrence un hexagone, n'a pas de sens; ne s'agit-il pas plutôt des coordonnées des centres de gravité.

Oui, le centre de gravité si tu veux. M'enfin, à la base je préférais considérer mon pavage comme une grille à deux dimensions, car je ne peux absolument pas utiliser les corrdonnées réelles car, comme je l'expliquais plus haut:
. je ne connais pas ces coordonnées (je reçois ma grille sous forme d'un tableau à 2 dimensions)
. les hexagones ne sont pas isocèles (leurs côtés ne sont pas égaux). Ils peuvent être "plats" ou "allongés verticalement". Et je ne connais pas leur forme réelle.

[Jean-Marc.Bourguet]

A premiere vue

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
p_1 = x_1, y_1
p_2 = x_2, y_2
 
d(p_1, p_2) = |x_1 - x_2| +
          si y_1-y_2 > (|x_1 - x_2|+1)/2 alors y_2-y_1 - (|x_1-x_2|+1)/2
          si y_2-y_1 > |x_1 - x_2|/2     alors y_1-y_2 - |x_1-x_2|/2
          sinon                                0

[pseudocode]

Tiens, une variante de la distance D6.

Personne n'a eu l'idée de faire une translation pour ramener l'une des 2 cases en (0,0) ?

Enfin, bon... c'est vous qui voyez.

[Zavonen]

Personne n'a eu l'idée de faire une translation pour ramener l'une des 2 cases en (0,0) ?

Si, moi .

[pseudocode]

Si, moi .

Heu... je parlais de faire une translation dans le repère de D6, histoire de pouvoir utiliser les formules connues pour le calcul de distance:

http://www.developpez.net/forums/d64...age-hexagonal/

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
// changement de repère R0d vers D6
int x0=R0d_x0, y0=R0d_y0+(R0d_x0+1)/2;
int x1=R0d_x1, y1=R0d_y1+(R0d_x1+1)/2;
 
// translation de (X1,Y1) par le vecteur (-X0,-Y0)
int dx = x1-x0;
int dy = y1-y0;
 
// distance a l'origine dans D6
int distance = (Math.abs(dx)+Math.abs(dy)+Math.abs(dx-dy))/2;

[FR119492]

Salut!

à 2 dimensions

Exprimées en quelle unité?
Jean-Marc Blanc

[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é).

[Gouyon]

J'ai eu le même problème et voici la solution que j'ai trouvée:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
function distance(xdep, ydep, xbut, ybut: integer): integer;
var
  d, dyplus, dymoins, dy, dx: integer;
begin
  dx := abs(xbut - xdep);
  dy := ybut - ydep;
  if dx = 0 then
    d := abs(dy)
  else
  begin
    if (xdep mod 2 <> 0) then
    begin
      dymoins := -(dx div 2);
      dyplus := (dx + 1) div 2;
    end
    else
    begin
      dymoins := -(dx + 1) div 2;
      dyplus := dx div 2;
    end;
    d := dx;
    if (dy > dyplus) then
      d := d + dy - dyplus;
    if (dy < dymoins) then
      d := d + dymoins - dy;
  end;
  Result := d;
end;

La distance est donnée en nombre d'hexagone.
Après si on la veut en une autre unité (en pixels écran par exemple) il suffit de calculer les coordonnée du centre de l'hexagone de départ et d'arrivé et utiliser la bonne vielle formule du calcule de la distance entre 2 points