Algoritma Pengisian Poligon

Poligon adalah daftar simpul yang diurutkan seperti yang ditunjukkan pada gambar berikut. Untuk mengisi poligon dengan warna tertentu, Anda perlu menentukan piksel yang berada di tepi poligon dan yang berada di dalam poligon. Dalam bab ini, kita akan melihat bagaimana kita dapat mengisi poligon dengan menggunakan teknik yang berbeda.

Pindai Algoritma Garis

Algoritma ini bekerja dengan memotong garis pindai dengan tepi poligon dan mengisi poligon di antara pasangan persimpangan. Langkah-langkah berikut menggambarkan cara kerja algoritma ini.

Step 1 - Cari tahu Ymin dan Ymax dari poligon yang diberikan.

Step 2- ScanLine berpotongan dengan setiap tepi poligon dari Ymin ke Ymax. Beri nama setiap titik potong poligon. Sesuai gambar yang ditunjukkan di atas, mereka dinamai sebagai p0, p1, p2, p3.

Step 3 - Urutkan titik potong dalam urutan koordinat X yang semakin meningkat yaitu (p0, p1), (p1, p2), dan (p2, p3).

Step 4 - Isi semua pasangan koordinat yang ada di dalam poligon dan abaikan pasangan alternatifnya.

Algoritma Pengisian Banjir

Terkadang kita menemukan objek yang ingin kita isi area dan batasnya dengan warna yang berbeda. Kita bisa melukis objek seperti itu dengan warna interior tertentu daripada mencari warna batas tertentu seperti pada algoritma pengisian batas.

Alih-alih bergantung pada batas objek, itu bergantung pada warna isian. Dengan kata lain, ini menggantikan warna interior objek dengan warna isian. Jika tidak ada lagi piksel dari warna interior asli, algoritme selesai.

Sekali lagi, algoritma ini mengandalkan metode Four-connect atau Eight-connect untuk mengisi piksel. Tetapi alih-alih mencari warna batas, ia mencari semua piksel yang berdekatan yang merupakan bagian dari interior.

Algoritma Pengisian Batas

Algoritme pengisian batas berfungsi sesuai namanya. Algoritma ini mengambil satu titik di dalam sebuah objek dan mulai mengisi hingga mencapai batas objek tersebut. Warna batas dan warna yang kita isi harus berbeda agar algoritme ini berfungsi.

Dalam algoritma ini, kami mengasumsikan bahwa warna batasnya sama untuk keseluruhan objek. Algoritme pengisian batas dapat diimplementasikan dengan 4 piksel yang terhubung atau 8 piksel yang terhubung.

Poligon 4-Terhubung

Dalam teknik ini 4 piksel yang terhubung digunakan seperti yang ditunjukkan pada gambar. Kami meletakkan piksel di atas, di bawah, ke kanan, dan ke sisi kiri piksel saat ini dan proses ini akan berlanjut hingga kami menemukan batas dengan warna berbeda.

Algoritma

Step 1 - Inisialisasi nilai seed point (seedx, seedy), fcolor dan dcol.

Step 2 - Tentukan nilai batas poligon.

Step 3 - Periksa apakah titik benih saat ini adalah warna default, kemudian ulangi langkah 4 dan 5 hingga piksel batas tercapai.

If getpixel(x, y) = dcol then repeat step 4 and 5

Step 4 - Ubah warna default dengan warna isian pada titik benih.

setPixel(seedx, seedy, fcol)

Step 5 - Ikuti prosedur secara rekursif dengan empat titik lingkungan.

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 - Keluar

Ada masalah dengan teknik ini. Pertimbangkan kasus seperti yang ditunjukkan di bawah ini di mana kami mencoba mengisi seluruh wilayah. Di sini, gambar hanya diisi sebagian. Dalam kasus seperti itu, teknik 4 piksel yang terhubung tidak dapat digunakan.

