Bài giảng Đồ họa Raster - Chương 1, Phần 2: Các thuật toán vẽ đường tròn - Bùi Tiến Lên

ĐỒ HỌA RASTERCÁC THUẬT TOÁNVẼ ĐƯỜNG TRÒNGiảng viên : Bùi Tiến LênTrang 2Phân loại đường trònĐường tròn tâm OOOĐường tròn tâm bất kỳTrang 3Ứng dụng phép tịnh tiếnNếu (x, y) thuộc đường tròn tâm OThì (x + xc, y + yc) thuộc đường tròn tâm (xc, yc)O(xc, yc)(x, y)(x+xc, y+yc)Trang 4Phương trình đường trònOrTrang 5Tính đối xứng của đường trònĐường tròn có 4 trục đối xứng -Trục Ox-Trục Oy-Trục phân giác thứ nhất-Trục phân giác thứ haiOxyphân giác 1phân giác 2Trang 6Ứng dụng tính đối xứngNếu (x, y) thuộc đường trònThì (-x, y), (x, -y), (-x, -y), (y, x), (-y, x), (y, -x) và (-y, -x) thuộc đường trònO12345678chọnTrang 7Vẽ cung một phần tám thứ nhấtInput r bán kínhOutput {(x1, y1), (x2, y2) (xn, yn)} “thuộc” cung một phần tám thứ nhấtOABTrang 8Khảo sát cung một phần tám thứ nhấtMục tiêu khảo sát sự biến thiên của hoành độ và tung độTrang 9Khảo sát cung 1/8 thứ nhấtBảng biến thiênĐường cong giảm chậmTrang 10Thuật toán trực tiếpTrang 11Thuật toán MidPointDự đoán điểm sáng thứ i+1iABTrang 12Thuật toán MidPoint- Khái niệm bên trong / bên ngoài đường tròn- Hàm kiểm tra một điểm bên trong / bên ngoài đường tròn F(x, y) = x2 + y2 – r2- Cách kiểm trabên trongbên ngoàiP(x, y)F(x, y)beân trong 0Trang 13Thuật toán MidPointXây dựng biến fiTrung điểm M của AB M(xi + 1, yi – 1/2)Biến fi fi = F(M) fi = F(xi + 1, yi – 1/2)iBAMyi-1/2xixi+1yiyi-1Trang 14Thuật toán MidPointCông thức tính fiCông thức tính fi nguyênTrang 15Khi fi không nguyên !Có hai cách giải quyết để fi thành nguyênCách 1 fi 0Cách 2 fi < 0  [fi] < 0 fi  0  [fi]  0Trang 16Thuật toán MidPointThuật toánBước 1 Xác định điểm đầu tiên x1 = 0 y1 = rBước 2 Xác định những điểm tiếp theoLặp xi < yi fi = fi < 0 xi+1 = xi + 1 yi+1 = yi fi ≥ 0 xi+1 = xi + 1 yi+1 = yi – 1 Trang 17Thuật toán MidPointCách tính fi cải tiến f1 = 1 – r fi < 0 fi+1 = fi + 2xi + 3fi  0 fi+1 = fi + 2xi – 2yi + 5