Discussion :

[Rumpel]

Bonjour à tous,

Je cherche un algorithme de plus court chemin sur une Géode.
Alors l'algorithme, je pense que Dijkstra fera parfaitement l'affaire.
Mais le problème c'est de trouver dans l'espace quel hexagone est voisin de quel hexagone ( ou pentagone )



Alors je pense pouvoir le faire, mais c'est pas trivial du tout, je n'ai pas trouvé d'articles sur le sujet.
( ChatGPT me conseille d'aller voir les bibliothèques CGAL, Gmsh, ou les travaux de Jeff Eriskson, mais là aussi, je ne trouve rien de concret ... )
Rien trouvé sur Google après moult recherches ...
Alors ce n'est pas une distance géodésique que je recherche, si je passe d'un hexagone à un autre, ça fait juste 1.
Certains hexagones pouvant déjà être occupés ...

[Flodelarab]

Bonjour

N'est-on pas typiquement dans le contexte pour un algorithme A* ( "a étoile") ? Tu cherches le plus court chemin avec une pré-science du chemin le plus court. En effet, sur une sphère, le plus court chemin est l'intersection d'un plan englobant ton point de départ, ton point d'arrivée et le centre de la sphère, avec la sphère elle-même. Y a plus qu'à.

[tbc92]

Tu as une liste d'hexagones ou de pentagones.
Je pense que tout le problème réside dans la façon dont tes polygones sont définis.
J'imagine que tu n'as pas tout simplement une liste de n° avec l'information : tel n° est un hexagone ou bien un pentagone. Tu as un emplacement, sous une forme ou une autre..
Et à partir de cet emplacement, à toi de retrouver les voisins.

[Rumpel]

Hello, oui c'est ça, l'algorithme en lui même ne me pose pas de problème. Ce que je voudrais c'est un système de coordonnées pour pouvoir trouver les voisins simplement.
Par exemple, pour une grille hexagonale en 2 dimension, il suffit de prendre un repère qui n'est pas orthonormé



et ça simplifie tout.
En 3D je cherche un système pour exprimer chaque coordonnées ( x,y,z ) d'hexagone ou de pentagone de façon à ce que x, y et z soient des entiers ...

Alors est ce que ça existe déjà où je dois trouver une solution moi même ?

[Mat.M]

Je cherche un algorithme de plus court chemin sur une Géode.

1-est-ce qu'il y a des obstacles sur votre système de coordonnées ?
2-la première chose à faire c'est de définir une origine si vous voulez mesurer des distances, non ?
Donc sur votre géode où se situe l'origine ?

Hello, oui c'est ça, l'algorithme en lui même ne me pose pas de problème. Ce que je voudrais c'est un système de coordonnées pour pouvoir trouver les voisins simplement.

est-ce que vous avez cherché dans les relations du cercle trigonométrique,du triangle rectangle ?

Si vous voulez faire un système de coordonnées les coordonnées x,y selon un angle et un vecteur/mesure par rapport au centre de la géode donnés vous avez les positions des points.
Après pour ajouter une troisième dimension il faut passer par des mesures de cercles concentriques ou non.

[Rumpel]

la première chose à faire c'est de définir une origine si vous voulez mesurer des distances, non ?
Donc sur votre géode où se situe l'origine ?

Ben, peu importe l'origine, c'est comme sur une grille carré 2D, je peux prendre l'origine soit au centre, soit dans le coin en bas à gauche ( pour éviter les coordonnées négatives ) mais ça ne va pas changer beaucoup ...
Là pour la géode, je pense prendre comme origine le milieu de l'un des 12 pentagones, ça me semble être le plus simple ...

est-ce que vous avez cherché dans les relations du cercle trigonométrique,du triangle rectangle ?

Si vous voulez faire un système de coordonnées les coordonnées x,y selon un angle et un vecteur donnés vous avez les positions des points.
Après pour ajouter une troisième dimension il faut passer par des mesures de cercles concentriques ou non.

Alors il y a plusieurs choses, pour l'instant, je suis à l'étape où je cherche les voisins dans un repère non cartésien. Après bien entendu, il va y avoir une autre étape ou je devrais chercher la correspondance des coordonnées dans le repère cartésien.
Mais chaque chose en son temps. Par exemple sur une grille hexagonale 2D, l'hexagone de coordonnées X=1 et Y=3 va avoir des coordonnées cartésiennes qu'il faudra trouver avec des relations trigonométriques.

J'avais codé quelque chose en Scratch. ( en 2D j'y arrive )
Là par exemple il y a une fonction qui calcule les coordonnées cartésiennes (x,y) en fonction des coordonnées non cartésiennes entières.
Pas facile en 3D, mais je pense que j'y arriverais ...
Là pour l'instant je suis juste sur la problématique des voisins ...

