Algoritma Lingkaran Midpoint

        Algoritma Lingkaran Midpoint juga disebut algoritma lingkaran Bressenham. Bressenham mengembangkan generator lingkaran yang cukup efisien. Algoritma yang digunakan membentuk semua titik berdasarkan titik pusat dengan penambahan semua jalur sekeliling lingkaran. Algoritma ini diturunkan dari algoritma Midpoint untuk pembentukan garis. Dalam hal ini hanya diperhatikan bagian 45’ dari suatu lingkaran, yaitu oktan kedua dari x=0 ke x=R/Ö2, dan menggunakan CirclePoints untuk menampilkan titik dari seluruh lingkaran.

Langkah langkah untuk membentuk lingkaran algoritma Circle Midpoint:
1. Tentukan radius r dengan titk pusat lingkaran(xc,yc) kemudian diperoleh (x0,y0)=(0,r)

2. Hitung nilai dari parameter P0=5/4r
3. Tentukan nilai awal k=0, untuk setiap posisi xk berlaku sebagai berikut:
- Bila Pk< 0, maka titik selanjutnya adalah (xk+1,k+1,k+1,k+1,yk)k))dan Pk+1k+1k+1=Pk+2xk+1k+1k+1+1 - Bila tidak, maka selanjutnya adalah(xk+1,k+1,k+1,k+1,yk-1k-1k-1), dan Pk+1k+1k+1=Pk+2xk+1k+1k+1+12yk+1k+1k+1 Dimana 2xk+1=k+1=k+1=k+1=2xk+2 dan 2yk+k+=2yk2 4. Tentukan titik simetris pada ketujuh oktan yang lain 5.Gerakkan setiap posisi pixel(x,y) pada garis melingkar dari lingkaran dengan titik pusat (xc,yc) dan tentukan nilai koordinat: x=x+xcy=y+yc 6.Ulangi langkah ke3 sampai 5, sehingga x>=y

Prosedur algoritma lingkaran midpoint:
Input yang digunakan pada prosedur ini adalah koordinat titik pusat dan radius lingkaran. Posisi pixel ditentukan dengan rutin setPixel.

uses graph,crt;
procedure init;
var gd, gm : integer;
begin
gm:=detect; gd:=0;
InitGraph(gd,gm,'');
if GraphResult <> grOk then
begin
Writeln('Graph driver ',gd,' graph mode ',gm,' not supported');
Halt(1);
end;
end;
procedure destroy;
begin
closegraph;
end;
procedure circlePlotPoints(xCenter,yCenter,x,y:integer);
begin
putPixel(xCenter+x, yCenter+y,30);
putPixel(xCenter-x, yCenter+y,30);
putPixel(xCenter+x, yCenter-y,30);
putPixel(xCenter-x, yCenter-y,30);
putPixel(xCenter+y, yCenter+x,30);
putPixel(xCenter-y, yCenter+x,30);
putPixel(xCenter+y, yCenter-x,30);
putPixel(xCenter-y, yCenter-x,30);
end;
procedure circleMidPoint (xCenter,yCenter,radius:integer);
var
x,y,p:integer;
begin
x:=0;
y:=radius;
p:=1-radius;
circlePlotpoints(xCenter,yCenter,x,y);
while x
begin
x:=x+1;;
if p<0 then p:=p+(2*x+1) else begin y:=y-1; p:=p+(2*(x-y)+1); end; end; circlePlotPoints(xCenter,yCenter,x,y); end; begin init; circleMidPoint(100,100,90); readkey; destroy; end. Latihan : 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