ALGORITMA GARIS
Algoritma
merupakan langkah - langkah (prosedur) yang harus dilakukan untuk menyelesaikan
sebuah masalah. Garis merupakan sederetan pixel yang membentuk satu kesatuan. Sumbu-sumbu
koordinat memisahkan bidang ke dalam empat daerah, yang disebut kuadran. Biasanya
kuadran diidentifikasi dengan angka romawi. Titik-titik pada sumbu-sumbu
koordinat tidak masuk pada sembarang kuadran. Urutan tanda dari absis dan
ordinat ( x,y).
Dalam
sistem koordinat tegak lurus
setiap pasangan berurutan dari bilangan real dinyatakan dengan
satu dan hanya satu titik pada bidang koordinat, dan setiap titik pada bidang
koordinat berkorespondensi satu dan hanya satu pasangan berurutan dari bilangan real.
Koordinat
titik-titik yang ditentukan dengan cara ini, seringkali dikenal sebagai koordinat Cartesius,
sebagai penghormatan terhadap matematikawan dan filosof asal Perancis
yang bernama René Descartes yang hidup dari 1596 sampai1650. Satu hal yang
perlu dicatat adalah dua garis sumbu koordinat tidak perlu harus berpotongan
secara tegak lurus. Namun demikian jika kedua sumbu berpotongan miring, hasil-hasil
secara aljabar menjadi lebih rumit.
1.
Garis (Line)
Persamaan
garis :
q y = m.x + c
dimana
:
• m = (y2-y1)/(x2-x1) = Dy/Dx
• c = y1 – m.x1 atau c = y2 – m.x2
2. Algoritma
Pembuatan Garis
Algoritma
pembuatan garis lurus vertikal dan horisontal relatif mudah, tetapi bila garis
tersebut miring, maka algoritma menjadi sulit.
3. Algoritma
Garis
Algorithma
garis adalah algorithma untuk menentukan lokasi pixel yang paling dekat dengan garis
sebenarnya (actual line). Ada
tiga algorithma untuk menggambar garis :
A. Line
Equation (Persamaan Garis Lurus)
Persamaan
garis lurus merupakan persamaan linier yang mengandung satu atau dua variabel. 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
gradien m dan lokasi b dapat dihitung dengan :
B. DDA
(Digital Difference Analyser)
Digital
differential analyzer (DDA) merupakan algoritma untuk menghitung posisi pixel
di sepanjang garis dengan menggunakan posisi pixel sebelumnya. Algoritma ini
menggunakan asumsi bahwa garis berada di kuadran I atau II serta tipe garis
cenderung tegak atau cenderung mendatar
dan mengatur titik-titik koordinat pada
masing-masing sumbu.
·
Untuk garis dengan 0<
m ≤1 (cenderung mendatar di Kuadran
I), maka :
Ø yk+1=yk + m
Ø xk+1 = xk + 1
·
Untuk garis dengan m
> 1 (cenderung tegak di Kuadran I),
maka :
Ø xk+1=xk + 1/m
Ø yk+1 = yk + 1
·
Untuk garis
dengan 0 > m > -1 (cenderung mendatar di Kuadran II), maka:
Ø yk+1=yk - m
Ø xk+1 = xk - 1
·
Bila
m < -1 (cenderung tegak di Kuadran
II), maka :
Ø xk+1=xk - 1/m
Ø yk+1 = yk + 1
Digital
Diferensial Analyser (DDA) adalah algoritma pembentukan garis berdasarkan
perhitungan dx maupun dy, menggunakan rumus dy = m . dx. Garis dibuat menggunakan
dua endpoint, yaitu titik awal dan titik akhir. Setiap koordinat titik yang
membentuk garis diperoleh dari perhitungan, kemudian dikonversikan menjadi
nilai integer.
Langkah-langkah
membentuk garis menurut algoritma DDA adalah :
1. Tentukan
2 buah titik
2.
Tentukan yang menjadi
titik awal (X0,
Y0) dan titik akhir (X1, Y1)
3.
Hitung Dx dan Dy
Dx
= X1 – X0 dan Dy = Y1
– Y0
4. Bandingkan
absolut (Dx) dan absolut (Dy)
Jika absolute (Dx) > absolut (Dy),
maka
Steps = absolute (Dx) bila tidak, steps
= absolut (Dy)
5. Hitung
penambahan koordinat pixel, yaitu:
6. Koordinat
selanjutnya yaitu:
X + X_increment
Y + Y_increment
7. Posisi
pixel ditentukan dengan pembulatan nilai koordinat tersebut.
8. Ulangi
langkah 6 dan 7 untuk posisi selanjutnya sampai X = X1, Y= Y1
C. Algoritma
Bresenham
·
Garis Lurus
Garis lurus dinyatakan dinyatakan dalam
persamaan :
y
= mx + c è Persamaan (1)
dimana
:
m
: gradient
c
: konstanta
Untuk
menggambarkan pixel-pixel dalam garis lurus,
parameter yang digunakan tergantung dari gradient, jika besarnya gradien
diantara 0 dan 1, maka digunakan sumbu x sebagai parameter dan sumbu y sebagai
hasil dari fungsi, sebaliknya, bila gradien melebihi 1, maka sumbu y digunakan
sebagai parameter dan sumbu x sebagai hasil dari fungsi, hal ini bertujuan
untuk menghindari terjadinya gaps karena adanya pixel 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 operasi bilangan
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 setiap nilai x, dari =x1 sampai x=x2, operasi inilah yang
perlu dihindari,karena operasi ini memerlukan waktu operasi yang besar.
·
Algoritma Bresenham
untuk Penggambaran Garis
Bresenham
pada tahun 1965, melakukan perbaikan dari algoritma perhitungan koordinat
piksel yang menggunakan persamaan (1), dengan cara menggantikan operasi
bilangan real perkalian dengan operasi penjumlahan, yang kemudian dikenal
dengan Algoritma Bresenham. Pada algoritma bresenham, nilai y kedua dan
seterusnya, dihitung dari nilai y sebelumnya, sehingga hanya titik y pertama
yang perlu dilakukan operasi secara lengkap. Perbaikan algoritma ini ternyata
tidak menghasilkan perbaikan yang cukup siginifikan. Perbaikan berikutnya
dilakukan dengan cara menghilangkan operasi bilangan real dengan operasi
bilangan integer. Operasi bilangan integer jauh lebih cepat dibandingkan dengan
operasi bilangan real, terutama pada penambahan dan pengurangan.
·
Algoritma Garis
Bresenham
Prosedur
untuk menggambar kembali garis dengan membulatkan nilai x atau y ke bilangan
integer memerlukan waktu. serta variabel x,y maupun m memerlukan bilangan real
karena kemiringan merupakan nilai pecahan.Bressenham mengembangkan algoritma
klasik yang lebih menarik, karena hanya menggunakan perhitungan matematik
dengan bantuan bilangan integer. Dengan demikian tidak perlu membulatkan nilai
posisi pixel setiap waktu. Langkah-langkahnya adalah sebagai berikut:
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, maka titik 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
6.
Ulangi langkah no. 5
untuk menentukan posisi selanjutnya, sampai X=X1 dan Y=Y1.
Atribut Tipe Garis
Atribut
tipe atau style pada garis dibagi menjadi 3 (tiga) yaitu :
1.
Solid line
Algoritma pembentukan garis dilengkapi dengan pengaturan
panjang dan jarak yang menampilkan bagian solid sepanjang garis.
2.
Dashed line
(garis putus)
Garis putus dibuat dengan memberikan jarak dengan bagian
solid yang sama.
3.
Dotted line
(garis titik-titik)
Garis titik-titik dapat ditampilkan dengan memberikan
jarak yang lebih besar dari bagian.
Atribut Tebal Garis
·
Implementasi
dari tebal garis tergantung dari kemampuan alat output yang digunakan. Garis
tebal pada video monitor dapat ditampilkan sebagai garis adjacent parallel
(kumpulan garis sejajar yang berdekatan), sedangkan pada plotter mungkin
menggunakan ukuran pen yang berbeda.
·
Pada
implementasi raster, tebal garis standar diperoleh dengan menempatkan satu
pixel pada tiap posisi, seperti algoritma Bressenham. Garis dengan ketebalan
didapatkan dengan perkalian integer positif dari garis standar, dan menempatkan
tambahan pixel pada posisi sejajar. Untuk garis dengan slope kurang dari 1,
routine pembentukan garis dapat dimodifikasi untuk menampilkan ketebalan garis
dengan menempatkan pada posisi vertical setiap posisi x sepanjang garis. Untuk
garis dengan slope lebih besar dari 1, ketebalan garis dapat dibuat dengan
horizontal span.
Atribut Warna Garis
Bila suatu sistem dilengkapi dengan pilihan warna (atau
intensitas), parameter yang akan diberikan pada indeks warna termasuk dalam
daftar nilai atribut dari sistem. Routine polyline membuat garis pada warna
tertentu dengan mengatur nilai warna pada frame buffer untuk setiap posisi
pixel, menggunakan prosedur set pixel. Jumlah warna tergantung pada jumlah bit
yang akan digunakan untuk menyimpan informasi warna.
Sumber :
Tidak ada komentar:
Posting Komentar