Sebelum membahas mengenai Algoritma Pembentukan Garis, alangkah baiknya kita bahas dulu apa itu Garis? Garis adalah penghubung antara dua buah titik (titik awal dan titik akhir).
Seperti yang kita tahu, bahwa persamaan garis lurus dinyatakan dalam rumus: y=mx+c. Dimana m adalah gradien yang didapatkan dari hasil pembagian deltaY dengan deltaX dan c adalah sebuah konstanta. Berangkat dari sini kita coba mulai untuk membahas algortima apa saja yang digunakan dalam pembuatan garis lurus.
Langkah-Langkah Pembentukan Garis Menurut Algoritma :
Tentukan 2 buah titik yang akan dihubungkan.
Tentukan yang menjadi titik awal (X1,Y1) dan titik akhir (X2,Y2).
Hitung Dx dan Dy
Dx = X2-X1 dan Dy = Y2 – Y1
Tentukan r atau step, yaitu jarak maksimum jumlah penambahan nilai x maupun nilai y dengan cara :
bila nilai |Dx| > |Dy| maka r = nilai Dx
bila tidak maka r = nilai Dy
Hitung penambahan koordinat pixel |Dx| dan |Dy|, yaitu :
Xr = Dx/r
Yr = Dy/r
Koordinat selanjutnya (X+Xr dan Y+Yr)
Posisi pixel ditentukan dengan pembulatan nilai koordinat tersebut.
Ulangi langkah 6 dan 7 untuk posisi selanjutnya sampai X = X2, Y = Y2
Titik dan Garis:
Pembentukan titik dilakukan dengan mengkonversi suatu posisi titik koordinat dengan
program aplikasi ke dalam suatu operasi tertentu menggunakan output. Random-scan
(vektor ) system menyimpan instruksi pembentukan titik pada display list dan nilai
koordinat menentukan posisi pancaran electron ke arah lapisan fosfor pada layer.
Garis dibuat dengan menentukan posisi titik diantara titik awal dan akhir dari suatu
garis.
Persamaan garis menurut koordinat Cartesian adalah :
y = m.x+b
dimana m adalah slope (kemiringan) dari garis yang dibentuk oleh dua titik yaitu (x1, y1)
dan (x2, y2). Untuk penambahan x sepanjang garis yaitu dx akan mendapatkan
penambahan y sebesar : y = m. x
Algoritma Garis Bressenhem
Prosedur untuk menggambar kembali garis dengan membulatkan nilai x atau y
kebilangan integer membutuhkan waktu, serta variable x,y dan m merupakan bilangan
real karena kemiringan merupakan nilai pecahan. Bressenham mengembangkan
algoritma klasik yang lebih menarik, karena hanya menggunakan perhitungan
matematika dengan bilangan integer. Dengan demikian tidak perlu membulatkan nilai
posisi setiap pixel setiap waktu. Algoritma garis Bressenhem disebut juga midpoint line
algorithm adalah algoritma konversi penambahan nilai integer yang juga dapat
diadaptasi untuk menggambar sebuah lingkaran.
Langkah-langkah untuk membentuk garis menurut algoritma ini adalah :
1. Tentukan dua titik yang akan dihubungkan dalam pembentukan garis.
2. Tetukan salah satu titik disebelah kiri sebagai titik awal (x0, y0 ) dan titik lainnya
sebagai titik akhir (x1, y1 ).
3. Hitung x, y, 2 x, dan 2 y – 2 x.
4. Hitung parameter p0 = 2 y – x.
5. Untuk setiap xk sepanjang jalur garis, dimulai dengan k = 0
bila pk <0 maka titik selanjutnya (xk+1, yk) dan pk+1 = pk +2 y
bila tidak maka titik selanjutnya adalah (xk +1, yk +1)dan
pk+1 = pk +2 y–2 x.
6. Ulangi langkah nomor 5 untuk menentukan posisi pixel selanjutnya, sampai x =
x1 dan y = yk.
