IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Comment déterminer si une droite rencontre un obstacle


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre éclairé Avatar de touftouf57
    Profil pro
    Développeur .NET
    Inscrit en
    Décembre 2007
    Messages
    362
    Détails du profil
    Informations personnelles :
    Âge : 47
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Développeur .NET
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Décembre 2007
    Messages : 362
    Par défaut 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

  2. #2
    Membre éprouvé
    Inscrit en
    Mai 2006
    Messages
    196
    Détails du profil
    Informations forums :
    Inscription : Mai 2006
    Messages : 196
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    x_pt1 v x_pt2 = l, avec 'v' le produit vectoriel

  3. #3
    Membre éclairé Avatar de touftouf57
    Profil pro
    Développeur .NET
    Inscrit en
    Décembre 2007
    Messages
    362
    Détails du profil
    Informations personnelles :
    Âge : 47
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Développeur .NET
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Décembre 2007
    Messages : 362
    Par défaut
    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.

  4. #4
    Membre éprouvé
    Inscrit en
    Mai 2006
    Messages
    196
    Détails du profil
    Informations forums :
    Inscription : Mai 2006
    Messages : 196
    Par défaut
    Je ne suis pas mathématicien , 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,
    et un point par le produit vectoriel de deux droites,
    (notation du livre, '×' est l'opérateur "cross product", ou produit vectoriel).

  5. #5
    Expert confirmé
    Avatar de PRomu@ld
    Homme Profil pro
    Ingénieur de Recherche
    Inscrit en
    Avril 2005
    Messages
    4 155
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France, Vienne (Poitou Charente)

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2005
    Messages : 4 155
    Par défaut
    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.

  6. #6
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Une question en passant : pourquoi ne pas avoir discrétisé la scène (quadrillage) et utilisé l'algo A* ?
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

Discussions similaires

  1. [JavaScript] Comment déterminer si une année est bissextile ?
    Par Bovino dans le forum Contribuez
    Réponses: 4
    Dernier message: 23/08/2010, 09h43
  2. Réponses: 4
    Dernier message: 02/01/2009, 17h56
  3. Réponses: 8
    Dernier message: 22/06/2008, 08h12
  4. Réponses: 4
    Dernier message: 04/12/2007, 19h35
  5. Réponses: 3
    Dernier message: 13/12/2006, 14h03

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo