Discussion :

[Arno5788]

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!

[pseudocode]

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".

[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.

[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.

[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.

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.

[Zavonen]

Code Python :

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
# -*- 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.

[Arno5788]

Merci pour vos réponses claires! Je vais essayer de faire comme ça.