algoritma

Algoritma pembentukan garis

1.   Algoritma digital differential analyzer (DDA)

Merupakan algoritma untuk menggambar garis yang sederhana. Sebuah garis dikelompokkan ke dalam 3 bentuk : mendatar, 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;

{tambahkan pada bagian ini prosedur penginisialisasian device,

lihat pada bab 1}

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. 

2.  Algoritma garis Bressenham

Tidak seperti algoritma DDA, algoritma bressenham tidak membulatkan nilai posisi pixel setiap waktu. Algoritma Bressenham hanya menggunakan penambahan nilai integer yang juga dapat diadaptasi untuk menggambar lingkaran.

Berikut ini langkah langkah untuk membentuk garis menurut algoritma Bressenham:

1)      Tentukan dua titik yang akan dihubungkan

2)Tentukan salah satu titik di sebelah kiri sebagai titik awal yaitu(x0,y0) dan titik lainnya sebagai titik akhir(x1,y1).

3)      Hitung dx,dy,2dx dan 2dy­2dx.

4)      Hitung parameter

p0=2dy­dx

5)  Untuk  setiap xk sepanjang jalur garis, dimulai dengan k=0,

·                     Bila pk < 0, maka titik selanjutnya adalah (xk+1,yk), dan pk+1=pk+2dy

·                     Bila tidak, maka titik selanjutnya adalah(xk+1, yk+1), dan pk+1=pk+2dy­2dx.

6)      Ulangi langkah nomor 5 untuk menentukan posisi pixel selanjutnya, sampai x=x1 dan y=y1

Contoh prosedur algoritma Bressenham untuk menggambara garis pada titik (10,10) ke (500,10)

uses graph,crt;

{tambahkan pada bagian ini prosedur penginisialisasian device, lihat pada bab 1}

procedure DrawBressLine(xa,ya,xb,yb:integer);

var

dx,p,dy,xEnd:integer;

x,y:real;

     begin

dx:= abs(xb-xa);

dy:= abs(yb-ya);

p:=2*dy-dx;

if xa > xb then

begin

x:=xb;

y:=yb;

xEnd:=xa;

end

else

begin

x:=xa;

y:=ya;

xEnd:=xb;

end;

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

while x < xEnd do

begin

x:=x+1;

if p < 0 then

p:=p+(2*dy)

else

begin

y:=y+1;

p:=p+(2*(dy-dx));

end;

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

            end;

            end;

begin

                        init;

                        DrawBressLine(10,10,500,10);

                        readkey;

                        destroy;

end.

3.      Algoritma Pembentuk Lingkaran

Secara umum prosedur pembentuk lingkaran dibuat dengan rumus dasr x2_y2=R2. Terdapat beberapa cara untuk membentuk suatu lingkaran namun tidak efisien. Lingkaran dapt dibuat dengan menggambarkan seperempat lingkaran karena bagian lain dapat dibuat sebagai bagian yang simetris.

1)      Algoritma Simetris delapan titik

Pada algoritma ini pembuatan lingkaran dilakukan dengan menentukan satu titik awal. Bila titik titik awal pada lingkaran (x,y) maka terdapat tiga posisi lain, sehingga dapat diperoleh delapan titik/delapan oktan.

Dengan demikian sebenaranya hanya diperlukan untuk menghitung segmen 45⁰  dalam menentukan lingkaran selengkapnya. Dengan titik pusat lingkaran tertentu, delapan titik simetris dapat ditampilkan dengan prosedur Circle Point Sebagai berikut:

procedure CirclePoints(x, y, value:integer);

begin

putPixel(x,y,value);

putPixel(-x,y,value);

putPixel(x,-y,value);

putPixel(-x,-y,value);

putPixel(y,x,value);

putPixel(-y,x,value);

putPixel(y,-x,value);

putPixel(-y,-x,value);

end;

2)      Algoritma Lingkaran Midpoint

Algoritma lingkaran Midpoint juga disebut algoritma lingkaran Bressenham. Bressenham mengembangkan generator lingkaran yang cukup efisien. Algoritma yang digunakan membentuk semua titik berdasarkan titik pusat dengan penambahan semua jalur sekeliling llingkaran. Algoritma ini diturunkan dari algoritma Midpoint untuk pembentukan garis. Dalam hal ini hanya diperhatikan bagian 45⁰ dari suatu lingkaran, yaitu oktan kedua dari x=0 ke x=R/√2, dan menggunakan circle points untuk menampilkan titik dariseluruh lingkaran.

