Tugas Grafika Q - Algoritma Lingkaran Midpoint

 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

          Tabel Hasil Proses :   

                                                           

Gambar Hasil Program :