Các thuật toán tô màu 1. Thuật toán tô màu hình thang cơ bản Giả sử cho hình thang cơ bản có dạng: (x4y4) (x3y3) (x1y1) Thuật toán nh- sau: (x2y2) | 16. CÁC THUẬT TQÁN TÓ MÀU 1. Thuật toán tô màu hình thang cơ bản Giả sử cho hình thang cơ bản có dạng Thuật toán như sau 1. Đặt ymin y1 ymax y3 m ymax-ymin 1 2. tính hệ số góc Cl x4-xi y4-yi Cr x3-x2 y3-y2 2. Đặt yi ymin i-1 i 1 m tính xi X1 yi - y1 .Ci xr X2 ới - y2 .Cr 89 Kỹ thuật Đổ hoạ máy tính 3. Kẻ đoạn thẳng xi y i x yi bằng màu tô Chú ý 1. Khi hình thang cơ bản biến dạng về tam giác chẳng hạn X1 X2 yi y2 X4Y4 X3Y3 C Cr XL1 xL X1Y1 khi đó xi xr 2. Tô màu đa giác Dựa vào kết quả của việc phân chia đa giác thành tổng các hình thang cơ bản ta suy ra để tô màu một đa giác bất kỳ ta cần phân chia đa giác thành tổng các hình thang cơ bản và sau đó tô màu các hình thang đã được chia 3. Tô màu một vùng kín bất kỳ Cho một tập các pixel tập được gọi là liên thông nếu từ một pixel ta có thể di chuyển đến các pixel bất kỳ thuộc tập Cho một tập W các điểm ảnh Pixel tập W gọi là liên thông cấp 8 nếu mỗi pixel có 8 điểm lân cận thuộc tập Cho một tập W các điểm ảnh pixel tập được gọi là liên thông cấp 4 nếu mỗi điểm ảnh thuộc tập có 4 điểm lân cận thuộc tập 90 Kỹ thuật Đổ hoạ máy tính e---------o---------0 Bài toán tô màu vùng bất kỳ Cho một tập W các điểm ảnh liên thông cấp 4 được giới hạn bởi đường biên có mầu cb và một điểm ảnh trong W hãy tô vùng W bằng màu Ct ý tưởng của thuật toán đơn giản như sau Xuất phát từ điểm trong P của vùng W kiểm tra 4 điểm lân cận của P là P1 P2 P3 P4 nếu điểm Pi i 1 4 không có mầu Cb thì tô Pi bằng Ct và lại coi Pi là điểm trong P của W quá trình được lặp lại cho đến khi gặp màu biên Cb. Thuật toán ngắn gọn trên có thể được gọi là thuật toán vết dầu loang. Thuật toán ngắn gọn trên có thể mô tả bằng thủ tục đệ quy sau Procedure Tomau x y Cb Ct Integer Begin If Color x y Cb and Color x y Ct Then . Begin Putpixel x y Ct Tomau x y-1 Cb Ct Tomau x y 1 Cb Ct Tomau x-1 y Cb Ct Tomau x 1 y Cb Ct End End Chú ý Thuật toán trên có ưu điểm là chương trình ngắn gọn song do thủ tục đệ quy nên yêu cầu bộ nhớ rất lớn nếu miền W có n điểm ảnh thì bộ nhớ .
