Algoritma DDA, Algoritma Bresenham,

                Persamaan Garis

            y = mx + b       Persamaan garis menurut koordinat Cartesian adalahdimana m adalah slope/kemiringan garis yang dibentuk dari dua titik, yaitu (x₁,y₁) dan (x₂,y₂).Untuk penambahan x sepanjang garis yaitu dx akan mendapatkan penambahan y sebesar : dy = m . dx

          Atribut

            Atribut dasar untuk garis lurus adalah type (tipe), width (tebal) dan color (warna). Dalam beberapa paket aplikasi grafik, garis ditampilkan dengan menggunakan pilihan pen atau brush . Berikut ini dibicarakan bagaimanafungsi garis dapat mengakomodasi bermacam-macam spesifikasi atribut.

            Tipe Garis

            Garis mempunyai beberapa linetype (tipe garis) diantaranya solid line (garis tebal), dashed line (garis putus), dan dotted line (garis titik-titik).Algoritma pembentukan garis dilengkapi dengan pengaturan panjang dan jarak yang menampilkan bagian solid sepanjang garis.

·  Garis putus dibuat dengan memberikan nilai jarak dengan bagian solid yang sama.

·  Garis titik–titik dapat ditampilkan dengan memberikan jarak yang lebih besar dari bagain solid.

·  Prosedur yang serupa digunakan pula untuk membuat bermacam-macam tipe garis. Untuk mengatur atribut dalam program aplikasi PHIGS menggunakan fungsi: setLinetype (lt)

Di mana parameter it menunjukkan integer positif dengan nilai 1,2,3,4 untuk membuat garis solid, dashed, dotted atau dotted dash. nilai lain untuk parametergaris dapat digunakan untuk menampilkan berbagai macam pola dot dashed. Ketika parameter linetype diatur dalam aplikasi PHIGS, perintah line drawing membuat garis dengan tipe garis tersebut.

            Algoritma Pembentukan Garis

Algoritma pembentukan garis menggunakan 2 algoritma :
            ALGORITMA GARIS DDA

            Digital Diferensial Analyser (DDA) adalah algoritma pembentukan garis berdasarkan perhitungan dx maupun dy, menggunakan rumus dy = m . dx. Garis dibuat menggunakan dua endpoint, yaitu titik awal dan titik akhir. Setiap koordinat titik yang membentuk garis diperoleh dari perhitungan, kemudian dikonversikan menjadi nilai iteger.

Langkah-langkah membentuk garis menurut algoritma DDA adalah :

1.     Tentukan dua titik yang akan dihubungkan dalam pembentukan garis

2.     Tentukan titik awal yaitu dan titik akhir .

3.     Hitung dx = x₁- x₀ dan dy = y₁ – y₀

4.     Tentukan step = max( |dx| , |dy| )

5.     Hitung penambahan koordinat pixel XInc = dx / step dan YInc = dy / step

6.     Koordinat selanjutnya (x+XInc, y+yInc)

7.     Posisi pada layar ditentukan dengan pembulatan nilai koordinat tersebut

8.     Ulangi nomor 6 dan 7 untuk menentukan posisi pixel berikutnya. sampai x=x₁dan y=y₁.

