Đang chuẩn bị liên kết để tải về tài liệu:
Chương 2: Thuật toán tô màu

Tài liệu tham khảo về Các thuật toán tô màu trong môn toán hình học dành cho những bạn yêu thích học môn toán tham khảo học tập. | 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 . | 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 .