- Chương 2 : CÁC THUẬT TOÁN TÔ MÀU. - Hiểu được khái niệm về không gian màu RGB,CMY, HSV.. - Thiết kế và cài đặt được các giải thuật tô màu.. - Kiến thức tin học : lập trình cấu trúc dữ liệu, cách lưu trữ và xây dựng mãng dữ liệu chứa các giao điểm của đường thẳng và đa giác.. - Trình bày các không gian màu RGB, CMY, HSV. - Giới thiệu các thuật toán tô màu bao gồm : tô đơn giản, tô theo đường biên và tô scan-line. - Các không gian màu. - Không gian màu RGB (Red - Green - Blue). - Không gian màu RGB mô tả màu sắc bằng 3 thành phần chính là Red - Green và Blue. - Mỗi màu trong không gian này được xác định bởi 3 thành phần R, G, B. - Hình 2.1 : Không gian màu RGB.. - Trong hình lập phương trên (xem hình 2.1), mỗi màu gốc (R,G,B) có các gốc đối diện là các màu bù với nó. - Không gian màu CMY (Cyan - Magenta - Yellow). - Tương tự như không gian màu RGB nhưng 3 thành phần chính là Cyan - Magenta - Yellow. - Do đó, tọa độ các màu trong không gian CMY trái ngược với không gian RGB. - Không gian màu HSV ( Hue - Saturation - Value. - Không gian HSV được mô tả bằng lệnh lập phương RGB quay trên đỉnh Black. - Hình 2.2 : Không gian màu HSV.. - Các thuật toán tô màu. - Tô màu một vùng là thay đổi màu sắc của các điểm vẽ nằm trong vùng cần tô.. - Dạng đường biên đơn giản thường gặp là đa giác.. - Việc tô màu thường chia làm 2 công đoạn. - Xác định vị trí các điểm cần tô màu.. - Có 3 cách tiếp cận chính để tô màu. - Đó là : tô màu theo từng điểm (có thể gọi là tô đơn giản), tô màu theo dòng quét và tô màu dựa theo đường biên.. - Thuật toán này bắt đầu từ việc xác định một điểm có thuộc vùng cần tô hay không ? Nếu đúng là điểm thuộc vùng cần tô thì sẽ tô với màu muốn tô.. - Hình 2.3 : đường tròn nội tiếp hình vuông.. - Tô đa giác. - Tìm hình chữ nhật nhỏ nhất có các cạnh song song với hai trục tọa độ chứa đa giác cần tô dưa vào hai tọa độ (xmin, ymin), (xmax, ymax). - Trong đó, xmin, ymin là hoành độ và tung độ nhỏ nhất, xmax, ymax là hoành độ và tung độ lớn nhất của các đỉnh của đa giác.. - Xét điểm P(x,y) có thuộc đa giác không ? Nếu có thì tô với màu cần tô (xem hình 2.4).. - Hình 2.4 : đa giác nội tiếp hình chữ nhật.. - Thông thường một điểm nằm trong đa giác thì số giao điểm từ một tia bất kỳ xuất phát từ điểm đó cắt biên của đa giác phải là một số lẻ lần. - Đặc biệt, tại các đỉnh cực trị (cực đại hay cực tiểu ) thì một giao điểm phải được tính 2 lần (xem hình 2.5).. - Ví dụ : Xét đa giác gồm 13 đỉnh là P 0 , P 1. - (xem hình 2.5).. - Hình 2.5 : Đa giác có 13 đỉnh.. - Thuật toán kiểm tra điểm có nằm trong đa giác. - Với mỗi đỉnh của đa giác ta đánh dấu là 0 hay 1 theo qui ước như sau: nếu là đỉnh cực trị hay đoạn cực trị thì đánh số 0. - Xét số giao điểm của tia nữa đường thẳng từ P là điểm cần xét với biên của đa giác.. - Nếu số giao điểm là chẳn thì kết luận điểm không thụôc đa giác. - Ngược lại, số giao điểm là lẻ thì điểm thuộc đa giác.. - Minh họa thuật toán xét điểm thuộc đa giác. - if x_cut >= P.x then count. - Minh họa thuật toán tô đa giác. - Thuật toán tô đơn giản có ưu điểm là tô rất mịn và có thể sử dụng được cho đa giác lồi hay đa giác lõm, hoặc đa giác tự cắt, đường tròn, ellipse.. - Để khắc phục nhược điểm này người ta đưa ra thuật toán tô màu theo dòng quét.. - Tô màu theo dòng quét (scan - line). - Phương pháp này sẽ xác định phần giao của các dòng quét kế tiếp nhau với đường biên của vùng tô. - Sau đó, sẽ tiến hành tô màu các điểm thuộc phần giao này.. - Phương pháp này thường được dùng để tô màu đa giác lồi , lõm hay đa giác tự cắt, đường tròn, ellipse, và một số đường cong đơn giản khác.. - Các bước chính của thuật toán. - Tìm ymin, ymax lần lượt là giá trị nhỏ nhất, lớn nhất của tập các tung độ của các đỉnh của đa giác đã cho.. - Ứng với mỗi dòng quét y = k với k thay đổi từ ymin đến ymax, lặp. - Tìm tất cả các hoành độ giao điểm của dòng quét y = k với các cạnh của đa giác.. - Sắp xếp các hoành độ giao điểm theo thứ tự tăng dần : x 0 ,x 1. - Tô màu các đoạn thẳng trên đường thẳng y = k lần lượt được giới hạn bởi các cặp (x 0 , x 1. - ....(xem hình 2.6).. - Hình 2.6 : Tô đa giác bằng giải thuật scan -line.. - Hạn chế đụơc số cạnh cần tìm giao điểm ứng với mỗi dòng quét vì ứng với mỗi dòng quét không phải lúc nào cũng giao điểm với các cạnh của đa giác.. - Xác định nhanh hoàn độ giao điểm vì nếu lặp lại thao tác tìm giao điểm của cạnh đa giác với mỗi dòng quét sẽ tốn rất nhiều thời gian.. - Giải quyết trường hợp số giao điểm đi qua đỉnh đơn điệu thì tính số giao điểm là 1 hay đi qua đỉnh cực trị.thì tính số giao điểm là 0 (hoặc 2).. - Tổ chức cấu trúc dữ liệu và thuật toán. - chứa toàn bộ các cạnh của đa giác (loại các cạnh song song với trục Ox) được sắp theo thứ tự tăng dần của trục y. - Xem hình 2.5 ta có thể sắp xếp các cạnh trong ET là : AB, AI, HG, BC, GF, DC, EF (loại IH và DE. - chứa các cạnh của đa giác có thể cắt ứng với dòng quét hiện hành, các cạnh này được sắp theo thứ tự tăng dần của hoành độ giao điểm của hoành độ giao điểm giữa cạnh và dòng quét.. - Khi dòng quét không còn cắt cạnh này nữa, khi. - Khi không còn cạnh nào trong ET hay AET thì quá trình tô màu kết thúc ( xem hình 2.5).. - Hình 2.7 : Tô đa giác bằng giải thuật scan -line.. - Để tìm giao điểm giữa cạnh đa giác và dòng quét, ta có nhận xét sau. - Lưu đồ thuật toán scan - line. - Tạo danh sách tất cả các cạnh (ET) của đa giác.. - Tìm hoành độ giao điểm và sắp xếp theo thứ tự tăng dần. - Cập nhật lại thông tin của các cạnh để sử dụng cho dòng quét kế tiếp. - Phương pháp tô màu dựa theo đường biên. - Bài toán đặt ra : Cần tô màu một vùng nếu biết được màu của đường biên vùng tô và một điểm nằm bên trong vùng tô.. - Hình 2.8 : Tô màu theo đường biên.. - Hình 2.9 : 4 liên thông và 8 liên thông.. - Cài đặt minh họa thuật toán 4 liên thông. - Thuật toán có thể không chính xác khi có một số điểm nằm trong vùng tô có màu là màu cần tô của vùng.. - Việc thực hiện gọi đệ qui làm thuật toán không thể sử dụng cho vùng tô lớn ( tràn stack).. - Khởi đầu điểm (x,y) là điểm có vị trí đặc biệt trong vùng tô, sau đó, gọi đệ qui các điểm lân cận của (x,y) (xem hình 2.8).. - Hình 2.10: Tam giác với 3 tọa độ đỉnh.. - Ví dụ 1: Trong hình 2.10, ta có thể xét điểm (x,y) có tọa độ là (498, 200). - Khi đó thủ tục tô màu theo đường biên được viết lại như sau. - Ví dụ 2: Trong hình 2.10, ta có thể xét điểm (x,y) có tọa độ là (102, 102). - Một cải tiến khác : không cài đặt đệ qui mà tô theo từng dòng (xem hình 2.11).. - Hình 2.10 : Tô theo từng dòng.. - Sinh viên cần hiểu được khái niệm về các không gian màu.. - Trong giải thuật tô biên, việc thực hiện gọi đệ qui nhiều lần làm thuật toán không thể sử dụng cho vùng tô lớn (tràn stack). - Thực hiện gọi đệ qui tại đỉnh đặc biệt của đa giác.. - Viết chương trình vẽ một đa giác n đỉnh, xét xem một điểm P nào đó có thuộc đa giác không. - Viết chương trình vẽ một đa giác n đỉnh. - Tô đa giác bằng giải thuật tô đơn giản ( Tìm xmin, ymin, xmax, ymax).. - Tô đường tròn bằng giải thuật tô đơn giản.. - Tô đa giác bằng giải thuật tô biên.. - Lưu ý cho các trường hợp của đa giác : hình chữ nhật, đa giác lồi, đa giác lõm.. - Tô đường tròn bằng giải thuật tô biên.. - Tô đa giác bằng giải thuật scan-line.. - Tô đường tròn bằng giải thuật tô scanline.
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt