Algorithme de tracé de segment

Un algorithme de tracé de segment est un algorithme utilisé en infographie pour tracer approximativement un segment de droite sur des média graphiques discrets.

Sur les médias discrets, tels que les écrans ou les imprimantes avec une définition dépendant du pixel, le tracé de segment nécessite une telle approximation (en particulier, dans les cas non triviaux). Par contre, sur les médias continus, aucun algorithme n'est nécessaire pour dessiner un segment. Par exemple, les oscilloscopes analogiques ne dépendent pas d'un élément minimal affichable pour dessiner des segments et des courbes.

Un algorithme naïf de tracé de segmentModifier

On cherche à dessiner un segment entre deux points donnés par (x1, y1) et (x2, y2)

dx = x2 - x1
dy = y2 - y1
pour x de x1 à x2 faire
    y = y1 + dy * (x - x1) / dx
    plot(x, y)
fin pour

Pour cet algorithme, nous devons avoir x1 < x2. Cet algorithme fonctionne correctement lorsque dxdy, mais il est plutôt lent sur les ordinateurs car il utilise des calculs sur des nombres à virgule flottante. Si dx < dy, des trous apparaissent dans le segment et dans le cas où dx = 0, seul un point est dessiné.

Liste des algorithmes de tracé de segmentModifier

Les algorithmes suivants sont généralement utilisés pour tracer des segments :