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

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

1. Thuật toán Bresenham vẽ đường thẳng 1
2. Xét k<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 thẳng đượ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<k<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 Bresenham (tiếp) • Phương trình đường thẳng qua 2 điểm (x1, y1) và (x2, y2) là y=kx+m với m=Dy/Dx và m=y1-kx1. • Đặ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 Bresenham (tiếp) • d1 - d2 = (2y – 2yi – 1) là một số thực do chứa k • 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. Cài đặt thuật toán (với 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 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 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 vẽ hình sau 15