Comment déterminer si une droite rencontre un obstacle

Bonjour tout le monde.

Avec mon groupe de projet, nous sommes en train d'implémenter l'algo de Dijkstra. On nous donnera un fichier qui définira la scène, avec un point de départ, point d'arrivée et les obstacles.
Avec la scène nous allons générer une liste d'adjacence, qui représentera notre graphe.
Donc première chose que nous faisons, c'est de déterminer les points de passage (noeuds) de notre scène.
A partir de là, nous allons essayer de créer toutes les arêtes possibles. Mais nous ne savons pas comment nous pourrions implémenter le cas des arêtes "impossibles" en cas d'obstacle.

D'ou ma question, comment à partir d'une liste d'obstacles, un point de départ et un point d'arrivée savoir si la ligne entre le point A et le point B passe sur un obstacle?

Nous nous sommes creusé la tête de différentes façons, jusqu'à voir pixels par pixels, si le pixel était compris dans un obstacle.

J'espère que quelqu'un pourra nous aider, parce que c'est le dernier point sombre du projet.

Merci, d'avance

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 ?

Code:

---

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?

Code:

---

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:

Code:

---

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

Code:

---

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:

Code:

---

x_pt1 v x_pt2 = l, avec 'v' le produit vectoriel

---

Merci pour la piste.

Je n'avais pas précisé que mes obstacles sont des rectangles parallèles aux limites de la scène. La scène étant elle même un rectangle.
Un obstacle est défini par son coin bas gauche et son coin haut droit.

Donc il faut que je puisse voir s'il y a un croisement entre les segments représentant le périmètre de mon obstacle et l'arête que je cherche à créer.

Je savais bien qu'il y avait une solution "mathématique", donc merci pour le produit vectoriel. Mais n'est-ce pas le produit vectoriel de 2 droites plutôt, qui donne un point? le point d'intersection en l'occurrence.
Maintenant il a de fortes chances que je trouve une collision pour chaque arête en les traitant comme des droites.
Je vais creuser un peu plus.
Si quelqu'un aurait une autre solution, nous sommes preneurs.
Mais merci tout de même ça nous donne une piste de recherche.
:ccool:

Je ne suis pas mathématicien :aie:, je ne fais qu'utiliser les mathématique comme outils.

Un de mes livres de chevet est "Multiple View Geometry in Computer Vision", Hartley R.; Zisserman A., dans lequel on trouve entre autre qu'en coordonné homogène on peut définir une droite comme étant le produit vectoriel de deux points,

Code:

---

l = x × x'

---

et un point par le produit vectoriel de deux droites,

Code:

---

x = l × l'

---

(notation du livre, '×' est l'opérateur "cross product", ou produit vectoriel).

Ca ressemble à un problème de visibilité exacte (ie une recherche de classe d'équivalence d'ensemble de droite).

Si ton problème est 2D, ça doit pouvoir se résoudre via un espace dual.

Une question en passant : pourquoi ne pas avoir discrétisé la scène (quadrillage) et utilisé l'algo A* ?

Citation:

---

Envoyé par pseudocode

Une question en passant : pourquoi ne pas avoir discrétisé la scène (quadrillage) et utilisé l'algo A* ?

---

Parce que le sujet du projet est "implémentation de l'algorithme de Dijkstra avec 2 files de priorité"
Tout simplement.

Citation:

---

Envoyé par touftouf57

Parce que le sujet du projet est "implémentation de l'algorithme de Dijkstra avec 2 files de priorité"
Tout simplement.

---

C'est une bonne raison. :D