ALGORITMA UNTUK PENGGAMBARAN GARIS
Penggambaran grafik garis lurus dan kurva memerlukan waktu komputasi yang tinggi, untuk
mereduksi waktu komputasi yang tinggi tersebut dapat dilakukan dengan peningkatan kemampuan
komputasi prosesor dan peningkatan efisiensi algoritma. Algoritma Midpoint merupakan Algoritma
dengan dasar operasi bilangan integer, sehingga memerlukan waktu operasi yanglebih sedikit
dibandingkan dengan algoritma yang menggunakan operasi bilangan riel.
Implementasi ke dalam bahasa pemrograman C dari kedua macam algoritma diatas,
menunjukkan bahwa waktu komputasi algoritma midpoint lebih cepat sebesar 8 kali pada pembuatan
garis lurus, dan lebih cepat sebesar 15 kali pada penggambaran lingkaran, dibandingkan dengan waktu
komputasi algoritma yang menggunakan dasar operasi bilangan riel. Dan waktu komputasi algoritma
midpoint lebih cepat sebesar 6 kali pada pembuatan garis lurus, dibandingkan dengan waktu komputasi
lgoritma yang Breserham telah menggunakan dasar operasi bilangan integer juga.
Kata kunci: Penggambaran garis, penggambaran kurva,
Algoritma Bresenham, Algoritma midpoint, Algoritma DDA.
1. PENDAHULUAN
Perkembangan kemampuan komputasi prosesor yang pesat telah membuatkomputer desktop
mempunyai kemampuan komputasi yang besar. Hal inimendorong perkembangan program aplikasi
yang memerlukan komputasi yangbesar seperti program aplikasi yang menggunakan grafik 3
dimensi.Peningkatan kemampuan komputasi prosesor untuk aplikasi grafik yangsarat komputasi, perlu
dibarengi peningkatan efisiensi algoritma,sehingga pembuatan grafik garis dan kurva yang merupakan
dasar pembuatangrafik dapat memberikan hasil yang optimal.
Algoritma midpoint merupakan algoritma pembuatan garis dan kurva dengan dasar operasi
bilangan integer yang menonjolkan ciri kecepatan. Sehingga algoritma ini dapat dipakai sebagai
algoritma pembuatan grafik yang menuntut kecepatan sebagai hal yang diutamakan. Pembahasan algoritma Midpoint dilakukan dengan mengasumsikan garis lurus dari kiri ke kanan,dan gadient antara
0 dan 1, sedangkan untuk lingkaran dengan mengasumsikan hanya sebagian lingkaran dengan sudut
sebesar 45° , hal ini dilakukan untuk mempermudah penjelasan, sedangkan untuk kondisi yanglain
dapat diderivasi dengan cara yang serupa. Untuk mendapatkan kinerja algoritma midpoint, dilakukan
uji kecepatan komputasi dengan cara mengimplementasikan kedalam bahasa pemrograman C, dan
melakukan perbandingan waktu komputasi dengan algoritma yang menggunakan dasar komputasi
bilangan riel, maupun algoritma lain yang telah banyak dikenal seperti algoritma dda dan algoritma
bressenham.
2. GARIS LURUS
Garis lurus dinyatakan dinyatakan dalam persamaan :
y = mx + c (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
riel, 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 riel untuk menghitung gradient m dan konstanta c.
m = (y2 - y1 ) / (x2-x1) (2)c = y1 ? m* x1* (3)
Operasi bilangan riel 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.
2.1 Algoritma Bresenham
Bresenham pada tahun 1965, melakukan perbaikan dari algoritma perhitungan koordinat piksel
yang menggunakan persamaan (1), dengan cara menggantikan operasi bilangan riel 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 riel dengan operasi bilangan integer. Operasi bilangan integer jauh
lebih cepat dibandingkan dengan operasi bilangan riel, terutama pada penambahan dan pengurangan.
2.2 Algoritma Midpoint untuk Penggambaran Garis
Algoritma midpoint dikembangkan oleh Pitteway pada tahun 1967. Pada gambar 1, titik abu-
abu menyatakan posisi piksel, titik hitam menyatakan posisi piksel yang telah digambar. Berdasarkan
piksel ke n yang telah digambar, diperlukan metode untuk menentukan piksel berikut yang akan
digambar, karena penggambaran dilakukan dari kiri ke kanan, maka piksel berikutnya harus pada
kolom n+1. Karena gradien diantara 0 dan 1, maka piksel berikutnya adalah pada posisi titik p atau titik
q.
Persamaan garis lurus yang telah dinyatakan dalam persamaan (1) dapat dinyatakan dalam fungsi x,y
berikut.
*f(x, y) = ax + by + c = 0 *(4)Fungsi f(x,y) dalam persamaan (4), akan memberikan nilai 0 pada setiap titik yang terletak pada
garis, dan bernilai positip pada setiap titik yang terletak dibawah garis, dan bernilai negatif pada setiap
titik yang terletak diatas garis. Maka untuk menentukan apakah titik P atau Q sebagai koordinat piksel
berikutnya, maka dilakukan dengan cara menghitung nilai fungsi f(x,y) dalam persamaan (4) pada titik
P dan titik Q . Jika fungsi f(x,y) tersebut memberikan nilai positif, maka piksel berikutnya adalah Q,
sebaliknya piksel berikutnya adalah P.
*g(x, y) = f(xn + 1, yn + 1/2) *(5)
Fungsi g(x,y) persamaan (5) merupakan variabel penentu, dengan mengevaluasi g (x, y) dapat
ditentukan piksel berikutnya yang mana berdasarkan tanda plus atau minus dari hasil fungsi g(x,y).
Untuk mempercepat komputasi fungsi g(x,y), dilakukan dengan cara incremental berdasarkan nilai
sebelumnya. Untuk setiap piksel, increment sederhana (DeltaG) dipakai sebagai variabel penentu.
Karena hanya ada 2 pilihan piksel pada setiap tahap, maka hanya ada 2 increment yang dapat
digunakan. Hal ini dilakukan dengan cara pengurangan nilai g(x,y) yang berurutan dengan
menggunakan persamaan 4 dan persamaan 5.
*DeltaG = a * DeltaX + b * DeltaY *(6)
Dimana DeltaX dan DeltaY adalah increment yang dipakai pada x dan y, yang bernilai 0 atau 1. Bila
bergeser 1 piksel ke kanan :
*DeltaG1 = a* (7)
Bila bergeser 1 piksel ke kanan dan 1 piksel ke atas.
*DeltaG2 = a + b *(8)
Jadi nilai dari variable penentu dapat dihitung dari nilai sebelumnya dengan cara menambah dengan (a)
atau (a+b). Algoritma untuk menggambar garis lurus dari (x1, y1) sampai (x2, y2) dilakukan dengan
langkah-langkah sebagai-berikut: 1. Gambar piksel pertama (x1,y1). Hitung variabel penentu dengan persamaan (3).
2. Tentukan tanda variabel penentu. Jika variabel penentu bernilai positif, increment x dan y dan
tambahkan (a+b) pada vaiabel penentu, sebaliknya increment x dan y dan tambahkan (a)
pada variabel penentu.
3. Plot piksel pada posisi (x, y).
4. Ulangi langkah mulai langkah kedua, sampai piksel terakhir (x2,y2).
DDA (Digital Defferential Analyzer)
Prinsip algoritma ini adalah mengambil nilai integer terdekat dengan jalur garis berdasarkan atas
sebuah titik yang telah ditentukan sebelumnya(titik awal garis).
Algoritma pembentukan garis DDA :
1. Tentukan dua titik yang akan dihubungkan dalam pembentukan garis.
2. Tentukan salah satu titik sebagai awal(x0,y0) dan titik akhir(x1,y1).
3. Hitung dx=x1¬x0, dan dy= y1¬y0.
4. Tentukan langkah, yaitu dengan cara jarak maksimum jumlah penambahan nilai x maupun nilai y,
dengan caara :
- Bila nilai absolut dari dx lebih besar dari absolut dy, maka langkah= absolut
dari dx.
- Bila tidak maka langkah= absolut dari dy
5. Hitung penambahan koordinat pixel yaitu x_increment=dx/langkah, dan y_increment=dy/langkah.
6. Koordinat selanjutnya (x+x_increment, y+y_increment).
7. Posisi pixel pada layar ditentukan dengan pembulatan nilai koordinat tersebut.
8. Ulangi nomor 6 dan 7 untuk menentukan posisi pixel selanjutnya,sampai x=x1
dan y=y1.
Garis merupakan kumpulan dari titik-titik, untuk membentuk garis lurus adalah dengan
mengetahui titik awal dan titik akhir. Dengan mengetahui titik awal dan titik akhir maka kita dapat
membentuk garis. Untuk menggambarkan proses pembuatan garis dari titik awal ke titik akhir ada
berbagai algoritma. Algoritam yang umum adalah DDA dan Bresenham.
Perkembangan kemampuan komputasi prosesor yang pesat telah membuat komputer desktop
mempunyai kemampuan komputasi yang besar. Hal ini mendorong perkembangan program aplikasi
yang memerlukan komputasi yang besar seperti program aplikasi yang menggunakan grafik 3 dimensi.
Peningkatan kemampuan komputasi prosesor untuk aplikasi grafik yang sarat komputasi, perlu
dibarengi peningkatan efisiensi algoritma, sehingga pembuatan grafik garis dan kurva yang merupakan
dasar pembuatan grafik dapat memberikan hasil yang optimal.Contoh Aplikasi
Tampilan Awal Aplikasi
Tampilan Form GarisKoordinat Garis berubah
Source Code :
' Gambas class file
PUBLIC SUB form_Open()

'Membuat Garis menggunakan label
LabelGaris.Text = "__________________________________"
'membuat form menjadi maximize saat dibuka
ME.Maximized = TRUE

END
PUBLIC SUB Form_Keypress()
'Perintah Select Case untuk mengatur koordinat garis menggunakan tombol arah di keyboard
SELECT Key.Code
'Menset tombol arah kiri, bila ditekan maka koordinat X garis akan berpindah sebanyak -20 dari
koordinat sebelumnya
CASE Key.Left LabelGaris.X = LabelGaris.X - "20"
'Menset tombol arah kanan, bila ditekan maka koordinat X garis akan berpindah sebanyak +20 dari
koordinat sebelumnya
CASE Key.Right
LabelGaris.X = LabelGaris.X + "20"
'Menset tombol arah atas, bila ditekan maka koordinat Y garis akan berpindah sebanyak -20 dari
koordinat sebelumnya
CASE Key.Up
LabelGaris.Y = LabelGaris.Y - "20"
'Menset tombol arah bawah, bila ditekan maka koordinat Y garis akan berpindah sebanyak +20 dari
koordinat sebelumnya
CASE Key.Down
LabelGaris.Y = LabelGaris.Y + "20"
END SELECT
END
PUBLIC SUB Form_Close()

FMain.Close

ENDTampilan Form Titik
Koordinat titik berubahSource Code :
' Gambas class file
PUBLIC SUB Form_Open()

'Membuat Titik menggunakan label
LabelTitik.Text = "............................."
'membuat form menjadi maximize saat dibuka
ME.Maximized = TRUE

END
PUBLIC SUB Form_Keypress()
'Perintah Select Case untuk mengatur koordinat Titik menggunakan tombol arah di keyboard
SELECT Key.Code
'Menset tombol arah kiri, bila ditekan maka koordinat X titik akan berpindah sebanyak -20 dari
koordinat sebelumnya
CASE Key.Left
LabelTitik.X = LabelTitik.X - "20"
'Menset tombol arah kanan, bila ditekan maka koordinat X titik akan berpindah sebanyak +20 dari
koordinat sebelumnya
CASE Key.Right
LabelTitik.X = LabelTitik.X + "20"

'Menset tombol arah atas, bila ditekan maka koordinat Y titik akan berpindah sebanyak -20 dari
koordinat sebelumnya
CASE Key.Up
LabelTitik.Y = LabelTitik.Y - "20"
'Menset tombol arah bawah, bila ditekan maka koordinat Y titik akan berpindah sebanyak +20 dari
koordinat sebelumnya
CASE Key.Down
LabelTitik.Y = LabelTitik.Y + "20"
END SELECT
END
PUBLIC SUB Form_Close()
FMain.Close

END
Catatan :
Contoh dari program menggunakan Pemrograman Basic di Sistem Operasi Linux menggunakan
Gambas 2.KESIMPULAN
Panjang garis atau banyak piksel dalam garis lurus sangat berpengaruh terhadap perbandingan
performance antara sebuah algoritma dengan algoritma yang lain, hal ini disebabkan adanya perbedaan
waktu operasi yang berada didalam perulangan sepanjang pembuatan piksel, dan waktu operasi yang
berada pada sebelumnya. Panjang jari-jari dalam lingkaran tidak berpengaruh terhadap perbandingan
performance antara sebuah algoritma dengan algoritma yang lain, hal ini menunjukkan perbandingan
waktu operasi yang berada didalam perulangan sepanjang pembuatan piksel, dan waktu operasi yang
berada pada sebelumnya berimbang.
Algoritma dengan dasar operasi bilangan integer memberikan waktu operasi yang lebih cepat
dibandingkan dengan algoritma dengan dasar operasi bilangan riel, hal ini ditunjukkan dengan waktu
komputasi algoritma DDA, algoritma Bresenham dan algoritma Midpoint yang lebih cepat, baik pada
pembuatan garis lurus maupun lingkaran dibandingan waktu komputasi dengan algoritma yang
menggunakan dasar operasi bilangan riel. Algoritma midpoint memberikan waktu operasi tercepat
diantara algoritma penggambaran garis lurus yang telah menggunakan dasar operasi bilangan integer,
seperti algoritma DDA, algoritma Bresenham. Jadi algoritma Midpoint merupakan algoritma yang
cocok untuk penggambaran grafik yang menuntut kecepatan sebagai hal yang diutamakan.









Hasil nya :
Tampilan garis



Koordinat Garis berubah



Source code titik :
' Gambas class file
PUBLIC SUB form_Open()
'Membuat Garis menggunakan label
LabelGaris.Text = "__________________________________"
'membuat form menjadi maximize saat dibuka
ME.Maximized = TRUE
END
PUBLIC SUB Form_Keypress()
'Perintah Select Case untuk mengatur koordinat garis menggunakan tombol arah di keyboard
SELECT Key.Code
'Menset tombol arah kiri, bila ditekan maka koordinat X garis akan berpindah sebanyak -20 dari koordinat sebelumnya
CASE Key.Left
LabelGaris.X = LabelGaris.X - "20"
'Menset tombol arah kanan, bila ditekan maka koordinat X garis akan berpindah sebanyak +20 dari koordinat sebelumnya
CASE Key.Right
LabelGaris.X = LabelGaris.X + "20"
'Menset tombol arah atas, bila ditekan maka koordinat Y garis akan berpindah sebanyak -20 dari koordinat sebelumnya
CASE Key.Up
LabelGaris.Y = LabelGaris.Y - "20"
'Menset tombol arah bawah, bila ditekan maka koordinat Y garis akan berpindah sebanyak +20 dari koordinat sebelumnya
CASE Key.Down
LabelGaris.Y = LabelGaris.Y + "20"
END SELECT
END
PUBLIC SUB Form_Close()
FMain.Close
END

Hasilnya :








Tampilan Form Titik








Koordinat titik berubah