Langkah langkah untuk membentuk lingkaran algoritma Circle Midpoint:

1)      Tentukan radius r dengan titk pusat lingkaran(xc,yc) kemudian diperoleh

(x0,y0)=(0,r)

2)      Hitung nilai dari parameter 

P0=5/4­r

3) Tentukan nilai awal k=0, untuk setiap posisi xk berlaku sebagai berikut:       Bila Pk< 0, maka titik selanjutnya adalah (xk+1,yk)) dan Pk+1=Pk+2xk+1+1

Bila tidak, maka selanjutnya adalah(xk+1,yk­1), dan Pk+1=Pk+2xk+1+1­ 2yk+1

Dimana 2xk+1=2xk+2 dan 2yk+=2yk­2

4)      Tentukan titik simetris pada ketujuh oktan yang lain

5) Gerakkan setiap posisi pixel(x,y) pada garis melingkar dari lingkaran dengan titik pusat (xc,yc) dan tentukan nilai koordinat:

x=x+xcy=y+yc

6)      Ulangi langkah ke­3 sampai 5, sehingga x>=y

Contoh algoritma lingkaran midpoint 
untuk menggambarkan algoritma Bressenham dalam pembentukan suatu lingkaran dengan titik pusat (0,0) dan radius 10, perhitungan berdasarkan pada oktan dari kuadran pertama dimana x=0 sampai x=y. Nilai parameter dapat ditentukan dengan P0=1r=110=9

Koordinat titk awal adalah(x,r)=(0,8).

Prosedur algoritma lingkaran midpoint 

Input yang digunakan pada prosedur ini adalah koordinat titik pusat dan radius lingkaran. Posisi pixel ditentukan dengan rutin setPixel.

uses graph,crt;

{tambahkan pada bagian ini prosedur penginisialisasian device, lihat pada bab 1}

procedure circlePlotPoints(xCenter,yCenter,x,y:integer);

begin

putPixel(xCenter+x, yCenter+y,30);

putPixel(xCenter-x, yCenter+y,30);

putPixel(xCenter+x, yCenter-y,30);

putPixel(xCenter-x, yCenter-y,30);

end;

procedure circleMidPoint (xCenter,yCenter,radius:integer);

var

    x,y,p:integer;

begin

x:=0;

y:=radius;

p:=1-radius;

circlePlotpoints(xCenter,yCenter,x,y);

while x<y do

                        begin

x:=x+1;;

if p<0 then

p:=p+(2*x+1)

else

                                    begin

y:=y-1;

p:=p+(2*(x-y)+1);

                                    end;

circlePlotPoints(xCenter,yCenter,x,y);

end;

begin

             init;

              circleMidPoint(100,100,90);

             readkey;

             destroy;

       end.

4.      Algoritma Pembentukan Elips

Elips merupakan modifikasi dari bentuk lingkaran, dengan memasukkan mayor dan minor axis pada prosedur lingkaran. Elips ditentukan oleh satu set titik dengan memperhitungkan jumlah jarak kedua posisi (foci). Bila jarak kedua foci dari sembarang titik (p,y) pada elips diberi label d1 dan d2, maka persamaan elips menjadi

d1+d2=konstan

Untuk menggambarkan jarak d1 dan d2 dengan ketentuan koordinat masing masing 

F1(x1,y1) dan F2(X2,Y2)

