ALGORITMA DDA, BERSENHAM, DAN MID POINT CIRCLE
ALGORITMA DDA, BERSNHAM, DAN MID POINT CIRCLE
Pengertian :
- Algoritma DDA :
Algoritma
DDA adalah algoritma pembentukan garis berdasarkan perhitungan dx maupun dy,
menggunakan rumus dy=m.dx Semua koordinat titik yang membentuk garis diperoleh
dari perhitungan kemudian dikonversikan menjadi nilai integer.
Algoritma Digital
Differential Analyzer (DDA) adalah algoritma pembentukangaris berdasarkan
perhitungan dx maupun dy dengan menggunakan rumus dy = m.dx.Garis dibuat dengan
menentukan dua endpoint yaitu titik awal dan titik akhir. Setiapkoordinat titik
yang membentuk garis diperoleh dari perhitungan kemudian dikonversikanmenjadi
nilai integer.[5]
a.
langkah-langkah
· Tentukan dua
titik yang akan dihubungkan dalam pembentukan garis.
· Tentukan
salah satu titik sebagai awal(x0,y0) dan titik akhir(x1,y1).
· Hitung
dx=x1x0, dan dy= y1y0.
· Tentukan
langkah, yaitu dengan cara jarak maksimum jumlah penambahan nilai xmaupun nilai
y, dengan cara :*Bila nilai absolut dari dx lebih besar dari absolut dy, maka
langkah= absolut dari dx.*Bila tidak maka langkah= absolut dari dy
· Hitung
penambahan koordinat pixel yaitu x_increment=dx/langkah,
dany_increment=dy/langkah
· Koordinat
selanjutnya (x+x_increment, y+y_increment)
· Posisi pixel
pada layar ditentukan dengan pembulatan nilai koordinat tersebut.
· Ulangi nomor 6 dan 7 untuk menentukan posisi pixel selanjutnya,sampai x=x1dan y=y1.
Algoritma DDA merupakan salah satu algoritma menggambar cukup sederhana
Bentuk garis:
- Cenderung Mendatar :
Gradien bernilai 0 < m < 1
Pixel bertambah 1 pada sumbu x dan bertambah sebesar m pixel pada
sumbu y
- Cenderung Tegak :
Gradien bernilai m > 1
Pixel bertambah 1 pada sumbu y dan bertambah sebesar 1/m pixel pada sumbu x
Gradien
bernilai m = 1
Pixel
bertambah 1 pada sumbu x dan bertambah sebesar 1
pixel pada sumbu y[6]
b. Keuntungan dan Kerugian Algoritma DDA
Keuntungan dari
algoritma Digital Differential
Analyzer (DDA) adalah tidak perlu
menghitung koordinat berdasarkan persamaan yang lengkap (menggunakan metode off
set)
Kerugiannya dari algoritma Digital Differential Analyzer (DDA) adalah adanya akumulasi Round-off errors, sehingga garis akan melenceng dari garis lurus, selain itu operasi round-off juga menghabiskan waktu. [5]
- Algoritma BERSENHAM :
Algoritma Garis Bressenham merupakan algoritma yang menentukan dimana titik-titik dalam raster n-dimensi harus ditempatkan untuk membentuk garis lurus antara dua titik yang diberikan. Hal ini biasanya digunakan untuk menggambar garis pada layar komputer, karena hanya menggunakan integer penambahan, pengurangan dan pergeseran bit, yang mana semua itu merupakan proses yang sangat murah dalam arsitektur komputer yang standar. Algoritma ini adalah algoritma yang paling awal dikembangkan di bidang grafika komputer . Algoritma ini juga dapat membentuk lingkaran dengan sedikit penambahan pada algoritma-nya. [5]
a. langkah-langkah
v dx>dy
·
Tentukan 2 titik yang akan
dihubungkan dalam pembentukan garis
·
Tentukan salah satu titik disebelah
kiri sebagai titik awal, yaitu (X0, Y0) dan titik lainnyasebagai titik akhir
(X1, Y1).
·
Hitung Dx=x2-x1, Dy=y2-y1, d1=2*DX
dan d2=2*Dy - 2*Dx, e=d1-dx, x=x1, y=y1
·
Gambar pixel di (x,y)
·
Untuk setiap e>=0 hitung e=e+d2
dan y=y+1 Jika tidak hitung e=e+d1 dan y=y
·
Hitung x=x+17. Jika x>=x2 stop,
jika tidak kembali ke langkah bagian ke
4
v DX<DY
·
Tentukan 2 titik yang akan
dihubungkan dalam pembentukan garis.
·
Tentukan salah satu titik disebelah
kiri sebagai titik awal, yaitu (X0, Y0) dan titik lainnyasebagai titik akhir
(X1, Y1)
·
Hitung Dx=x2-x1, Dy=y2-y1, d1=2*Dy
dan d2=2*Dy - 2*Dx, e=d1-dy, x=x1, y=y1
·
Gambar pixel di (x,y)
·
Untuk setiap e>=0 hitung e=e+d2
dan x=x+1 Jika tidak hitung e=e+d1 dan x=x
·
Hitung y=y+1. Jika y>=y2 stop, jika tidak kembali
ke langkah 4
- Algoritma Bresenham
Langkah-langkah pembentukan garis berdasarkan
algoritma Bressenham adalah:
1. Tentukan dua
titik yang akan dihubungkan dalam pembentukan garis.
2. Tentukan
salah satu sebagai titik awal (x0, y0) dan titik akhir (x1, y1).
3. Hitung dx,
dy, 2dy dan 2dy - 2dx
4. Hitung parameter : po = 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, titik selanjutnya adalah:
(xk+1, yk+1) dan
pk+1 = pk + 2dy – 2dx
6. Ulangi
nomor 5 untuk menentukan posisi pixel berikutnya, sampai
x =
x1 atau
y = y1.
- Algoritma MID POINT CIRCLE :
Algoritma Lingkaran Midpoint juga disebut algoritma lingkaranBressenham. Bressenham mengembangkan generator lingkaran yang cukup efisien. Algoritma yang digunakan membentuk semua titik berdasarkan titik pusat dengan penambahan semua jalur sekeliling lingkaran. 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 CirclePoints untuk menampilkan titik dari seluruh 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/4r
3. Tentukan nilai awal k=0, untuk setiap posisi xk berlaku sebagai berikut:
– Bila Pk=y
- 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;
procedure init;
var gd, gm : integer;
begin
gm:=detect; gd:=0;
InitGraph(gd,gm,”);
if GraphResult grOk then
begin
Writeln(‘Graph driver ‘,gd,’ graph mode ‘,gm,’ not supported’);
Halt(1);
end;
end;
procedure destroy;
begin
closegraph;
end;
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);
putPixel(xCenter+y, yCenter+x,30);
putPixel(xCenter-y, yCenter+x,30);
putPixel(xCenter+y, yCenter-x,30);
putPixel(xCenter-y, yCenter-x,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
begin
x:=x+1;;
if p y
Komentar
Posting Komentar