Discussion :

[ToTo13]

Bonsoir,

je travaille dans un espace discret (des images, tout le monde s'en doute) et j'utilise des distances et voisinages entre les points.

Tout ce passe bien sur une discrétisation classique (maillage carré) où je sais définir la distance d4 (City bloc ou Manhathan) et d8 (Diamond) ainsi que les notions de voisinage associées N4 et N8 ( Ni(x) = {y dans Z^2 / di(x,y) <= 1} ).
Je m'en sors aussi en 3D.

Mais comment peut on définir tout cela sur un maillage hexagonal ? Donc comment définir la distance D6 dans Z^2 et D14 dans Z^3.
Est ce que quelqu'un connaîtrait le problème, sinon un bon cours sur le sujet, voire des articles.
Sur le net, c'est pas les notions les mieux expliquée :s

Merci par avance...

[Zavonen]

Mais comment peut on définir tout cela sur un maillage hexagona

Ce que tu veux c'est une formule, bien entendu, parce que définir on peut toujours.

[pseudocode]

@ToTo13 : tu devrais poser la question sur le forum jeux 2D car le maillage hexagonal - aka hexmap - y est beaucoup utilisé.

De mémoire la distance (6-connexe) est un truc du genre: (|dx|+|dy|+|dx-dy|)/2

Edit: correction dans ma formule de distance. A confirmer quand même.

[ToTo13]

Bonjour,

alors, après quelques recherches et réponses, voilà ce que j'ai trouvé :

Pour la distance 2D hexagonale, la formule souvent utilisée est donnée ici :

Code C :

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

1
2
3
4
5
 
dx = B.x - A.x;
dy = B.y - A.y;
if ( sign(dx) == sign(dy) ) dist = max(abs(dx),abs(dy)) ;
else dist = abs(dx) + abs(dy) ;

Mais dans un livre référence en géométrie discrète de Montanvert, on trouve celles-ci (version Latex car formule assez longue), les crochets désignant la partie entière :
En version normale mais moche :
- Distance hexagonale => dh(x,y) = max(|x1-y1|, 1/2 (|x1-y1|+(x1-y1))-([x1/2]-[y1/2])+ y2-x2, 1/2 (|x1-y1|+(x1-y1))-([x1/2]-[y1/2])+ x2-y2 )
- Distance Octogonale => do(x,y) = max ( d8(x,y), [ 2/3 ( |x1-y1| + |x2-y2| + 1)] )
Version Latex :
- Distance hexagonale => $$
\begin{array}{r}
d_{h}(x,y) = \max( |x_{1}-y_{1}|, \frac{1}{2} (|x_{1}-y_{1}|+(x_{1}-y_{1}))-([\frac{x_{1}}{2}]-[\frac{y_{1}}{2}])+ y_{2}-x_{2}, \\
\frac{1}{2} (|x_{1}-y_{1}|+(x_{1}-y_{1}))-([\frac{x_{1}}{2}]-[\frac{y_{1}}{2}])+ x_{2}-y_{2} )
\end{array}
\; , \; \mathrm{Hexagonale}
$$
- Distance Octogonale => $$ d_{o}(x,y) = \max \left( d_{8}(x,y), \left[ \frac{2}{3} \left( |x_{1}-y_{1}| + |x_{2}-y_{2}| + 1 \right) \right] \right) \; , \; \mathrm{Octogonale} $$


En revanche, je n'ai rien trouvé sur la distance 3D D14