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

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

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

Bài gửi by nth on 19/10/09, 08:05 pm

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);
}
}


Được sửa bởi nth ngày 23/01/10, 11:04 pm; sửa lần 2.
avatar
nth
Admin
Admin

Tổng số bài gửi : 550
Số điểm : 1113
Số lần được cám ơn : 33
Ngày đến diễn đàn: : 01/08/2009
Tuổi : 29
Đến từ : Thiên Đường

Xem lý lịch thành viên http://thuhuong.hot4um.com

Về Đầu Trang Go down

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

Bài gửi by nth on 19/10/09, 08:07 pm

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.
avatar
nth
Admin
Admin

Tổng số bài gửi : 550
Số điểm : 1113
Số lần được cám ơn : 33
Ngày đến diễn đàn: : 01/08/2009
Tuổi : 29
Đến từ : Thiên Đường

Xem lý lịch thành viên http://thuhuong.hot4um.com

Về Đầu Trang Go down

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

Bài gửi by anbinhtrong on 30/11/09, 10:21 pm

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ành viên Forum Thien Than CNTT ====
The only way to begin is to begin.
avatar
anbinhtrong
Mod
Mod

Tổng số bài gửi : 77
Số điểm : 142
Số lần được cám ơn : 32
Ngày đến diễn đàn: : 18/10/2009
Tuổi : 28
Đến từ : BT

Xem lý lịch thành viên http://khoahockithuat.blogspot.com

Về Đầu Trang Go down

MidPoint hay Bresenham

Bài gửi by anbinhtrong on 14/12/09, 09:38 pm

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);
}
}

}

===== Thành viên Forum Thien Than CNTT ====
The only way to begin is to begin.
avatar
anbinhtrong
Mod
Mod

Tổng số bài gửi : 77
Số điểm : 142
Số lần được cám ơn : 32
Ngày đến diễn đàn: : 18/10/2009
Tuổi : 28
Đến từ : BT

Xem lý lịch thành viên http://khoahockithuat.blogspot.com

Về Đầu Trang Go down

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

Bài gửi by nth on 15/12/09, 09:35 am

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.

===== Thành viên Forum Thien Than CNTT ====
Nothing!

(~~/)
(~'.'~)
(_(__)~~
avatar
nth
Admin
Admin

Tổng số bài gửi : 550
Số điểm : 1113
Số lần được cám ơn : 33
Ngày đến diễn đàn: : 01/08/2009
Tuổi : 29
Đến từ : Thiên Đường

Xem lý lịch thành viên http://thuhuong.hot4um.com

Về Đầu Trang Go down

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

Bài gửi by Sponsored content


Sponsored content


Về Đầu Trang Go down

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang


 
Permissions in this forum:
Bạn không có quyền trả lời bài viết