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 :

Point à l'intérieur d'un triangle ?


Sujet :

Algorithmes et structures de données

  1. #1
    Membre régulier
    Homme Profil pro
    Inscrit en
    Juin 2003
    Messages
    127
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Seine et Marne (Île de France)

    Informations professionnelles :
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2003
    Messages : 127
    Points : 88
    Points
    88
    Par défaut Point à l'intérieur d'un triangle ?
    Bonjour
    Je suis face a un exercice de programmation qui me donne quelques soucis, voici l'enoncé:
    Soit un triangle defini par trois points A(x...,y...) B(x...;y....) C(x....,Y.....)
    Ecrire le code qui verifie si oui ou non un quatrieme point D(x...,y....) se trouve a l'interieur de ce triangle.
    Si vous avez des suggestions :
    A bientot
    Rémi

  2. #2
    Membre du Club
    Inscrit en
    Février 2003
    Messages
    39
    Détails du profil
    Informations forums :
    Inscription : Février 2003
    Messages : 39
    Points : 46
    Points
    46
    Par défaut
    C'est assez simple, mais il s'agit d'un pb de mathématique.. Voila la solution:

    Avec les trois points, tu calcules les équations de tes trois droites. Une fois que tu a les équations, voila l'algorithme:

    Pour chaque droite, tu vérifies que le point D appartient au même demi plan que celui contenant le troisième point de ton triangle.

    Avec un exmple:

    tu consideres les points A et B, tu as l'auqtion de la droite (AB)., Si D appartient au même demi plan que C (demi plan definis par rapport à la droite AB), tu as verifies une des trois conditions.

    Ensuites, tu consideres les points A et C, tu calcules l'equation de la droite (AC), si D appartient au même demi plan que B, tu as deux confditions sur trois

    Ensuite tu consideres les points B et C. Si D appartient au même demi plan que A, c'est gagné...

    Par contre, si une des trois conditions n'est pas remplies, ton point n'est pas dans le triangle.

    Ton programme se code tres vite, si tu veux jouer le beau gosse ecrit un programme qui calcule ce genre de chose pour un polygone à n cotes, c'est plus marrant!

    N'hesites pas si tu as des questions. Bon courage. Bye

  3. #3
    Membre régulier
    Profil pro
    Inscrit en
    Mars 2003
    Messages
    52
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2003
    Messages : 52
    Points : 75
    Points
    75
    Par défaut
    Des pistes dans un triangle ABC où on veut savoir si M est à l'intérieur du triangle:


    Avec les coordonées barycentriques
    On détermine les coordonnées barycentriques de M par rapport à A, B, C
    un point est à l'intérieur d'un triangle ABC si et seulement si ses coordonnées barycentriques sont toutes les trois positivers


    Avec des demi-plans
    La droite (AB) d'équation ax + by + c = 0 partage le plan en deux régions. Dans l'une les coordoonées des points vérifient ax + by + c < 0, dans l'autre ax + by + c > 0.
    Pour savoir si les points C et M sont dans le même demi-plan, il suffit de tester si la formule ax + by + c appliquée à leurs coordonnées donne le même signe.
    Enfin, le triangle ABC est défini comme l'intersection des trois demi-plans:
    - le demi-plan de bord (AB) contenant C
    - le demi-plan de bord (AC) contenant B
    - le demi-plan de bord (BC) contenant A


    Avec des produits vectoriels
    M est dans le triangle si et seulement si les trois conditions suivantes sont vérifiées:
    (vect(AB) ^ vect(AM)) . (vect(AM) ^ vect(AC)) >= 0
    (vect(BA) ^ vect(BM)) . (vect(BM) ^ vect(BC)) >= 0
    (vect(CA) ^ vect(CM)) . (vect(CM) ^ vect(CB)) >= 0

    où ^ désigne le produit vectoriel de deux vecteurs
    . désigne le produit scalaire
    A mon avis, cete méthode devrait être efficace. il suffit de te procurer un bon formulaire.


    P.S. Pourrais-tu éditer ton premier message et mettre un titre plus explicite (c'est plus facile à lire pour les habitués du forum) du style "point intérieur à un triangle ?"

  4. #4
    Candidat au Club
    Profil pro
    Inscrit en
    Juin 2003
    Messages
    3
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2003
    Messages : 3
    Points : 4
    Points
    4
    Par défaut
    Il me semble aussi que tu peux faire en calculant les angles:
    si la somme des trois angles ADC, CDB, BDA est égale à 360 degrés, alors le point D est à l'intérieur du triangle (il faut tenir compte de l'orientation)
    Dans la vie faut pas s'en faire, moi je m'en fais pas

  5. #5
    Membre habitué

    Profil pro
    Inscrit en
    Octobre 2002
    Messages
    66
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2002
    Messages : 66
    Points : 129
    Points
    129
    Par défaut
    La réponse pratique en Delphi ici (et sur le Net en C à l'adresse donnée par Maamar au post sur les algos géométriques) :
    http://www.geometryalgorithms.com/

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
     
    Function IsLeft&#40;p1,p2,newp &#58; TPoint&#41; &#58; real;
    // Teste si point newp est &#58; à Gauche|Sur| à Droite de la droite &#40;p1p2&#41;.
    // Result&#58; >0 si newp est à gauche de la droite P1-P2
    //           =0 si le point est surla droite
    //          <0 ... droite
    // NB &#58; surface du triangle = Isleft / 2 .
    begin   // chaque point défini par ses coordonnées X,Y ...
      result &#58;= &#40;p2.X - p1.X&#41; * &#40;newp.Y - p1.Y&#41;
        - &#40;newp.X - p1.X&#41; * &#40;p2.Y - p1.Y&#41;
    end;
     
    Function IsInsideTriangle&#40;A,B,C,H &#58; TPoint&#41; &#58; boolean;
    // Teste si point H est intérieur au Triangle ABC.
    // Méthode&#58; H à gauche de &#40;CA&#41; -> IsLeft&#40;CAH&#41; > 0
    //          H à G &#40;dessus&#41;&#40;BC&#41; -> IsLeft&#40;BCH&#41; > 0
    //          H à droite de &#40;BA&#41; -> IsLeft&#40;BAH&#41; < 0
    begin
      result &#58;= false;
      if &#40;Isleft&#40;C,A,H&#41;>0&#41; and &#40;Isleft&#40;B,C,H&#41;>0&#41;
        and &#40;Isleft&#40;B,A,H&#41;<0&#41; then result &#58;= true;
    end;
    Facile, non ? Et adaptable ...
    Consultez :
    - La F.A.Q Delphi + Les Cours Delphi
    - La sélection des Freewares Delphi

  6. #6
    Scorpi0
    Invité(e)
    Par défaut
    W00t, déterrage puissance 6 années, qui dit mieux ?
    Bon, le code ci dessus m'a bien aidé, sauf qu'il est faux, donc je corrige !


    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    Function IsLeft(p1,p2,newp : TPoint) : real;
    // Teste si point newp est : à Gauche|Sur| à Droite de la droite (p1p2).
    // Result: >0 si newp est à gauche de la droite P1-P2
    //           =0 si le point est surla droite
    //          <0 ... droite
    // NB : surface du triangle = Isleft / 2 .
    begin   // chaque point défini par ses coordonnées X,Y ...
      result := (p2.X - p1.X) * (newp.Y - p1.Y)
        - (newp.X - p1.X) * (p2.Y - p1.Y)
    end;
     
    Function IsInsideTriangle(A,B,C,H : TPoint) : boolean;
    // Teste si point H est intérieur au Triangle ABC.
    // Méthode: Test si H et C sont a gauche de AB, ou pas, mais en meme temps
    begin
      result := false;
      if (IsLeft(C,A,H)*IsLeft(C,A,B)>0 and IsLeft(A,B,H)*IsLeft(A,B,C)>0 and IsLeft(C,B,H)*IsLeft(C,B,A)>0) then result := true;
    end;

  7. #7
    Nouveau membre du Club
    Homme Profil pro
    Minimexé
    Inscrit en
    Août 2009
    Messages
    25
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : Minimexé

    Informations forums :
    Inscription : Août 2009
    Messages : 25
    Points : 29
    Points
    29
    Par défaut Et en 3D?
    Peut-on faire la même chose en 3D?

    La formule que Scorpi0 a donnée est elle toujours valable?

  8. #8
    Nouveau Candidat au Club
    Inscrit en
    Mai 2011
    Messages
    1
    Détails du profil
    Informations forums :
    Inscription : Mai 2011
    Messages : 1
    Points : 1
    Points
    1
    Par défaut Déterminants
    Hello,
    Est-ce qu'on peut utiliser le déterminant pour calculer l'aire du triangle (on va dire ABC), et ensuite calculer l'aire des trois triangles formés par A,B,C et le quatrieme point D dont on veut savoir si il est à l'intérieur ou non?
    et si Aire(ADC)+Aire(ADB)+Aire(CDB)=Aire(ABC) alors D est à l'interieur de ABC?
    avec, Aire()=det()/2.
    On peut utiliser cette méthode en 3D pour un point dans un tétraèdre.

  9. #9
    Futur Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Février 2015
    Messages
    10
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 25
    Localisation : France, Somme (Picardie)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Février 2015
    Messages : 10
    Points : 6
    Points
    6
    Par défaut Deux méthodes simples
    Bonjour,

    Il y a un article de blog qui explique deux méthodes de détermination d'un point à un triangle, et propose une application en C++.

    C'est très intéressant.

  10. #10
    Candidat au Club
    Homme Profil pro
    Enseignant
    Inscrit en
    Janvier 2013
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Algérie

    Informations professionnelles :
    Activité : Enseignant
    Secteur : Enseignement

    Informations forums :
    Inscription : Janvier 2013
    Messages : 6
    Points : 3
    Points
    3
    Par défaut problemes à voir
    le calcul de la position d'un point par rapport à un triangle peut se faire par calcul de déterminant de trois triangles virtuels
    soit ABC les sommets du triangle dans l'ordre contraire aux aiguilles d'une montre (ordre topographique) et M le 4eme point . On à 3 triangles virtuels ABM , AMC, MBC soit D le déterminant calculé avec les sommets ABC
    | xa ya 1 |
    D= | xb yb 1 |
    | xc yc 1 |
    on calcul le signe des trois déterminants des triangles virtuels on a 3 possibilités
    1 - les trois déterminants sont tous positifs ==> le point M appartient au triangle ABC
    2 - un déterminant est nul ==> le point M appartient à un côté du triangle (si deux déterminants nuls ==> M confondu avec sommet )
    3 - un déterminant est négatif ==> M est à droite du cote du triangle

    le problème sérieux qui se pose dans certaines situations est le calcul exact de D (ou la détermination de son signe ) à cause des flottants (un calcul avec des nombres entiers ne pose pas de difficultés particulières)

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 5
    Dernier message: 22/03/2012, 20h06
  2. Oracle Locator - Point à l'intérieur d'un polygone
    Par thisistheend dans le forum SQL
    Réponses: 0
    Dernier message: 30/10/2011, 14h11
  3. Calcul vectoriel (savoir si un point est à l'intérieur d'un triangle)
    Par Invité dans le forum Général JavaScript
    Réponses: 2
    Dernier message: 29/10/2008, 23h46
  4. Test: point au dessus d'un triangle
    Par NailMaker dans le forum Algorithmes et structures de données
    Réponses: 14
    Dernier message: 12/06/2006, 20h55
  5. [Algo] Point à l'intérieur d'un polygone ?
    Par kebby dans le forum C++Builder
    Réponses: 5
    Dernier message: 23/05/2003, 14h22

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