Algoritma Midpoint untuk Penggambaran Garis
Algoritma midpoint dikembangkan oleh Pitteway pada tahun 1967. Pada gambar di atas, titik abu-abu menyatakan posisi piksel, titik hitam menyatakan posisi piksel yang telah digambar. Berdasarkan piksel ke n yang telah digambar, diperlukan metode untuk menentukan piksel berikut yang akan digambar, karena penggambaran dilakukan dari kiri ke kanan, maka piksel berikutnya harus pada kolom n+1. Karena gradien diantara 0 dan 1, maka piksel berikutnya adalah pada posisi titik p atau titik q.
Persamaan garis lurus dalam persamaan y = mx + c dapat dinyatakan dalam fungsi x,y berikut.
f(x, y) = ax + by + c = 0 (1)
Fungsi f(x,y) dalam persamaan di atas, akan memberikan nilai 0 pada setiap titik yang terletak pada garis, dan bernilai positip 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 di atas 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) (2)
Fungsi g(x,y) persamaan di atas 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 1 dan persamaan 2.
DeltaG = a * DeltaX + b * DeltaY (3)
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 (4)
Bila bergeser 1 piksel ke kanan dan 1 piksel ke atas.
DeltaG2 = a + b (5)
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:
- Gambar piksel pertama (x1,y1). Hitung variabel penentu dengan persamaan c = y1 – m* x1.
- 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.
- Plot piksel pada posisi (x, y).
- Ulangi langkah mulai langkah kedua, sampai piksel terakhir (x2,y2).
Algoritma Midpoint
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 (6).
f(x, y) = x*x + y+y - r*r = 0 (6)
Fungsi f(x, y) persamaan (6) 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 (7), (8), dan (9).
g(x, y) = (x + 1)*(x + 1) + (y - 1/2)*(y - 1/2) - r*r (7)
DeltaG1 = 2x + 3 (8)
DeltaG2 = 2x - 2y + 5 (9)
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.
Contoh Program :
//———————————————————————
#include <vcl.h> // deklarasi vcl.h
#pragma hdrstop
#include <stdlib.h> // deklarasi stdlib.h atau standar library
#include “Unit1.h”
#include <math.h> // deklarsi fungsi matematika
//———————————————————————
#pragma package(smart_init)
#pragma resource “*.dfm”
TForm1 *Form1;
int tergambar, XC,YC,QX,QY; //deklarasi variable bertipe integer
//———————————————————————
__fastcall TForm1::TForm1(TComponent* Owner) : TForm(Owner) // deklarasi dari form itu sendiri
{
}
//———————————————————————
//untuk mengaktifkan form
void __fastcall TForm1::FormActivate(TObject *Sender)
{
Image1->Canvas->Rectangle(0,0,Image1->Width,Image1->Height); //untuk membuat obyek kotak dengan ukuran sebesar obyek Image1 yang ada dilayar
}
//———————————————————————
void __fastcall TForm1::Button2Click(TObject *Sender) // fungsi dari button2 jika diklik
{
Close(); //perintah untuk keluar dari program
}
//———————————————————————
void __fastcall TForm1::Button1Click(TObject *Sender) // fungsi dari button1 jika diklik
{
tergambar=false; // nilai tergambar false maka
Image1->Canvas->Rectangle(0,0,Image1->Width,Image1->Height); //untuk membuat obyek kotak dengan ukuran sebesar obyek Image1 yang ada dilayar
}
//———————————————————————
void __fastcall TForm1::Image1MouseDown(TObject *Sender, TMouseButton Button, TShiftState Shift, int X, int Y) // fungsi jika keadaan mouse ada diklik tapi dalam keadaan belum dilepaskan
{
tergambar=true; XC=X; YC=Y; // maka tergambar menjadi true dan keadaan variable menjadi yang diinginkan di sript
}
//———————————————————————
void __fastcall TForm1::Image1MouseUp(TObject *Sender, TMouseButton Button, TShiftState Shift, int X, int Y) // fungsi jika keadaan mouse dilepaskan setelah didrag
{
int R; //deklarasi variable R berrtipe integer
Button1Click(Sender); // perintah untuk membentuk lingkaran
tergambar=false;
QX=X; QY=Y;
R=int(sqrt(pow(XC-QX,2)+pow(YC-QY,2)));
if (RadioGroup1->ItemIndex==0)
{ CircleMidPoint(XC,YC,R); }
}
//———————————————————————
void __fastcall TForm1::CirclePlotpoint(int XC, int YC, int X, int Y)
{
Image1->Canvas->Pixels[XC+X][YC+Y]=clRed;
Image1->Canvas->Pixels[XC-X][YC+Y]=clRed;
Image1->Canvas->Pixels[XC+X][YC-Y]=clRed;
Image1->Canvas->Pixels[XC-X][YC-Y]=clRed;
Image1->Canvas->Pixels[XC+Y][YC+X]=clRed;
Image1->Canvas->Pixels[XC-Y][YC+X]=clRed;
Image1->Canvas->Pixels[XC+Y][YC-X]=clRed;
Image1->Canvas->Pixels[XC-Y][YC-X]=clRed; // perintah untuk membuat warna dari titik2 yang membentuk lingkaran dengan warna merah
}
//———————————————————————
void __fastcall TForm1::CircleMidPoint(int XC, int YC,int R)
{int x,y,p,k=0;
R=10;
x=0; y=R; p=1-R;
judul((float)x,(float)y,k,p);
do
{
k++;
if (p<0) { x=x+1; }
else
{ x=x+1; y=y-1; }
if (p<0) { p=p+2*x+1; }
else { p=p+2*(x-y)+1; }
CirclePlotpoint(XC,YC,x,y);
tampil((float)x,(float)y,k,p);
} while (x<y); // untuk melakukan perhitungan dari mid point dari linkaran yang terbentuk
}
//———————————————————————
void __fastcall TForm1::tampil(float x,float y, int k, int p)
{
{
char tampilX[20],tampilY[20],tampilK[20],tampilPk[20];
int i,xt=200, yt=15;
//Menampilkan bilangan asli tanpa pembulatan
_gcvt(x,7,tampilX);
_gcvt(y,7,tampilY);
_gcvt(p,7,tampilPk);
if (k==0) { for (i=0; i<20;i++) { tampilK[i]=”; } }
else { _gcvt(k-1,10,tampilK); }
k=k+2;
//Menampilkan koordinat X dan Y
Image1->Canvas->TextOut(xt-50, k*yt,tampilK);
Image1->Canvas->TextOut(xt+100, k*yt,”(“);
Image1->Canvas->TextOut(xt+120, k*yt,tampilX);
Image1->Canvas->TextOut(xt+150, k*yt,”,”);
Image1->Canvas->TextOut(xt+160, k*yt,tampilY);
Image1->Canvas->TextOut(xt+190, k*yt,”)”);
Image1->Canvas->TextOut(xt, k*yt,tampilPk);
}
}
//———————————————————————
void __fastcall TForm1::judul(float x,float y, int k, int p)
{
int xt=200, yt=15, kt=2;
Image1->Canvas->TextOut(xt-50,(kt-1)*yt,”k”);
Image1->Canvas->TextOut(xt, (kt-1)*yt,”pk”);
Image1->Canvas->TextOut(xt+100, (kt-1)*yt,”(x k+1,y k+1)”); // untuk membuat tulisan judul dari pehitungan mid point yang ditampilkan dilayar
}
//———————————————————————
Output :
Sumber :
Tidak ada komentar:
Posting Komentar