Algoritma MidPoint (Elips)

Algoritma ini pengembangan dari algoritma bresenham

Elips memiliki 2 jari jari yang berbeda,  dan lengkungannya tidak mungkin sempurna

Kita ambil seperempat bagiannya saja. Di lengkungan seperempat bagian ini, dibagi 2 region, region 1 yang gradiennya lebih besar dari -1 dan region 2 yang gradiennya lebih kecil dari -1

Persamaan elips bisa dituliskan sebagai :

f(x,y) = b2 x2 + a2 y2 – a2 b2

Dimana b adalah jari jari vertikal, dan a adalah jari jari horizontal, dan f(x,y) dalah perdiksi eror dari koordinat (x,y)

Region 1 (dy/dx > –1)

Nilai x selalu increment xk+1 = xk + 1 , nilai Y ditentukan apakah E atau SE yang terpilih, jika E terpilih, maka yk+1 = yk + 0 , namun jika SE yang terpilih, maka yk+1 = yk + 1

Untuk menentukan E atau SE, menggunakan prediction (xk+1,yk-12) di tengah tengan pixel antara E dan SE, fungsi Pk bisa dituliskan sebagai :

Pk = f(xk+1, yk–½)

= b2 (xk+1)2 + a2 (yk–½)2 – a2 b2

= b2 (xk 2 + 2xk + 1) + a2 (yk 2 – yk + ¼) – a2 b2

Jika Pk > 0 , maka SE terpilih

Pk+1 SE = f(xk+2, yk–3/2)

= b2 (xk+2)2 + a2 (yk–3/2)2 – a2 b2

= b2 (xk 2 + 4xk + 4) + a2 (yk 2 – 3yk + 9/4) – a2 b2

perubahan Pk SE adalah ∆Pk SE = Pk+1 SE – Pk = b2 (2xk + 3) – 2a2 (yk – 1)

Jika Pk < 0 , maka E terpilih

Pk+1 E= f(xk+2, yk–½)

= b2 (xk+2)2 + a2 (yk–½)2 – a2 b2

= b2 (xk 2 + 4xk + 4) + a2 (yk 2 – yk + ¼) – a2 b2

perubahan Pk E is: ∆Pk E = Pk+1 E – Pk = b2 (2xk + 3)

If E is selected,

∆Pk+1 E = b2 (2xk + 5)

∆2 Pk E = ∆Pk+1 E – ∆Pk E = 2b2

∆Pk+1 SE = b2 (2xk + 5) – 2a2 (yk – 1)

∆2 Pk SE = ∆Pk+1 SE – ∆Pk SE = 2b2

If SE is selected,

∆Pk+1 E = b2 (2xk + 5)

∆2 Pk E = ∆Pk+1 E – ∆Pk E = 2b2

∆Pk+1 SE = b2 (2xk + 5) – 2a2 (yk – 2)

∆2 Pk SE = ∆Pk+1 SE – ∆Pk SE = 2(a2 + b2 )

Initial values:

x0 = 0,

y0 = b,

P0 = b2 + ¼a2 (1 – 4b)

∆P0 E = 3b2 ,

∆P0 SE = 3b2 – 2a2 (b – 1)

Region 2 (dy/dx < –1),

semua kalkulasi sama dengan region 1, namun nilai y selalu decrement, dan x ditentukan oleh decision parameter

Implementasi di C,

void ellipseMidpoint (int xCenter, int yCenter, int Rx, int Ry) { int Rx2 = Rx*Rx; int Ry2 = Ry*Ry; int twoRx2 = 2*Rx2; int twoRy2 = 2*Ry2; int p; int x = 0; int y = Ry; int px = 0; int py = twoRx2 * y; void ellipsePlotPoints (int, int, int, int); // Plot the first set of points ellipsePlotPoints (xCenter, yCenter, x, y); // Region 1 *I p = ROUND (Ry2 - (Rx2 * Ry) + (0.25 * Rx2)); while (px < py) { x++; px += twoRy2; if (p < 0) p += Ry2 + px; else { y--; py -= twoRx2; p += Ry2 + px - py; } ellipsePlotPoints (xCenter, yCenter, x, y); } /* Region 2 */ p = ROUND (Ry2*(x+0.5)*(x+0.5) + Rx2*(y-1)*(y-1) - Rx2*Ry2); while (y > 0) { y--; py -= twoRx2; if (p > 0){ p += Rx2 - py; } else { x++; px += twoRy2; p += Rx2 - py + px; } ellipsePlotPoints (xCenter, yCenter, x, y); } } void ellipsePlotPoints (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); }

ellipseMidpoint(200,200,30,20);

ellipseMidpoint(200,200,100,50);

ellipseMidpoint(600,500,300,100);

Namun akan berbentuk seperti lemon jika elipsnya semakin besar

ellipseMidpoint(600,500,500,300);

Saya belum tahu penyebabnya, saya belum menganalisis terlalu dalam tentang masalah ini, namun saya akan mencaritahu kenapa jika r2 lebih dari 500 akan berbentuk seperti lemon.