Algoritma line clipping dengan memanfaatkan ruang semi dual

Abstract

Ada beberapa algoritma line clipping yang menggunakan poligon sebagai pembatas, antara lain: algoritma Modified Cyrus-Beck (MCB), algoritma Dual Space (DS), dan algoritma Semi Dual Space (SDS). Algoritma DS dan MCB membutuhkan N kali pengujian untuk menentukan perpotongan garis dengan sisi-sisi poligon. Seliingga semakin banyak sisi paligon (N) maka semakin besar waktu eksekusi yang diperlukan. Sedangkan algoritma SDS memanfaatkan ruang semi dual untuk melakukan proses line clipping, sehingga penentuan perpotongan garis dengan sisi poligon tidak membutuhkan N kali pengujian. Dengan demikian algoritma SDS akan lebih efisien jika digunakan untuk jumlah sisi poligan yang semakin besar. Aigaritma DS dan MCB terdiri dari satu tahap, yaitu tahap line clipping. Sedangkan algoritma SDS terdiri dari dua tahap, yaitu: tahap prakalkulasi dan tahap line clipping. Tahap prakalkulasi dilakukan satu kali dan tahap line clipping dilakukan sebanyak jumlah garis dan ulangan. Namun prakalkulasi memerlukan banyak komputasi sehingga dapat memperiambat proses line clipping secara keseluruhan. Pengaruh prakalkulasi dapat dibuat sekecil mungkin dengan pemilihan jumlah partisi yang sesuai.