Clipping Polygon

Suatu poligon dinyatakan dengan deretan koordinat titik-titik verteksnya. Poligon bisa konveks atau konkaf. Diharapkan dari kliping poligon terhadap suatu window maka akan diperoleh poligon (atau poligon-poligon) baru irisan dari poligon asal dengan window. Window sendiri seperti halnya pada masalah kliping garis yang paling sederhana bisa berbentuk segi empat, atau poligon konveks atau poligon konkaf yaitu yang paling sulit.

Algoritma Sutherland-Hodgeman (SH)

Algoritma ini adalah untuk kliping poligon konkaf/konveks terhadap suatu poligon konveks. Idenya adalah melakukan pemotongan terhadap batas demi batas window secara terpisah. Pemotongan terhadap suatu batas (dan perpanjangan batas itu) menghasilkan suatu poligon lain yang akan dipotongkan terhadap batas selanjutnya (dan perpanjangannya). Perhatikan contoh pada gambar berikut ini di mana suatu poligon dipotong terhadap suatu window berbentuk persegi panjang. Pemotongan dilakukan pertama terhadap sisi kiri, kemudian terhadap sisi kanan, bawah, dan terakhir atas.

Pertanyaan selanjutnya adalah bagaimana caranya pemotongan terhadap suatu garis batas? Algoritma ini memiliki aturan-aturan sebagai berikut jika poligon dinyatakan oleh verteks-verteks v1, v2, …, vn.

· Sisi demi sisi diperiksa terhadap batas window mulai dari sisi v1v2, v1v3, …, vn-1vn, dan vnv1, untuk mendapatkan verteks-verteks membentuk poligon baru hasil pemotongan tersebut. Pada tahap inisialisasi poligon hasil berisikan 0 verteks.

· Bila suatu sisi vivi+1 berpotongan dengan batas window dengan vi berada di luar mengarah dan vi+1 berada di dalam batas window maka dilakukan komputasi untuk mendapatkan titik perpotongannya yaitu vi’, dan verteks-verteks vi’ dan vi+1 dicatat sebagai verteks berikutnya di poligon hasil pemotongan.

· Bila suatu sisi vivi+1 berpotongan dengan batas window dengan vi berada di dalam mengarah dan vi+1 berada di luar batas window maka dilakukan komputasi untuk mendapatkan titik perpotongannya yaitu vi’, dan verteks vi’ dicatat sebagai verteks berikutnya di poligon hasil pemotongan.

· Bila suatu sisi vivi+1 tidak berpotongan dengan batas window dan berada di sebelah dalam batas window maka verteks vi+1 dicatat sebagai verteks berikutnya di poligon hasil pemotongan.

· Bila suatu sisi vivi+1 tidak berpotongan dengan batas window dan berada di sebelah luar batas window maka tidak ada yang dicatat.

Contoh berikut adalah pemotongan poligon terhadap sisi kiri window persegi empat.

Poligon yang dihasilkan adalah dengan verteks-verteks v1’v2v3v3’.

Masalah yang muncul pada algoritma ini adalah apabila terjadi lebih dari satu kali keluar-masuk window maka akan terbentuk suatu poligon yang sebenarnya adalah beberapa area terpisah tapi dihubungkan oleh garis-garis. Ini mungkin terjadi pada poligon konkaf dan tidak terjadi pada poligon konveks.

Perhatikan gambar berikut yang menggambarkan sebelum dan setelah kliping suatu poligon.

Jika diharapkan bahwa untuk kasus ini akan terbentuk bukan hanya satu poligon tetapi sejumlah piligon untuk setiap area maka perlu modifikasi pada algoritma dengan menambahkan pemeriksaan akhir ada tidaknya sisi-sisi poligon yang berimpit dan jika ada melakukan pemotongan pada tempat tersebut.