Distance entre 2 points en évitant des obstac
sulletf
Messages postés
8
Statut
Membre
-
sulletf Messages postés 8 Statut Membre -
sulletf Messages postés 8 Statut Membre -
Bonjour,
voici mon problème :
prenez une feuille et dessinez-y des rectangles au hasard.
Choisissez 2 points quelconques sur la feuille ( en dehors des rectangles ).
Existe-t-il un algorithme permettant de déterminer le plus cours chemin en ces 2 points en utilisant des lignes droites verticales ou horizontales et sans toucher les rectangles ?
Je pensais à une extension de l'algorithme de Dijkstra ...
Merci !
voici mon problème :
prenez une feuille et dessinez-y des rectangles au hasard.
Choisissez 2 points quelconques sur la feuille ( en dehors des rectangles ).
Existe-t-il un algorithme permettant de déterminer le plus cours chemin en ces 2 points en utilisant des lignes droites verticales ou horizontales et sans toucher les rectangles ?
Je pensais à une extension de l'algorithme de Dijkstra ...
Merci !
1 réponse
-
Bonjour,
Question : est-ce que les rectangles et les lignes sont positionnés sur un quadrillage, ou non ? (Autre formulation : existe-t-il un référentiel cartésien dans lequel leurs coordonnées sont des valeurs entières)
Si oui, alors un Dijkstra simple te donne la solution, en mettant un coût à 1 sur le passage d'un point à un point adjacent, et en enlevant du maillage les points inclus dans un rectangle)
Sinon, alors je ne sais pas te répondre là comme ça, il faudrait que j'y réfléchisse, et j'ai pas le temps ^^'
Xavier
