algoritma pembentukan garis (DDA dan Bresenham

Garis dibuat dengan menentukan dua endpoint atau posisi awal dan posisi akhir dari suatu garis. Kmeudian peralatan output membuat garis sesuai posisi titik titik tersebut. Untuk peralatan analog seperti plotter an random-scan display garis lurus dapat dihasilkan dengan halus.

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. 

1. ALGORITMA DDA

A. 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.

DDA ( Digital Differential Analyzer) adalah garis yang membentang antara 2 titik, P1 dan P2. Dimana ke-2 titik ini membentuk sudut yang besarnya sangat bervariasi. Bekerja atas dasar penambahan nilai x dan nilai y. Dimana pada garis lurus, turunan pertama dari x dan y adalah kostanta.

B. LANGKAH LANGKAH PEMBENTUKAN GARIS ALGORITMA DDA

1.       Tentukan dua titik yang akan dihubungkan dalam pembentukan garis.

2.       Tentukan salah satu sebagai titik awal (x1, y1) dan titik akhir (x2, y2).

3.       Hitung dx = x2 – x1 dan dy = y2 – y1

4.       Tentukan step, yaitu jarak maksimum jumlah penambahan nilai x atau nilai y, dengan ketentuan:

                a.  bila |dx| > |dy| maka step = |dx|

                b.  bila tidak, maka step = |dy|

5.       Hitung penambahan koordinat pixel dengan persamaan:

 x_inc = dx / step

y_inc = dy / step

6.       Koordinat selanjutnya (x+x_inc, y+y_inc)

7.       Plot pixel pada layar, nilai koordinat hasil perhitungan dibulatkan

8.       Ulangi step nomor 6 dan 7 untuk menentukan posisi pixel berikutnya sampai x = x1 atau y = y1.

C. 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.

D. PENERAPAN ALGORITMA DDA

#define BLACK

0 #include

#include

using namespace std;

void draw_pixel(int ix, int iy, int value)

{

glBegin(GL_POINTS);

glVertex2i( ix, iy);

glEnd();

}

int bres(int x1,int y1,int x2,int y2)

{

int dx, dy, i, e;

int incx, incy, inc1, inc2;

int x,y;

dx = x2 - x1;

dy = y2 - y1;

if(dx < 0) dx = -dx;

if(dy < 0) dy = -dy;

incx = 1;

if(x2 < x1) incx = -1;

incy = 1;

if(y2 < y1) incy = -1;

x=x1;

y=y1;

if(dx > dy)

{

draw_pixel(x,y, BLACK);

e = 2*dy - dx;

inc1 = 2*( dy -dx);

inc2 = 2*dy;

for(i = 0; i < dx; i++)

{

if(e >= 0)

{

y += incy;

e += inc1;

}

else e += inc2;

x += incx;

draw_pixel(x,y, BLACK);

}

}

else

{

draw_pixel(x,y, BLACK);

e = 2*dx - dy;

inc1 = 2*( dx - dy);

inc2 = 2*dx;

for(i = 0; i < dy; i++)

{

if(e >= 0)

{

x += incx;

e += inc1;

}

else e += inc2;

y += incy;

draw_pixel(x,y, BLACK);

}

}

}

void display()

{

glClear(GL_COLOR_BUFFER_BIT);

bres(200, 200, 100, 50);

glFlush();

}

void myinit()

{

glClearColor(1.0, 1.0, 1.0, 1.0);

glColor3f(1.0, 0.0, 0.0);

glPointSize(1.0);

glMatrixMode(GL_PROJECTION);

glLoadIdentity();

gluOrtho2D(0.0, 499.0, 0.0, 499.0);

}

int main(int argc, char** argv)

{

glutInit(&argc;,argv);

glutInitDisplayMode (GLUT_SINGLE | GLUT_RGB);

glutInitWindowSize(500,500);

glutInitWindowPosition(0,0);

glutCreateWindow("Bresenham's Algorithm");

glutDisplayFunc(display);

myinit();

glutMainLoop();

}

2. ALGORITMA BRESENHAM

A.PENGERTIAN ALGORITMA BRESENHAM

Algoritma bresenham merupakan suatu algoritma (pendekatan) yang dikreasikan oleh bresenham yang tidak kalah akurat dan efisien dengan algoritma primitif lainnya (seperti DDA). Bagian pengkonversian (scan-knversi) garis akan melakukan kalkulasi untuk penambahan nilai-nilai integer (yang dibutuhkan untuk membentuk garis) yang disesuaikan dengan tipe grafik yang dipakai oleh layar komputer (keadaan monitor pc) kita. Untuk mengilustrasikan pendekatan bresenham, pertama kita harus memperhatikan proses scan- konvensi untuk garis dengan slope positif yang lebih kecil dari 1. Posisi pixel sepanjang line-path kemudian ditentukan dengan penyamplingan pada unit interval x.dimulai dari endpoint kiri (Xo,Yo) dari garis yang diberikan, kita pindahkan beberapa kolom berturut-turut (berdasarkan posisi x) dan plot pixel-pixel yang mempunyai nilai scan-line y ke jarak yang paling dekat dengan line-path.

B. ATURAN BRESENHAM

·         Jika Pk bernilai positif (+), maka tambahkan hasilnya dengan B dan nilai x dan y ditambah 1.

·         Jika Pk bernilai negatif (-), maka tambahkan hasilnya dengan A dan nilai x ditambah 1, sedangkan y ditambah 0 (tetap).

·         Putaran dihentikan jika koordinat x dan y sudah mencapai batas akhir.

C. PRINSIP DARI ALGORITMA BRESENHAM

1.       Sumbu vertikal memperlihatkan posisi scan line.

2.       Sumbu horizontal memperlihatkan kolom pixel

3.       Pada tiap langkah, penentuan pixel selanjutnya didasari oleh parameter integer yang nilainya proporsional dengan pengurangan antara vertical separations dari dua posisi piksel dari nilai actual.

Garis lurus dinyatakan dinyatakan dalam persamaan :

y = mx + c   è Persamaan(1)

dimana :

m : gradient dan

c : konstanta.

              Untuk menggambarkan piksel-piksel dalam garis lurus, parameter yang digunakan tergantung dari gradient, jika besarnya gradient diantara 0 dan 1, maka digunakan sumbu x sebagai parameter dan sumbu y sebagai hasil dari fungsi, sebaliknya, bila gradient melebihi 1, maka sumbu y digunakan sebagai parameter dan sumbu x sebagai hasil dari fungsi, hal ini bertujuan untuk menghindari terjadinya gaps karena adanya piksel yang terlewatkan. Hasil dari fungsi biasanya merupakan bilangan real, sedangkan koordinat pixel dinyatakan dalam bilangan integer (x,y), maka diperlukan operasi pembulatan kedalam bentuk integer terdekat. Penggambaran garis lurus dengan metode diatas dimulai dengan operasibilangan real untuk menghitung gradient m dan konstanta c.

m = (y2 – y1 ) / (x2-x1)          (2)

c = y1 / m* x1*                       (3)

Operasi bilangan real berikutnya adalah menghitung nilai y dengan persamaan (1) Untuk mendapatkan koordinat piksel (x,y), untuk setiapnilai x, dari =x1 sampai x=x2, operasi inilah yang perlu dihindari,karena operasi ini memerlukan waktu operasi yang besar.

D. LANGKAH LANGKAH PEMBENTUKAN GARIS ALGORITMA DDA

1.       Tentukan 2 titik yang akan dihubungkan dalam pembentuk garis.

2.       Tentukan salah satu titik disebelah kiri sebagai titik awal, yaitu (X0,Y0) dan titik lainnya sebagai titik akhir (X1, Y1)

3.       hitung Dx, Dy, 2DX dan 2Dy-2Dy

4.       Hitung parameter P0= 2Dy – 2Dx

5.       Untuk setiap X1 sepanjang jalur garis, dimulai dengan k=0,

·         bila pk<0, makatitik 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 no. 5 untuk menentukan posisi selanjutnya, sampai X=X1 dan Y=Y1

E. PENERAPAN ALGORITMA BRESENHAM

#include<stdio.h>

#include<conio.h>

#include<graphics.h>

int main()

{

 int gd = DETECT, gm;

 int dx, dy, p, xakhir;

 float x0, x1, y0, y1, x, y;

 initgraph(&gd, &gm,0);

 printf("Masukkan Nilai X0: ");

 scanf("%f", &x0);

 printf("Masukkan Nilai Y0: ");

 scanf("%f", &y0);

 printf("Masukkan Nilai X1: ");

 scanf("%f", &x1);

 printf("Masukkan Nilai Y1: ");

 scanf("%f", &y1);

 dx = abs(x1 - x0);

 dy = abs(y1 - y0);

 p = 2 * dy - dx;

 if(x0 > x1)

 {

   x = x1;

   y = y1;

   xakhir = x0;

 }

 else

 {

   x = x0;

   y = y0;

   xakhir = x1;

 }

 while(x < xakhir)

 {

   x = x + 1;

   if(p < 0)

   {

     p = p + 2 * dy;

   }

   else

   {

     y = y + 1;

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

   }

   putpixel(x, y, WHITE);

 }

 getch();

 closegraph();

}

• Tweet
• Share
• Share
• Share
• Share

About Admin MC3

This is dummy text. It is not meant to be read. Accordingly, it is difficult to figure out when to end it. But then, this is dummy text. It is not meant to be read. Period.

Related Post