Tous les points traversés par une ligne

Question

Je dois trouver tous les points qui sont sur une ligne. J'ai essayé l'algorithme de Bresenham mais il ne fonctionne pas sur le cas suivant:

(0, 0) 
.-----------+-----------+-----------. 
|...........|   |   | 
|...........|   |   | 
|.....XXXX..|   |   | 
|........XXXX   |   | 
|...........XXXXX  |   | 
+-----------+---XXXX----+-----------+ 
|   |......XXXXX|...........| 
|   |..........XXXX.........| 
|   |...........|.XXXXX.....| 
|   |...........|...........| 
|   |...........|...........| 
`-----------+-----------+-----------´ 
           (2, 1) 

X est la ligne réelle, . est ce que le rendement de l'algorithme de Bresenham, notez la ligne traverse (1, 0) mais ce n'est pas marqué.
Comment puis-je trouver tous les pixels qu'une ligne traverse efficacement? Je n'ai pas besoin de cet anti-aliasé donc je pense que l'algorithme de Wu est une overkill. Les points de terminaison de ligne sont au milieu des pixels.

Pour référencer l'algorithme que j'ai est:

int dx = System.Math.Abs(x0 - x1); 
int dy = System.Math.Abs(y0 - y1); 

int sx = x0 < x1 ? 1 : -1; 
int sy = y0 < y1 ? 1 : -1; 

int err = dx - dy; 

int lx = x0; 
int ly = y0; 

for(int i = 0; true; i++) 
{ 
    Mark(x0, y0); 

    if(x0 == x1 && y0 == y1) 
     break; 

    int e2 = err * 2; 
    if(e2 > -dy) 
    { 
     err -= dy; 
     x0 += sx; 
    } 
    if(e2 < dx) 
    { 
     err += dx; 
     y0 += sy; 
    } 
} 

Answer 1

Eh bien, mettre en œuvre l'algorithme simple évident: départ d'un bout de la ligne, trouver quel côté de la, il case de départ traverse, sauter au correspondant carré adjacent ... et ainsi de suite. Marcher jusqu'à la place d'arrivée. La manière la plus simple de l'implémenter en nombres entiers serait de passer à la précision du superpixel: il suffit de tout multiplier par un facteur constant. La partie difficile commence lorsque vous découvrez que vous n'avez pas assez de gamme entière pour le multiplier suffisamment ... Je ne sais pas si c'est le cas dans votre cas.