Algoritma pembentukan garis

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.