Distance entre 2 points en évitant des obstac
sulletf
Messages postés
7
Date d'inscription
Statut
Membre
Dernière intervention
-
sulletf Messages postés 7 Date d'inscription Statut Membre Dernière intervention -
sulletf Messages postés 7 Date d'inscription Statut Membre Dernière intervention -
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 !
A voir également:
- Distance entre 2 points en évitant des obstac
- Supercopier 2 - Télécharger - Gestion de fichiers
- Mettre des points sur une carte - Guide
- Allumer pc à distance - Guide
- Comment insérer des points de suite sur word - Guide
- 2 ecran pc - Guide
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
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
En effet je dois appliquer ça à une interface graphique donc on peut en effet considérer chaque pixel adjacent comme un élément du graphe de dijkstra.
Par contre il faudrait limiter le nombre de pixels à considérer comme adjacents, performances obligent...