Discussion :

[Neitsa]

Bonjour à tous,

Une question qui pourra sembler simple à certains d'entre vous , mais je n'arrive pas à trouver de solution.

Je suis en train d'écrire un petit programme de calculs géométriques et je me heurte à un petit problème :

j'ai trois paires de coordonnées représentant des points définissant un triangle dans un repère cartésien à deux dimensions ( axe x et y).

exemple :

A(-152,326) B(658,-762) C(148,-651)

Comment savoir si l'aire du triangle contient l'origine du plan (O ou 0,0) ?

Je n'arrive pas à savoir quel formule je dois utiliser... (et comme mes lecons de trigo sont loin derrière moi ) Le problème étant que je doivent tester plusieurs centaines de triangles, il faut donc que j'arrive à trouver une règle

C'est pour un défi mathématique: http://mathschallenge.net/index.php?section=project

Je vous invite à y jeter un oeil c'est très sympa

Je ne demande pas une solution toute faite, bien au contraire, mais juste une direction dans laquelle regarder.

Merci à vous

[Matthieu Brucher]

Si tu tournes dans le sens horaire sur ton triangle, tu auras toujours l'aire qui sera "à gauche" du vecteur.
Donc tu classes tes triangles dans le sens horaire : produit vectoriel de 2 des vecteurs, si le produits est négatif, c'est que c'est l'autre sens qu'il faut prendre, non tu fais AB * AC > 0 ? si oui, tu parcours ABC, sinon ACB.
Ensuite, tu fais AB * AO > 0, BC * BO > 0, CA * CO > 0 ? Si c'est toujours vrai, O devrait être dans le triangle.

[Jedai]

Tu peux éviter la première étape en te contentant de vérifier si les trois produits sont du même signe (optimisons, optimisons en restant lisible, il en restera toujours quelque chose ! ).
(NB : là tu considère que le contour ne fait pas partie du triangle, ce qui est souvent raisonnable, mais dépend de ta problématique)

--
Jedaï

[Neitsa]

Merci bien pour vos réponses.

Il a fallu que je cherche comment obtenir les composantes d'un vecteur à partir des coordonnées, là c'était encore assez simple :

(xB - xA ; yB - yA)

Hmm, mais je vais encore vous embêter car j'ai encore une petite question et je ne suis plus très sur...

