Problème de Vecteur

**larchicha** · 20/04/2010, 13h54

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** · 20/04/2010, 15h30

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

Quel est exactement le principe du "same side" ?

**Obsidian** · 20/04/2010, 20h59

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** · 21/04/2010, 00h34

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** · 21/04/2010, 11h15

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** · 21/04/2010, 11h32

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 ?

**diogene** · 21/04/2010, 12h37

Equation() doit évaluer la fonction pour un triplet de trois points donnés. Elle calcule donc une valeur, pas un nouveau point. Le commentaire est faux.

On devrait avoir :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
double Equation(Coord A, Coord B, Coord X){
    /*FAB(X) = (ya-yb)x - (xa-xb)y + xayb-xbya */
        return (A.y - B.y)*X.x - (A.x - B.x)*X.y + (A.x)*(B.y) - (B.x)*(A.y);
}

**larchicha** · 21/04/2010, 13h00

Ahhhhhh.... Ok merci.

Une question qui n'a rien à voir......

Les modos/rédacteurs ou les gens très doués qui répondent, sont ils des profs ?!

Edit : Vu que vous êtes des tueurs (en C ^^), j'aimerais comprendre un point qui me fait terriblement défaut, si vous êtes d'accord....

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
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;
            }
    }

Mon code est faux à tous les coups si je ne met pas le return en dehors du "if" non ?
Car dès que le return est atteint, on sort de la fonction ? Mais si je le met à l'extérieur de la boucle, ma condition ne sert plus à rien... ou alors je passe à coté de quelque chose...

Deuxio, pourquoi je ne peux pas utiliser le type prédéfini "bool" au lieu de créer mon propre type "boolean" ? (la raison de ce nouveau type c'est que juste bool me renvoyé des erreurs...)

Merci d'avance.

**diogene** · 21/04/2010, 13h12

Les modos/rédacteurs ou les gens très doués qui répondent, sont ils des profs ?!

Probablement non pour la plupart d'entre eux.

**larchicha** · 21/04/2010, 13h35

Vu que vous êtes des tueurs (en C ^^), j'aimerais comprendre un point qui me fait terriblement défaut, si vous êtes d'accord....

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
 
 
 
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;
            }
    }

Mon code est faux à tous les coups si je ne met pas le return en dehors du "if" non ?
Car dès que le return est atteint, on sort de la fonction ? Mais si je le met à l'extérieur de la boucle, ma condition ne sert plus à rien... ou alors je passe à coté de quelque chose...

Deuxio, pourquoi je ne peux pas utiliser le type prédéfini "bool" au lieu de créer mon propre type "boolean" ? (la raison de ce nouveau type c'est que juste bool me renvoyé des erreurs...)

Merci d'avance.

PS : désolé pour le doublon, mais tu m'as répondu avant :s

**haraelendil** · 21/04/2010, 15h20

l'idée (si j'ai bien compris), c'est que tu renvoie vrai si ta condition est validée et faux sinon?
Dans ce cas, il faut que tu renvoie vrai dans ton if, et faux sinon, sinon tu pourrais te retrouver avec des trucs instables...
Techniquement, ta fonction doit toujours passer par un return quel que soit le cas ou tu te trouve, sinon elle renverra n'importe quoi...

Et tu ne peux pas utiliser le type bool en C tout simplement parce qu'il n'existe pas par defaut, seulement en C++

**larchicha** · 21/04/2010, 15h49

Merci énormément pour vos réponses...
J'avance enfin...

**diogene** · 21/04/2010, 19h06

- le if est inutile :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
boolean isDansTriangle(Coord A, Coord B, Coord C, Coord M){
        /* Teste si le point M est situe dans le triangle */
  return 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 ;
}

- le type bool (ou _Bool) existe mais en C99

**larchicha** · 26/04/2010, 13h51

Re bonjour à vous,

Désolé d'utiliser mon ancien post, mais ma série de question a reprise (dans ma tête), d'où ma présence...

La précédente question m'a permi de déterminer si un point était ou non dans un triangle, mais maintenant je veux determiner si un point est ou non dans un carré, puis je me resservir de ce précédent algorithme ?
En effet, si je colle 2 triangle equilatéraux , ca me donne un carré (~~ un losange) ?

Donc se resservir des équations de droites, enfin c'est le projet mais niveau algorithme je sèche un peu ...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
/* Si A, B et X sont des points de coordonnées (xa,ya), (xb,yb) et (x,y), on pose : */
		double Equation(Coord A, Coord B, Coord X){
		    /*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 */
			return (A.y - B.y)*X.x - (A.x - B.x)*X.y + (A.x)*(B.y) - (B.x)*(A.y);
		}

Vu qu'un carré n'est que 2 triangles equ collés, je me dis , pourquoi pas ?

**diogene** · 26/04/2010, 14h52

Tu peux toujours considérer un rectangle (ou un carré) comme étant composé de deux triangles rectangles et utiliser l'algo précédent sur les triangles.

Si tu as compris la méthode pour le triangle, il est immédiat de l'étendre directement à un rectangle (ou à un polygone convexe) , il y aura moins de choses à tester que de considérer le rectangle comme deux triangles juxtaposés

**larchicha** · 26/04/2010, 15h21

Ok merci pour l'astuce. Je joins mon code dès que ça ressemble à quelque chose

Encore merci.

**larchicha** · 27/04/2010, 14h16

Bon je sais c'est bête mais j'ai pas fait comme tu m'as dit , soit étendre l'algorithme a un rectangle, ce qui aurait eviter la surcharge des tests, mais comme tu l'as aussi dit, c'est surement parce que j'ai pas compris le fond du fond...

Enfin bon, j'ai dessiné un rectangle( ~~ carre), et une des diagonales, histoire d'avoir mes 2 triangles. Puis j'ai suivi le même raisonnement que pour isDansTriangle...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
boolean isDansCarre(Coord A, Coord B, Coord C, Coord D, Coord M){
		/* Teste si le point M est situe dans le carre */
		/* Un carre etant 2 triangles equ colle, on a donc : */
 
		return ( (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) 			&& (Equation(C,D,A) * Equation(C,D,M) >=0) && (Equation(D,A,C) * Equation(D,A,M) >=0) && (Equation(A,C,D) * Equation(A,C,M) >= 0) );
 
		}

Si vous pouvez m'expliquer ou m'aider à m'améliorer, je prends !

Merci d'avance.

**diogene** · 27/04/2010, 15h58

Si tu utilises cette méthode, soyons logique : Le point doit être dans un triangle ou dans l'autre. Or on a écrit une fonction qui teste si un point est dans un triangle, autant l'utiliser :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
boolean isDansCarre(Coord A, Coord B, Coord C, Coord D, Coord M){
		/* Teste si le point M est situe dans le carre */
		/* Un carre etant 2 triangles equ colle, on a donc : */
 
   return isDansTriangle(A,B,C,M)|| isDansTriangle(A,D,C,M);		
}

Ceci marchera pour tout quadrilatère convexe (et non croisé), mais suppose que AC est une diagonale, donc l'ordre A,B,C,D n'est pas indifférent.

Problème de Vecteur

C

Discussions similaires

Partager

Partager