(Source code)

	//—————————————————————————    #include <vcl.h>    #pragma hdrstop    #include “Unit1.h”    #include “math.h”    #include “stdlib.h”    //—————————————————————————    #pragma package(smart_init)    #pragma resource “*.dfm”    TForm1 *Form1;    int x1,x2,y1,y2;    int tergambar;    //—————————————————————————    __fastcall TForm1::TForm1(TComponent* Owner)    : TForm(Owner)    {    }    //—————————————————————————    void __fastcall TForm1::FormActivate(TObject *Sender)    {    Image1->Canvas->Rectangle(0,0,Image1->Width,Image1->Height);    }    //—————————————————————————    void __fastcall TForm1::Image1MouseDown(TObject *Sender,    TMouseButton Button, TShiftState Shift, int X, int Y)    {    tergambar=true;    x1=X;    y1=Y;    Edit1->Text=(IntToStr(X)+”,”+IntToStr(Y));    }    //—————————————————————————    void __fastcall TForm1::BARUClick(TObject *Sender)    {    tergambar=false;    Image1->Canvas->Rectangle(0,0,Image1->Width,Image1->Height);    ListBox1->Items->Clear();    }    //—————————————————————————    void __fastcall TForm1::CLOSEClick(TObject *Sender)    {    Close();    }    //—————————————————————————    void __fastcall TForm1::Image1MouseUp(TObject *Sender, TMouseButton Button, TShiftState Shift, int X, int Y)    { {    BARUClick(Sender);    tergambar=false;    x2=X;    y2=Y;    Edit2->Text=(IntToStr(X)+”,”+IntToStr(Y));    //ListBox1->Items->Add(IntToStr(X)+”,”+IntToStr(Y));   if(RadioGroup1->ItemIndex==0)    {DDA(x1,y1,x2,y2);} }    }    //—————————————————————————    //—————————————————————————    void __fastcall TForm1::DDA(int xa,int ya,int xb,int yb)    { int dx, dy,step,k ;    float Xincrement,Yincrement,x,y;    xa=10;ya=10;xb=17;yb=16;    dx = xb-xa;    dy = yb-ya;    x=(float)xa;    y=(float)ya;    if (abs(dx)>abs(dy))    { step = (abs(dx));}    else    { step = (abs(dy)); };    Xincrement=(float)dx/step;    Yincrement=(float)dy/step;    Image1->Canvas->Pixels[int (x)][int (y)]=clBlack;    judul(x,y);    for (k=0;k<=step;k++)    {    x+=Xincrement;    y+=Yincrement;    Image1->Canvas->Pixels[int(x)][int(y)]=clBlack;    tampil(x,y,k);    }    }    //——————————————————–    void __fastcall TForm1::judul(float x,float y)    {    char tampilX[20], tampilY[20];    //int xt=200, yt=15, kt=2;    _gcvt(x,4,tampilX);    _gcvt(y,4,tampilY);    String a = “k x y (x bulat,y bulat)”;    ListBox1->Items->Add(a);    String b=tampilX;    String c=tampilY;    _gcvt(x,2,tampilX);    _gcvt(y,2,tampilY);    String d=tampilX;    String e=tampilY;    ListBox1->Items->Add(” “+b+” “+c+” “+d+” “+e);    }    //—————————————————————-    void __fastcall TForm1::tampil(float x, float y, int k)    {    char tampilX[20],tampilY[20],tampilK[20];    //int xt=200, yt=15;    k += 2;    _gcvt(x,4,tampilX);    _gcvt(y,4,tampilY);    String a=tampilX;    String b=tampilY;    _gcvt(x,2,tampilX);    _gcvt(y,2,tampilY);    _gcvt(k-3,10,tampilK);    String c=tampilK;    String d=tampilX;    String e=tampilY;    ListBox1->Items->Add(c+” “+a+” “+b+” “+d+” “+e); }
	(output program)

                ALGORITMA GARIS BRESSENHAM

                Prosedur untuk menggambar kembali garis dengan membulatkan nilai x atau y ke bilangan integer memerlukan waktu. serta variabel x,y maupun m memerlukan bilangan real karena kemiringan merupakan nilai pecahan.Bressenham mengembangkan algoritma klasik yang lebih menarik, karena hanya menggunakan perhitungan matematik dengan bantuan bilangan integer. Dengan demikian tidak perlu membulatkan nilai posisi pixel setiap waktu. Langkah-langkahnya adalah sebagai berikut:

1.     Tentukan dua titik yang akan dihubungkan dalam pembentukan garis.

2.     Tentukan salah satu titik disebelah kiri sebagai titik awal (x_0,y₀) dan titik lainnya sebagai titik akhir (x_1,y₁)

3.     Hitung dx, dy, 2dx dan 2dy-2dx

4.     Hitung parameter P₀ = 2dy – dx

5.     Untuk setiap x_k sepanjang garis dimulai dengan k=0

§  Bila P_k < 0 maka titik selanjutnya adalah (x_k+1, y_k) dan P_k+1=P_k+2dy

§  Bila tidak maka titik selanjutnya adalah (x_k+1, y_k+1) dan P_k+1=P_k+2dy-2dx

