Algoritma DDA, Bresenham, C++
TITIK DAN GARIS
Persamaan Garis
y = mx + b Persamaan garis menurut koordinat Cartesian adalahdimana m adalah slope/kemiringan garis yang dibentuk dari dua titik, yaitu (x1,y1) dan (x2,y2).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 3 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 integer.
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 = x1- x0 dan dy = y1 – y0
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=x1dan y=y1.
(Source code)
001 //—————————————————————————
002
003 #include <vcl.h>
004
005 #pragma hdrstop
006
007 #include “Unit1.h”
008
009 #include “math.h”
010
011 #include “stdlib.h”
012
013 //—————————————————————————
014
015 #pragma package(smart_init)
016
017 #pragma resource “*.dfm”
018
019 TForm1 *Form1;
020
021 int x1,x2,y1,y2;
022
023 int tergambar;
024
025 //—————————————————————————
026
027 __fastcall TForm1::TForm1(TComponent* Owner)
028
029 : TForm(Owner)
030
031 {
032
033 }
034
035 //—————————————————————————
036
037 void __fastcall TForm1::FormActivate(TObject *Sender)
038
039 {
040
041 Image1->Canvas->Rectangle(0,0,Image1->Width,Image1->Height);
042
043 }
044
045 //—————————————————————————
046
047 void __fastcall TForm1::Image1MouseDown(TObject *Sender,
048
049 TMouseButton Button, TShiftState Shift, int X, int Y)
050
051 {
052
053 tergambar=true;
054
055 x1=X;
056
057 y1=Y;
058
059 Edit1->Text=(IntToStr(X)+”,”+IntToStr(Y));
060
061 }
062
063 //—————————————————————————
064
065 void __fastcall TForm1::BARUClick(TObject *Sender)
066
067 {
068
069 tergambar=false;
070
071 Image1->Canvas->Rectangle(0,0,Image1->Width,Image1->Height);
072
073 ListBox1->Items->Clear();
074
075 }
076
077 //—————————————————————————
078
079 void __fastcall TForm1::CLOSEClick(TObject *Sender)
080
081 {
082
083 Close();
084
085 }
086
087 //—————————————————————————
088
089 void __fastcall TForm1::Image1MouseUp(TObject *Sender, TMouseButton Button,
090
091 TShiftState Shift, int X, int Y)
092
093 {
094
095 {
096
097 BARUClick(Sender);
098
099 tergambar=false;
100
101 x2=X;
102
103 y2=Y;
104
105 Edit2->Text=(IntToStr(X)+”,”+IntToStr(Y));
106
107 //ListBox1->Items->Add(IntToStr(X)+”,”+IntToStr(Y));
108
109 if(RadioGroup1->ItemIndex==0)
110
111 {DDA(x1,y1,x2,y2);}
112
113 }
114
115 }
116
117 //—————————————————————————
118
119 //—————————————————————————
120
121 void __fastcall TForm1::DDA(int xa,int ya,int xb,int yb)
122
123 { int dx, dy,step,k ;
124
125 float Xincrement,Yincrement,x,y;
126
127 xa=10;ya=10;xb=17;yb=16;
128
129 dx = xb-xa;
130
131 dy = yb-ya;
132
133 x=(float)xa;
134
135 y=(float)ya;
136
137 if (abs(dx)>abs(dy))
138
139 { step = (abs(dx));}
140
141 else
142
143 { step = (abs(dy)); };
144
145 Xincrement=(float)dx/step;
146
147 Yincrement=(float)dy/step;
148
149 Image1->Canvas->Pixels[int (x)][int (y)]=clBlack;
150
151 judul(x,y);
152
153 for (k=0;k<=step;k++)
154
155 {
156
157 x+=Xincrement;
158
159 y+=Yincrement;
160
161 Image1->Canvas->Pixels[int(x)][int(y)]=clBlack;
162
163 tampil(x,y,k);
164
165 }
166
167 }
168
169 //——————————————————–
170
171 void __fastcall TForm1::judul(float x,float y)
172
173 {
174
175 char tampilX[20], tampilY[20];
176
177 //int xt=200, yt=15, kt=2;
178
179 _gcvt(x,4,tampilX);
180
181 _gcvt(y,4,tampilY);
182
183 String a = “k x y (x bulat,y bulat)”;
184
185 ListBox1->Items->Add(a);
186
187 String b=tampilX;
188
189 String c=tampilY;
190
191 _gcvt(x,2,tampilX);
192
193 _gcvt(y,2,tampilY);
194
195 String d=tampilX;
196
197 String e=tampilY;
198
199 ListBox1->Items->Add(” “+b+” “+c+” “+d+” “+e);
200
201 }
202
203 //—————————————————————-
204
205 void __fastcall TForm1::tampil(float x, float y, int k)
206
207 {
208
209 char tampilX[20],tampilY[20],tampilK[20];
210
211 //int xt=200, yt=15;
212
213 k += 2;
214
215 _gcvt(x,4,tampilX);
216
217 _gcvt(y,4,tampilY);
218
219 String a=tampilX;
220
221 String b=tampilY;
222
223 _gcvt(x,2,tampilX);
224
225 _gcvt(y,2,tampilY);
226
227 _gcvt(k-3,10,tampilK);
228
229 String c=tampilK;
230
231 String d=tampilX;
232
233 String e=tampilY;
234
235 ListBox1->Items->Add(c+” “+a+” “+b+” “+d+” “+e);
236
237 }
(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 (x0,y0) dan titik lainnya sebagai titik akhir (x1,y1)
3. Hitung dx, dy, 2dx dan 2dy-2dx
4. Hitung parameter P0 = 2dy – dx
5. Untuk setiap xk sepanjang garis dimulai dengan k=0
§ Bila Pk < 0 maka titik selanjutnya adalah (xk+1, yk) dan Pk+1=Pk+2dy
§ Bila tidak maka titik selanjutnya adalah (xk+1, yk+1) dan Pk+1=Pk+2dy-2dx
6. Ulangi nomor 5 untuk menentukan posisi pixel selanjutnya sampai x=x1 dan y=y1
(Source code)
001 //—————————————————————————
002
003 #include <vcl.h>
004
005 #pragma hdrstop
006
007 #include “Unit1.h”
008
009 #include “math.h”
010
011 #include “stdlib.h”
012
013 //—————————————————————————
014
015 #pragma package(smart_init)
016
017 #pragma resource “*.dfm”
018
019 TForm1 *Form1;
020
021 int x1,x2,y1,y2;
022
023 int tergambar;
024
025 //—————————————————————————
026
027 __fastcall TForm1::TForm1(TComponent* Owner)
028
029 : TForm(Owner)
030
031 {
032
033 }
034
035 //—————————————————————————
036
037 void __fastcall TForm1::FormActivate(TObject *Sender)
038
039 {
040
041 Image1->Canvas->Rectangle(0,0,Image1->Width,Image1->Height);
042
043 }
044
045 //—————————————————————————
046
047 void __fastcall TForm1::Image1MouseDown(TObject *Sender,
048
049 TMouseButton Button, TShiftState Shift, int X, int Y)
050
051 {
052
053 tergambar=true;
054
055 x1=X;
056
057 y1=Y;
058
059 Edit1->Text=(IntToStr(X)+”,”+IntToStr(Y));
060
061 }
062
063 //—————————————————————————
064
065 void __fastcall TForm1::BARUClick(TObject *Sender)
066
067 {
068
069 tergambar=false;
070
071 Image1->Canvas->Rectangle(0,0,Image1->Width,Image1->Height);
072
073 ListBox1->Items->Clear();
074
075 }
076
077 //—————————————————————————
078
079 void __fastcall TForm1::CLOSEClick(TObject *Sender)
080
081 {
082
083 Close();
084
085 }
086
087 //—————————————————————————
088
089 void __fastcall TForm1::Image1MouseUp(TObject *Sender, TMouseButton Button,
090
091 TShiftState Shift, int X, int Y)
092
093 {
094
095 {
096
097 BARUClick(Sender);
098
099 tergambar=false;
100
101 x2=X;
102
103 y2=Y;
104
105 Edit2->Text=(IntToStr(X)+”,”+IntToStr(Y));
106
107 //ListBox1->Items->Add(IntToStr(X)+”,”+IntToStr(Y));
108
109 if(RadioGroup1->ItemIndex==0)
110
111 {Bressenham(x1,y1,x2,y2);}
112
113 }
114
115 }
116
117 //—————————————————————————
118
119 //—————————————————————————
120
121 void __fastcall TForm1::Bressenham(int xa, int ya, int xb, int yb)
122
123 {
124
125 int dx, dy, p, twoDy, twoDyDx, xEnd;
126
127 float x,y;
128
129 int k;
130
131 k=0;
132
133 dx=abs(xb-xa);
134
135 dy=abs(yb-ya);
136
137 p=2*dy-dx;
138
139 twoDy=2*dy;
140
141 twoDyDx=2*(dy-dx);
142
143 if(xa>xb)
144
145 {x=xb; y=yb; xEnd=xa;}
146
147 else
148
149 {x=xa; y=ya; xEnd=xb;}
150
151 Image1->Canvas->Pixels[int (x)][int (y)]=clBlack;
152
153 judul(x,y);
154
155 while(x<xEnd)
156
157 {x++; k++;
158
159 if(p<0)
160
161 {
162
163 p+=twoDy;
164
165 }
166
167 else
168
169 {
170
171 y++;
172
173 p+=twoDyDx;
174
175 }
176
177 Image1->Canvas->Pixels[int (x)][int (y)]=clBlack;
178
179 tampil(x,y,k);
180
181 }
182
183 }
184
185 //——————————————————–
186
187 void __fastcall TForm1::judul(float x,float y)
188
189 {
190
191 char tampilX[20], tampilY[20];
192
193 //int xt=200, yt=15, kt=2;
194
195 _gcvt(x,4,tampilX);
196
197 _gcvt(y,4,tampilY);
198
199 String a = “k x y (x bulat,y bulat)”;
200
201 ListBox1->Items->Add(a);
202
203 String b=tampilX;
204
205 String c=tampilY;
206
207 _gcvt(x,2,tampilX);
208
209 _gcvt(y,2,tampilY);
210
211 String d=tampilX;
212
213 String e=tampilY;
214
215 ListBox1->Items->Add(” “+b+” “+c+” “+d+” “+e);
216
217 }
218
219 //—————————————————————-
220
221 void __fastcall TForm1::tampil(float x, float y, int k)
222
223 {
224
225 char tampilX[20],tampilY[20],tampilK[20];
226
227 //int xt=200, yt=15;
228
229 k += 2;
230
231 _gcvt(x,4,tampilX);
232
233 _gcvt(y,4,tampilY);
234
235 String a=tampilX;
236
237 String b=tampilY;
238
239 _gcvt(x,2,tampilX);
240
241 _gcvt(y,2,tampilY);
242
243 _gcvt(k-3,10,tampilK);
244
245 String c=tampilK;
246
247 String d=tampilX;
248
249 String e=tampilY;
250
251 ListBox1->Items->Add(c+” “+a+” “+b+” “+d+” “+e);
252
253 }
(tampilan output)
ALORITMA GARIS C++
Algoritma garis C++ adalah pembentukan garis dengan memanfaatkan fungsi yang disediakan oleh C++. Dalam C++, fungsi yang digunakan untuk pembentukan garis dengan menggunakan pasangan fungsi MoveTo dan LineTo. MoveTo digunakan untuk mengubah posisi gambar dari X ke Y. LineTo digunakan untuk menggambar garis pada canvas dengan pen dimana garis dimulai dari titik X menuju Y.
(Source code)
001 //—————————————————————————
002
003 #include <vcl.h>
004
005 #pragma hdrstop
006
007 #include “Unit1.h”
008
009 //—————————————————————————
010
011 #pragma package(smart_init)
012
013 #pragma resource “*.dfm”
014
015 TForm1 *Form1;
016
017 int X1,X2,Y1,Y2;
018
019 int tergambar;
020
021 //—————————————————————————
022
023 __fastcall TForm1::TForm1(TComponent* Owner)
024
025 : TForm(Owner)
026
027 {
028
029 }
030
031 void __fastcall TForm1::FormActivate(TObject *Sender)
032
033 {
034
035 Image1->Canvas->Rectangle(0,0,Image1->Width,Image1->Height);
036
037 }
038
039 //—————————————————————————
040
041 void __fastcall TForm1::Button2Click(TObject *Sender)
042
043 {
044
045 Close();
046
047 }
048
049 //—————————————————————————
050
051 void __fastcall TForm1::Button1Click(TObject *Sender)
052
053 {
054
055 tergambar=false;
056
057 Image1->Canvas->Rectangle(0,0,Image1->Width,Image1
058
059 ->Height);
060
061 }
062
063 //—————————————————————————
064
065 //—————————————————————————
066
067 void __fastcall TForm1::FormMouseDown(TObject *Sender, TMouseButton Button,
068
069 TShiftState Shift, int X, int Y)
070
071 {
072
073 tergambar=true; X1=X; Y1=Y;
074
075 }
076
077 //—————————————————————————
078
079 void __fastcall TForm1::Image1MouseUp(TObject *Sender, TMouseButton Button,
080
081 TShiftState Shift, int X, int Y)
082
083 {
084
085 {
086
087 Button1Click(Sender);
088
089 tergambar=false;
090
091 X2=X; Y2=Y;
092
093 if (RadioGroup1->ItemIndex==0)
094
095 {
096
097 Image1->Canvas->MoveTo(X1,Y1);
098
099 Image1->Canvas->LineTo(X2,Y2);
100
101 }
102
103 };
104
105 }
106
107 //—————————————————————————
Fikir Program 