Giải thuật Bresenham

Xét đoạn thẳng với 0 < k < 1
Gọi (xi+1,y) là điểm thuộc đoạn thẳng, ta có y=k(xi+1)+b
d1 = y - yi = k(xi +1) + b - yi
d2 = yi+1 - y = yi + 1 - k(xi + 1) - b
- Nếu d1 <= d2 => yi+1 = yi
- Ngược lại d1 > d2 => yi+1 = yi +1
Đặt D = d1 - d2= 2k(xi + 1) - 2yi + 2b - 1
Có k=Δy/Δx
Đặt Pi = ΔxD = Δx (d1 - d2)
Pi = Δx(2Δy/Δx(xi +1)- 2yi +2b-1)
= 2Δyxi +2Δy -2Δxyi + 2bΔx -Δx
Ta tính bước tiếp:
Pi+1 = 2Δyxi+1 +2Δy -2Δxyi+1 + 2bΔx -Δx
Pi+1 - Pi = -2Δx(yi+1 -yi) + 2Δy(xi+1 -xi)
Có xi+1 =xi+1 nên:
Pi+1 - Pi = - 2Δx(yi+1 -yi) + 2Δy = 2Δy - 2Δx(yi+1 -yi)
Nếu Pi <= 0 thì yi
+1 = yi
Pi+1 = Pi + 2Δy
Nếu Pi > 0 thì yi+1 = yi +1
Pi+1 = Pi + 2Δy - 2Δx
Tính giá trị đầu: P1?
P1 = Δx(d1 - d2)
= Δx(2Δy/Δx(x1 +1)- 2y1 +2b-1)
= 2Δyx1 +2Δy -2Δxy1 + 2bΔx -Δx
Có y1=kx1 + b = Δy/Δx x1 +b
P1 = 2Δyx1 +2Δy -2Δx((Δy/Δx)x1 +b) + 2bΔx -Δx
= 2Δyx1 +2Δy -2Δyx1 - 2bΔx + 2bΔx -Δx
P1 = 2Δy - Δx


cài đặt Chương trình
/*Thuat toan Bresenham ve dthang (0<k<1) */
void Bre_line(int x1, int y1, int x2, int y2, int c)
{int x, y, dx, dy,p,const1,const2;
y = y1;
dx = x2 - x1;
dy = y2 - y1;
p = 2*dy - dx;
const1 = 2*dy;
const2 = 2*(dy-dx);
for (x=x1; x<=x2; x++) {
putpixel(x, y, c);
if (p < 0)
p += const1; // p=p + 2dy
else {
p +=const2; //p=p+2dy-2dx
y++;
}
}
}

mình đang thắc mắc các trường hợp k còn lại. nếu mình đặt d1 với d2 ngược nhau có được không vậy:D