Contenu | Rechercher | Menus

Annonce

Si vous avez des soucis pour rester connecté, déconnectez-vous puis reconnectez-vous depuis ce lien en cochant la case
Me connecter automatiquement lors de mes prochaines visites.

À propos de l'équipe du forum.

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

Q7frkz

Algorithme chemin le plus court 3D

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 !!

Hors ligne

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

Nasman

Re : Algorithme chemin le plus court 3D

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


PC fixe sous Bionic 64 bits et portable avec Focal 64 bits

Hors ligne

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

Q7frkz

Re : Algorithme chemin le plus court 3D

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 smile
merci !

Hors ligne

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

Nasman

Re : Algorithme chemin le plus court 3D

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


PC fixe sous Bionic 64 bits et portable avec Focal 64 bits

Hors ligne

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

serged

Re : Algorithme chemin le plus court 3D

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


LinuxMint Vera Cinnamon et d'autres machines en MATE, XFCE... 20.x , 21.x ou 19.x
Tour : Asus F2A55 / AMD A8-5600K APU 3,6GHz / RAM 16Go / Nvidia GeForce GT610 / LM21.1 Cinnamon
Portable : LDLC Mercure MH : Celeron N3450 /RAM 4Go / Intel HD graphics 500 i915 / biboot Win 10 (sur SSD) - LM21.1 MATE (sur HDD)

Hors ligne