( Je précise que je suis Docteur en Mathématiques, j'ai cherché sur Google et j'ai essayé toutes les solutions triviales, le problème n'est pas si simple que ça ... )

[Mat.M]

Ben, peu importe l'origine, c'est comme sur une grille carré 2D, je peux prendre l'origine soit au centre

eeehh si le système de coordonnées il de dimension géodésique le centre et l'origine c'est bien celui de la géode non ?
Si vous prenez une API 3d comme Direct X il faut toujours définir une origine mais ça c'est un autre sujet certes
Après si vous obtenez un ensemble de points oui on peut prendre l'algorithme de recherche en A.
Après si vous obtenez une carte avec des hexagones l'algorithme pour passer d'un hexagone vers un autre c'est un sujet déjà abordé.
Mais si vous obtenez une carte à "plat" les coordonnées centrales de chaque hexagones seront différentes de celles d'un système géodésique.

[tbc92]

En cherchant 'maillage sphère pentagones hexagones', j'arrive à la page wikipedia géode ; visiblement tu connais cette page

On trouve d'autres pages qui peuvent être assez intéressantes, mais je ne vois pas de solution toute faite.

Une géode, c'est en fait 20 triangles, chaque triangle est ensuite découpé en k hexagones.
Actuellement, tu sais codifier k hexagones dans un plan.
Tu peux donc avoir un système de codification avec 3 dimensions (t,x,y)
t est le numéro de triangle, entre 1 et 20 forcément. Et x et y sont entre 1 et a ... a étant variable, selon la taille du maillage que tu as choisi.
Chaque zone délimitée par les hexagones jaunes (exclus) est assimilable à un plan.
Reste à gérer les hexagones que tu as dessinés en jaune, ceux qui sont à la frontière entre 2 triangles. A priori, il faut utiliser 3 systèmes de codification, correspondant aux 3 couleurs de l'image. Tenter de coder tous les hexagones de la même façon, ça risque de bien compliquer la chose, déjà assez compliquée.
Tu as un icosaèdre avec les sommets en rouge, les arêtes en jaune, et les faces en bleu.

[Flodelarab]

Je précise que je suis Docteur en Mathématiques

Ah ! Bon à savoir.

A priori, pas de solution. On prend un pentagone comme origine. Puis la distance à l'origine comme première coordonnée. Et enfin la distance à l'axe "des abscisses" en seconde coordonnée.

Si on prend l'image du premier message, on obtient une origine de coordonnées (0,0), ses voisins (1,0) (1,1) (1,2) (1,3) (1,4), les voisins de (1,4) sont (1,0) (0,0) (1,3) (2,7) (2,8) (2,9), les pentagones suivants sont de coordonnées (10,0) (10,10) (10,20) (10,30) (10,40), etc...

Ou alors, on peut compter de 2 en 2. Car les coordonnées après la première ligne de 5 pentagones se décale. Donc on comptera 1 (si on va de 2 en 2). Cela évitera les 0.5. Les coordonnées jusqu'ici toutes paires (0 2 4 6...) deviendront impaires (1 3 5 7 ...). Le premier point sera donc (11,1) voisin de (10,0) (10,2) (11,3) etc. Attention, ne pas confondre avec les coordonnées du paragraphe précédent pour lesquelles on avançait de 1 en 1.

On peut aussi tricher et faire comme si il n'y avait pas de décalage. Mais quand on va vouloir mélanger avec la géométrie 3D, on ne retrouvera pas nos petits.

[Rumpel]

En cherchant 'maillage sphère pentagones hexagones', j'arrive à la page wikipedia géode ; visiblement tu connais cette page

Oui je connais

Une géode, c'est en fait 20 triangles, chaque triangle est ensuite découpé en k hexagones.
Actuellement, tu sais codifier k hexagones dans un plan.
Tu peux donc avoir un système de codification avec 3 dimensions (t,x,y)

Alors il y a une ou deux étapes de plus pour construire une Géode, chacun des 20 triangles d'origine est subdivisé en petits triangles. On obtient une géode avec plein de petits triangles, ensuite on prend le dual de la géode obtenue par triangulation ( on relie les centres de gravité des petits triangles ) pour obtenir une géode avec des pentagones et des hexagones.
Donc oui, en fait actuellement j'ai 2 solutions en tête, l'une est effectivement d'avoir des coordonnées ( non cartésiennes ) de type (t,x,y)
Mais si on reprend la figure de mon premier message, pour trouver les voisins d'un hexagone " bleu ", c'est relativement facile, je reste dans le même grand triangle d'origine. Mais ensuite pour les hexagones "jaunes" c'est plus difficile, ils sont à la frontière de deux grands triangles ...

t est le numéro de triangle, entre 1 et 20 forcément. Et x et y sont entre 1 et a ... a étant variable, selon la taille du maillage que tu as choisi.
Chaque zone délimitée par les hexagones jaunes (exclus) est assimilable à un plan.
Reste à gérer les hexagones que tu as dessinés en jaune, ceux qui sont à la frontière entre 2 triangles. A priori, il faut utiliser 3 systèmes de codification, correspondant aux 3 couleurs de l'image. Tenter de coder tous les hexagones de la même façon, ça risque de bien compliquer la chose, déjà assez compliquée.

Oui, c'est ça, on arrive à la même conclusion
Bon, je crois que j'ai un truc qui tient à peu près la route, je vais essayer de creuser et programmer pour vérifier ...

[tbc92]

L'histoire du dual à partir de plein de (petits) triangles, ok, mais je ne passais pas par là.
Tes segments jaunes définissent des triangles , c'est de ces (grands) triangles là que je parlais. Donc 20 triangles.
Et ensuite, chaque triangle est découpé en un certain nombre d'hexagones.
Dans les faits, ces 20 triangles sont en quelque sorte des calottes sphériques, mais on peut les assimiler à 20 triangles plans.
La piste à laquelle on arrive paraît assez efficace
Reste peut-être un point à bien penser, pour que la gestion des frontières soit le moins problématique possible, c'est comment orienter les axes dans chacun de ces grands triangles.

Et dernier point, en première lecture, je n'étais pas convaincu par ta façon de coder les cases dans ce dessin ; quand j'ai eu l'occasion de faire des pavages hexagonaux (plans), je ne sais plus comment je faisais, mais je pense que c'était autrement. Mais ce n'est pas un critère, ton choix est peut-être meilleur.

[Rumpel]

Et ensuite, chaque triangle est découpé en un certain nombre d'hexagones.

C'est un peu plus compliqué que cela malheureusement, preuve en image, certains hexagones sont à la frontière de 2 grands triangles ...

[Flodelarab]

Hum. Et ma proposition ? Tu l'as pas vu ? Pas comprise ? Au moins, tu restes sur les nombres entiers.

[Rumpel]

Hum. Et ma proposition ? Tu l'as pas vu ? Pas comprise ? Au moins, tu restes sur les nombres entiers.

Oui, désolé, c'était pas top clair.
Est ce que tu n'aurais pas un petit schéma pour voir ?

[tbc92]

C'est un peu plus compliqué que cela malheureusement, preuve en image, certains hexagones sont à la frontière de 2 grands triangles ...

Oui, on est d'accord. Je recopie ce que je disais :

Reste à gérer les hexagones que tu as dessinés en jaune, ceux qui sont à la frontière entre 2 triangles. A priori, il faut utiliser 3 systèmes de codification, correspondant aux 3 couleurs de l'image. Tenter de coder tous les hexagones de la même façon, ça risque de bien compliquer la chose, déjà assez compliquée.

Le dessin initial, avec les 3 couleurs Rouge/Jaune/Bleu est parfait, il décrit parfaitement toute la structure.

[Flodelarab]

Ainsi, toutes les positions ont des coordonnées entières. Si je ne m'abuse, il y a un seul point (0;X) et un seul point (30;Y), donc (30,0), le pentagone opposé à l'origine.

La proposition de multiplication par deux de l'échelle circulaire, c'est pour gérer le décalage élégamment. À voir.

[tbc92]

Avec cette proposition, le point (3,14) a pour voisins les points (2,9),(2,10),(3,13),(3,15),(4,18) et (4,19) sauf erreur. On retrouve assez facilement ces 6 points.
Sauf que quand on s'éloigne du sommet origine, il y a un moment où ça se complique.
On retrouve facilement les 6 voisins de chaque point, mais certains points n'ont que 5 voisins. Donc ils génèrent des décalages.
Au final, 10 couronnes de plus en plus grandes (+ 5 hexagones à chaque fois)
Puis 10 couronnes qui ont toutes le même nombre d'hexagones. Pas de problème pour trouver les voisins sur cette portion 'équatoriale'.
Et enfin 10 couronnes de plus en plus petites.
Cette piste ne donne pas la solution en 3 clics, mais elle paraît quand même plus simple que l'autr

Edit : suite à la remarque de Flodelarab, en fait, je numérote le cercle n°k de 1 à 5*k, et pas de 0 à 5k-1, d'où ces décalages.

[Flodelarab]

J'explicite l'échelle double.



(10,0)
(10,2)
(10,4)
(11,1)
(12,0)
(13,1)
(14,0)

PS: je n'arrive pas à supprimer la pièce jointe inepte.

[Flodelarab]

(3,15)

Euh (3,14) est la dernière. (3,15) est (3,0). Dans cette partie, les points ont pour coordonnées (x,y[5x]). (Lire "y modulo cinq x")

[Rumpel]

Ainsi, toutes les positions ont des coordonnées entières. Si je ne m'abuse, il y a un seul point (0;X) et un seul point (30;Y), donc (30,0), le pentagone opposé à l'origine.

La proposition de multiplication par deux de l'échelle circulaire, c'est pour gérer le décalage élégamment. À voir.

Oui, c'est d'accord, mais n'oublie pas, le but n'est pas simplement de trouver une façon de coder les hexagones par un triplet de nombre entiers. Il faudra aussi trouver des fonctions pour passer de l'identifiant au triplet et du triplet aux coordonnées cartésiennes ... Déjà je pense qu'il faut savoir coder des déplacements sur une grille en 2D avant de passer au 3D ....