Tracé manuel d'un triangle

Bonjour à tous,:D

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.:)

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+

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:

---

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.

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é ? :roll: :lol: :)

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:

---

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

---

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 :oops: :roll:

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:

---

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:

---

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:

---

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.

Quand le triangle est quelconque, tu peux le découper en 2 triangles en faisant passer une droite horizontale par le sommet qui est à la hauteur intermédiaire.
Les 2 triangles ont alors un coté horizontal, et tu peux les dessiner avec l'algorithme que j'ai donné...
par exemple pour tracer le triangle A(1,2) B(5,4) C(4,6), tu rajoutes le point D du segment [AC] qui est à la meme hauteur que B, et tu traces les 2 triangles ADB et DBC qui ont tous les deux le coté DB horizontal.
Pour trouver les coordonnées de D, c'est encore le théoreme de thales qu'il faudrait appliquer, ça doit etre (xC - xA) * (yB - yA)/(yC - yA) dans ce cas là...

Dans le cas général, il faut donc trouver le sommet le plus bas, le plus haut, et le sommet intermédiaire, puis calculer le nouveau sommet D avec la formule que j'ai donnée, où C est le plus haut sommet, et A le plus bas.

Ensuite tu peux appliquer l'algorithme que j'ai donné avant.

PS : j'espere que je n'ai pas fait d'erreur dans mes formules, c'est pas sur du tout :roll:

Merci à tous les deux. J'ai réussi à comprendre ! Pour ce qui est du fait que les formules soit fausses ou pas, je les teste, et je vous dis s'il y a un problème. DrTopos, il est vrai que tu as écrit ce message un peu pour rien, mais j'ai quand même appris des trucs sur les barycentres, par exemple. Merci encore !:D

Citation:

---

Envoyé par 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:

---

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 8O :( . Si quelqu'un peut me faire juste un croquis éxplicatif avec le noms des sommets, des heuteurs, et des droites avec Paint ?:roll: :? :)

Bonjour, voila la figure du triangle avec le nom des points et leurs coordonnées...
l'algorithme consiste à faire varier y de yA à yC, puis de tracer le segment en faisant varier x de x1 à x2.

Merci, c'est plus clair maintenant.:D