Algoritma
Garis
Algoritma garis adalah algoritma untuk menentukan
lokasi pixel yang paling dekat dengan garis sebenarnya (actual line)
Ada 3 algoritma utama untuk menggambar garis :
1.Line
Equation
2.DDA
Algorithm
3.Bresenham’s
Algorthm
1.ALGORITMA
LINE EQUATION (PERSAMAAN GARIS LURUS)
Persamaan
garis lurus merupakan persamaan linier yang mengandung satu atau dua variable.
Sebuah garis lurus
dapat diperoleh dengan menggunakan rumus :
y=mx + b
dimana :
m = Gradient
b = Perpotongan garis dengan sumbu y.
Apabila dua pasang titik akhir dari sebuah garis
dinyatakan sebagai (x1,y1) and (x2,y2) , maka nilai dari gradient m dan lokasi
b dapat dihitung dengan :
Persamaan garis dapat digunakan disemua kwadran
Tipe Garis
Dapatkah anda mencari perbedaan yang esensial antara
garis A dan B (misal : gradient,pertambahan
x dan y ) ?
Garis
A : (3;1)-(8;4)
m
= (y2 – y1)/(x2-x1) = (4-1)/(8-3)=3/5=0,6
0
< m < 1
x1+1
= xi + 1 ; y1 + 1 = y1 + d1
Garis
B : (1;2)-(2;7)
m
= (7-2) / (2-1) = 5/1 = 5
m
> 1
xi
+ 1 = xi + d2 ; yi + 1 = yi + 1
2.ALGORITMA DDA
A.
PENGERTIAN ALGORITMA DDA
Algoritma DDA adalah algoritma pembentukan garis berdasarkan
perhitungan dx maupun dy, menggunakan rumus dy=m.dx. Semua koordinat titik yang
membentuk garis diperoleh dari perhitungan kemudian dikonversikan menjadi nilai
integer.
DDA ( Digital Differential Analyzer) adalah garis yang
membentang antara 2 titik, P1 dan P2. Dimana ke-2 titik ini membentuk sudut
yang besarnya sangat bervariasi. Bekerja atas dasar penambahan nilai x dan
nilai y. Dimana pada garis lurus, turunan pertama dari x dan y adalah kostanta.
B.
LANGKAH LANGKAH PEMBENTUKAN GARIS ALGORITMA DDA
1. Tentukan dua titik yang akan dihubungkan dalam pembentukan
garis.
2. Tentukan salah satu sebagai titik awal (x1, y1) dan titik
akhir (x2, y2).
3. Hitung dx = x2 – x1 dan dy = y2 – y1
4. Tentukan step, yaitu jarak maksimum jumlah penambahan nilai
x atau nilai y, dengan ketentuan:
a. bila |dx| > |dy| maka
step = |dx|
b. bila tidak, maka step =
|dy|
5. Hitung penambahan koordinat pixel dengan persamaan:
x_inc = dx / step
y_inc
= dy / step
6. Koordinat selanjutnya (x+x_inc, y+y_inc)
7. Plot pixel pada layar, nilai koordinat hasil perhitungan
dibulatkan
8. Ulangi step nomor 6 dan 7 untuk menentukan posisi pixel
berikutnya sampai x = x1 atau y = y1.
C.
KEUNTUNGAN DAN KERUGIAN ALGORITMA DDA
Keuntungan dari algoritma Digital Differential Analyzer (DDA) adalah
tidak perlu menghitung koordinat berdasarkan persamaan yang lengkap (menggunakan
metode off set)
Kerugiannya dari algoritma Digital Differential Analyzer (DDA) adalah adanya akumulasi Round-off errors, sehingga garis akan melenceng dari garis lurus, selain itu operasi round-off
juga menghabiskan waktu.
3.ALGORITMA BRESENHAM
A.PENGERTIAN
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.
B.
ATURAN BRESENHAM
· Jika Pk bernilai positif (+), maka tambahkan hasilnya dengan
B dan nilai x dan y ditambah 1.
· Jika Pk bernilai negatif (-), maka tambahkan hasilnya dengan
A dan nilai x ditambah 1, sedangkan y ditambah 0 (tetap).
· Putaran dihentikan jika koordinat x dan y sudah mencapai
batas akhir.
C.
PRINSIP DARI ALGORITMA BRESENHAM
1. Sumbu vertikal memperlihatkan posisi scan line.
2. Sumbu horizontal memperlihatkan kolom pixel
3. Pada tiap langkah, penentuan pixel selanjutnya didasari oleh
parameter integer yang nilainya proporsional dengan pengurangan antara vertical
separations dari dua posisi piksel dari nilai actual.
Garis
lurus dinyatakan dinyatakan dalam persamaan :
y
= mx + c è Persamaan(1)
dimana
:
m
: gradient dan
c
: konstanta.
Untuk menggambarkan piksel-piksel dalam garis lurus,
parameter yang digunakan tergantung dari gradient, jika besarnya gradient
diantara 0 dan 1, maka digunakan sumbu x sebagai parameter dan sumbu y sebagai
hasil dari fungsi, sebaliknya, bila gradient melebihi 1, maka sumbu y digunakan
sebagai parameter dan sumbu x sebagai hasil dari fungsi, hal ini bertujuan
untuk menghindari terjadinya gaps karena adanya piksel yang terlewatkan. Hasil
dari fungsi biasanya merupakan bilangan real, sedangkan koordinat pixel
dinyatakan dalam bilangan integer (x,y), maka diperlukan operasi pembulatan
kedalam bentuk integer terdekat. Penggambaran garis lurus dengan metode diatas
dimulai dengan operasibilangan real untuk menghitung gradient m dan konstanta c.
m
= (y2 – y1 ) / (x2-x1) (2)
c
= y1 / m* x1* (3)
Operasi
bilangan real berikutnya adalah menghitung nilai y dengan persamaan (1) Untuk
mendapatkan koordinat piksel (x,y), untuk setiapnilai x, dari =x1 sampai x=x2,
operasi inilah yang perlu dihindari,karena operasi ini memerlukan waktu operasi
yang besar.
D.
LANGKAH LANGKAH PEMBENTUKAN GARIS ALGORITMA DDA
1. Tentukan 2 titik yang akan dihubungkan dalam pembentuk
garis.
2. Tentukan salah satu titik disebelah kiri sebagai titik awal,
yaitu (X0,Y0) dan titik lainnya sebagai titik akhir (X1, Y1)
3. hitung Dx, Dy, 2DX dan 2Dy-2Dy
4. Hitung parameter P0= 2Dy – 2Dx
5. Untuk setiap X1 sepanjang jalur garis, dimulai dengan k=0,
· bila pk<0, makatitik selanjutnya adalah (Xk + 1, Yk) dan
Pk+1 = Pk +2Dy
· bila tidak, maka titik selanjutnya adalah (Xk + 1, Yk +1)
dan Pk+1 = Pk +2Dy – 2Dx
Referensi :
http://iswahyuniiswahyuni.blogspot.com/2013/12/komputer-grafik-algoritma-garis.html
http://gustiam74.blogspot.com/2016/04/algoritma-pembentukan-garis-dda-dan.html