Algoritma Pembentukan Garis

1.   Algoritma digital differential analyzer (DDA)

Merupakan algoritma untuk menggambar garis yang sederhana. Sebuah garis dikelompokkan ke dalam 3 bentuk mendatar tetapi cenderung tegak dan miring 45º.

Ada 3 nilai untuk gradien (m) :m > 1, m = 1, 0 < m < 1

·         m>1

• m =1 

·         0<m<1

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 cara:

• Bila nilai absolut dari dx lebih besar dari absolut dy, maka langkah= absolute dari dx.
• Bila tidak maka langkah= absolutdari 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

Contoh Prosedur DDA dalam pascal:

uses graph,crt;

procedure drawLine(xstart,ystart,xend,yend:integer);

var

step,k:integer;

dx,dy:real;

x_inc,y_inc,x,y:real;

begin

dx:=xend-xstart;

dy:=yend-ystart;

x:=xstart;

y:=ystart;

if abs(dx) > abs(dy) then

step:=round(abs(dx))

else

step:=round(abs(dy));

x_inc:=dx/step;

y_inc:=dy/step;

putPixel(round(x),round(y),30);

for k:=1 to step do

begin

x:=x+x_inc;

y:=y+y_inc;

putPixel(round(x),round(y),30);

end;

end;

begin

  init;

  {menggambar garis dari titik 10,10 ke 500,10}

  drawLine(10,10,500,10);

  readkey;

  destroy;

end.

Kelemahan Algoritma DDA:

• Hanya dapat digunakan untuk nilai x1<x2 dan y1<y2 atau garis yang berada di kuadran I
•  Menggunakan pembagian serta pembulatan.