√((x­x1)2+(y­y1)2)2+√((x­x2)2+(y­y2)2=konstan

Dimana mayor dan minor  axis elips dalam posisi parallel dengan sumbu x dan sumbu y pada contoh ini, parameter rx disebut semi major axis dan ry disebut semi minor axis, sehingga persamaan elips dengan parameter rx dan ry menjadi

((x­rc)/rx)2 + ((y­yc)/ry)2=1

Algoritma elips Midpoint 

Untuk algoritma pembentukan elips, pendekatan yang dilakukan sama dengan 

penggunaan pada saat menampilkan lingkaran. Dengan parameter untuk elips pada posisi 

standar, yaitu rx, ry, dan(xc,yc). Bila elips ditampilkan pada posisi standar, maka dapat 

dilakukan dengan memutar elips tersebut menurun koordinat titik pusat, dan 

mendapatkan kembali mayor dan minor axis.

Metode midpoint untuk elips dijalankan pada kuadran pertama dalam dua bagian. 

Bagian pertama menrut kemiringan elips rx<ry. Penambahan dengan unit step pada arah 

sumbu x dilakukan bila slope lebih kecil dari 1, dan dengan unit step menurut sumbu y 

bila kemiringan lebih besar dari 1.

Bagian 1 dan 2 dapat digunakan untuk bermacam macam cara. Pertama dimulai 

dari posisi (0,ry) dan step searah jarum jam sepanjang jalur elips pada kuadran pertama. 

Pergeseran dengan unit step dalam x pada saat slope lebih besar dari 1.

Alternatif lain, dimulai dari (rx,0) dan seleksi titik dalam arah berlawanan dengan 

arah jarum jam. Penggeseran unit step y ke unit step x pada saat kemiringan lebih besar 

dari ­1. dengan prosesor pararel, posisi pixel dapat dihitung dalam dua bagian sekaligus

Pembentukan elips menurut algoritma Circle midpoint sebagai berikut:

1)      Tentukan rx,ry dan pusat elips (xc,yc) kemudian diperoleh 

(xo,yo)=(0,ry)

2)      Hitung nilai parameter 

P1₀= r_y² –r_x r_y² + ¼ r_x²

3)      Tentukan nilai awal k=0, untuk setiap posisi xk berlaku sebagai berikut :

·         Bila p1k< 0 maka titik selanjutnya adalah (xk+1, yk)

p1_k+1=p1_k+2r_y² X_k+1+r_y²

·         Bila tidak, maka titik selanjutnya adalah (xk+!,yk­1) dan

p1_k+1=p1_k+2r_y² X_k+1­2r_x y_k+1+r_y²

dengan 

2r_y²x_k+1=2r_y²x_k +2r_y²

Dan 2r_x y_k+1=2r_x² y_k +2r_x²

Teruskan sampai 

2r_y²x >= 2r_x² y

4)      Tentukan nilai parameter pada bagian kedua menggunakan titik terakhir (x0,y0) yang  telah dihitung pada bagian pertama, sebagai berikut

P²_k+1=2r_y² (x_o+1/2)²+2r_x² (y_o­1)²­ r_x² r_y²

5)      Setiap posisi yk pada bagian kedua, dimulai dengan k=0

·         Bila p2k> 0 maka titik selanjutnya adalah (xk, yk­1)

p2_k+1=p2_k+2r_x²y_k+1+r_x²

·         Bila tidak, maka titik selanjutnya adalah (xk+1,yk­1) dan

p2_k+1=pk+2r_y²x_k+1­2r_x y_k+1+r_y²

6)      Tentukan titik simetris pada ketiga kuadran lainnya

7)      Gerakkan setiap posisi(x,y) pada garis melingkar dari elisp dengan titik pusat(xc,yc) dan  tentukan nilai koordinat 

x=x+xc  y=y+yc

8)      Ulangi langkah untuk bagian pertama di atas, sehingga 2r_y²x >= 2r_x² y

Contoh algoritma elips Midpoint 

Untuk menggambarkan algoritma midpoint dalam pembentukan elips dengan titik 

pusat(0,0) dan mayor axis rx=6, serta minor axis ry=8, perhitungan berdasarkan pada 

kuadran pertama sebagai berikut:, nilai parameter dapat ditentukan 

2r_y²x=0

2r_y²x=2r_x² ry

p1o= r_y²  + r_x² r_y ­1/4 r_x²

=­ 215

Koordinat titik awal (x,r) =(0,8)

Prosedur algoritma elips Midpoint

Prosedur berikut menampilkan posisi pixel pada monitor dengan algorima 

Midpoint. Input yang digunakan adalah koordinat titik pusat mayor axis, dan minor axis. 

Posisi pixel ditentukan dengan rutin setPixel.

uses graph,crt;

{tambahkan pada bagian ini prosedur penginisialisasian device, lihat pada bab 1}

procedure elipsPlotPoints(xCenter,yCenter,x,y:integer);

begin

putPixel(xCenter+x, yCenter+y,30);

putPixel(xCenter-x, yCenter+y,30);

putPixel(xCenter+x, yCenter-y,30);

