Membuat Lingkaran Dengan Algoritma Bressenham

Penggambaran grafik garis lurus dan kurva memerlukan waktu komputasi yang tinggi, untuk mereduksi waktu komputasi yang tinggi tersebut dapat dilakukan dengan peningkatan kemampuan komputasi prosesor dan peningkatan efisiensi algoritma. Algoritma Midpoint merupakan Algoritma dengan dasar operasi bilangan integer, sehingga memerlukan waktu operasi yanglebih sedikit dibandingkan dengan algoritma yang menggunakan operasi bilangan riel. 

Implementasi ke dalam bahasa pemrograman C dari kedua macam algoritma diatas, menunjukkan bahwa waktu komputasi algoritma midpoint lebih cepat sebesar 8 kali pada pembuatan garis lurus, dan lebih cepat sebesar 15 kali pada penggambaran lingkaran, dibandingkan dengan waktu komputasi algoritma yang menggunakan dasar operasi bilangan riel. Dan waktu komputasi algoritma midpoint lebih cepat sebesar 6 kali pada pembuatan garis lurus, dibandingkan dengan waktu komputasi lgoritma yang Breserham telah menggunakan dasar operasi bilangan integer juga.

Kata kunci: Penggambaran garis, penggambaran kurva,

Algoritma Bresenham, Algoritma midpoint, Algoritma DDA.

1. PENDAHULUAN

Perkembangan kemampuan komputasi prosesor yang pesat telah membuatkomputer desktop mempunyai kemampuan komputasi yang besar. Hal inimendorong perkembangan program aplikasi yang memerlukan komputasi yangbesar seperti program aplikasi yang menggunakan grafik 3 dimensi.Peningkatan kemampuan komputasi prosesor untuk aplikasi grafik yangsarat komputasi, perlu dibarengi peningkatan efisiensi algoritma,sehingga pembuatan grafik garis dan kurva yang merupakan dasar pembuatangrafik dapat memberikan hasil yang optimal.

Algoritma midpoint merupakan algoritma pembuatan garis dan kurva dengan dasar operasi bilangan integer yang menonjolkan ciri kecepatan. Sehingga algoritma ini dapat dipakai sebagai algoritma pembuatan grafik yang menuntut kecepatan sebagai hal yang diutamakan. Pembahasan algoritma Midpoint dilakukan dengan mengasumsikan garis lurus dari kiri ke kanan,dan gadient antara 0 dan 1, sedangkan untuk lingkaran dengan mengasumsikan hanya sebagian lingkaran dengan sudut sebesar 45° , hal ini dilakukan untuk mempermudah penjelasan, sedangkan untuk kondisi yanglain dapat diderivasi dengan cara yang serupa. Untuk mendapatkan kinerja algoritma midpoint, dilakukan uji kecepatan komputasi dengan cara mengimplementasikan kedalam bahasa pemrograman C, dan melakukan perbandingan waktu komputasi dengan algoritma yang menggunakan dasar komputasi bilangan riel, maupun algoritma lain yang telah banyak dikenal seperti algoritma dda dan algoritma bressenham.

2. GARIS LURUS

Garis lurus dinyatakan dinyatakan dalam persamaan :

