Algoritma Bresenham

 

 

          Prosedur untuk menggambar kembali garis dengan membulatkan nilai x atau y kebilangan integer membutuhkan waktu, serta variable x,y dan m merupakan bilangan real karena kemiringan merupakan nilai pecahan. Bressenham mengembangkan algoritma klasik yang lebih menarik, karena hanya menggunakan perhitungan matematika dengan bilangan integer. Dengan demikian tidak perlu membulatkan nilai posisi setiap pixel setiap waktu. Algoritma garis Bressenhem disebut juga midpoint line algorithm adalah algoritma konversi penambahan nilai integer yang juga dapat diadaptasi untuk menggambar sebuah lingkaran. 

Langkah-langkah untuk membentuk garis menurut algoritma ini adalah : 

1. Tentukan dua titik yang akan dihubungkan dalam pembentukan garis. 
2. Tetukan salah satu titik disebelah kiri sebagai titik awal (x 0, y 0 ) dan titik lainnya sebagai titik akhir (x1,y1 ). 
3. Hitung x, y, 2 x, dan 2 y – 2 x. 
4. Hitung parameter p0 = 2 y – x. 
5. Untuk setiap xk sepanjang jalur garis, dimulai dengan k = 0 bila bila pk <0 maka titik selanjutnya (xk+1,yk) dan pk+1 = pk +2 y bila tidak maka titik selanjutnya adalah (xk +1, yk +1) dan pk+1 = pk +2y–2 x.
6. Ulangi langkah nomor 5 untuk menentukan posisi pixel selanjutnya, sampai x = x1 dan y = y

Algoritma  Bresenham  merupakan  algoritma  penggambaran  garis  yang  efisien  dengan menggunakan perhitungan incremental integer.   Prinsip dari algoritma Bresenham adalah :

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.

 

 Ini Source Codenya :

function bresenham_line()

clc

clear all

point = input('Input Koordinat[ x0 y0 x1 y1]: ');

x0 = point(1);

y0 = point (2);

x1 = point(3);

y1 = point (4);

if (abs(point(4)-point(2)) > abs(point(3)-point(1)))       % If the line is steep                                

    x0 = point(2);y0 = point(1); x1 = point(4);y1=point(3);% then it would be converted to 

    token =1;                                              % non steep by changing coordinate

else

    x0 = point(1);y0 = point(2); x1 = point(3);y1=point(4);

    token = 0; 

end

if(x0 >x1)

    temp1 = x0; x0 = x1; x1 = temp1;

    temp2 = y0; y0 = y1; y1 = temp2;

end

dx = abs(x1 - x0) ;                              % Distance to travel in x-direction

dy = abs(y1 - y0);                               % Distance to travel in y-direction

sx = sign(x1 - x0);                              % sx indicates direction of travel in X-dir

sy = sign(y1 - y0);                              % Ensures positive slope line

clf, subplot(2,1,1) ,hold on , grid on ,axis([x0-1 x1+1 y0-1 y1+1]);

title('Bresenham Line Generation Algorithm: Point form')

x = x0; y = y0;                                  % Initialization of line

param = 2*dy - dx ;                              % Initialization of error parameter

for i = 0:dx-1                                   % FOR loop to travel along X

    x_coord(i+1) = x;                            % Saving in matrix form for plot

    y_coord(i+1) = y;

    if (token ==0)                               % Plotting in point form 

        plot(x,y,'r*');                          % For steep line coordinate is again

    else                                         % converted for actual line drawing.

        plot(y,x,'r*');

    end

    param = param + 2*dy;                        % parameter value is modified

    if (param >0)                                % if parameter value is exceeded

        y = y +1*sy;                             % then y coordinate is increased

        param = param - 2*(dx );                 % and parameter value is decreased

        

    end

    x = x + 1*sx;                                % X-coordinate is increased for next point

end

subplot(2,1,2)                                   % Plotting in line fragment form

if (token ==0)

    plot(x_coord,y_coord,'r-','LineWidth',2);

else

    plot(y_coord,x_coord,'r-','LineWidth',2);

end

grid on

axis([x0-1 x1+1 y0-1 y1+1]);

title('Bresenham Line Generation Algorithm: Line fragment form')

 

 

Selamat mencoba, semoga sukses

Posted in: PKG