Komputer Grafik - Algoritma Garis

KOMPUTER GRAFIK

ALGORITMA GARIS

Nama                                       : Iswahyuni

NPM                                       : 1111706

Kelas                                       : TI - P1101

Dosen                                      : Sinar Sinurat, ST, M.Kom

SEKOLAH TINGGI MANAJEMEN INFORMATIKA DAN KOMPUTER

STMIK BUDIDARMA

MEDAN

T.A 2012/2013

DAFTAR ISI

Daftar Isi…………………………………………………………………..   1

ALGORITMA GARIS...………………………………………………….  2

1.      Garis (Line)….…………………………………….…..….……  2

2.      Algoritma Pembuatan Garis……..……………...............……... 2

3.   Algoritma Garis…………………………...............………........ 3

A.     Line Equation (Persamaan Garis Lurus...….............…   3

·         Tipe Garis……………………………………...  4

B.     DDA (Digital Difference Analyser) ...…...................…  4

·         Algoritma DDA………………………………..  5

·         Contoh Soal……………………………….…… 7

C.     Bresenham’s Algorithm...............................................… 8

·         Garis Lurus…………………………………….. 8

·         A. Bresenham untuk Penggambaran Garis……..9

·         Algoritma Garis Bresenham…………………….10

·         Contoh Soal………...….............………………. 10

D.    Algoritma Midpoint...………………………..............… 12

·         A. Midpoint untuk Penggambaran Garis...….…  12

·         A. Midpoint untuk Menggambar Lingkaran...…  15

·         Contoh Soal………...….............………………. 17

DAFTAR PUSTAKA................................................................................... 20

ALGORITMA GARIS

Algoritma merupakan langkah - langkah (prosedur) yang harus dilakukan untuk menyelesaikan sebuah masalah. Garis merupakan sederetan pixel yang membentuk satu kesatuan.

     1.      Garis (Line)

Persamaan garis :

q 

q  y = m.x + c

dimana :         

·         m = (y₂-y₁)/(x₂-x₁) = Dy/Dx

·         c = y₁ – m.x₁ atau

c = y₂ – m.x₂

2.      Algoritma Pembuatan Garis

Algoritma pembuatan garis lurus vertikal dan horisontal relatif mudah, tetapi bila garis tersebut miring, maka algoritma menjadi sulit.

Misalkan : Line (1,3,8,5).

m = (y₂-y₁)/(x₂-x₁) = (5-3)/(8-1) = ²/₇

c = y₁ – m.x₁ = 3 – ²/₇.1 = ¹⁹/₇

y = ²/₇.x + ¹⁹/₇

Selanjutnya kita membuat iterasi dari x₁ à x₂

Xi	Yi	Yi (dibulatkan)
1	3.00	3
2	3.29	3
3	3.57	4
4	3.86	4
5	4.14	4
6	4.43	4
7	4.71	5
8	5.00	5

    3.      Algoritma Garis

Algorithma garis adalah algorithma untuk menentukan lokasi pixel yang paling dekat dengan garis sebenarnya (actual line).

Ada tiga algorithma untuk menggambar garis :

A.    Line Equation (Persamaan Garis Lurus)

B.     DDA (Digital Difference Analyser)

C.     Bresenham’s Algorithm

D.    Algoritma Midpoint

A.    Line Equation ( Persamaan Garis lurus )

·         Persamaan garis lurus merupakan persamaan linier yang mengandung satu atau dua variabel.

·         Sebuah garis lurus dapat diperoleh dengan menggunakan rumus :

y = mx + b

dimana :

m = gradient

b  = perpotongan garis dengan sumbu y.

·         Apabila dua pasang titik akhir dari sebuah garis dinyatakan sebagai  (x1,y1) and (x2, y2), maka nilai dari gradien m dan lokasi b dapat dihitung dengan :

 

·         Persamaan Garis dapat digunakan di semua kwadran

Ø  Tipe Garis

Dapatkah anda mencari perbedaan yang esensial antara garis A dan B (misal : gradien, pertambahan x dan y) ?

·         Garis A : (3;1) – ( 8;4)

-       m = (y2 – y1) / (x2 – x1) = (4-1)/ (8-3) = 3/5= 0,6

-       0 < m < 1

-       xi+1 = xi + 1 ; yi+1 = yi + d1

·         Garis B : (1;2) – (2;7)

-       m = (7-2) / (2-1) = 5 / 1 = 5

-       m > 1

-       xi+1 = xi + d2 ; yi+1 = yi + 1

B.     DDA (Digital Difference Analyser)

        ·         Digital differential analyzer (DDA) merupakan algoritma untuk menghitung posisi pixel di sepanjang garis dengan menggunakan posisi pixel sebelumnya

        ·         Algoritma ini menggunakan asumsi bahwa garis berada di kuadran I atau II serta tipe garis cenderung tegak atau cenderung mendatar

        ·         Mengatur titik-titik koordinat pada masing-masing sumbu

• Algorithma DDA

  ü  Untuk garis dengan 0< m ≤1 (cenderung mendatar di Kw I), maka :

Ø  y_k+1=y_k + m

Ø  x_k+1 = x_k + 1

  ü  Untuk garis dengan m > 1 (cenderung tegak di Kw I), maka :

Ø  x_k+1=x_k + 1/m

Ø  y_k+1 = y_k + 1

  ü  Garis dengan 0 > m > -1 (cenderung mendatar di Kw II), maka:

Ø  y_k+1=y_k - m

Ø  x_k+1 = x_k - 1

  ü  Sedangkan bila m < -1 (cenderung tegak di Kw II), maka :

Ø  x_k+1=x_k - 1/m

Ø  y_k+1 = y_k + 1

Digital Diferensial Analyser (DDA) adalah algoritma pembentukan garis berdasarkan perhitungan dx maupun dy, menggunakan rumus dy = m . dx. Garis dibuat menggunakan dua endpoint, yaitu titik awal dan titik akhir. Setiap koordinat titik yang membentuk garis diperoleh dari perhitungan, kemudian dikonversikan menjadi nilai integer.

Langkah-langkah membentuk garis menurut algoritma DDA adalah :

           1.      Tentukan 2 buah titik

2. Tentukan yang menjadi titik awal (X0, Y0) dan titik akhir (X1, Y1)
3. Hitung Dx dan Dy

Dx = X1 – X0 dan Dy =  Y1 – Y0

4. Bandingkan absolut (Dx) dan absolut (Dy)

Jika absolute (Dx) > absolut (Dy), maka

Steps = absolute (Dx) bila tidak, steps = absolut (Dy)

5. Hitung penambahan koordinat pixel, yaitu:

6. Koordinat selanjutnya yaitu:

X + X_increment

Y + Y_increment

7. Posisi pixel ditentukan dengan pembulatan nilai koordinat tersebut
8. Ulangi langkah 6 dan 7 untuk posisi selanjutnya sampai X = X1, Y= Y1

Digital Diferential Analyser adalah suatu algoritma (pendekatan) pengkonversian suatu himpunan pixel menjadi suatu garis yang didasari atas perhitungan Dx dan Dy, dengan menggunakan persamaan (4) dan (5) diatas. Kita cocokan sebuah garis pada unit interval di dalam satu koordinat dan kemudian kita tentukan nilai interger yang mempunyai jarak terdekat dengan line-path untuk koordinat yang lain. Perhatikan garis pertama dengan slope positif yang ditunjukkan gambar di atas. Jika slope kurang dari 1, kita tentukan nilai untuk unit interval x (dalam hal ini Dx=1) dan hitung beberapa hasil iterasi secara berturut2 untuk nilai y dengan persamaan

yk+1= yk + m è Persamaan (6)

subskrip k bernilai integer yang dimulai dari 1, untuk pengiterasian pertama, dan terus menambahakan nilai k dengan 1 sampai pasangan koordinat (x,y) Yng terpenuhi oleh algoritma tersebut. Slope m dapat berupa suatu nilai antara 0 dan 1, kemudian  hasil hitungan y akan dibulatkan (trancation) menjadi suatu nilai integer yang mendekati dengan nilai sebenarnya yang bertipe pecahan (floating). Untuk garis dengan kemiringan positif atau > (lebih besar) dari 1, kita harus menukarkan peran dari x dan y, dapat kita contohkan pada interval y (Dy=1), lalu hitung beberapa nilai x secara berturut-turut menggunakan persamaan

Xk+1 = Xk + 1/m   è Persamaan  (7)

Persamaan (6) dan (7) didasarkan dari pengasumsian suatu garis yang diproses dari titik ujung paling kiri dari garis menuju titik ujung paling kanan dari garis tersebut. Jika proses ini dibalikkan atau ditukar, suapaya diperoleh keadaan di mana titik ujung awalnya berada du sebelah kanan, maka kita harus memberikan nilai Dx=1 dan yk+1 = yk – m atau (di saat slope atau kemiringan garis lebih besar dari 1) maka kita harus memasukkan nilai Dy = -1 dan Xk+1 = Xk - 1/m  

Persamaan (6) dan (9) dapat juga digunakan untuk menghitung posisi pixel yang membentuk suatu garis dengan slope negatif. Jika nilai absolut slope lebih kecil dari 1 dan titik-titik ujung (endpoint) awalnya berada di sisi paling kiri, kita berikan nilai Dx = 1 dang hitung nilai yk+1 dengan persamaan (6). Dan kemudian endpoint awal berada pada posisi sebelah kanan (untuk slope yang sama), kita masukkan Dx = -1 dan kita dapatkan nilai y dari hasil perhitungan menggunakan persmaan (8). Sama juga ketika nilai absolut dari sebuah slope positif adalah besar dari 1, kita gunakan Dy = -1 dan kita tentukan Xk+1 dengan persamaan (9) atau kita gunakan Dy = 1 dan kita tentukan Xk+1 dengan persamaan (7). Algoritma ini dirangkum di dalam prosedur berikut, yang mana program menerima input dua posisi pixel endpoint (titik-titik ujung suatu garis) sebagai awalnya dan menentukan perbedaan horizontal den vertikal diantara dua posisi endpoint yang diperoleh untuk parameter dx dan dy. Perbedaan nilai yang cenderung besar akan menentukan nilai dari parameter step di dalam algoritma DDA. Dimulai dari posisi pixel (Xa,ya) kita tentukan penyeimbang yang dibutuhkan pada beberapa langkah program untuk menghasilkan posisi pixel selanjutnya sepanjang line path. Digital diferential analyzer merupakan suatu metode yang paling cepat melakukan kalkulasi (menghitung) keberadaan posisi pixel dan merupakan implementasi langsung dari persamaan (1).
  

    ·         Contoh soal:

Diketahui 2 buah titik A(10,10) dan titik B(17,16) bila titik A sebagai titik awal dan titik B sebagai titik akhir, maka buatlah garis yang menghubungkan titik tersebut dengan menggunakan algoritma DDA.

Jawab:

Titik awal = A(10,10)

Titik akhir = B(17,16)

Dx= X1-X0 = 17 – 10 = 7

Dy= Y1-Y0 = 16 – 10 = 6

Absolut (Dx) = 7

Absolut (Dy) = 6

Absolut (Dx) > absolute (Dy) maka steps = Absolut (Dx) = 7

X_increment ==7/7 = 1

Y_increment =  = 6/7 = 0,86

X1 = X + X_increment = 10 + 1 =11

Y1 = Y + Y_increment = 10 + 0,857 = 10,857 =11

Atau lebih cepatnya kita singkat dengan menggunakan table

K	X	Y	X_incre	Y_incre
-	-	-	10	10
0	11	10,857	11	11
1	12	11,71	12	12
2	13	12,57	13	13
3	14	13,43	14	14
4	15	14,28	15	14
5	16	15,14	16	15
6	17	16	17	16

     C.    Algoritma Bresenham

     ·         Garis Lurus

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.

    ·         Algoritma Bresenham untuk Penggambaran Garis

Bresenham pada tahun 1965, melakukan perbaikan dari algoritma perhitungan koordinat piksel yang menggunakan persamaan (1), dengan cara menggantikan operasi bilangan real 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 real dengan operasi bilangan integer. Operasi bilangan integer jauh lebih cepat dibandingkan dengan operasi bilangan real, terutama pada penambahan dan pengurangan.

    ·         Algoritma Garis Bresenham

Prosedur untuk menggambar kembali garis dengan membulatkan nilai x atau y ke bilangan integer memerlukan waktu. serta variabel x,y maupun m memerlukan bilangan real karena kemiringan merupakan nilai pecahan.Bressenham mengembangkan algoritma klasik yang lebih menarik, karena hanya menggunakan perhitungan matematik dengan bantuan bilangan integer. Dengan demikian tidak perlu membulatkan nilai posisi pixel setiap waktu. Langkah-langkahnya adalah sebagai berikut:

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 P₀= 2Dy – 2Dx
5. Untuk setiap X1 sepanjang jalur garis, dimulai dengan k=0,

-          bila pk<0, makatitik selanjutnya adalah (X_k + 1, Y_k) dan P_k+1 = P_k +2D_y

-          bila tidak, maka titik selanjutnya adalah (X_k + 1, Y_k +1) dan P_k+1 = P_k +2D_y – 2Dx

6. Ulangi langkah no. 5 untuk menentukan posisi selanjutnya, sampai X=X1 dan Y=Y1

     ·         Contoh soal:

Diketahui 2 buah titik A(10,10) dan titik B(17,16) bila titik A sebagai titik awal dan titik B sebagai titik akhir, maka buatlah garis yang menghubungkan titik tersebut dengan menggunakan algoritma Bressenham

Jawab:

Periksa Xa dan Xb

Xa = 10 < Xb=17

Maka, X = Xa = 10

            Y=Ya = 10

Xend = xa= 17

Ulangi selama x < xend

* K0:

x = x + 1 = 10 + 1 = 11

Periksa nilai p , dimana p = 5

y = y + 1 = 10 + 1 = 11

p = p + twodydx = 5 + (-2) = 3

* K1:

x = x + 1 = 11 + 1 = 12

Periksa nilai p, dimana p = 3

y = y +1 = 11 + 1 = 12

p = p + twodydx = 3 + (-2) = 1

* K2:

x = x + 1 = 12 + 1 = 13

Periksa nilai p, dimana p = 1

y = y +1 = 12 + 1 = 13

p = p + twodydx = 1 + (-2) = -1

* K3:

x = x + 1 = 13 + 1 = 14

Periksa nilai p, dimana p = -1

Nilai y tetap yaitu y=13

p = p + twody = (-1) + 12 = 11

* K4:

x = x + 1 = 14 + 1 = 15

Periksa nilai p, dimana p = 11

y = y +1 = 13 + 1 = 14

p = p + twodydx = 11 + (-2) = 9

* K5:

x = x + 1 = 15 + 1 = 16

Periksa nilai p, dimana p = 9

y = y +1 = 14 + 1 = 15

p = p + twodydx = 9 + (-2) = 7

* K6:

x = x + 1 = 16 + 1 = 17

Periksa nilai p, dimana p = 7

y = y +1 = 15 + 1 = 16

p = p + twodydx = 7 + (-2) = 5

Proses berhenti karena x = x1 dan y = y1

K	Pk	(Xk+1 , Yk+1)
-	-	10,10
0	3	11,11
1	1	12,12
2	-1	13,13
3	11	14,13
4	9	15,14
5	7	16,15
6	5	17,16

     D.    Algoritma Midpoint

    ·         Algoritma Midpoint untuk Penggambaran Garis

Algoritma midpoint dikembangkan oleh Pitteway pada tahun 1967.

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 positif 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).

