Algorithme de tracé de segment 314572 31138809 2008-06-29T21:07:55Z Grizzy Kret 319044 Un '''algorithme de tracé de segment''' est un [[Algorithmique|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 [[Moniteur d'ordinateur|écrans]] ou les [[imprimante|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 [[oscilloscope|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 <tt>(''x<sub>1</sub>'',''y<sub>1</sub>'')</tt> et <tt>(''x<sub>2</sub>'',''y<sub>2</sub>'')</tt> dx = ''x<sub>2</sub>'' - ''x<sub>1</sub>'' dy = ''y<sub>2</sub>'' - ''y<sub>1</sub>'' '''pour''' x '''de''' ''x<sub>1</sub>'' '''à''' ''x<sub>2</sub>'' '''faire''' y = ''y<sub>1</sub>'' + dy * (x - ''x<sub>1</sub>'') / dx plot(x, y) '''fin pour''' Pour cet algorithme, nous devons avoir <tt>''x<sub>1</sub>''</tt> < <tt>''x<sub>2</sub>''</tt>. Cet algorithme fonctionne correctement lorsque <tt>dx</tt> ≥ <tt>dy</tt>, mais il est plutôt lent sur les ordinateurs car il utilise des calculs sur des nombres à virgule flottante. Si <tt>dx</tt> < <tt>dy</tt>, des trous apparaissent dans le segment et dans le cas où <tt>dx</tt> = 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&nbsp;: * [[analyseur différentiel digital]] est un algorithme de tracé de segment basé sur les nombres flottants, * [[Algorithme de tracé de segment de Bresenham|algorithme de Bresenham]]&nbsp;: optimisé pour utiliser des nombres entiers, * [[Algorithme de tracé de segment de Xiaolin Wu|algorithme de Xiaolin Wu]]&nbsp;: trace des segments avec un effet d'[[anticrénelage]]. * [[Algorithme de tracé de segment fenêtré de Hadrien Flammang|algorithme de Hadrien Flammang]]&nbsp;: trace de segment fenêtré. {{Portail|informatique|mathématiques}} [[Catégorie:Algorithme d'infographie]] {{Lien_AdQ|de}} {{Lien AdQ|de}} [[bs:Algoritmi za crtanje linija]] [[de:Rasterung von Linien]] [[en:Line drawing algorithm]] [[it:Algoritmo di rasterizzazione di linea]] [[no:Linjetegningsalgoritme]] [[ru:Алгоритмы построения отрезка]] [[sr:Алгоритам за исцртавање линија]]