Distance entre 2 points en évitant des obstac Fermé

Question

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 !


Configuration: Windows XP / Internet Explorer 6.0

Reivax962 · Answer

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

Distance entre 2 points en évitant des obstac

1 réponse

Discussions similaires