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édia 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édia 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 segment

On cherche à dessiner un segment entre deux points donnés par (x₁,y₁) et (x₂,y₂)

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 x₁ < x₂. Cet algorithme fonctionne correctement lorsque dx ≥ dy, 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 segment

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

• analyseur différentiel digital est un algorithme de tracé de segment basé sur les nombres flottants,
• algorithme de Bresenham : optimisé pour utiliser des nombres entiers,
• algorithme de Xiaolin Wu : trace des segments avec un effet d'anticrénelage.