tailieunhanh - Area Filling - Tô màu đồ thị

Interior defined: Tất cả các pixel trong vùng có cùng một màu, gọi là inside-color. Các pixel trên biên không có màu này. Có thể có lỗ trong vùng. Boundary defined. Các pixel thuộc biên có cùng màu – boundary-color. Các pixel trong vùng không có màu này. Nếu một số pixel trong vùng có màu boundary-color thì vùng sẽ chứa lỗ. | Area Filling Tô màu đồ thị Vùng tô Vùng được xác định bởi điểm ảnh – pixel-defined region Vùng xác định bởi đa giác – polygonal region pixel-defined region polygonal region Pixel-defined region Vùng được định nghĩa bởi màu của pixel, chia làm 3 phần: Vùng trong – interior Vùng ngoài – exterior Biên (liên tục) - boundary interior exterior boundary Liên thông 4 và liên thông 8 4-connected : 2 pixel liên thông với nhau nếu chúng kề nhau theo chiều ngang hay chiều dọc 8-connected : 2 pixel liên thông với nhau nếu chúng kề nhau theo chiều ngang, hay chiều dọc, hay đường chéo Cách thức định nghĩa pixel-defined region Interior defined Tất cả các pixel trong vùng có cùng một màu, gọi là inside-color Các pixel trên biên không có màu này Có thể có lỗ trong vùng Boundary defined Các pixel thuộc biên có cùng màu – boundary-color Các pixel trong vùng không có màu này Nếu một số pixel trong vùng có màu boundary-color thì vùng sẽ chứa lỗ Interior-defined Boundary-defined inside color Polygonal Region Định nghĩa bằng đa giác: xác định các định các đỉnh pi = (xi,yi) Các loại đa giác: Convex Concave, simple Nonsimple polygonal region convex concave nonsimple Recursive Flood-Fill Algorithm (interior-defined, 4-connected region) Đổi màu của tất cả các interior-pixel thành màu tô – fill color. Quá trình tô màu bắt đầu từ một điểm (seed pixel) thuộc phía trong vùng tô và lan truyền khắp vùng tô => Flood-Fill Interior-defined seed pixel inside color Recursive Flood-Fill fill color Recursive Flood-Fill Algorithm (cont) Thuật toán Nếu pixel tại (x,y) thuộc vùng trong – màu của pixel đó là inside-color thì Đổi màu của nó thành fill-color Áp dụng quá trình trên cho 4 điểm lân cận nó (4-connected). Ngược lại, không làm gì. 0 1 2 4 3 5 6 0 1 2 3 4 5 6 S S (4,2) (4,2) (2,3) (3,2) (3,2) (1,2) (2,2) (2,1) (3,3) Recursive Flood-Fill Program void FloodFill(int x, int y, int inside_color, int fill_color) { if (getpixel(x,y) == inside_color) { putpixel(x,y,fill_color); | Area Filling Tô màu đồ thị Vùng tô Vùng được xác định bởi điểm ảnh – pixel-defined region Vùng xác định bởi đa giác – polygonal region pixel-defined region polygonal region Pixel-defined region Vùng được định nghĩa bởi màu của pixel, chia làm 3 phần: Vùng trong – interior Vùng ngoài – exterior Biên (liên tục) - boundary interior exterior boundary Liên thông 4 và liên thông 8 4-connected : 2 pixel liên thông với nhau nếu chúng kề nhau theo chiều ngang hay chiều dọc 8-connected : 2 pixel liên thông với nhau nếu chúng kề nhau theo chiều ngang, hay chiều dọc, hay đường chéo Cách thức định nghĩa pixel-defined region Interior defined Tất cả các pixel trong vùng có cùng một màu, gọi là inside-color Các pixel trên biên không có màu này Có thể có lỗ trong vùng Boundary defined Các pixel thuộc biên có cùng màu – boundary-color Các pixel trong vùng không có màu này Nếu một số pixel trong vùng có màu boundary-color thì vùng sẽ chứa lỗ Interior-defined Boundary-defined inside color