ChưƠng 2 CÁc thuật toán cơ SỞ Thuật toán tô màu



tải về 81.31 Kb.
Chuyển đổi dữ liệu25.03.2018
Kích81.31 Kb.

CHƯƠNG 2
CÁC THUẬT TOÁN CƠ SỞ

2.6. Thuật toán tô màu

2.6.1. Một số khái niệm

  • Lân cận 4

  • Hai điểm ảnh được gọi là lân cận 4 nếu chúng kề nhau theo đường thẳng đứng hoặc nằm ngang



  • Lân cận 8

  • Hai điểm ảnh được gọi là lân cận 8 nếu chúng kề nhau theo đường thẳng đứng, ngang và đường chéo.

2.6.2. Thuật toán tô màu loang

  • Cho miền kín V có mầu biên Cb.Tô kín V bằng mầu tô Ct

  • Cho điểm P(x,y) Є V

  • Tư tưởng

  • Tô điểm P(x,y) với màu Ct

  • Tô lân cận 4 hoặc lân cận 8 của P nếu không phải là biên và chưa được tô

  • Lặp lại quá trình trên đến khi tô hết V



  • Thủ tục



  • Nhận xét

  • Đơn giản

  • Tô được miền có hình dạng bất kỳ

  • Sử dụng đệ quy tràn stack không tô được vùng lớn

  • Cải tiến

  • Dựa vào điểm khởi tạo trong V để quyết định số lần gọi đệ quy

2.6.3. Thuật toán tô màu biên

  • Cho miền kín V có mầu biên Cb.Tô kín V bằng mầu tô Ct

  • Cho điểm P(x,y) Є V

  • Tư tưởng

  • Từ điểm xuất phát P(x,y)

  • Tăng x để xác định xmax

  • Giảm x để xác định xmin

  • Vẽ đường nối (xmin,y,xmax,y), chia V thành hai phần

  • Tăng y xác định xmin, xmax mới và lặp lại quá trình trên cho nửa thứ nhất

  • Giảm y, xác định xmin, xmax mới và lặp lại quá trình trên cho nửa thứ hai













  • Thủ tục

  • Nhận xét

  • Không sử dụng đệ quy  tránh tràn stack

  • Tô màu nhanh hơn

  • Khó khăn khi tô vùng phức tạp

2.6.4. Tô màu đường tròn

  • Tư tưởng

  • Tìm hình vuông nhỏ nhất ngoại tiếp đường tròn

  • Xác định điểm trên bên trái (xc-r, yc-r)

  • Xác định điểm dưới bên phải (xc+r, yc+r)

  • Cho i đi từ xc-r đến xc+r

  • Cho j đi từ yc-r đến yc+r

  • Tính khoảng cách d giữa hai điểm (i,j) và tâm (xc,yc)
  • Nếu d
  • Thủ tục

2.6.5. Tô màu hình thang cơ bản

  • Hình thang cơ bản

  • Là hình thang có cạnh đáy song song với trục tọa độ

  • Tư tưởng

  • Đặt ymin = y1; ymax = y3; m = ymax-ymin +1

  • Tính hệ số góc

Cl = (x4-x1)/(y4-y1)
Cr = (x3-x2)/(y3-y2)
  • Đặt yi = ymin + (i-1), i=1..m

  • Tính xil = x1 +(yi-y1)Cl

  • Tính xir = x2 +(yi-y2)Cr

  • Kẻ đoạn thẳng (xil,yil),(xir,yir) bằng màu tô

  • Thủ tục

2.6.6. Tô màu đa giác

  • Tư tưởng

  • Tìm hình chữ nhật nhỏ nhất có các cạnh song song với hai trục tọa độ chứa đa giác cần tô dựa vào hai tọa độ (xmin, ymin), (xmax, ymax).

  • xmin, ymin là hoành độ và tung độ nhỏ nhất của các đỉnh của đa giác

  • xmax, ymax là hoành độ và tung độ lớn nhất của các đỉnh của đa giác.



  • Tư tưởng

  • Cho x chạy từ xmin đến xmax

Cho y chạy từ ymin đến ymax

Xét điểm P(x,y) có thuộc đa giác không ?

Nếu đúng thì tô với màu cần tô

  • Điểm trong đa giác

  • Là điểm có số giao điểm từ một tia bất kỳ xuất phát từ điểm đó cắt biên của đa giác phải là một số lẻ lần.

  • Tại các đỉnh cực trị (cực đại hay cực tiểu ) thì một giao điểm phải được tính 2 lần.

  • Tia có thể qua phải hay qua trái. Thông thường, chọn tia qua phải.

  • Cho đa giác W và P là điểm bất kỳ

  • Thuật toán1

  • B1: Từ P, kẻ nửa đường thẳng L song song với trục ox hướng sang phải

  • B2: Tính số giao điểm N của nửa đường thẳng L với các cạnh của đa giác

  • B3: Nếu N lẻ P nằm trong đa giác, nếu N chẵn P nằm ngoài đa giác

  • Cải tiến thuật toán

  • Giả sử P(x0,y0) và Pi có tọa độ (xi,yi), i=1,n

  • Cạnh (Pi,Pi+1) không cần tính giao điểm với L nếu max(xi,xi+1)0

  • Cạnh (Pi,Pi+1) có giao điểm với L nếu

min(xi,xi+1)>x0

