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.
Nội dung trích xuất từ tài liệu:
Chương 2: Thuật toán tô màuCác hệ màu 234 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) 5 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ô 6Thuật toán tô màu dựa theo đường biên Boundary-fill 7 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ô 8 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 9Tô màu theo 8 hướng 10Thuật toán Flood-fill 11Thuậ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ô 12Minh hoạ thuật toán Flood-fill không dùng đệ qui 13 Đ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? 14Phương pháp tiếp cận dựa theo dòng quét 15Ví dụ 16Xét trường hợp – cắt hai cạnh 17Trường hợp – đi qua một đỉnh 18Trường hợp – đi qua cạnh nằm ngang 19Minh họa thuật toán 20