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.

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

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