ALGORITMA PENGGAMBARAN GARIS
Persamaan slope-intercept pada bidang kartesius, untuk garis lurus dinyatakan sebagai:
Y = m.x + b (1)
Dengan m menyatakan slope atau kemiringan garis dan b sebagai suatu intercept y. Misalkan diketahui dua endpoint pada sebuah garis yang dispesifikasi pada posisi (x1.y1) dan (x2,y2).
Dengan m menyatakan slope atau kemiringan garis dan b sebagai suatu intercept y. Namun kita juga dapat menentukan nilai untuk slope atau kemiringan garis yang dinotasikan dengan m dan nilai y, serta intercept b dengan menggunakan persamaan:
m =(y2-y1) / (x2-x1) (2)
b = y1 - m.x1 (3)
Algoritma untuk penggambaran garis didasari pada persamaan (1), (2) dan (3).untuk, dan interval garis Dx. Kita dapat menghitung persamaan y, pada interval Dy melalui persamaan:
Dy = m. Dx (4)
Secara sederhana kita juga dapat memperoleh x pada interval Dx dengan persamaan :
Dx = Dy / m (5)
Algoritma penggambaran garis yang akan kita ulas dan implementasikan di dalam bab ini terdiri dari dua algoritma penggambaran, yaitu algoritma DDA dan algoritma bresenham.
1.1 ALGORITMA DDA
Digital Diferential Analyser adalah suatu algoritma (pendekatan) pengkonversian suatu himpunan pixel menjadi suatu garis yang didasari atas perhitungan Dx dan Dy, dengan menggunakan persamaan (4) dan (5) diatas. Kita cocokan sebuah garis pada unit interval di dalam satu koordinat dan kemudian kita tentukan nilai interger yang mempunyai jarak terdekat dengan line-path untuk koordinat yang lain. Perhatikan garis pertama dengan slope positif yang ditunjukkan gambar di atas. Jika slope kurang dari 1, kita tentukan nilai untuk unit interval x (dalam hal ini Dx=1) dan hitung beberapa hasil iterasi secara berturut2 untuk nilai y dengan persamaan
yk+1= yk + m (6)
subskrip k bernilai integer yang dimulai dari 1, untuk pengiterasian pertama, dan terus menambahakan nilai k dengan 1 sampai pasangan koordinat (x,y) Yng terpenuhi oleh algoritma tersebut. Slope m dapat berupa suatu nilai antara 0 dan 1, kemudian hasil hitungan y akan dibulatkan (trancation) menjadi suatu nilai integer yang mendekati dengan nilai sebenarnya yang bertipe pecahan (floating).
Untuk garis dengan kemiringan positif atau > (lebih besar) dari 1, kita harus menukarkan peran dari x dan y, dapat kita contohkan pada interval y (Dy=1), lalu hitung beberapa nilai x secara berturut-turut menggunakan persamaan
Xk+1 = Xk + 1/m (7)
Persamaan (6) dan (7) didasarkan dari pengasumsian suatu garis yang diproses dari titik ujung paling kiri dari garis menuju titik ujung paling kanan dari garis tersebut. Jika proses ini dibalikkan atau ditukar, suapaya diperoleh keadaan di mana titik ujung awalnya berada du sebelah kanan, maka kita harus memberikan nilai Dx=1 dan
yk+1 = yk – m
atau (di saat slope atau kemiringan garis lebih besar dari 1) maka kita harus memasukkan nilai Dy = -1 dan
Xk+1 = Xk - 1/m
Persamaan (6) dan (9) dapat juga digunakan untuk menghitung posisi pixel yang membentuk suatu garis dengan slope negatif. Jika nilai absolut slope lebih kecil dari 1 dan titik-titik ujung (endpoint) awalnya berada di sisi paling kiri, kita berikan nilai Dx = 1 dang hitung nilai yk+1 dengan persamaan (6). Dan kemudian endpoint awal berada pada posisi sebelah kanan (untuk slope yang sama), kita masukkan Dx = -1 dan kita dapatkan nilai y dari hasil perhitungan menggunakan persmaan (8). Sama juga ketika nilai absolut dari sebuah slope positif adalah besar dari 1, kita gunakan Dy = -1 dan kita tentukan Xk+1 dengan persamaan (9) atau kita gunakan Dy = 1 dan kita tentukan Xk+1 dengan persamaan (7). Algoritma ini dirangkum di dalam prosedur berikut, yang mana program menerima input dua posisi pixel endpoint (titik-titik ujung suatu garis) sebagai awalnya dan menentukan perbedaan horizontal den vertikal diantara dua posisi endpoint yang diperoleh untuk parameter dx dan dy. Perbedaan nilai yang cenderung besar akan menentukan nilai dari parameter step di dalam algoritma DDA. Dimulai dari posisi pixel (Xa,ya) kita tentukan penyeimbang yang dibutuhkan pada beberapa langkah program untuk menghasilkan posisi pixel selanjutnya sepanjang line path. Digital diferential analyzer merupakan suatu metode yang paling cepat melakukan kalkulasi (menghitung) keberadaan posisi pixel dan merupakan implementasi langsung dari persamaan (1).
1. ALGORITMA BRESENHAM
Algoritma bresenham merupakan suatu algoritma (pendekatan) yang dikreasikan oleh bresenham yang tidak kalah akurat dan efisien dengan algoritma primitif lainnya (seperti DDA). Bagian pengkonversian (scan-knversi) garis akan melakukan kalkulasi untuk penambahan nilai-nilai integer (yang dibutuhkan untuk membentuk garis) yang disesuaikan dengan tipe grafik yang dipakai oleh layar komputer (keadaan monitor pc) kita. Untuk mengilustrasikan pendekatan bresenham, pertama kita harus memperhatikan proses scan- konvensi untuk garis dengan slope positif yang lebih kecil dari 1. Posisi pixel sepanjang line-path kemudian ditentukan dengan penyamplingan pada unit interval x.dimulai dari endpoint kiri (Xo,Yo) dari garis yang diberikan, kita pindahkan beberapa kolom berturut-turut (berdasarkan posisi x) dan plot pixel-pixel yang mempunyai nilai scan-line y ke jarak yang paling dekat dengan line-path.secara matematis pembentukan algoritma bresenham adalah sebagai berikut:
y = m(Xk+1) + b (10)
di mana d1 = y-yk dan subtitusikan (10) ke da;a, d1;
d1 = m(Xk+1) + b – yk
di mana d2 = (yk + 1) – y, dan subtitusikan (10) ke dalam d2;
d2 = yk + 1 – m(Xk+1) – b
kemudian d1-d2
d1-d2 – 2m(Xk+1) – 2yk +2b – 1 (11)
nilai parameter keputusan pk untuk langkah ke-k th (k th – step) didalam algoritma bresenham dapat ditentukan dengan menyusun suatu persamaan (11).
Pk = Dx (d1 – d2)
= 2Dy. Xk - 2Dx.yk + c
Pk+1 = 2Dy.Xk+1 - 2Dx.yk+1 + c (12)
Kemudian pk+1 – pk
Pk+1 – pk = 2Dy(xk+1 – xk) - 2Dx(yk+1 – yk)
Disini kita peroleh xk+1 = xk+1, agar diperoleh suatu manipulasi persamaan berikut:
Pk+1 = pk + 2Dy - 2Dx(yk+1 – yk) (13)
Dimana yk+1 – yk mempunyai perkisaran nilai antara 0 dan 1, di mana nilai – nilai tersebut sanagt tergantung pada tanda (+ dan -) dari parameter pk. Perhitungan rekursif dari parameter ini dilakukan pada beberapa posisi integer x, dimulai pada koordinat endpoint yang paling kiri pada garis. Parameter pertama, po, dievaluasi atau digeneralisasikan dari persamaan (12) dengan posisi awal pixel (xo,yo) dan slope atau kemiringan m yang nilainya dapat ditentukan dari perhitungan atau kalkulasi Dy / Dx:
P = 2Dy - Dx
0 komentar:
Posting Komentar