y = mx + c (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 riel, 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 riel untuk menghitung gradient m dan konstanta c.

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

c = y1 ? m* x1* (3)

Operasi bilangan riel 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.

2.1 Algoritma Bresenham

Bresenham pada tahun 1965, melakukan perbaikan dari algoritma perhitungan koordinat piksel yang menggunakan persamaan (1), dengan cara menggantikan operasi bilangan riel perkalian dengan operasi penjumlahan, yang kemudian dikenal dengan Algoritma Bresenham. Pada algoritma bresenham, nilai y kedua dan seterusnya, dihitung dari nilai y sebelumnya, sehingga hanya titik y pertama yang perlu dilakukan operasi secara lengkap. Perbaikan algoritma ini ternyata tidak menghasilkan perbaikan yang cukup siginifikan. Perbaikan berikutnya dilakukan dengan cara menghilangkan operasi bilangan riel dengan operasi bilangan integer. Operasi bilangan integer jauh lebih cepat dibandingkan dengan operasi bilangan riel, terutama pada penambahan dan pengurangan. 

2.2 Algoritma Midpoint untuk Penggambaran Garis

Algoritma midpoint dikembangkan oleh Pitteway pada tahun 1967. Pada gambar 1, titik abu-abu menyatakan posisi piksel, titik hitam menyatakan posisi piksel yang telah digambar. Berdasarkan piksel ke n yang telah digambar, diperlukan metode untuk menentukan piksel berikut yang akan digambar, karena penggambaran dilakukan dari kiri ke kanan, maka piksel berikutnya harus pada kolom n+1. Karena gradien diantara 0 dan 1, maka piksel berikutnya adalah pada posisi titik p atau titik q.

Persamaan garis lurus yang telah dinyatakan dalam persamaan (1) dapat dinyatakan dalam fungsi x,y berikut. 

*f(x, y) = ax + by + c = 0 *(4)

Fungsi f(x,y) dalam persamaan (4), akan memberikan nilai 0 pada setiap titik yang terletak pada garis, dan bernilai positip pada setiap titik yang terletak dibawah garis, dan bernilai negatif pada setiap titik yang terletak diatas garis. Maka untuk menentukan apakah titik P atau Q sebagai koordinat piksel berikutnya, maka dilakukan dengan cara menghitung nilai fungsi f(x,y) dalam persamaan (4) pada titik P dan titik Q . Jika fungsi f(x,y) tersebut memberikan nilai positif, maka piksel berikutnya adalah Q, sebaliknya piksel berikutnya adalah P.

*g(x, y) = f(xn + 1, yn + 1/2) *(5)

Fungsi g(x,y) persamaan (5) merupakan variabel penentu, dengan mengevaluasi g (x, y) dapat ditentukan piksel berikutnya yang mana berdasarkan tanda plus atau minus dari hasil fungsi g(x,y). Untuk mempercepat komputasi fungsi g(x,y), dilakukan dengan cara incremental berdasarkan nilai sebelumnya. Untuk setiap piksel, increment sederhana (DeltaG) dipakai sebagai variabel penentu. Karena hanya ada 2 pilihan piksel pada setiap tahap, maka hanya ada 2 increment yang dapat digunakan. Hal ini dilakukan dengan cara pengurangan nilai g(x,y) yang berurutan dengan menggunakan persamaan 4 dan persamaan 5.

*DeltaG = a * DeltaX + b * DeltaY *(6)

Dimana DeltaX dan DeltaY adalah increment yang dipakai pada x dan y, yang bernilai 0 atau 1. Bila bergeser 1 piksel ke kanan :

*DeltaG1 = a* (7)

Bila bergeser 1 piksel ke kanan dan 1 piksel ke atas.

*DeltaG2 = a + b *(8)

Jadi nilai dari variable penentu dapat dihitung dari nilai sebelumnya dengan cara menambah dengan (a) atau (a+b). Algoritma untuk menggambar garis lurus dari (x1, y1) sampai (x2, y2) dilakukan dengan langkah-langkah sebagai-berikut: 

1. Gambar piksel pertama (x1,y1). Hitung variabel penentu dengan persamaan (3).
2. Tentukan tanda variabel penentu. Jika variabel penentu bernilai positif, increment x dan y dan tambahkan (a+b) pada vaiabel penentu, sebaliknya increment x dan y dan tambahkan (a) pada variabel penentu.
3. Plot piksel pada posisi (x, y).
4. Ulangi langkah mulai langkah kedua, sampai piksel terakhir (x2,y2).

DDA (Digital Defferential Analyzer)

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

   Bila nilai absolut dari dx lebih besar dari absolut dy, maka langkah= absolut 
   
   
   
   
   
   
   
   

   dari dx. 
   
   
   
   
   
   
   
   

   Bila tidak maka langkah= absolut dari 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
   
   
   
   
   
   
   
   

   1. dan y=y1.

Garis merupakan kumpulan dari titik-titik, untuk membentuk garis lurus adalah dengan mengetahui titik awal dan titik akhir. Dengan mengetahui titik awal dan titik akhir maka kita dapat membentuk garis. Untuk menggambarkan proses pembuatan garis dari titik awal ke titik akhir ada berbagai algoritma. Algoritam yang umum adalah DDA dan Bresenham.

Perkembangan kemampuan komputasi prosesor yang pesat telah membuat komputer desktop mempunyai kemampuan komputasi yang besar. Hal ini mendorong perkembangan program aplikasi yang memerlukan komputasi yang besar seperti program aplikasi yang menggunakan grafik 3 dimensi. Peningkatan kemampuan komputasi prosesor untuk aplikasi grafik yang sarat komputasi, perlu dibarengi peningkatan efisiensi algoritma, sehingga pembuatan grafik garis dan kurva yang merupakan dasar pembuatan grafik dapat memberikan hasil yang optimal.

Source Code Untuk Menggambar Garis Menggunakan Netbeans :

/*

 * To change this template, choose Tools | Templates

 * and open the template in the editor.

 */

package Tugas1;

import java.awt.Graphics;

/**

 *

 * @author JC

 */

public class Garis {

   

    public void Garisku (Graphics g, int x0, int y0, int x1, int y1){

        int dx,dy,steps;

        int x_tambah,y_tambah,x,y;

                             

dx= x1-x0;

dy= y1-y0;      

                

if (Math.abs(dx) > Math.abs(dy)){

steps = Math.abs(dx);

}

else{

steps = Math.abs(dy);

}

x_tambah = dx / steps;

y_tambah = dy / steps;

                x=x0;

                y=y0;

                        

                g.fillRect(x, y, 1, 1);

for (int k=10; k< steps ;k++){

x += x_tambah;

y += y_tambah;

                        g.fillRect(x, y, 1, 1);

}              

        

    }

    

}

Kemudian Simpan dengan Nama Garis.Java

Lalu Buat Class untuk memanggil Garis.Java

Berikut Source Code nya :

/*

 * To change this template, choose Tools | Templates

 * and open the template in the editor.

 */

package Tugas1;

import java.awt.Color;

import java.awt.Graphics;

import javax.swing.JFrame;

import javax.swing.JPanel;

/**

 *

 * @author JC

 */

public class PanggilGaris extends JPanel{

    @Override

    public void paintComponent(Graphics g){

        

        Garis baru = new Garis();

        g.setColor(Color.BLACK); 

        baru.Garisku(g, 100, 200, 300, 200);

        baru.Garisku(g, 100, 150, 300, 150);

            }

    

    public static void main(String[] args) {

        Garis baru = new Garis();

        JFrame frame = new JFrame("Gambar Garis");

        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        frame.add(new PanggilGaris());

        frame.setSize(600, 600);

        frame.setLocationRelativeTo(null);

        frame.setVisible(true);

               

    }

}

Jika Di Running maka Hasilnya Akan Seperti Ini

Ini Di jalankan DI Netbeans 7.1 di Windows 7.