Discussion :

[Matt2094]

Bonjour à tous,

Je cherche un algo de tracé de triangle plein dans un espace d'affichage virtuel (je ne peux donc pas utiliser de fonctions appartenant au language). Je cherche donc un moyen de trouver tous les points à l'intérieur d'un triangle.

Merci d'avance.

[Kangourou]

saut,

tu consideres tes 3 cotes AB, BC et CA,

pour chaque point x que tu veux tester tu cherches si x est à l'interieur des demi plan defini par chaque cote.
si les 3 tests sont positifs, le point est dans le triangle. Tu peux generaliser a tout polygone convexe.
Pour savoir si il est du bon cote du segment, le signe du produit vectoriel entre AB et Ax (ou bien BC et Bx pour le 2eme cote, ou CA et CX pour le troisieme cote) te permet de le connaitre.

A+

[DrTopos]

L'intérieur d'un triangle est tout simplement l'ensemble des points qui sont des barycentres des trois sommets avec des coefficients positifs. Il s'agit donc (si les sommets sont A, B et C) des points suivants:

Code :

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

1
2
 
aA + bB + cC

avec a+b+c = 1, a, b et c positifs.

On peut se passer de c en posant c = 1-a-b, ce qui nous laisse deux paramètres pour parcourir le triangle. Les conditions sont simplement que a et b doivent être positifs et a+b au plus 1. On peut donc faire varier a entre 0 et 1, et pour chaque a, faire varier b entre 0 et 1-a.

[Matt2094]

Merci pour vos réponses, mais je suis encore qu'au collège, et je ne suis pas très doué en maths. Donc si pouviez éxpliquez un plus simplement, sans trop de mots compliqué ?

[Tellmarch]

tu travailles dans un plan, ou en 3 dimensions?

Si c'est dans un plan tu peux tracer ton triangle comme ça :

- tu commences par le découper en 2 triangles tels que leurs bases soient horizontales par exemple, et tu traces les deux triangles.
- Pour chacun des triangles, tu les traces par segments horizontaux, avec 2 boucles for. Si tu as les deux sommets A et B en bas, et C en haut par exemple, tu fais

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
pour y allant de yA à yC, faire
// on trace le segment horizontal à la hauteur y
// il faut calculer ses 2 extremités, avec le théoreme de Thales par exemple si tu connais
// ça doit donner un truc du genre (je suis pas sur, il faut vérifier) :
x1 = xA + (xC - xA)*(y-yA)/(yC-yA)
x2 = xB + (xC - xB)*(y-yA)/(yC-yA)
  pour x allant de x1 à x2 faire
    Tracer le point (x,y)
  fin pour
fin pour

[Matt2094]

Merci. Je travaille en 2D. Mais imaginons que le trinagle soit quelquonque, et qu'il ne soit ni horysontale, ni verticale, bref, qu'il soit un triangle sans aucune particularité ?...

P.S : je connais pas encore le théoreme de Thales

[Matt2094]

tu travailles dans un plan, ou en 3 dimensions?

Si c'est dans un plan tu peux tracer ton triangle comme ça :

- tu commences par le découper en 2 triangles tels que leurs bases soient horizontales par exemple, et tu traces les deux triangles.
- Pour chacun des triangles, tu les traces par segments horizontaux, avec 2 boucles for. Si tu as les deux sommets A et B en bas, et C en haut par exemple, tu fais

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
pour y allant de yA à yC, faire
// on trace le segment horizontal à la hauteur y
// il faut calculer ses 2 extremités, avec le théoreme de Thales par exemple si tu connais
// ça doit donner un truc du genre (je suis pas sur, il faut vérifier) :
x1 = xA + (xC - xA)*(y-yA)/(yC-yA)
x2 = xB + (xC - xB)*(y-yA)/(yC-yA)
  pour x allant de x1 à x2 faire
    Tracer le point (x,y)
  fin pour
fin pour

Bon, maintenant que j'essaie d'adapter ces formules, je me rends compte que je m'embrouille dans toutes les noms de variables . Si quelqu'un peut me faire juste un croquis éxplicatif avec le noms des sommets, des heuteurs, et des droites avec Paint ?

[DrTopos]

Ah évidemment, si tu es au collège tu n'as sans doute pas vu les barycentres (autant que je me souvienne, c'est en seconde ou première). Je te donnes donc quelques explications supplémentaires.

Tes points sont soit dans le plan soit dans l'espace. Ils ont donc 2 ou 3 coordonnées. Ca n'a pas d'importance. Le principe est le même. Les sommets du triangle A, B et C ont des coordonnées (disons dans l'epace):

Code :

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

1
2
3
4
A = (a_1,a_2,a_3)
B = (b_1,b_2,b_3)
C = (c_1,c_2,c_3)

On peut aussi les considérer comme des vecteurs dans l'espace.

Si maintenant, je prends trois nombres a, b et c, je peux calculer:

Code :

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

1
2
 G = aA + bB + cC = (aa_1+bb_1+cc_1, aa_2+bb_2+cc_2, aa_3+bb_3+cc_3)

La condition pour que G soit dans le plan déterminé par A, B et C est que a+b+c = 1. Dans ce cas, on dit que G est le 'barycentre' de A, B et C, pour les 'poids' (ou 'coefficients') a, b et c.

Physiquement, ça veut dire que si tu places un poids (en plomb) qui pèse a en A, un poids qui pèse b en B et un poids qui pèse c en C, G sera le centre de gravité du système obtenu (dont le poids total sera 1).

La condition pour G soit à l'intérieur du triangle est que tous les poids soient positifs.

Ce que j'ai proposé par ailleurs permet de parcourir tout le triangle. On considère l'application qui a (a,b) associe:

Code :

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

1
2
(aa_1+bb_1+(1-a-b)c_1, aa_2+bb_2+(1-a-b)c_2, aa_3+bb_3+(1-a-b)c_3)

On fait varier a de 0 à 1, et pour chaque valeur de a on fait varier b de 0 à 1-a. De cette façon, on obtient tous les triplets (a,b,c) satisfaisant les conditions pour que G soit dans le triangle.

Maintenant, il reste le problème de la discrétisation, car tu ne dessines pas en continu, tu te contentes de colorier des pixels. Il faut donc choisir pour a une série de valeurs entre 0 et 1, de même pour b.

Considérons le cas a=0. b va varier entre 0 et 1. De cette façon, on trace le segment BC. Il faut donc mesurer la longeur de BC (théorème de pythagore), pour déterminer combien de points il faut prendre. On fera de même pour les cas où b=0, ce qui permet de tracer le segment AC. Je pense que cela suffira pour tracer complètement le triangle sans avoir de trous dedans.

Note: Je viens de voir le post de Tellmarch, qui est arrivé pendant que je tapais celui-ci. Ce qu'il propose est plus simple évidemment, mais ne s'applique qu'au cas où tu dessines dans un plan. Pour dessiner dans l'espace, c'est un peu plus compliqué évidemment.

Renote: au moment où je finis de taper cette note, je trouve la réponse de Matt2094, qui me signale qu'il est en 2D. Tout ce que je viens de raconter ne l'intéressera sans doute pas. Je poste quand même.