(y-y0)(yi+1-y0)<0

  • Nhận xét Thuật toán1

  • Không giải quyết đúng khi L đi qua một đỉnh nào đó của đa giác

  • Không giải quyết đúng khi L đi qua một cạnh của đa giác

 Thuật toán này không phải là thuật toán tổng quát để xác định điểm P nằm trong hay ngoài đa giác

  • Thuật toán 2


\


  • Từ điểm P nối với các đỉnh đa giác để tạo thành các góc theo thứ tự ngược chiều kim đồng hồ

  • Các góc này có giá trị dương hoặc âm tùy theo hướng đo

  • Tính tổng các góc

  • Nếu tổng các góc bằng 0 thì P nằm ngoài đa giác

  • Nếu tổng các góc bằng 360o thì P nằm trong đa giác

  • Xét đa giác gồm 13 đỉnh là P0 , P1 , ....., P12 = P0



Gọi tung độ của đỉnh Pi là Pi.y

  • Pi.y < Min ( Pi+1.y, Pi-1.y) Pi là đỉnh cực trị (cực tiểu)

  • Pi.y > Max ( Pi+1.y, Pi-1.y) Pi là đỉnh cực trị (cực đại )

  • Pi-1.y < Pi.y < Pi+1.y hay Pi-1 > Pi.y > Pi+1.y

 Pi là đỉnh đơn điệu.

  • Pi = Pi+1 và Pi.y < Min ( Pi+2.y, Pi-1.y) hay Pi > Max ( Pi+2.y, Pi-1.y) thì đoạn [Pi,Pi+1] là đoạn cực trị (cực tiểu hay cực đại ).

  • Pi = Pi+1 và Pi-1.y < Pi.y < Pi+2.y hay Pi-1 > Pi.y > Pi+2.y thì đoạn [Pi,Pi+1] là đoạn đơn điệu.

  • Điểm trong đa giác

  • Tư tưởng

  • Với mỗi đỉnh của đa giác ta đánh dấu là 0 hay 1 theo qui ước như sau: nếu là đỉnh cực trị hay đoạn cực trị thì đánh số 0. Nếu là đỉnh đơn điệu hay đoạn đơn điệu thì đánh dấu 1.

  • Xét số giao điểm của tia nửa đường thẳng từ P là điểm cần xét với biên của đa giác. Nếu số giao điểm là chẵn thì kết luận điểm không thụôc đa giác. Ngược lại, số giao điểm là lẻ thì điểm thuộc đa giác.

2.6.7. Tô màu dòng quét

  • Ý tưởng

  • Sử dụng giao điểm giữa các biên đa giác và đường quét để nhận ra pixel có trong đa giác?



  • Thuật toán

  • Cho trước đa giác P với n đỉnh v0 đến vn-1(vnΞv0)

  • Cho trước C là màu tô đa giác

  • Giao của mỗi đường quét với các cạnh đa giác thì sẽ là điểm vào hay điểm ra đa giác

  • Tìm ra các đoạn thẳng nằm trong đa giác để vẽ theo màu C

  • Với mỗi dòng quét

  • Tìm giao điểm với các cạnh của đa giác

  • Sắp xếp theo chiều tăng của x

  • Tô các điểm ảnh giữa các cặp giao điểm

  • Tìm giao điểm đường quét với cạnh đa giác

  • Tìm ymin và ymax của mỗi cạnh

  • Tính giao điểm của cạnh với đường quét đầu tiên nếu có giao nhau

  • Tính dx/dy

  • Với mỗi đường quét sau, tính giao điểm mới x=x+dx/dy



  • Danh sách cạnh

  • Một dãy các mục là danh sách móc nối

  • Tất cả các cạnh được sắp xếp theo ymin của chúng

  • Lưu giữ một bucket riêng cho mỗi đường quét

  • Với mỗi bucket, cạnh được sắp theo tăng dần của x (của ymin)

  • Mỗi đường quét sẽ có một danh sách móc nối rỗng khi và chỉ khi tọa độ y thấp hơn của đoạn thẳng.

  • Cấu trúc của danh sách móc nối

  • Mỗi nút trong ds móc nối có

  • Tọa độ y lớn hơn của cạnh (đường quét lớn nhất còn cắt cạnh)

  • Tọa độ x của điểm thấp hơn (tọa độ x của điểm ymin)

  • Số gia của x (tăng theo đường quét liền nhau)

  • Con trỏ trỏ tới phần tử tiếp theo (nếu cần)

  • Sử dụng danh sách cạnh kích hoạt

  • Khi quét từng dòng, giá trị giao điểm x mới được tính nhờ: xi+1 = xi + 1/m

  • Khi có thêm cạnh sẽ cắt đường quét tiếp theo thì nó sẽ được đưa vào trong danh sách cạnh kích hoạt, cạnh không còn cắt sẽ bị loại bỏ (có thể cần sắp xếp).

  • Danh sách các cạnh kích hoạt với đường đang quét được sắp theo chiều tăng x.

Begin

  • Xây dựng danh sách các cạnh (EL)

  • Danh sách cạnh kích hoạt AEL = null

  • For y:=ymin to ymax do

  • If edge.ymax = y then
  • Loại edge khỏi AET
  • Else
  • Edge.x=edge.x + dx/dy
  • Sắp xếp AET theo giá trị x

End;






Cơ sở dữ liệu được bảo vệ bởi bản quyền ©tieuluan.info 2017
được sử dụng cho việc quản lý

    Quê hương