ALGORITMA MID-POINT DAN BRESENHAM LINGKARAN SERTA PERBEDAANNYA

Algoritma MidPoint (Lingkaran)

Algoritma ini diawali dengan menentukan jari jari r dan titik pusat di (xk,yk)

Algoritma ini mengenerate pixel ke 8 arah dari 4 titik lurus (0°, 90°, 180°, 270°) , ke 4 titik ini memiliki masing masing 2arah generate pixel yang ditentukan oleh algoritma lalu loop berhenti pada saat sudut terdekat kelipatan 45° (45°, 135°, 225°, 315°) atau kondisi ini sama dengan nilai x=y

Algoritma midpoint menggunakan fungsi untuk menentukan pixel selanjutnya

Rumus tersebut menerapkan rumus metematika dasar lingkaran yaitu

Untuk menentukan titik selanjutnya, cek hasil dari fungsi tadi,

Untuk menentukan titik selanjutnya dengan menggunakan fungsi, parameter yang digunakaan adalah (xk+1,yk-12) , parameter tersebut adalah letak midpoint untuk decision point dalam menentukan pixel selanjutnya.

Nilai x akan selalu increment (+1), namun nilai y selanjutnya ditentukan dengan letak midpoint yang didapatkan dari persamaan fungsi.

Jika midpoint di dalam lingkaran (f(x,y)<0) atau pas pada lingkaran, maka nilai y tidak akan dirubah, namun jika midpoint di telah diluar lingkaran, (f(x,y)>0) maka nilai y akan dikurangi agar tetap dalam jalur lingkaran

Untuk menentukan decision point, kita menggunakan fungsi tadi dan dengan memasukan parameter midpoint

Algoritmanya yaitu : 

1. Tentukan titik awal, dan decision point awal 

Khusus untuk desicion parameter setelah menentukan titik awal atau p0 di (0,r), menggunakan parameter :

Atau

Karena radius r adalah integer, maka di bulatkan menjadi

2. Tentukan titik berikutnya dengan memasukan rumus decision point

Setelah itu, decision pointnya menggunakan rumus awal yang telah disederhanakan menjadi :


Untuk Pk < 0 aatau Pk = 0,


Xk+1 Xk + 1

Yk+1 Yk

Dan

Untuk Pk> 0

Xk+1 Xk + 1

Yk+1 Yk  + 1

3. Sesuaikan X dan Y ke 7 titik generate pixel lainnya

Setelah mendapatkan nilai Xk dan Yk, generate pixel dan sesuaikan dengan 7 titik generate lainnya yang diatur lewat x dan y nya.

4. Lalu ulangi tahap 2 dan 3 sampai nilai X=Y

Saat nilai x=y atau sudah mencapai sudut dengan kelipatan 45 derajat, berarti titik itu telah bertemu dengan titik dari sudut generate lain yang menuju titik 45 derajat yang sama.

void circleMidpoint (int xCenter, int yCenter, int radius){ int x = 0; int y = radius; int p = 1 - radius; void circlePlotPoints (int, int, int, int); // Plot first set of points circlePlotPoints (xCenter, yCenter, x, y); while (x < y) { x++; if (p < 0){ p += 2 * x + 1; } else { y--; p += 2 * (x - y) + 1; } circlePlotPoints (xCenter, yCenter, x, y); } } void circlePlotPoints (int xCenter, int yCenter, int x, int y) { putpixel (xCenter + x, yCenter + y,WHITE); putpixel (xCenter - x, yCenter + y,WHITE); putpixel (xCenter + x, yCenter - y,WHITE); putpixel (xCenter - x, yCenter - y,WHITE); putpixel (xCenter + y, yCenter + x,WHITE); putpixel (xCenter - y, yCenter + x,WHITE); putpixel (xCenter + y, yCenter - x,WHITE); putpixel (xCenter - y, yCenter - x,WHITE); }

BACA JUGA : ALGORITMA MID-POINT ELIPS
Algoritma Bresenham (Lingkaran)

Pada dasarnya algoritma bresenham ini hampir sama dengan midpoint, karena cara men-generate pixelnya dibagi di 8 titik dan berhenti jika sudah mencapai sudut kelipatan 45 derajat atau x=y,

Namun, algoritma bresenham ini menggunakan decision parameter yang berbeda, yaitu dengan cara membandingkan titik selanjutnya, apakah titik F(s) (xk+1,yk-1) lebih dekat, atau titik F(N) (xk+1,yk) yang lebih dekat, mengambil persamaan lingkaran, bisa kita rumuskan seperti ini :

F(x,y) = x2 + y2 – r2

F(N) = (xk + 1)2 + y2k – r2

F(S) = (xk + 1)2 + (yk - 1)2 – r2

Decision parameter (Pk) = F(N) + F(S)

Pk = 2( xk + 1 )2 + y2k + (yk - 1)2 – r2

Setelah kita mendapat decision parameter, kita akan membuat decision parameter pertama, dengan persamaan :

Initial decision parameter
Po = 2(1+0)2 + r2 + (r-1)2 – 2r2

Po = 3-2r

Lalu decision parameter selanjutnya adalah :

1. jika P < 0,

xk+1 – xk = 1

yk+1 – yk = 0

Put in (A)

Pk+1 = Pk + 2(2xk + 3)

Pk+1 = Pk + 4xk + 6

2. Jika P > 0,

xk+1 – xk = 1

yk+1 – yk = -1

Put in (A)

Pk+1 = Pk + 4xk+6 + (yk+1 +yk)(-1) + (yk+1 +yk -2)(-1)

Pk+1 = Pk + 4xk – 4yk + 10

Selebihnya sama dengan algoritma midpoint.

void circleBres(int xc, int yc, int r) {    int x = 0, y = r;    int d = 3 - 2 * r;    void circlePlotPoints (int, int, int, int);    while (y >= x)    {        // for each pixel we will        // draw all eight pixels        circlePlotPoints(xc, yc, x, y);        x++;        // check for decision parameter        // and correspondingly        // update d, x, y        if (d > 0)        {            y--;            d = d + 4 * (x - y) + 10;        }        else            d = d + 4 * x + 6;        circlePlotPoints(xc, yc, x, y);        delay(50);    } } void circlePlotPoints (int xCenter, int yCenter, int x, int y) { putpixel (xCenter + x, yCenter + y,WHITE); putpixel (xCenter - x, yCenter + y,WHITE); putpixel (xCenter + x, yCenter - y,WHITE); putpixel (xCenter - x, yCenter - y,WHITE); putpixel (xCenter + y, yCenter + x,WHITE); putpixel (xCenter - y, yCenter + x,WHITE); putpixel (xCenter + y, yCenter - x,WHITE); putpixel (xCenter - y, yCenter - x,WHITE); }

Percobaan

circleMidpoint(400,500,10); //MidPoint KIRI

circleBres(430,500,10); //Bresenham KANAN

circleMidpoint(400,500,50);  //MidPoint KIRI

circleBres(510,500,50); //Bresenham KANAN

circleMidpoint(420,500,100);

circleBres(200,500,100);

Kesimpulan

Perbedaan hasil dari algoritma beresnham dan midpoint saat jari jarinya kecil, algoritma beresnham kurang bisa