Chương 2: Thuật toán tô màu

Chia sẻ: Lê Thị Nguyên An | Ngày: | Loại File: PPT | Số trang:36

Thêm vào BST

Báo xấu

641
lượt xem 116
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chương 2: Thuật toán tô màu

Các hệ màu 2
3
4
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ô 6
Thuậ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 9
Tô màu theo 8 hướng 10
Thuật toán Flood-fill 11
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ô 12
Minh 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? 14
Phương pháp tiếp cận dựa theo dòng quét 15
Ví dụ 16
Xét trường hợp – cắt hai cạnh 17
Trường hợp – đi qua một đỉnh 18
Trường hợp – đi qua cạnh nằm ngang 19
Minh họa thuật toán 20