putPixel(xCenter-x, yCenter-y,30);

end;

procedure elipsMidPoint(xCenter,yCenter,Rx, Ry:integer);

var

Rx2,Ry2,x,y,twoRx2,twoRy2,py,px,p:integer;

begin

Rx2:=Rx*Rx;

Ry2:=Ry*Ry;

x:=0;

y:=Ry;

twoRx2:=2*Rx2;

twoRy2:=2*Ry2;

px:=0;

py:=twoRx2*y;

elipsPlotPoints(xCenter,yCenter,x,y);

//bagian1

p:=round(Ry2-(Rx2*Ry)+(0.25*Rx2));

while px<py do

begin

x:=x+1;

px:=px+twoRy2;

if p<0 then

p:= p+(Ry2+px)

else

begin

y:=y-1;

py:=py-twoRx2;

p:=p+(Ry2+px-py);

end;

elipsPlotPoints(xCenter,yCenter,x,y);

end;

//bagian 2

p:=round(Ry2*(x+0.5) *(x+0.5)+Rx2*(y-1) *(y-1)-Rx2*Ry2);

while y>0 do

begin

y:=y-1;

py:=py-twoRx2;

if p>0 then

p:=p+(Rx2-py)

else

begin

x:=x+1;

px:=px+twoRy2;

p:=p+Ry2+px-py;

end;

elipsPlotPoints(xCenter,yCenter,x,y);

end;

end;

begin

    init;

    elipsMidPoint(130,120,120,190);

    readkey;

    destroy;

end.

5.      Fill area primitive

Terdapat dua dasar pendekatan untuk mengisi area pada raster system. Pertama, 

menentukan overlap internal untuk scan line yang melintasi area. Metode lain yaitu 

dengan memulai dari titik tertentu pada posisi di dalam polygon dan menggambar 

dengan arah menyebar ke pinggir, sampai batas polygon.

1)      Algoritma  scan line 

Titik potong diurutkan dari kiri ke kanan. Posisi yang berhubungan pada 

frame buffer antara sepasang titik potong diberi warna tertentu. Posisi empat 

pixel sebagai titik potong antara garis batas polygon ditentukan oleh dua buah 

pixel pada koordinat darri x=8 ke x=13  dan dari x=23 ke x=34

2)    Algoritma boundary fill. 

Metode ini bermanfaat untuk paket aplikasi grafik interaktif dimana titik 

dalam dapat dengan mudah ditentukan. Prosedur boundary fill menerima inout 

koordinat suatu titik(x,y), warna isi dan garis batas. Dimulai dari titik (x,y), 

prosedur memeriksa posisi titik tetangga, yaitu apakah merupakan warna batas. 

Bila tidak, maka titik tersebut digambar dengan warna isi. Proses ini dilanjutkan

sampai semua titik pada batas diperiksa. Prosedur berikut menampilkan metode

rekursif mengisi 4 bidang dengan intensitas pada parameter fill.

procedure  boundaryFil( x,y,fill,boundary:integer);

var

current:integer;

begin

current:= getPixel(x,y);

if (current <> boundary) and (current <> fill) then

begin

putPixel(x,y,fill);

boundaryFill(x+1,y,fill,boundary);

boundaryFill(x-1,y,fill,boundary);

boundaryFill(x,y+1,fill,boundary);

boundaryFill(x,y-1,fill,boundary);

end;

end;

3)    Algoritma flood fill

Pendekatan lain untuk mengisi suatu bidang polygon adalah algorima 

flood fill. Metode ini dimulai pada titik (x,y) dan mendefinisikan seluruh pixel 

pada bidang tersebut dengan warna yang sama. Bila bidang yang akan diisi 

warna memiliki beberapa warna. Pertama tama yang dibuata adalah membuat 

nilai pixel baru, sehingga smua pixel memiliki warna yang sama.  Prosedur 

berikut menggambarkan metode flood­fill untuk mengisi warna suatu polygon.

procedure floodFill( x,y,fillColor,oldColor:integer);

begin

if getPixel(x,y) = oldcolor then

begin

putPixel(x,y,fillcolor);

floodFill(x+1,y , fillColor, oldColor);

floodFill(x-1,y , fillColor, oldColor);

floodFill(x,y+1 , fillColor, oldColor);

floodFill(x,y-1 , fillColor, oldColor);

end;

end;