Thuật toán vẽ Đường Thẳng

Thuật DDA:
Tư tưởng chính
Giả sử ta có phương trình đường thẳng y = ax + b
mỗi khi tăng x 1 đơn vị thì sự lựa chọn y = y + 1 hay bằng y phụ thuộc vào phương trình y = ax + b (vì để vẽ đường thẳng này ta phải xét đến pixel x và y không thể là số thực mà phải làm tròn thành số nguyên).
sau khi tăng x 1 đơn vị
x = x + 1.
thì
y = a(x + 1) + b.
như vậy y(i + 1) = round(y)
ta thấy yi = ax + b và y(i+1) = ax + b + a.
=> y(i + 1) = yi + a.
do đó y(i + 1) = round(yi + a).

public void Swap(ref int x1, ref int y1, ref int x2, ref int y2)
        {
            int a, b;
            a = x1;
            b = y1;

            x1 = x2;
            y1 = y2;

            x2 = a;
            y2 = b;
        }
public void DrawLineDDA(int x1, int y1, int x2, int y2, Color color)
 {
            ArrStep = new ArrayList();
            int i = y1;
            if (x1 == x2 && y2 > y1)
            {
                for (i = y1; i < y2; i++)
                {
                    SetPixel(x1, i, color);
                //hàm này tự viết, tùy trên mỗi môi trường lập trình
                }
                return;
            }
            if (x1 > x2)
                Swap(ref x1, ref y1, ref x2, ref y2); //Hoan vi 2 diem
            int x = x1;
            float y = y1;
            int Dx = x2 - x1;
            int Dy = y2 - y1;
            float m = (float)Dy / Dx;
            float b = y1 - m * x1;
                for (x = x1; x < x2; x++)
                {
                    y = m * x + b;
                    SetPixel(x, (int)Math.Round(y), color);
                }
}

Vẽ đường thẳng bằng thuật toán MidPoint

Thuật toán Midpoint đưa ra cách chọn y(i+1) là yi hay yi + 1 bằng cách so sánh điểm thực Q(xi + 1, y), trên đường thẳng
giả sử điểm S(xi, yi) và P(xi, yi + 1) với điểm MidPoint là trung điểm của S và P, ta có
Nếu Q nằm dưới MidPoint thì ta chọn S
Nếu Q nằm trên MidPoint thì ta chọn P (xem hình).
ta có dạng tổng quát của phương trình đường thẳng:
Ax + By + C = 0 với A = y2 - y1, B = -(x2 - x1), C = x2y1 - x1y2.
Đăt F(x, y) = Ax + By + C ta có:
F(x,y) < 0 nếu (x,y) nằm trên đường thẳng.
F(x,y) = 0 nếu (x, y) thuộc đường thẳng.
F(x,y) > 0 nếu (x,y) nằm dưới đường thẳng

Lúc này việc chọn các điểm S, P ở trên được đưa về việc xét dấu của pi = 2F(MidPoint) = 2F(xi + 1, yi + 1/2).
Nếu pi < 0, điểm MidPoint nằm phía trên đoạn thẳng. Lúc này điểm Q nằm dưới điểm MidPoint nên ta chọn điêm S, tức là y(i+1) = yi.
Ngược lại, Nếu pi >= 0, điểm MidPoint nằm phía dưới đoạn thẳng. Lúc này điểm Q nằm trên điểm MidPoint nên ta chọn điêm P, tức là y(i+1) = yi + 1.

Mặt khác ta có: p(i+1)-p(i)=2F(x(i+1)+1, y(i+1)+1/2)-2F(x(i)+1, y(i)+1/2).
<=> 2[A(x(i+1) + B(y(i) + 1/2) + C] + 2[A(x(i) + 1) + B(y(i) + 1/2) + C].
<=> 2A + 2B(y(i+1) - y(i)) = 2Dy - 2Dx(y(i+1) - y(i)).

Như vậy:

p(i+1) = P(i) + 2Dx. nếu p(i) < 0 do ta chọn y(i+1) = y(i)
p(i+1) = p(i) + 2Dy - 2Dx nếu p(i) >= 0, do ta chọn y(i+1) = y(i)+1.
Tính giá trị p(0) ứng với điểm ban đầu (x0, y0). Ta thấy (x0, y0) là điểm thuộc đường thẳng => Ax0 + By0 + C = 0.
p0 = 2F(x0+1, y0 + 1/2) = 2[A(x0+1) + B(y0 + 1/2) + C]
p0 = 2(Ax0 + By0 + C) + 2A + B = 2A + B = 2Dy - Dx.

ah, vậy là trong bài vẽ đường thẳng, Bresenham và MidPoint cùng 1 đoạn code vì p0 và p(i+1) giống nhau???

Thực ra trong bài vẽ đường thẳng, mình thấy MidPoint và Bresenham đều lập trình giống nhau, chỉ khác nhau ý tưởng ban đầu thôi.
Nhưng mình đọc Bresenham, lấy ý tưởng MidPoint làm bài, và cuối cùng cũng ra. Chú ý kĩ Dy, Dx và đặt câu hỏi why,how, chắc chắn bạn sẽ hiểu và tự lập trình, không cần nhớ công thức.

void Bresenham(int x1, int y1, int x2, int y2)
{
    bool flag=0;
    int p,const1,const2;
    int Dy,Dx;
    int i,tang;
    if(abs(x1-x2)<abs(y1-y2))
    {
        flag=1;        
        swap(x1,y1);
        swap(x2,y2);
    }    
    if(x1>x2)
    {
        swap(x1,x2);
        swap(y1,y2);
    }
    //---------Tinh Bresenham------------
    Dy=y2-y1;
    Dx=x2-x1;
    //--------Tinh huong tang cua Dy
    if(Dy>0) tang=1;
    else 
    {
        tang=-1;
        Dy=Dy*-1;
    }
    p=2*Dy-Dx;
    const1=2*Dy;
    const2=2*(Dy-Dx);
    putpixel(x1,y1);
    if(flag==0)
    {
        for(i=x1;i<x2;i++)
        {
            if(p<0)    p=p+const1;
            else
            {
                p=p+const2;
                y1+=tang;
            }
            x1++;        
            putpixel(x1,y1);
        }        
    }
    else
    {
        for(i=x1;i<x2;i++)
        {
            if(p<0)    p=p+const1;
            else
            {
                p=p+const2;
                y1+=tang;
            }
        x1++;
        putpixel(y1,x1);
        }        
    }
    
}

vậy ư? Thank bạn thật nhìu bài này nha, cái Bresenham này mình cũng chưa hiểu rõ nữa.