6.     Ulangi nomor 5 untuk menentukan posisi pixel selanjutnya sampai x=x₁ dan y=y₁

(Source code)

//—————————————————————————    #include <vcl.h>    #pragma hdrstop    #include “Unit1.h”    #include “math.h”    #include “stdlib.h”    //—————————————————————————    #pragma package(smart_init)    #pragma resource “*.dfm”    TForm1 *Form1;    int x1,x2,y1,y2;    int tergambar;    //—————————————————————————    __fastcall TForm1::TForm1(TComponent* Owner)    : TForm(Owner)    {    }    //—————————————————————————    void __fastcall TForm1::FormActivate(TObject *Sender)    {    Image1->Canvas->Rectangle(0,0,Image1->Width,Image1->Height);    }    //—————————————————————————    void __fastcall TForm1::Image1MouseDown(TObject *Sender,    TMouseButton Button, TShiftState Shift, int X, int Y)    {    tergambar=true;    x1=X;    y1=Y;    Edit1->Text=(IntToStr(X)+”,”+IntToStr(Y));    }    //—————————————————————————    void __fastcall TForm1::BARUClick(TObject *Sender)    {    tergambar=false;    Image1->Canvas->Rectangle(0,0,Image1->Width,Image1->Height);    ListBox1->Items->Clear();    }    //—————————————————————————    void __fastcall TForm1::CLOSEClick(TObject *Sender)    {    Close();    }    //—————————————————————————    void __fastcall TForm1::Image1MouseUp(TObject *Sender, TMouseButton Button,    TShiftState Shift, int X, int Y)    {    {    BARUClick(Sender);    tergambar=false;    x2=X;    y2=Y;    Edit2->Text=(IntToStr(X)+”,”+IntToStr(Y));    //ListBox1->Items->Add(IntToStr(X)+”,”+IntToStr(Y));    if(RadioGroup1->ItemIndex==0)    {Bressenham(x1,y1,x2,y2);}    }    }    //—————————————————————————    //—————————————————————————    void __fastcall TForm1::Bressenham(int xa, int ya, int xb, int yb)    {    int dx, dy, p, twoDy, twoDyDx, xEnd;    float x,y;    int k;    k=0;    dx=abs(xb-xa);    dy=abs(yb-ya);    p=2*dy-dx;    twoDy=2*dy;    twoDyDx=2*(dy-dx);    if(xa>xb)    {x=xb; y=yb; xEnd=xa;}    else    {x=xa; y=ya; xEnd=xb;}    Image1->Canvas->Pixels[int (x)][int (y)]=clBlack;    judul(x,y);    while(x<xEnd)    {x++; k++;    if(p<0)    {    p+=twoDy;    }    else    {    y++;    p+=twoDyDx;    }    Image1->Canvas->Pixels[int (x)][int (y)]=clBlack;    tampil(x,y,k);    }    }    //——————————————————–    void __fastcall TForm1::judul(float x,float y)    {    char tampilX[20], tampilY[20];    //int xt=200, yt=15, kt=2;    _gcvt(x,4,tampilX);    _gcvt(y,4,tampilY);    String a = “k x y (x bulat,y bulat)”;    ListBox1->Items->Add(a);    String b=tampilX;    String c=tampilY;    _gcvt(x,2,tampilX);    _gcvt(y,2,tampilY);    String d=tampilX;    String e=tampilY;    ListBox1->Items->Add(” “+b+” “+c+” “+d+” “+e);    }    //—————————————————————-    void __fastcall TForm1::tampil(float x, float y, int k)    {    char tampilX[20],tampilY[20],tampilK[20];    //int xt=200, yt=15;    k += 2;    _gcvt(x,4,tampilX);    _gcvt(y,4,tampilY);   String a=tampilX;    String b=tampilY;    _gcvt(x,2,tampilX);    _gcvt(y,2,tampilY);    _gcvt(k-3,10,tampilK);    String c=tampilK;    String d=tampilX;    String e=tampilY;    ListBox1->Items->Add(c+” “+a+” “+b+” “+d+” “+e);    }

(tampilan output)