Tiểu luận 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

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)