Poligon 8-Terhubung

Dalam teknik ini digunakan 8 piksel yang terhubung seperti yang ditunjukkan pada gambar. Kami menempatkan piksel di atas, di bawah, kanan dan kiri piksel saat ini seperti yang kami lakukan dalam teknik 4-terhubung.

Selain itu, kami juga menempatkan piksel dalam diagonal sehingga seluruh area piksel saat ini tertutup. Proses ini akan berlanjut hingga kita menemukan batas dengan warna berbeda.

Algoritma

Step 1 - Inisialisasi nilai seed point (seedx, seedy), fcolor dan dcol.

Step 2 - Tentukan nilai batas poligon.

Step 3 - Periksa apakah titik benih saat ini adalah warna default kemudian ulangi langkah 4 dan 5 hingga piksel batas tercapai

If getpixel(x,y) = dcol then repeat step 4 and 5

Step 4 - Ubah warna default dengan warna isian pada titik benih.

setPixel(seedx, seedy, fcol)

Step 5 - Ikuti prosedur secara rekursif dengan empat titik lingkungan

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 - Keluar

Teknik 4 piksel terkoneksi gagal mengisi area seperti yang ditandai pada gambar berikut yang tidak akan terjadi pada teknik 8 terkoneksi.

Tes di dalam-luar

Metode ini juga dikenal sebagai counting number method. Saat mengisi suatu objek, kita sering kali perlu mengidentifikasi apakah titik tertentu ada di dalam objek atau di luarnya. Ada dua metode yang dapat kita gunakan untuk mengidentifikasi apakah titik tertentu ada di dalam suatu objek atau di luar.

  • Aturan Ganjil-Genap
  • Aturan nomor belitan bukan nol

Aturan Ganjil-Genap

Dalam teknik ini, kita akan menghitung tepi yang melintasi garis dari titik mana pun (x, y) hingga tak terhingga. Jika jumlah interaksi ganjil, maka titik (x, y) adalah titik interior; dan jika jumlah interaksinya genap, maka titik (x, y) adalah titik eksterior. Contoh berikut menggambarkan konsep ini.

Dari gambar di atas, kita dapat melihat bahwa dari titik (x, y), banyaknya titik interaksi di sisi kiri adalah 5 dan di sisi kanan adalah 3. Dari kedua ujungnya, jumlah titik interaksi adalah ganjil, jadi intinya dipertimbangkan di dalam objek.

Aturan Nomor Berliku Bukan Nol

Metode ini juga digunakan dengan poligon sederhana untuk menguji titik yang diberikan interior atau tidak. Ini dapat dipahami secara sederhana dengan bantuan pin dan karet gelang. Pasang pin di salah satu tepi poligon dan ikat karet gelang di dalamnya lalu regangkan karet gelang di sepanjang tepi poligon.

Ketika semua tepi poligon tertutup oleh karet gelang, periksa pin yang telah dipasang di titik yang akan diuji. Jika kita menemukan setidaknya satu angin pada titik tersebut, pertimbangkan itu dalam poligon, jika tidak, kita dapat mengatakan bahwa titik tersebut tidak berada di dalam poligon.

Dalam metode alternatif lain, berikan arah ke semua tepi poligon. Gambar garis pindai dari titik yang akan diuji ke arah paling kiri dari arah X.

  • Berikan nilai 1 ke semua sisi yang mengarah ke atas dan -1 lainnya sebagai nilai arah.

  • Periksa nilai arah tepi yang dilewati garis pindai dan jumlahkan.

  • Jika jumlah total nilai arah ini bukan nol, maka titik yang akan diuji ini adalah interior point, jika tidak, itu adalah exterior point.

  • Pada gambar di atas, kami menjumlahkan nilai arah dari mana garis pindai melewati maka totalnya adalah 1 - 1 + 1 = 1; yang bukan nol. Jadi intinya dikatakan sebagai titik interior.