pertemuan 6

ALGORITHMA GARIS

* Algorithma garis adalah algorithma untuk menentukan lokasi pixel yang paling dekat dengan garis sebenarnya (actual line), Ada tiga algorithma utama untuk menggambar garis , Line Equation, DDA Algorithm, Bresenham’s Algorithm

Kuadran Garis
Kuadran Kriteria Arah Garis Contoh

Kuadran Garis

   Di kuadran mana garis A ? Di kuadran mana garis B ? Dapatkah garis  A dan B dinyatakan sebagai garis dengan kuadran yang sama ? Bagaimana caranya ? Bagaimana halnya dengan garis C dan D ?

Kuadran Garis
- Garis A : (3 ; 1) – (8 ; 4)
      - Garis A berada di kuadran I
- Garis B : (3 ; 7) – (1 ; 2)
      - Garis B berada di kuadran III
      - m = (2 – 7) / (1 – 3) = -5 / -2 = 2.5
      - tetapi apabila garis B dinyatakan sebagai (1 ; 2) – (3 ; 7) maka garis B akan berada di kuadran I        - m = (7 – 2 ) / ( 3 – 1) = 5 / 2 = 2.5

LINE EQUATION
- Sebuah garis lurus dapat diperoleh dengan menggunakan
rumus : y = mx + b 
- dimana :
m = gradien
b = perpotongan garis dengan sumbu y. x1 x2 y1 y2 b

LINE EQUATION
- Apabila dua pasang titik akhir dari sebuah garis dinyatakan sebagai  (x1,y1) and (x2, y2), maka nilai dari gradien m dan lokasi b

Contoh : Gambar garis (0,1) – (5,7) dengan menggunakan Line Equation

Gradien dan Tipe Garis

Tipe Garis
Dapatkah anda mencari perbedaan yang esensial antara garis A dan B (misal : gradien, pertambahan x dan y) ?

Tipe Garis
* Garis A : (3;1) – ( 8;4)
   -m = (y2 – y1) / (x2 – x1) = (4-1)/ (8-3) = 3/5= 0,6
   - 0 < m < 1  xi+1 = xi + 1 ; yi+1 = yi + 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
   - Berapa nilai d1 dan d2 ?

ALGORITHMA DDA
- Digital differential analyzer (DDA) merupakan algorithma untuk menghitung posisi pixel disepanjang garis dengan menggunakan posisi pixel sebelumnya.
- Algorithma berikut ini menggunakan asumsi bahwa garis berada di kuadran I atau II serta garis bertipe cenderung tegak atau cenderung mendatar.

Algorithma DDA
- Untuk garis dengan 0 < m < 1, maka xi+1 = xi +1
- Untuk garis dengan  m > 1, maka yi+1 = yi + 1

Algorithma DDA
- Garis dengan 0 > m > -1, maka xi+1 = xi-1
- Sedangkan bila m < -1, maka yi+1 = yi+1

Contoh Algorithma DDA
- Gambar garis dari (0;1) – (5;7) dengan menggunakan DDA. x1=0,y1=1  x2=5,y2=7 m = (7-1)/(5-0) = 1,20 1/m=1/1,20 = 0,83

Algorithma Bresenham
 -Bresenham mengembangkan algorithma yang lebih efisien.
- Algorithma ini mencari nilai integer yang paling mendekati garis sesungguhnya (actual line).
- Algorithma ini tidak memerlukan pembagian.

Algorithma Bresenham
- Algorithma Bresenham yang disajikan berikut ini hanya dapat digunakan untuk garis yang berada di kuadran I dan 0 < m < 1.
- Anda yang ingin mempelajari pembuktian matematis dari algorithma Bresenham silahkan membaca buku Computer Graphics (Hearn dan Baker)


Atribut Garis