Balayage d'un triangle dans un repère

Version imprimable

13/12/2008, 16h18
Arno5788

Balayage d'un triangle dans un repère

:salut:

J'ai beau me creuser mais je ne trouve pas la solution à mon problème.

Je connais les positions des 3 sommets du triangle et j'ai besoin de balayer tous les points de ce triangle (pour y mettre des pixels) mais je ne vois pas comment m'y prendre.
Est-ce que quelqu'un aurait une idée de piste à suivre ?

Merci!
13/12/2008, 17h12
pseudocode

Citation:

Envoyé par Arno5788

Est-ce que quelqu'un aurait une idée de piste à suivre ?

Un algo de remplissage scanline.

1. Tu crées un tableau à 3 colonnes [Y][X gauche][X droit]

2. Tu parcours les 3 segments de ton triangle, cela te donnes des pixels (x,y) que tu ranges dans ton tableau. Tu t'arranges pour que "X gauche" soit toujours inférieur a "X droit"

3. pour parcourir tous les pixels du triangle, tu parcours horizontalement chaque ligne du triangle => pou chaque Y tu parcours les pixels entre "X gauche" et "X droit".
13/12/2008, 17h51
Zavonen

J'aurais dit un peu la même chose que Pseudocode mais seulement avec 2 côtés.
Tu parcoures [AB] avec un point M(t) t dans [0,1]
Tu parcoures [AC] avec le même paramètre t N(t) t dans [0,1]
Pour chaque valeur de t tu parcoures le segment [[M(t)N(t)] par un point P(t,s) s dans [0,1].
Ainsi ton triangle est en bijection avec le carré (s,t) dans [0,1]x[0,1].
Tu ne t'occupes pas de question d'ordre, le triangle est balayé dans tous les cas.
13/12/2008, 18h02
Arno5788

Merci pour vos réponses claires! Je vais essayer de faire comme ça.
13/12/2008, 18h12
pseudocode

@Zavonen: le problème d'utiliser un paramètre réel entre 0 et 1, c'est le "pas" de déplacement. Trop petit et on retombe sur un pixel déjà visité, trop grand et on loupe des pixels.
14/12/2008, 09h23
Zavonen

Citation:

le problème d'utiliser un paramètre réel entre 0 et 1, c'est le "pas" de déplacement. Trop petit et on retombe sur un pixel déjà visité, trop grand et on loupe des pixels.

Bien sûr, j'ai omis de dire, et cela va de soi, qu'il fallait 'discrétiser' le processus. c'est à dire choisir un 'step' dt. On passe de M(t) au point suivant M(t+dt) et comme à chaque fois on a des coordonnées réelles, on convertit et on arrondit.

Code:

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
# -*- coding: utf-8 -*-
 
class Point:
    def __init__(self,a,b):
        self.x=int(a)
        self.y=int(b)
    def __str__(self):
        return "("+str(self.x)+","+str(self.y)+")"
 
def PointParam(t,P1,P2):#point de paramètre t du segment [AB]
    return Point(P1.x+t*(P2.x-P1.x),P1.y+t*(P2.y-P1.y))
 
def PointParamTriangle(t,s,A,B,C):#point de paramètres s,t du triangle ABC
    return PointParam(s,PointParam(t,A,B),PointParam(t,A,C))
 
def Balayage(A,B,C, dt):# dt est le step
    span=[k*dt for k in range(0,int(1.0/dt)+1)]
    print span
    return [PointParamTriangle(t,s,A,B,C) for t in span for s in span]
 
 
def main ():
    A= Point(100,200)
    B= Point(200,300)
    C=Point(400,400)
    print PointParam(0,A,B)
    print PointParam(1,A,B) 
    print PointParam(0.5,A,B)
    print PointParamTriangle(1,1,A,B,C)
    for P in Balayage(A,B,C,0.1):
        print P
 
main()

NB: le balayage ainsi réalisé n'est pas uniforme. Il y a autant de points sur les petites longueurs que sur les grandes. Pour avoir un balayage (plus) uniforme il faut bosser un peu plus, prendre pour paramètre supplémentaire la distance entre les extrêmités du segment.

15/12/2008, 19h10
Arno5788

Je vois comment faire, je connais pas du tout le langage python mais c'est pas grave. Merci pour vos réponses! je posterai mon algo dans quelques jours lorsque j'aurai trouvé du temps pour le faire

Voici quelque chose de mieux et de plus uniforme :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# -*- coding: utf-8 -*-
 
# balayage d'un triangle basé sur le fait que l'intérieur du triangle
# est l'ensemble des barycentres des 3 sommets avec des coefficients (a,b,c)
# tous positifs tels que a+b+c=1
 
def TripletsSomme(n):
    return [(i/float(n),j/float(n),(n-i-j)/float(n)) for i in range(0,n+1) for j in range(0,n+1) if j+i<=n]
 
#Les coordonnées de A
Ax,Ay=100,200
#les coordonnées de B
Bx,By=100,100
#les coordonnées de C
Cx,Cy=200,200
 
def Balayage(n):
    return [(int(Ax*t[0]+Bx*t[1]+Cx*t[2]),int(Ay*t[0]+By*t[1]+Cy*t[2])) for t in TripletsSomme(n)]
 
def main():
    print Balayage(10)
 
main()

15/01/2009, 17h39
Arno5788

Je poste finalement la solution pour laquelle j'ai opté pour le balayage du triangle. C'est surement pas la meilleure (beaucoup de tests), mais cela fonctionne en C.

Premièrement il faut englober le triangle ,dont on a les coordonnées de chaque point, par un rectangle.

Ensuite le principe sera de balayer ce rectangle et de regarder si chaque point fait partie ou non du triangle. On va appeler P le point que l'on teste.

Il faut calculer l'équation de droite de [AB] (sous la forme a*x +b) et regarder le signe de C par rapport à AB, en remplaçant a et b par les coordonnées de C. Faire de même avec [AB] et P. Si les deux signes sont les même, les C et P seront du même côté de AB.

Ensuite refaire ceci pour chaque côté. Si à chaque fois, P et 3eme côté du triangle sont de même signe, P sera dans le triangle.

Désolé si mes explications ne sont pas très claires, j'espère que vous aurez compris le principe.
20/01/2009, 22h11
b_reda31
Salut,
Alors si je comprend bien le principe est de vérifier pour chaque coté du triangle si le point P et le troisième point du triangle sont dans le même sous-plan délimité par la droite du coté en question.

Citation:

Il faut calculer l'équation de droite de [AB] (sous la forme a*x +b) et regarder le signe de C par rapport à AB, en remplaçant a et b par les coordonnées de C. Faire de même avec [AB] et P. Si les deux signes sont les même, les C et P seront du même côté de AB.

Avez vous testé cela?

D'une manière générale un droite d'equation Ax+By+C = 0 sépare le plan en deux sous-plans :
- Ax+By+c<0
- Ax+By+c>0
Il faudra donc remplacer x et y (dans l'équation de la droite : Ax+By+c) par les coordonnées des point P et le troisiéme point du triangle et comparer le signe du résultat obtenu pour chaque point afin de voir s'ils sont dans le même sous-plan.