Đề tài Viết chương trình thể hiện các thuật toán vẽ đoạn thẳng qua hai điểm cho trước
XÂY DỰNG THUẬT TOÁN
Phương trình đường thẳng có thể phát biểu dưới dạng: y = m.x + b (1)
Phương trình đường thẳng qua 2 điểm:
= (*)
Đặt x = x2 - x1
y = y2 - y1
(*) y = x. + y1 - x1.
Suy ra m = nên y = m. x (2)
b = y1 - m.x1 (3)
Ta chỉ xét trường hợp hệ số góc 0<m<1.
Giả sử điểm (xi,yi) đã được vẽ. Ta phải chọn điểm kế tiếp là:
(xi + 1,yi) hoặc (xi +1,yi +1) (Xem hình 1.2)
Xét khoảng cách giữa 2 điểm chọn với điểm nằm trên đường thực. Nếu khoảng cách nào bé hơn thì ta lấy điểm đó.
14 trang |
Chia sẻ: lvcdongnoi | Lượt xem: 3585 | Lượt tải: 1
Bạn đang xem nội dung tài liệu Đề tài Viết chương trình thể hiện các thuật toán vẽ đoạn thẳng qua hai điểm cho trước, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
TRƯỜNG CAO ĐẲNG CÔNG NGHỆ HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
BÀI TIỂU LUẬN
ĐỀ TÀI:
VIẾT CHƯƠNG TRÌNH THỂ HIỆN CÁC THUẬT TOÁN VẼ ĐOẠN THẲNG QUA HAI ĐIỂM CHO TRƯỚC
Giáo viên hướng dẫn:
Bùi Thế Truyền
Sinh viên thực hiện:
Đào Khắc Tuấn
Nguyễn Văn Linh
Lê Ngọc Tuyền
Lương Văn Thượng
Nguyễn Thị Phượng
Nguyễn Thị Quý
Lớp :
CNTT2 – K2
Hà Nội, tháng 6 năm 2010
Lời nói đầu
Đồ họa máy tính được ra đời bởi sự kết hợp của 2 lĩnh vực thông tin và truyền hình.Đầu tiên kỹ thuật đồ họa được phát triển bởi các nhóm kỹ sư sử dụng máy tính lớn. Trong giai đoạn đầu của sự phát triển người ta phải tốn nhiều tiền cho việc trang bị các thiết bị phần cứng. Ngày nay, nhờ vào sự tiến bộ của vi xử lý, giá thành của máy tính càng lúc càng phù hợp với túi tiền của người sử dụng trong khi các kỹ thuật ứng dụng đồ họa của nó ngày càng cao hơn nên có nhiều người quan tâm nghiên cứu đến lĩnh vực này.
Chúng ta có thể vẽ ra những hình ảnh không chỉ là ảnh tĩnh mà còn có thể biến đổi thành những hình ảnh sinh động qua các phép quay, tịnh tiến... Do vậy, đồ họa máy tính trở thành một lĩnh vực lý thú và có nhiều ứng dụng trong thực tế.
Bài tập lớn này bao gồm 4 phần:
PHẦN I: LƯU ĐỒ THUẬT TOÁN BRESENHAM
PHẦN 2: XÂY DỰNG THUẬT TOÁN
PHẦN III: VÍ DỤ
PHẦN IV: CHƯƠNG TRÌNH CHẠY
I :LƯU ĐỒ THUẬT TOÁN BRESENHAM
Begin
p=2Dy-Dx;
Const1=2Dy;
Const2=2(Dy-Dx);
x=x1;
y=y1;
putpixel(x, y, c);
x<x2 No
Yes
p<0
p=p+Const2;
y=y+1
End
x=x+1;
putpixel(x,y,c);
p=p+Const1;
Yes
II: XÂY DỰNG THUẬT TOÁN
Phương trình đường thẳng có thể phát biểu dưới dạng: y = m.x + b (1)
Phương trình đường thẳng qua 2 điểm:
= (*)
Đặt Dx = x2 - x1
Dy = y2 - y1
(*) Û y = x. + y1 - x1.
Suy ra m = nên Dy = m. Dx (2)
b = y1 - m.x1 (3)
Ta chỉ xét trường hợp hệ số góc 0<m<1.
Giả sử điểm (xi,yi) đã được vẽ. Ta phải chọn điểm kế tiếp là:
(xi + 1,yi) hoặc (xi +1,yi +1) (Xem hình 1.2)
Xét khoảng cách giữa 2 điểm chọn với điểm nằm trên đường thực. Nếu khoảng cách nào bé hơn thì ta lấy điểm đó.
Đặt:
d1 = y - yi = m.(xi +1) + b - yi
d2 = (yi +1) - y = yi + 1 - m.(xi + 1) - b
Suy ra:
d1 - d2 = 2m.(xi + 1) - 2yi + 2b - 1
= 2. .(xi + 1) - 2yi + 2b - 1
Û Dx(d1 - d2) = 2Dy.xi - 2Dx.yi + 2Dy + Dx.(2b - 1)
Đặt pi = Dx(d1 - d2) và C = 2Dy + Dx.(2b - 1)
thì pi = 2Dy.xi - 2Dx.yi + C (4)
pi+1 = 2Dy.xi+1 - 2Dx.yi+1 + C
Suy ra:
pi+1 - pi = 2Dy(xi+1 - xi) - 2Dx(yi - yi+1)
= 2Dy - 2Dx(yi+1 - yi) (5)
( vì xi+1 - xi = 1 )
* Nhận xét:
. Nếu pi < 0: Chọn yi+1 = yi Từ (5) Þ pi+1 = pi + 2Dy. (d1<d2)
. Nếu pi ³ 0: Chọn yi+1 = yi + 1 Từ (5) Þ pi+1 = pi + 2Dy - 2Dx. (d1>d2)
Với điểm mút đầu tiên, theo (4) ta có:
p1 = 2Dy.x1 - 2Dx.y1 + 2Dy + Dx[2.(y1 - m.x1) - 1] = 2Dy - Dx
Từ đó, ta có thể tóm tắt thuật toán vẽ đường thẳng theo Bresenham cho trường hợp hệ số góc 0<m<1 như sau:
· Bước 1: Nhập các điểm đầu mút. Điểm đầu mút bên trái chứa tọa độ (x1,y1), điểm đầu mút bên phải chứa tọa độ (x2,y2).
· Bước 2: Điểm được chọn để vẽ đầu tiên là (x1,y1).
· Bước 3: Tính Dx = |x2 - x1| , Dy = |y2 - y1| và P1 = 2Dy - Dx
Nếu pi < 0 thì điểm kế tiếp là (xi + 1,yi)
Ngược lại: điểm kế tiếp là (xi + 1,yi + 1)
· Bước 4: Tiếp tục tăng x lên 1 Pixel. Ở vị trí xi +1, ta tính:
pi+1 = pi + 2Dy nếu pi < 0
pi+1 = pi + 2.( Dy - Dx) nếu pi ³ 0
Nếu pi+1 < 0 thì ta chọn toạ độ y kế tiếp là yi+1
Ngược lại thì ta chọn yi+1 +1
· Bước 5: Lặp lại bước 4 cho đến khi x = x2.
Sau đây là thủ tục cài đặt thuật toán:
Procedure LINE(x1,y1,x2,y2:integer); { 0<m<1}
var dx,dy,x,y,p,c1,c2,xMax:integer;
Begin
dx:=abs(x1-x2);
dy:=abs(y1-y2);
c1:=2*dy;
c2:=2*(dy-dx);
p:=2*dy-dx;
if x1>x2 then
begin
x:=x2; y:=y2; xMax:=x1;
end
else
begin
x:=x1;y:=y1;xMax:=x2;
end;
putpixel(x,y,red);
while x<xMax do
begin
x:=x+1;
if p<0 then p:=p+c1
else begin
y:=y+1;
p:=p+c2;
end;
putpixel(x,y,red);
end;
end;
III.VÍ DỤ
Cho A(12,20) và B(22,27)
Ta có:
Dx=22-12=10 , Dy=27-20=7
Const1=2Dy=14 , Cost2=2(Dx-Dy)=-6
Po=2Dy-Dx=14-10=4
i
Xi
Yi
Pi
0
12
20
4
1
13
21
-2
2
14
21
12
3
15
22
6
4
16
23
0
5
17
24
-6
6
18
24
8
7
19
25
2
8
20
26
-4
9
21
26
10
10
22
27
4
Cài đặt chương trình bằng thuật toán Bresenham
void LineBres (int x1, int y1, int x2, int y2)
{
int Dx, Dy, p, Const1, Const2;
int x, y;
Dx = x2 - x1;
Dy = y2 - y1;
p = 2*Dy - Dx; // Dy <<1 - Dx
Const1 = 2*Dy; // Dy <<1
Const2 = 2*(Dy-Dx); // (Dy-Dx) <<1
x = x1;
y = y1;
putpixel(x, y, Color);
for(i=x1; i<x2; i++)
{
if (p<0)
p += Const1;
else
{
p += Const2;
y++;
}
x++;
putpixel(x, y, Color);
}
} // LineBres
IV:CHƯƠNG TRÌNH CHẠY
Chúng em thiết kế chạy trên chương trình C++
#include
#include
#include
#include
#include
#include
#include
void khoitao()
{
int gdriver = DETECT, gmode, errorcode;
initgraph(&gdriver, &gmode, "C:\\tc\\bgi");//Duong dan den thu muc bgi
errorcode = graphresult();
if (errorcode != grOk)
{
cout<<"\n Graphics error: "<<grapherrormsg(errorcode)
<<"\n Press any key to halt:";
getch();
exit(1);
}
}
//===============VE DUONG THANG VOI THUAT TOAN MIDPOINT==================
void midpoint(int x1,int y1,int x2,int y2,int val)
{
int tx=x2-x1,ty=y2-y1;
if (tx>=0)
if (ty>=0)
if (ty>=tx)//goc 2
{
int tg = x1; x1 = y1; y1 = tg;
tg = x2; x2 = y2; y2 = tg;
}
else endl;
else //if (ty<0)
if(tx>=-ty)//goc 8
{
y1 = -y1;
y2 = -y2;
}
else //if(-ty>tx && tx>0 && ty<0)//goc 7 doi xung voi goc 3 qua goc
{
x1 = -x1; x2 = -x2;
int tg = x1; x1 = y1; y1 = tg;
tg = x2; x2 = y2; y2 = tg;
int tg1 = x1, tg2 = y1;
x1 = x2; y1 = y2;
x2 = tg1; y2 = tg2;
}
if(tx<0)
if(ty>0)
if(ty>=-tx)// && tx0)//goc 3 tinh thong qua goc 4
{
x1 = -x1; x2 = -x2;
int tg = x1; x1 = y1; y1 = tg;
tg = x2; x2 = y2; y2 = tg;
}
else
//if(-tx>ty && ty>0 && tx<0)//goc 4
{x1=-x1;x2=-x2;}
else
if(-ty>=-tx)// && tx<0 && ty<0)//goc 6
{
int tg = x1; x1 = y1; y1 = tg;
tg = x2; x2 = y2; y2 = tg;
int tg1 = x1, tg2 = y1;
x1 = x2; y1 = y2;
x2 = tg1; y2 = tg2;
}
else
// if(-tx>-ty && ty<0 && tx<0)//goc 5
{
int tg1 = x1, tg2 = y1;
x1 = x2; y1 = y2;
x2 = tg1; y2 = tg2;
}
int dx=x2-x1,dy=y2-y1;
int d=dy-dx/2,x=x1,y=y1;
while(x<x2)
{
if(d<=0) d+=dy;
else{d+=dy-dx;y++;}
++x;
if ((ty>=tx && tx>=0 && ty>=0)||(-ty>=-tx && tx<0 && ty<0)) putpixel(y,x,val);//goc 2 va goc 6
else if (tx>=-ty && tx>0 && ty<0) putpixel(x,-y,val);//goc 8
else if ((ty>=-tx && tx0)||(-ty>=tx && tx>=0 && ty<=0)) putpixel(-y,x,val);//goc 3 va goc 7
else if (-tx>=ty && tx0) putpixel(-x,y,val);//goc 4
else putpixel(x,y,val);//goc 1 va goc 5
}
}
void main()
{
khoitao();
clrscr();
cleardevice();
setbkcolor(0);
int x1,y1,x2,y2,c;
cout>x1;cout>y1;
cout>x2;cout>y2;
cout>c;
clrscr();
cleardevice();
setbkcolor(0);
midpoint(x1,y1,x2,y2,c);
getch();
}
NHẬN XÉT CỦA GIÁO VIÊN
……………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………
Giáo viên nhận xét
(ký tên)
Các file đính kèm theo tài liệu này:
- Viết chương trình thể hiện các thuật toán vẽ đoạn thẳng qua hai điểm cho trước.doc