Thuật toán điền đa giác
Polygon là một danh sách các đỉnh có thứ tự như trong hình sau. Để tô các đa giác bằng các màu cụ thể, bạn cần xác định các pixel nằm trên đường viền của đa giác và các pixel nằm bên trong đa giác. Trong chương này, chúng ta sẽ xem cách chúng ta có thể điền vào các đa giác bằng các kỹ thuật khác nhau.
Thuật toán dòng quét
Thuật toán này hoạt động bằng cách cắt đường quét với các cạnh đa giác và lấp đầy đa giác giữa các cặp giao điểm. Các bước sau mô tả cách hoạt động của thuật toán này.
Step 1 - Tìm Ymin và Ymax từ đa giác đã cho.
Step 2- ScanLine cắt với mỗi cạnh của đa giác từ Ymin đến Ymax. Đặt tên cho mỗi giao điểm của đa giác. Như hình trên, chúng được đặt tên là p0, p1, p2, p3.
Step 3 - Sắp xếp giao điểm theo thứ tự tăng dần của tọa độ X tức là (p0, p1), (p1, p2), và (p2, p3).
Step 4 - Điền vào tất cả các cặp tọa độ bên trong đa giác và bỏ qua các cặp thay thế.
Thuật toán lấp đầy lũ
Đôi khi chúng ta bắt gặp một đối tượng mà chúng ta muốn tô vùng và ranh giới của nó bằng các màu khác nhau. Chúng ta có thể sơn các đối tượng như vậy với một màu nội thất cụ thể thay vì tìm kiếm màu ranh giới cụ thể như trong thuật toán tô đường biên.
Thay vì dựa vào ranh giới của đối tượng, nó dựa vào màu tô. Nói cách khác, nó thay thế màu bên trong của đối tượng bằng màu tô. Khi không còn pixel của màu nội thất ban đầu tồn tại, thuật toán đã hoàn tất.
Một lần nữa, thuật toán này dựa trên phương pháp Bốn kết nối hoặc Tám kết nối để điền vào các pixel. Nhưng thay vì tìm kiếm màu ranh giới, nó đang tìm kiếm tất cả các pixel lân cận là một phần của nội thất.
Thuật toán điền ranh giới
Thuật toán điền đường biên hoạt động như tên gọi của nó. Thuật toán này chọn một điểm bên trong một đối tượng và bắt đầu lấp đầy cho đến khi nó chạm vào ranh giới của đối tượng. Màu của ranh giới và màu mà chúng ta tô phải khác nhau để thuật toán này hoạt động.
Trong thuật toán này, chúng tôi giả định rằng màu của ranh giới là giống nhau cho toàn bộ đối tượng. Thuật toán lấp đầy ranh giới có thể được thực hiện bởi các pixel 4 kết nối hoặc 8 pixel kết nối.
Đa giác 4 kết nối
Trong kỹ thuật này, 4 điểm ảnh được kết nối được sử dụng như trong hình. Chúng tôi đang đặt các pixel bên trên, bên dưới, bên phải và bên trái của các pixel hiện tại và quá trình này sẽ tiếp tục cho đến khi chúng tôi tìm thấy một ranh giới có màu khác.
Thuật toán
Step 1 - Khởi tạo giá trị của seed point (seedx, seedy), fcolor và dcol.
Step 2 - Xác định các giá trị biên của đa giác.
Step 3 - Kiểm tra xem điểm hạt giống hiện tại có màu mặc định hay không, sau đó lặp lại các bước 4 và 5 cho đến khi đạt đến điểm ảnh biên.
If getpixel(x, y) = dcol then repeat step 4 and 5Step 4 - Thay đổi màu mặc định với màu tô tại điểm hạt.
setPixel(seedx, seedy, fcol)Step 5 - Đệ quy theo quy trình với bốn điểm lân cận.
FloodFill (seedx – 1, seedy, fcol, dcol)
FloodFill (seedx + 1, seedy, fcol, dcol)
FloodFill (seedx, seedy - 1, fcol, dcol)
FloodFill (seedx – 1, seedy + 1, fcol, dcol)Step 6 - Thoát
Có một vấn đề với kỹ thuật này. Hãy xem xét trường hợp như được hiển thị bên dưới, nơi chúng tôi đã cố gắng lấp đầy toàn bộ khu vực. Ở đây, hình ảnh chỉ được lấp đầy một phần. Trong những trường hợp như vậy, không thể sử dụng kỹ thuật 4 điểm ảnh kết nối.
8-Đa giác kết nối
Trong kỹ thuật này, 8 pixel được kết nối được sử dụng như thể hiện trong hình. Chúng tôi đang đặt các pixel ở trên, bên dưới, bên phải và bên trái của các pixel hiện tại như chúng ta đang làm trong kỹ thuật 4 kết nối.
Ngoài ra, chúng tôi cũng đang đặt các pixel theo đường chéo để toàn bộ khu vực của pixel hiện tại được bao phủ. Quá trình này sẽ tiếp tục cho đến khi chúng ta tìm thấy một ranh giới có màu khác.
Thuật toán
Step 1 - Khởi tạo giá trị của seed point (seedx, seedy), fcolor và dcol.
Step 2 - Xác định các giá trị biên của đa giác.
Step 3 - Kiểm tra xem điểm hạt giống hiện tại có màu mặc định hay không, sau đó lặp lại các bước 4 và 5 cho đến khi đạt được các pixel ranh giới
If getpixel(x,y) = dcol then repeat step 4 and 5Step 4 - Thay đổi màu mặc định với màu tô tại điểm hạt.
setPixel(seedx, seedy, fcol)Step 5 - Theo quy trình đệ quy với bốn điểm lân cận
FloodFill (seedx – 1, seedy, fcol, dcol)
FloodFill (seedx + 1, seedy, fcol, dcol)
FloodFill (seedx, seedy - 1, fcol, dcol)
FloodFill (seedx, seedy + 1, fcol, dcol)
FloodFill (seedx – 1, seedy + 1, fcol, dcol)
FloodFill (seedx + 1, seedy + 1, fcol, dcol)
FloodFill (seedx + 1, seedy - 1, fcol, dcol)
FloodFill (seedx – 1, seedy - 1, fcol, dcol)Step 6 - Thoát
Kỹ thuật 4 điểm ảnh được kết nối không thể lấp đầy khu vực như được đánh dấu trong hình sau, điều này sẽ không xảy ra với kỹ thuật 8 kết nối.
Kiểm tra bên trong
Phương pháp này còn được gọi là counting number method. Trong khi điền vào một đối tượng, chúng ta thường cần xác định xem điểm cụ thể nằm bên trong đối tượng hay bên ngoài nó. Có hai phương pháp mà chúng ta có thể xác định xem điểm cụ thể nằm bên trong một đối tượng hay bên ngoài.
- Quy tắc chẵn lẻ
- Quy tắc số quanh co phizero
Quy tắc chẵn lẻ
Trong kỹ thuật này, chúng ta sẽ đếm cạnh cắt dọc theo đường thẳng từ bất kỳ điểm nào (x, y) đến vô cùng. Nếu số lượng tương tác là lẻ, thì điểm (x, y) là một điểm bên trong; và nếu số lượng tương tác là chẵn, thì điểm (x, y) là một điểm bên ngoài. Ví dụ sau đây mô tả khái niệm này.
Từ hình trên, chúng ta có thể thấy rằng từ điểm (x, y), số điểm tương tác ở phía bên trái là 5 và ở phía bên phải là 3. Từ hai đầu, số điểm tương tác là lẻ, do đó điểm được xem xét bên trong đối tượng.
Quy tắc số cuộn dây Nonzero
Phương pháp này cũng được sử dụng với các đa giác đơn giản để kiểm tra điểm đã cho có nằm trong hay không. Có thể hiểu đơn giản là có sự hỗ trợ của chiếc ghim và dây chun. Cố định ghim vào một trong các cạnh của đa giác và buộc dây chun vào đó rồi kéo căng dây chun dọc theo các cạnh của đa giác.
Khi tất cả các cạnh của đa giác được bao phủ bởi dây cao su, hãy kiểm tra chốt đã được cố định tại điểm cần kiểm tra. Nếu chúng ta tìm thấy ít nhất một ngọn gió tại điểm được coi là bên trong đa giác, nếu không chúng ta có thể nói rằng điểm đó không nằm bên trong đa giác.
Trong một phương pháp thay thế khác, chỉ đường cho tất cả các cạnh của đa giác. Vẽ một đường quét từ điểm cần kiểm tra về phía trái nhất của hướng X.
Cung cấp giá trị 1 cho tất cả các cạnh hướng lên và tất cả -1 khác làm giá trị hướng.
Kiểm tra các giá trị hướng cạnh mà từ đó dòng quét đi qua và tổng hợp chúng.
Nếu tổng tổng của giá trị hướng này khác 0, thì điểm cần kiểm tra này là interior point, nếu không nó là một exterior point.
Trong hình trên, chúng ta tính tổng các giá trị hướng mà dòng quét đi qua thì tổng là 1 - 1 + 1 = 1; là khác 0. Vì vậy, điểm được cho là một điểm nội thất.