-          Lingkaran

Kurva lingkaran dinyatakan dinyatakan dalam persamaan :

*(x-xc) ^2 + (y-yc) ^2 = r ^2 *          (9)

dimana : (xc,yc) : koordinat titik pusat lingkaran
r : jari-jari lingkaran

Untuk menggambarkan piksel-piksel dalam kurva lingkaran, dapat digunakan sumbu x dari x = (xc-r) sampai x = (xc+r) sebagai parameter dan sumbu y sebagai hasil dari persamaan (10)

*y = yc +- sqrt(r ^2 – (x-xc) ^2 *      (10)

Algoritma ini memerlukan waktu operasi yang besar, karena mengandung operasi bilangan riel perkalian maupun eksponential, dan menghasilkan posisi koordinat piksel yang tidak merata, karena terjadinya gaps yang disebabkan adanya perubahan gradient.
Untuk menghindari posisi koordinat piksel yang tidak merata, koordinat piksel (x,y) dinyatakan dengan menggunakan koordinat polar dalam persamaan (11)

*x = xc + r cos q *                              (11a)
*y = yc + r sin q *                              (11b)

Persamaan (11) diatas mengandung operasi bilangan riel perkalian untuk mendapatkan koordinat piksel (x,y), untuk setiap nilai x, dari x = (xc-r) sampai x = (xc+r), operasi inilah yang perlu dihindari, karena operasi ini memerlukan waktu operasi yang besar.

·         Algoritma Midpoint untuk Menggambar Lingkaran

Komputasi untuk membuat kurva lingkaran dimulai dengan mengidentifikasi bagian-bagian dari lingkaran yang dapat ditentukan dengan menggunakan sifat simetri, hal ini dilakukan dengan cara membagai lingkaran dengan masing-masing mempunyai sudut sebesar 45° , sehingga dalam sebuah lingkaran dibagi menjadi 8 bagian. Sebagai contoh, digambarkan bagian dari lingkaran dari sudut 90° sampai 45° . Seperti pada algoritma midpoint untuk garis lurus, maka pada setiap tahapan, terdapat 2 koordinat piksel yang harus dipilih yaitu (x+1, y) atau (x+1, y-1).

Langkah berikutnya, adalah menyatakan persamaan lingkaran dan fungsi untuk menentukan variabel penentu. Persamaan lingkaran dengan pusat (0,0) dinyatakan dalam persamaan (12).

*f(x, y) = x*x + y+y – r*r = 0 *         (12)

Fungsi f(x, y) persamaan (12) akan bernilai positif jika titik (x,y) diluar lingkaran, dan bernilai negatif jika titik (x,y) didalam lingkaran. Fungsi untuk variabel penentu dan increment dinyyatakan dalam persamaan (13), (14), dan (15).

g(x, y) = (x + 1) (x + 1) + (y – 1/2) (y – 1/2) – r*r                 (13)
*DeltaG1 = 2x + 3                                                                 (14)
*DeltaG2 = 2x – 2y + 5                                                         (15)

Berbeda dengan nilai dari increment pada algoritma garis lurus yang bernilai konstan, pada kurva lingkaran, increment tidak konstan. Terlihat bahwa komputasi increment memerlukan operasi perkalian, tetapi operasi perkalian dapat diubah dengan cara komputasi nilai increment secara increment pula, sehingga diperlukan 2 komputasi increment dalam setiap piksel yang diproses. Secara umum, kurva polinomial orde n memerlukan n level increment. Pada titik awal (x1,y1), komputasi variabel penentu mempunyai bagian bilangan riel, sehingga operasi bilangan integer tidak dapat digunakan secara langsung.

Dalam praktek hal ini diselesaikan dengan cara menambahkan nilai 1/4 pada variable penentu. Hal ini tidak mempengaruhi perubahan tanda bilangan, karena operasi yang dilakukan adalah operasi bilangan integer, sehingga menghasilkan operasi yang lebih cepat.

Panjang garis atau banyak piksel dalam garis lurus sangat berpengaruh terhadap perbandingan performance antara sebuah algoritma dengan algoritma yang lain, hal ini disebabkan adanya perbedaan waktu operasi yang berada didalam perulangan sepanjang pembuatan piksel, dan waktu operasi yang berada pada sebelumnya. Panjang jari-jari dalam lingkaran tidak berpengaruh terhadap perbandingan performance antara sebuah algoritma dengan algoritma yang lain, hal ini menunjukkan perbandingan waktu operasi yang berada didalam perulangan sepanjang pembuatan piksel, dan waktu operasi yang berada pada sebelumnya berimbang.

Algoritma dengan dasar operasi bilangan integer memberikan waktu operasi yang lebih cepat dibandingkan dengan algoritma dengan dasar operasi bilangan riel, hal ini ditunjukkan dengan waktu komputasi algoritma DDA, algoritma Bresenham dan algoritma Midpoint yang lebih cepat, baik pada pembuatan garis lurus maupun lingkaran dibandingan waktu komputasi dengan algoritma yang menggunakan dasar operasi bilangan riel. Algoritma midpoint memberikan waktu operasi tercepat diantara algoritma penggambaran garis lurus yang telah menggunakan dasar operasi bilangan integer, seperti algoritma DDA, algoritma Bresenham. Jadi algoritma Midpoint merupakan algoritma yang cocok untuk penggambaran grafik yang menuntut kecepatan sebagai hal yang diutamakan.

• Contoh Soal Lingkaran

Diketahui titik pusat lingkaran (0,0) dan radius 8, perhitungan berdasarkan oktan dari kuadran pertama dimana x = 0 sampai y = 0. Nilai parameter dapat ditentukan dengan P0 = 1 – r = 1 – 8 = -7

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

Jawab:

X = 0 Y = r = 8

--------------------------------------------------------------

K=0

P = 1 – r

= 1 – 8 = -7

Loop ke-1

x = x +1                       y tetap è 8

= 0 +1 = 1

---------------------------------------------------------------

K=1

P = P + 2 * X + 1

= -7 + 2 * 1 + 1

= -4

Loop ke-2

x = x +1                       y tetap è 8

= 1 +1 = 2

---------------------------------------------------------------

K=2

P = P + 2 * X + 1

= -4 + 2 * 2 + 1

= 1

Loop ke-3

x = x +1                       y = y-1

= 2 +1 = 3          = 8-1 = 7

---------------------------------------------------------------

K=3

P = P + 2 * (X –Y) +1

= 1 + 2 * (3 – 7) + 1

= -6

Loop ke-4

x = x +1                       y tetap è 7

= 3 +1 = 4

---------------------------------------------------------------

K=4

P = P + 2 * X + 1

= -6 + 2 * 4 + 1

= 3

Loop ke-5

x = x +1                       y = y-1

= 4 +1 = 5          = 7-1 = 6

---------------------------------------------------------------

K=5

P = P + 2 * (X - Y) + 1

= 3 + 2 *(5 - 6) + 1

= 2

Loop ke-6

x = x +1                       y = y-1

= 5 +1 = 6          = 6-2 = 5

---------------------------------------------------------------

K=6

P = P + 2 * (X - Y) + 1

= 2 + 2 *(6 - 5) + 1

= 5 Loop berhenti karena x > y

Tabel hasil proses;                                                                       

K	Pk	(Xk+1 , Yk+1) Oktan 1
-	-	(0,8)
0	-7	(1,8)
1	-4	(2,8)
2	1	(3,7)
3	-6	(4,7)
4	3	(5,6)
5	2	(6,5)

Gambar hasil tampilan program;

Daftar Pustaka :

q  http://ardye89.wordpress.com/2011/03/21/grafika-komputer/

q  http://hogyz.blogspot.com/2012/11/algoritma-dda-algoritma-bresenham.html

q  http://irmhawahyuni.blogspot.com/2012/11/komputer-grafik.html

q  http://xa.yimg.com

q  http://sizakia.blogspot.com/

By : Cut Iswahyuni