3. CÁC THUẬT TOÁN TÔ MÀU Các vùng tô là một trong những đối tượng đồ họa cơ sở được hầu hết các công cụ lập trình đồ họa hỗ trợ. Có hai dạng vùng tô thường gặp đó là : tô bằng một màu thuần nhất (solid fill) hay tô theo một mẫu tô (fill-pattern) nào đó. Một vùng tô thường được xác định bởi một đường khép kín nào đó gọi là đường biên. Một trong những dạng đường biên đơn giản nhất đó là đa giác. . | Bước 5 Tính W và hoần chính thuật toán. 3. CÁC THUẬT TOÁN TÔ MÀU Các vùng tô là một trong những đối tượng đồ họa cơ sở được hầu hết các công cụ lập trình đồ họa hỗ trợ. Có hai dạng vùng tô thường gặp đó là tô bằng một mầu thuần nhất solid fill hay tô theo một mẫu tô fill-pattern nào đó. Một vùng tô thường được xác định bởi một đường khép kín nào đó gọi là đường biên. Một trong những dạng đường biên đơn giản nhất đó là đa giác. Để tô màu một vùng tô người ta thường chia làm hai công đoạn công đoạn thứ nhất là xác định các điểm nào để tô và công đoạn còn lại đơn giản hơn đó là quyết định tô các điểm đó bằng giá trị màu nào. Công đoạn thứ hai chỉ thực sự phức tạp nếu ta tô theo một mẫu tô nào đó không phải là tô thuần một màư Có hai cách tiếp cận chính để tô màu một vùng tô đối với thiết bị hiển thị dạng điểm đó là tô theo dòng quét scan-line fill và tô dựa theo đường biên boundary fill . Phương pháp tô theo dòng quét sẽ xác định các phần giao của các dòng quét kế tiếp nhau với đường biên của vùng tô sau đó sẽ tô màu các điểm thuộc về phần giao này. Cách tiếp cận này thường được dùng để tô màu các đa giác đường tròn ellipse và một số đường cong đơn giản khác. Phương pháp tô dựa theo đường biên sẽ bắt đầu từ một điểm ở bên trong vùng tô và từ đó loang dần ra cho tới khi ta gặp các điểm biên. Cách tiếp cận này thường được dùng cho các vùng tô có dạng đường biên phức tạp hơn. . Thuật toán tô màu dựa theo dòng quét Giả sử vùng tô được cho bởi một đa giác N đỉnh ÍXỂ Ể -z 0 - -1. Đa giác này có thể là đa giác lồi đa giác lõm và cả đa giác tự cắt . Hình sau minh họa ý tưởng chính của thuật toán. Với mỗi dòng quét ta sẽ xác định phần giao của đa giác và dòng quét rồi tô màu các pixel thuộc đoạn giao đó. Để xác định các đoạn giao ta tiến hành việc tìm giao điểm của dòng quét với các cạnh của đa giác sau đó các giao điểm này sẽ được sắp theo thứ tự tăng dần của hoành độ giao điểm Các đoạn giao chính là các đoạn thẳng được giới hạn bởi từng cặp giao điểm một ví dụ như 0
