Bonjour,
Je ne sais pas si j'ai bien compris.
Tu as un fichier contenant:
- Un point de départ.
- Un point d'arrivé.
- Un liste de point "obstacle".
Utilisant Dijkstra, j'imagine que tu cherche le chemin à coût minimum. Donc tu crées une liste de sommet, disons les points médians de chaque obstacle, donc tu connais les coordonnés des sommets. Comme tu utilise des droites, pour relier chaque sommet j'imagine que tu peux calculer l'équation de chacune d'entre elle ?
1 2 3
| a x_1 + b = y_1
a x_2 + b = y_2
... |
A chaque fois que crées une de ces droites tu peux regarder parmi tout tes obstacles si un se trouve sur ta droite?
a x_n + b - Y_n =0?creer:ne_pas_creer ∀ n
∈ Obstacle
Forcement y a le cas où les obstacles ne sont pas seulement des points, A ce moment la, le plus simple est peut être d'utiliser un "hyper-volume" englobant, genre une "hyper-sphère", un cercle en 2D.
Dans ce cas un truc cool c'est l'espace de Hough:
1 2 3 4
| x_cercle_m = x_n + r cos(theta_m)
y_cercle_m = y_n + r sin(theta_m)
avec theta_m ∈ [0, 2pi] et (x_n, y_n) ∈ Obstacle |
Pour chaque point "obstacle, tu as la liste des points qui appartiennent au cercle de centre l'obstacle, et de rayon r (distance max entre le centre et la périphérie de l'obstacle ?) ".
Pour chacun des points de chacune des listes tu peux tester l’appartenance à la droite courante et choisir si elle peut être créée ou non.
Je ne suis pas un expert en évitement d'obstacle, et il doit y avoir des méthodes/raffinement/choix d'hyper-volume englobant plus intelligent moins coûteux ... Dans ce cas il faut peut être se tourner vers la communauté du jeux vidéo.
PS: si on prend l'equation d'une droite comme D:ax + by +c = 0, soit ses coordonnés l=(a, b, c), et P, un point de coordonné homogène x=(x_1, x_2, 1), alors le point P appartient à la droite D ssi
transpose(l).x = 0; avec '.' le produit "matriciel".
EDIT: En restant en coordonné homogène une droite D, de coordonné l=(a,b,c), se trouve simplement par le produit vectoriel de deux point:
x_pt1 v x_pt2 = l, avec 'v' le produit vectoriel
Partager