Bài giảng Thuật toán vẽ đường thẳng Bresenham

ppt 15 trang cucquyet12 7620
Bạn đang xem tài liệu "Bài giảng Thuật toán vẽ đường thẳng Bresenham", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptbai_giang_thuat_toan_ve_duong_thang_bresenham.ppt

Nội dung text: Bài giảng Thuật toán vẽ đường thẳng Bresenham

  1. Thuật toán vẽ đường thẳng Bresenham 1
  2. Mối tương quan giữa X & Y khi độ lớn hệ số góc nhỏ hơn 1 Dy Dx ➢ x tăng 1 và y giữ nguyên hay tăng 1 Điều này bảo đảm cho đường thẳng liên tục Nếu độ lớn của hệ số góc lớn hơn 1, chúng ta đổi vai trò của x & y ➢ x được gọi là giá trị độc lập và y là giá trị phụ thuộc 2
  3. Thuật toán Bresenham Giới thiệu: • Giả sử đường cong được xấp xỉ thành các điểm lần lượt là (xi,yi). Các điểm này có tọa độ nguyên và được hiển thị trên màn hình. • Bài toán đặt ra là nếu biết được tọa độ (xi,yi) của bước thứ i, thì điểm ở bước i+1 là (xi+1,yi+1) sẽ được xác định như thế nào. • Trong trường hợp hệ số góc 0<=m<=1, chúng ta có xi+1=xi+1 và yi+1=yi hay yi+1=yi+1 yi+1 yi yi-1 3 xi xi+1
  4. Thuật toán • Phương trình đường thẳng qua 2 điểm (x1, y1) và (x2, y2) là y=mx+b với m=Dy/Dx và b=y1-mx1. • Đặt d1=y-yi và d2=(yi+1)-y, do đó việc chọn tọa độ của yi+1 phụ thuộc vào d1 và d2 ( hay dấu của d1 - d2): – Nếu d1-d2<0 thì chọn yi+1=yi – Ngược lại, chọn yi+1=yi+1 yi+1 P d (xi+1,y=f(xi+1)) 2 d1 yi S xi xi+1=xi+1 4
  5. Thuật toán (cont.) • d1 - d2 = (2y – 2yi – 1) là một số thực do chứa m • Xét pi = Dx (d1 - d2) = Dx (2y - 2yi - 1) = 2Dy xi - 2Dx yi + C – C = 2Dy + (2b - 1)Dx • Do dấu của pi và (d1-d2) giống nhau nên khi xét dấu của pi thì ta xác định được yi+1 • Mặc khác, pi+1 – pi = (2Dy xi+1 - 2Dx yi+1 + C) - (2Dy xi - 2Dx yi + C) = 2Dy – 2Dx(yi+1 – yi) • Từ đây, ta suy ra cách tính pi+1 theo pi: – Nếu pi<0 thì yi+1=yi nên pi+1 = pi + 2Dy – Ngược lại thì yi+1=yi+1 nên pi+1 = pi + 2Dy – 2Dx • Giá trị p đầu tiên được tính tại (x1, y1) là p1 = 2Dy x1 -2Dx y1 + C = 2Dy – Dx 5
  6. Begin p = 2Dy - Dx; const1=2Dy; const2=2(Dy-Dx); x = x1; y = y1; putpixel(x,y,color); x<x2 End p<0 p=p+const2; p=p+const1; y = y + 1; x=x+1; putpixel(x,y,color); 6
  7. Chương trình (Dx>Dy>0) void BresenhamLine(int x1, int y1, int x2, int y2, int color) { int Dx = x2 – x1, Dy = y2 – y1; int x = x1, y = y1; int p = 2 * Dy – Dx; int const1 = 2 * Dy, const2 = 2 * (Dy-Dx); putpixel(x, y, color); while (x < x2) { if (p < 0) { p += const1; } else { p += const2; y++; } x++; putpixel(x, y, color); } } 7
  8. Tổng kết • Xác định d1 và d2 sao cho d1 là độ lệch từ y đến điểm hiện hành yi • Xác định pi sao cho pi cùng dấu với (d1 – d2) và mang giá trị nguyên • Tính pi+1 theo pi theo 2 trường hợp pi 0. Chú ý trường hợp pi = 0. • Tính p1 yi+1 P d (xi+1,y=f(xi+1)) 2 d1 yi S xi xi+1=xi+1 8
  9. Mở rộng 3 2 4 1 Dx 0,|Dx|>Dy Dx>0,Dy>0,Dx>Dy 5 8 Dx |Dy| Dx>0,Dy |Dy| 6 7 9
  10. Kết hợp vùng 1 và 8 • x tăng 1 • Vùng 1 y tăng còn vùng 2 y giảm int dy = (Dy < 0) ? -1 : 1; Dy = abs(Dy); while (x < x2) { if (p < 0) { p += const1; } else { p += const2; y += dy; } x++; putpixel(x, y, color); } 10
  11. Kết hợp vùng 1 và 4 • Vùng 1 x tăng 1, vùng 4 x giảm 1 • y tăng int dx = (Dx < 0) ? -1 : 1; Dx = abs(Dx); while (x != x2) { if (p < 0) { p += const1; } else { p += const2; y++; } x += dx; putpixel(x, y, color); } 11
  12. Kết hợp vùng 1, 4, 5, 8 • x tăng 1 khi Dx > 0, giảm 1 khi Dx 0, giảm khi Dy < 0 int dx = (Dx < 0) ? -1 : 1; Dx = abs(Dx); int dy = (Dy < 0) ? -1 : 1; Dy = abs(Dy); while (x != x2) { if (p < 0) { p += const1; } else { p += const2; y += dy; } x += dx; putpixel(x, y, color); } 12
  13. Kết hợp vùng 2, 3, 6, 7: x tính theo y • y tăng 1 khi Dy > 0, giảm 1 khi Dy 0, giảm khi Dx < 0 int dx = (Dx < 0) ? -1 : 1; Dx = abs(Dx); int dy = (Dy < 0) ? -1 : 1; Dy = abs(Dy); while (y != y2) { if (p < 0) { p += const1; } else { p += const2; x += dx; } y += dy; putpixel(x, y, color); } 13
  14. Chương trình hoàn chỉnh BresenhamLine(int x1, int y1, int x2, int y2, int color) { int Dx = x2 – x1, Dy = y2 – y1; int x = x1, y = y1; int dx = (Dx Dy) { int p = 2 * Dy – Dx; int const1 = 2 * Dy, const2 = 2 * (Dy-Dx); while (x != x2) { if (p < 0) { p += const1; } else { p += const2; y += dy; } x += dx; putpixel(x, y, color); } } else {// đổi vai trò giữa x và y } } 14
  15. Bài tập Cài đặt thuật toán Bresenham cho: 2 2 2 • Đường tròn tâm (xc,yc) bán kính R: (x-xc) + (y-yc) = R 2 2 • Đường elip tâm (xc,yc) bán kính dài là a, rộng là b: (x-xc) / a + (y- 2 2 yc) / b = 1 15