Hiểu sự khác biệt giữa flood fill và boundary fill. Chúng là thuật toán tô màu vùng, phân biệt dựa trên việc pixel ngẫu nhiên có màu gốc của vùng hay không.
Flood-fill algorithm
- Còn gọi seed fill algorithm.
- Tính diện tích kết nối với node cho trước trong mảng đa chiều.
- Hoạt động bằng cách tô màu/recolor vùng chứa nhiều màu bên trong, do đó tô màu đường viền ảnh.
- Biểu diễn bằng ảnh có neighborhood có border và vùng màu riêng biệt.
- Màu nội bộ cụ thể có thể thay thế để vẽ các phần này.
- Tiêu thụ bộ nhớ cao.
- Thuật toán tương đối đơn giản.
- Xử lý ảnh có nhiều màu border.
- Chậm hơn boundary-fill.
- Có thể dùng màu ngẫu nhiên tô nội bộ, pixel cũ thay bằng mới.
- Thuật toán hiệu quả.
Hai phương pháp kết nối pixel tạo nhiều border:
- 4-connected: pixel tối đa 4 neighbor (trái, phải, trên, dưới).
- 8-connected: pixel tối đa 8 neighbor (thêm 4 đường chéo).
Boundary-fill algorithm
- Khi border chỉ một màu, thuật toán lan ra ngoài pixel bởi pixel cho đến khi gặp màu border.
- Triển khai trong gói vẽ tương tác, chọn điểm bên trong dễ dàng.
- Bắt đầu từ tọa độ điểm trong (x, y), màu border và màu fill làm input.
- Từ (x, y), kiểm tra neighbor xem có phải màu border không.
- Nếu không phải màu border → tô màu fill, kiểm tra neighbor tiếp theo cùng điều kiện.
- Kết thúc khi mọi pixel đến màu border đã kiểm tra.
- Vùng xác định bằng một màu duy nhất.
- Tiêu thụ bộ nhớ thấp hơn.
- Nhanh hơn flood-fill.
- Phức tạp hơn flood-fill.
- Chỉ xử lý ảnh có một màu border.