Pour faire le produit de deux vecteurs (par exemple AB*AC comme vous me l'indiquez), c'est un produit scalaire ou un produit vectoriel ?

désolé

Merci encore

[sjrd]

Pour faire le produit de deux vecteurs (par exemple AB*AC comme vous me l'indiquez), c'est un produit scalaire ou un produit vectoriel ?

Produit scalaire puisqu'on le compare à un réel
AB * AC = |AB| * |AC| * cos BAC

[Jedai]

Non non, c'est un produit vectoriel, enfin presque... En fait c'est un produit mixte, c'est à dire le déterminant de la famille des deux vecteurs. Si très souvent on parle de produit vectoriel c'est qu'en fait si on se projette dans un espace à trois dimension, ce produit mixte sera la troisième coordonnée du produit vectoriel correspondant.
Pour abréger, ça se calcule comme ça :
AB(x, y), AO(x', y')
[ AB, AO ] = xy' - yx'

Voilà !

(NB : sjrd, quand on dispose des coordonnées des vecteurs (dans une base orthonormale !), on calcule le produit scalaire avec : <AB, AO> = xx' + yy', c'est beaucoup plus rapide !!)

--
Jedaï

[sjrd]

(NB : sjrd, quand on dispose des coordonnées des vecteurs (dans une base orthonormale !), on calcule le produit scalaire avec : <AB, AO> = xx' + yy', c'est beaucoup plus rapide !!)

Euh oui c'est juste... j'y avais même plus pensé

[Matthieu Brucher]

Effectivement, tu testes juste la troisième coordonnée du produit vectoriel. J'ai mis exprès "*" pour ne pas confondre avec le produit scalaire qui est plutôt symbolisé par "."

[DrTopos]

Bonjour à tous.

Un triangle ABC contient un point P si et seulement si P est un barycentre de A, B et C avec des poids positifs ou nuls. Il suffit donc de calculer ces poids.

Si A = (a1,a2), B = (b1,b2), C = (c1,c2), et P =(p1,p2), on doit trouver les trois poids x, y et z tels que

Code :

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

1
2
3
4
 
xa1 + yb1 + zc1 = p1
xa2 + yb2 + zc2 = p2
x   + y   + z   = 1

les deux première équations n'étant justifiées que si la somme des poids est 1.

Il s'agit donc d'un système d'équations linéaires que l'on peut résoudre par la méthode du pivot de Gauss (par exemple, il me semble d'ailleurs voir d'excellents pivots dans la troisième équation). Je fais remarquer que le déterminant principal est nul précisément quand le triangle est dégénéré (A, B et C alignés).

Une fois le système résolu, il suffit de vérifier que x, y et z sont positifs.

[Jedai]

C'est une solution, mais je ne sais pas si c'est utilisable : après un petit calcul, j'arrive pour le calcul du
premier poid (donc le plus difficile à calculer) à un total de 6 soustractions, 1 addition, 2 divisions, 2 multiplications, (ou 2 divisions, 4 multiplications)
puis le deuxième 1 addition, 1 multiplication, 1 division,(ou 0 divisions, 2 multiplications)
troisième : 1 soutraction, 1 addition. Soit un total de 7 soustractions, 3 additions, 3 divisions, 3 multiplications au pire (ou 2 divisions/6 multiplications, ce qui est sans-doute mieux). Bien sûr je n'ai pas l'habitude de ce type de problème, et peut-être y a-t-il des méthodes de simplification beaucoup plus sophistiquées, mais je pense que l'algorithme avec les produits mixtes sera plus léger (en tout 12 soustractions, 3 additions et 6 multiplications au pire).
Juste pour donner une idée du coût de la division comparativement à la multiplication : http://www.x86-secret.com/articles/cpu/p4/p4-5.htm .

--
Jedaï

[DrTopos]

Je n'ai pas cherché la performance. J'ai donné cette solution parce qu'elle me semble la plus naturelle (disons la plus élégante pour un matheux).

J'ai vu effectivement, en allant sur la référence que tu as donnée que la division est beaucoup plus couteuse que la multiplication.

Ceci dit, il n'y a aucune division à faire ici. On peut procéder comme suit. Si je résouds le système manuellement en éliminant x puis z, j'obtiens l'équation:

Code :

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

1
2
 
(c2 - 1)(b1 - 1) - (c1 - 1)(b2 - 1)y = (p1 - a1)(c2 - 1) - (p2 - a2)(c1 - 1)

qui donne y comme un quotient. Il n'y a pas besoin de diviser car il suffit de vérifier que les deux expressions:

Code :

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

1
2
3
 
Y1 = (c2 - 1)(b1 - 1) - (c1 - 1)(b2 - 1) 
Y2 = (p1 - a1)(c2 - 1) - (p2 - a2)(c1 - 1)

sont de même signe. On fait de même pour z.

Comme on a Y1y = Y2, Z1z = Z2 et x = 1 - y - z, on obtient:

Code :

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

1
2
 
Y1Z1x = Y1Z1 - Z1Y2 - Y1Z2

et on obtient le signe de x à nouveau par une comparaison de signes.

Si je compte bien on a au total (en stockant les calculs intermédiaires): 12 soustractions, 11 multiplications et 3 comparaisons de signes. Ca n'a pas l'air si mal. Mais il est possible qu'il y ait mieux, car le calcul des poids (qui n'est pas fait complètement ici puisqu'on ne fait pas les divisions finales) en fait sans doute plus que ce qui est nécessaire.

[Jedai]

Ces nombres me semblent légèrement sous-estimés : en effet, on a 12 soustractions sur les étapes y et x, mais il doit également y en avoir quelques une sur l'étape z. Je compte également 8 multiplications pour les étapes y et x, il n'y en a que 3 pour z (j'en comptais 4 aussi) ?
Il est possible qu'il y ait mieux effectivement, parce que la méthode "produit vectoriels" employé est générique donc il serait logique qu'il y ait mieux pour un triangle, le plus simple des polygônes...

--
Jedaï

[DrTopos]

J'ai une autre solution avec seulement 7 soustractions, 2 additions, 6 multiplications, 4 comparaisons. Pas de division.

On commence par translater la figure pour que A soit en O. Les nouveaux points sont donc:

A' = (0,0), B' = (b1-a1,b2-a2), C' = (c1-a1,c2-a2) et P' = (p1-a1,p2-a2). La matrice

Code :

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

1
2
3
 
M = (b1-a1   c1-a1)
    (b2-a2   c2-a2)

est la transformation qui amène les deux vecteurs de la base canonique i = (1,0) et j = (0,1) sur les vecteurs OB' et OC'., et donc le triangle 0ij sur le triangle A'B'C' = OB'C'. Si on appelle u et v les coordonées du vecteur M^(-1)P', il suffit donc de vérifier que 0 =< u, 0 =< v et u+v =< 1.

Or det(M)M^(-1) est la matrice N suivante (d'après la formule de la comatrice):

Code :

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

1
2
3
 
N = (c2-a2   a1-c1)
    (a2-b2   b1-a1)

Il en résulte que si U et V sont les deux coefficients de NP', on a U = det(M)u et V = det(M)v. Le test à faire est donc 0 =< U, 0 =< V et U+V =< det(M), à condition que det(M) soit positif. S'il est négatif, il suffit d'intervertir les rôles de B et C pour le rendre positif. On suppose en fait qu'il n'est pas nul, c'est à dire que le triangle ABC n'est pas dégénéré.

Il suffit donc de calculer N et P' (soit 6 soustractions), puis le produit NP' (4 multiplications et 2 additions), le déterminant de M, qui est le même que celui de N (2 multiplications et une soustraction). Pour finir, il faut faire les 3 comparaisons. Il reste le problème du signe du déterminant, mais il doit se régler avec une comparaison.

[Jedai]

Rien à dire, excellente méthode ! Tu as oublié l'addition du U+V et il y a une chance sur deux qu'il y ait une opération de plus à effectuer pour le déterminant (mais c'est du 1 cycle probablement) mais même ainsi on reste en dessous de l'algorithme initialement proposé (en fait c'est presque équivalent : 2 additions/soustractions en plus ou en moins...). Félicitations !!

--
Jedaï

[DrTopos]

Tu as oublié l'addition du U+V et ...

En effet, comme quoi on n'est jamais à l'abri d'une erreur. Merci pour le compliment, mais je ne crois pas avoir beaucoup de mérite après 31 années d'enseignement des maths.

[Jedai]

Mais si mais si ! Autant j'avais pensé à la première méthode, autant la seconde est beaucoup plus astucieuse.

Tu enseigne où à propos ? :

--
Jedaï, Normalien à compter de cette année

[Neitsa]

Houlala

Je ne comptais pas avoir autant de réponses détaillées. Merci à tous, j'ai attentivement lu vos réponses qui sont très claires.

Il ne me reste plus que l'embarras du choix on dirait (et parallèlement, plus qu'a mettre les mains dans le code, ce qui sera surement plus simple pour moi que de faire ce que vous avez fait...).

Problème très enrichissant et réponses allant dans le même sens, tout devient plus clair pour peu que l'on vous explique comment faire et quels procédés utilisés.

Merci à vous pour avoir pris le temps d'y réfléchir

Je passe le sujet en résolu.

[Matthieu Brucher]

C'est vrai qu'il y avait cette propriété...

[DrTopos]

Tu enseigne où à propos ? :

J'enseigne à l'Université Denis Diderot (alias Paris 7), sur le campus Jussieu.