Discussion :

[larchicha]

Autant vous dire que je suis une cave en maths, mais là n'est pas le problème...

Je dois tester si un point est dans un triangle, et j'ai trouvé 2 méthodes, l'une appellée ' Same side ' et l'autre est barycentrique...

J'ai voulu essayé la première méthode... et bon il y a sûrement pleins de fautes grosses comme des camions que j'ai loupé... mais il me manque un concept sans lequel je suis completement bloqué.

Ci joint mon code :

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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
struct Coordonnes {
    int x;//abcisses
    int y;//ordonnees
};
 
typedef enum {
       FALSE,
       TRUE
} boolean;
 
typedef struct Coordonnes Coord;
 
Coord Point, centre,A,B,P,cp1,cp2;
 
 
/*calcule la distance du point par rapport au centre du cercle */
int distanceOCentre(Coord centre, Coord point){
        double distance = sqrt((point.x - centre.x)*(point.x - centre.x) + (point.y - centre.y));
        return distance;
}
 
boolean isDansCercle(int point, int rayon){//Test si un point est dans un cercle
 
    point = distanceOCentre(centre, Point);
        if (point > rayon)
           return FALSE;
}
 
double produitScalaire(Coord A, Coord B){
    double produitS = ((A.x*B.x+A.y*B.y));
    return produitS;
 }
 
//Tres surement faux car concept erroné...
Coord produitVectoriel(Coord B,Coord A),(Coord P,Coord A)){
   Coord produitV = ( ((A.x)*(B.y)) - ((A.y)*(B.x)), ((P.x*A.y)) - ((P.y*A.x)));
   return produitV;
 }
 
 //Technique SAME SIDE
boolean sameSide(Coord P1, Coord P2, Coord A, Coord B){
        cp1 = produitVectoriel(B-A, P1-A)
        cp2 = produitVectoriel(B-A, P2 -A)
        if (produitScalaire(cp1, cp2) >= 0){
            return TRUE;
        }
        else {
            return FALSE;
                        }
    }
 
 
 
    int PointInTriangle(Coord P, Coord A,Coord B,Coord C){
        if ( SameSide(P,A B,C) and SameSide(P,B,A,C)
            and SameSide(P,C,A,B) ) {
                return true;
        } else {
            return false;
        }

Mais vous allez me dire, c'est pas compliqué de trouver la formule de produit vectoriel, fais un effort mon gars... Seulement tout ce que je trouve est en dimension 3, et bon j'ai besoin de dimension 2...

J'avoue c'est une excuse un peu pipée, mais je suis entrain de craquer mentalement...

Merci d'avance...

PS : Je teste aussi si un point est dans un cercle mais ce n'est pas la priorité.

[Médinoc]

Déjà, avec les variables globales et tout, ça n'est pas facile.

Quel est exactement le principe du "same side" ?

[Obsidian]

Dans un repère orthonormé aux valeurs discrètes tel que celui de l'écran d'un ordinateur, le plus simple est consiste effectivement à regarder où se trouve le point par rapport aux arêtes de ton triangle.

En admettant que celui-ci n'est pas plat, et qu'il ne possède aucun côté horizontal ou vertical, commence par vérifier l'ordonnée de ton point. Soit celui-ci est plus haut ou plus bas que ton triange et, dans ce cas, il n'y a rien à vérifier car on sait déjà que le point est dehors, soit il est à la même hauteur et, dans ce cas, la ligne horizontale qui passe par ton point va couper exactement deux des trois côtés de ton triangle.

Tu détermines l'abscisse des points d'intersection, et tu compares ces deux abscisses à celle de ton point : si la tienne est la plus petite, ton point est à gauche des deux segments, donc hors du triangle. Si c'est la plus grande, elle est à droite.

[larchicha]

Je vois le concept, c'est en effet plus clair...

Excusez moi pour mon morçeau de code, c'est vraiment pas sérieux... Je vais recommencer, je vous tiens au courant

Merci encore.

[diogene]

Tu as un bon récapitulatif des méthodes possibles dans cette ancienne discussion : Point a l'interieur d'un triangle?

La deuxième méthode présentée dans cette discussion peut être explicitée :
Si A, B et X sont des points de coordonnées (xa,ya), (xb,yb) et (x,y), on pose :

FAB(X) = (ya-yb)x - (xa-xb)y + xayb-xbya

Alors, FAB(X) = 0 est l'équation donnant les coordonnées des points X situés sur la droite passant par les points A et B.

Pour que M soit à l'intérieur (ou sur les cotés) du triangle (ABC) il faut que :

FAB(C)FAB(M) >= 0
FBC(A)FBC(M) >= 0
FCA(B)FCA(M) >= 0

[larchicha]

Merci pour la 2ème explication et pour votre rapidité de réponse.
Je joins ce que j'ai fait :

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
23
24
25
26
27
28
29
30
31
32
33
 
 
struct Coordonnes {
    int x;//abcisses
    int y;//ordonnees
};
 
typedef enum {
       FALSE,
       TRUE
} boolean;
 
typedef struct Coordonnes Coord;
 
Coord Point, centre,A,B,X,M;
 
 
Coord Equation(Coord A, Coord B, Coord X){
    /*FAB(X) = (ya-yb)x - (xa-xb)y + xayb-xbya / Donne les coordonnes du point d intersection M
    avec la droite AB */
        double equation = (A.y - B.y)*X.x - (A.x - B.x)*X.y + (A.x)*(B.y) - (B.x)*(A.y);
        if (equation == 0){
            return X;
        }
    }
 
    boolean isDansTriangle(Coord A, Coord B, Coord C, Coord M){
        /* Teste si le point M est situe dans le triangle */
        if ((Equation(A,B,C)) * (Equation(A,B,M) >= 0) && ((Equation(B,C,A)) * (Equation(B,C,M)) >= 0)
            && (Equation(C,A,B)) * (Equation(C,A,M)) >= 0)) {
                    return TRUE;
            }
    }

Premier problème que je vois, je ne peux pas multiplier des Coord entre elles (car Equation() me retourne une Coord, aurais-je pu retourner un type primitif ?)

(Tout en sachant que les composantes de Coord sont simplement 2 entiers x et y, pourquoi ne pourrais je pas les multiplier entre elles ?!)

Deuxième problème, c'est le "if" dans la fonction Equation, je l'ai mis par dépit de pas trouver autre chose...

Merci d'avance.

PS : Juste pour info, dans mon code, le fait d'avoir mis des struct et enum de variables globales, est-ce mal ? Ou y a t'il quelque chose de mieux ?