Thuật toán tô màu

Các hệ màu Các thuật toán tô màu Bằng các điểm và đoạn thẳng, chúng ta có thể dễ dàng biểu diễn các đối tượng với các đường biên khép kín bao quanh. Đối tượng đặc? Tô màu: Xác định điểm ảnh nằm trong đối tượng Thíêt lập 1 màu xác định cho những điểm ảnh thuộc đối tượng Loại đường biên Đa giác, đường tròn, các đường đơn giản Đường khép kín bất kỳ Phương pháp tô màu 1. Tô màu theo dòng quét (scan-line fill) 2. Tô màu dựa theo đường biên (boundary fill) Phương pháp tiếp cận dựa theo đường biên Boundary-fill Thông thường đường biên của một đối tượng là một hình khép kín bất kỳ được xác định bởi giá trị màu của các điểm trên biên. Phương pháp tô màu tổng quát: 1. Khởi tạo một điểm nằm trong vùng tô 2. Kiểm tra các điểm lân cận Nếu không phải điểm đã tô hoặc điểm biên thì tô màu cho điểm đó 3. Lặp bước 2 cho đến khi không còn điểm nào cần tô Thuật toán tô màu dựa theo đường biên Boundary-fill Minh hoạ thuật toán tô màu dựa theo đường biên Boundary-fill Phải đảm bảo đường biên là khép kín và màu cần tô khác màu biên Thuật toán thực hiện gọi đệ qui nên dễ dẫn tới tràn stack khi vùng tô lớn Dư thừa khi vẫn gọi đệ qui cho các điểm ảnh đã tô Tô màu 4 hướng hoặc 8 hướng Nếu chỉ xét bốn điểm lân cận (trái, phải, trên, dưới) thì vùng hình chữ nhật ở bên phải sẽ không được tô Tám điểm lân cận theo tám hướng: bắc, nam, đông, tây, đông bắc, đông nam, tây bắc, tây nam Tô màu theo 8 hướng Thuật toán Flood-fill Thuật toán Flood-fill không dùng đệ qui 1. Khởi tạo 1 điểm nằm trong vùng tô 2. Thực hiện tô loang dần theo chiều ngang (trái qua phải và phải qua trái) cho đến khi dụng biên thì dừng lại 3. Ứng với mỗi điểm trên dòng quét ngang, thực hiện loang để tìm những điểm ảnh có hoành độ nhỏ nhất sát với biên chưa được tô nằm trên và dưới, sau đó lưu vào Stack 4. Lặp bước 2 nếu còn một điểm trong Stack chưa được tô Minh hoạ thuật toán Flood-fill không dùng đệ qui Đa giác Đa giác với số cạnh đủ lớncó thể xấp xỉ tốt một đườngbiên khép kín Đa giác N đỉnh liền kề: Pi(xi,yi), i=0…N-1 Xác định vùng nằm trong, hoặc nằm ngoài đa giác? Phương pháp tiếp cận dựa theo dòng quét Ví dụ Xét trường hợp – cắt hai cạnh Trường hợp – đi qua một đỉnh Trường hợp – đi qua cạnh nằm ngang Minh họa thuật toán Nhắc lại 3 trường hợp đặc biệt Phân loại các trường hợp Rút ngắn cạnh theo tung độ Tiền xử lý đa giác Tối ưu tốc độ Bảng các cạnh bucket Tạo bảng cạnh ET Thuật toán tô màu đa giác Active Edge Table Active Edge Table Vòng lặp tiếp theo Integer Active Edge Table Integer Active Edge Table Edge hash table Câu hỏi