Tài liệu các thuật toán tô màu trong thiết kế đồ họa máy tính

Bài toán đặt ra : Cần tô màu một đa giác cho bởi N đỉnh
P (x , y ), i = 0, .N ư 1 i i i . Đ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,
Tóm tắtét cácùc bướcùc chính củảa thuật toán
ã Tìm top y , bottom y lần lượt là giá trị lớn nhất, nhỏ
nhất của tập các tung độ của các đỉnh của đa giác đã
cho: y {y (x y ) P} top = max i , i , i ∈ , y {y (x y ) P} bottom = min i , i , i ∈ .
ã Ứng với mỗi dòng quét y = k , với k thay đổi từ
bottom y đến top y , lặp :
♦ Tìm tất cả các hoành độ giao điểm của dòng quét y = k
với các cạnh của đa giác.
♦ Sắp xếp các hoành độ giao điểm theo thứ tự tăng dần :
, , , ., 0 1 2 x x x
♦ Tô màu các đoạn thẳng trên đường thẳng y = k lần lượt
được giới hạn bởi các cặp ( )( ) ( )0 1 1 2 2 2 1 , , , , ., , k k+ x x x x x x .