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.

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 : 28
Đế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.

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 : 28
Đế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.

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 : 27
Đế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.

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 : 27
Đế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!

(~~/)
(~'.'~)
(_(__)~~

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 : 28
Đế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 Today at 07:38 pm


Sponsored content


Về Đầu Trang Go down

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

- Similar topics

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