Algorithme chemin le plus court 3D

Q7frkz · Le 26/05/2021, à 13:43

Salut à vous !
Besoin d'aide pour des maths ou plutôt réfléchir à un algorithme.

J'ai un drone géré par un pc, aujourd'hui j'arrive à lui faire suivre un ensemble de points sur une sphère.
Quand il a fini, il reprend tous les points un par un dans le sens inverse et revient à son point de départ.

J'aimerais trouver le chemin le plus court en passant par les points déjà définis pour ramener le drone au début sans passer au milieu de la sphère naturellement, en admettant que je tourne autour d'un ballon de foot, je ne veux pas lui rentrer dedans en repartant.

Vous auriez des idées relativement faciles à coder ?

(à l'école j'avais eu l'occasion de regarder Dijkstra et A_star, mais en 3D ?)

Merci à vous !!

Nasman · Le 26/05/2021, à 14:05

A la surface d'une sphère ton drone se déplacera sur un grand cercle de rayon de la sphère et passant par le point actuel et par le point d'arrivée. Tu auras deux trajets possibles dont l'un sera le plus long (déplacement angulaire de plus de 180°) et un trajet le plus court d'angle inférieur à 180°.
Pour des questions de commodité il est préférable que les coordonnées soient exprimées en coordonnées sphériques (le rayon étant fixé).

Q7frkz · Le 26/05/2021, à 14:43

Nasman a écrit :

A la surface d'une sphère ton drone se déplacera sur un grand cercle de rayon de la sphère et passant par le point actuel et par le point d'arrivée. Tu auras deux trajets possibles dont l'un sera le plus long (déplacement angulaire de plus de 180°) et un trajet le plus court d'angle inférieur à 180°.
Pour des questions de commodité il est préférable que les coordonnées soient exprimées en coordonnées sphériques (le rayon étant fixé).

ah ben oui, j'ai deux points j'ai le rayon, ça ne me semble pas trop compliqué.
lol je me sens bête
merci !

Nasman · Le 26/05/2021, à 14:48

Précision : le grand cercle a pour centre le centre de la sphère.

serged · Le 26/05/2021, à 15:13

C'est le problème du voyageur de commerce, qui malgré la simplicité de son énoncé m'a pas de solution générale... Suis le lien Wikipédia que j'ai mis, peut-être trouveras-tu ton bonheur...

Ubuntu-fr

Navigation

Liens de recherche

Annonce

#1 Le 26/05/2021, à 13:43

Algorithme chemin le plus court 3D

#2 Le 26/05/2021, à 14:05

Re : Algorithme chemin le plus court 3D

#3 Le 26/05/2021, à 14:43

Re : Algorithme chemin le plus court 3D

#4 Le 26/05/2021, à 14:48

Re : Algorithme chemin le plus court 3D

#5 Le 26/05/2021, à 15:13

Re : Algorithme chemin le plus court 3D

Pied de page des forums