모든 점을 줄 넘김

Question

줄에있는 모든 점을 찾아야합니다. 나는 Bresenham의 알고리즘을 시도했지만 다음과 같은 경우에 작동하지 않습니다

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

X 실제 라인, .이 Bresenham 알고리즘 리턴, 줄을 알 것입니다 (1, 0) 교차하지만이 표시되지 않습니다.
효율적으로 선을 통과하는 모든 픽셀을 어떻게 찾을 수 있습니까? 이 앤티 앨리어싱이 필요하지 않으므로 Wu의 알고리즘이 과도하다고 생각합니다. 선 종점은 픽셀의 중간에 있습니다.

내가 가지고있는 알고리즘을 참조 할 수있다 :

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

음, 단지 명백한 간단한 알고리즘을 구현 : 라인의 한쪽 끝에서 시작이 교차 시작 정사각형의 어느 쪽을 찾아 해당로 이동 인접한 사각형 ... 등등. 마무리 스퀘어에이를 때까지 걷습니다.

정수로 구현하는 가장 간단한 방법은 슈퍼 픽셀 정밀도로 전환하는 것입니다. 모든 것을 상수 계수로 곱하면됩니다. 어려운 부분은 충분한 정수 범위가 충분하지 않아서 충분히 곱할 수 없다는 것을 발견했을 때부터 시작됩니다 ... 이것이 귀하의 경우에 해당하는지는 잘 모르겠습니다.