Algoritma Pembuatan Garis

Sebuah garis menghubungkan dua titik. Ini adalah elemen dasar dalam grafik. Untuk menggambar garis, Anda membutuhkan dua titik di mana Anda dapat menggambar garis. Dalam tiga algoritme berikut, kami merujuk satu titik baris sebagai $ X_ {0}, Y_ {0} $ dan titik kedua baris sebagai $ X_ {1}, Y_ {1} $.

Algoritma DDA

Algoritma Digital Differential Analyzer (DDA) adalah algoritma pembuatan garis sederhana yang dijelaskan selangkah demi selangkah di sini.

Step 1 - Dapatkan masukan dari dua titik akhir $ (X_ {0}, Y_ {0}) $ dan $ (X_ {1}, Y_ {1}) $.

Step 2 - Hitung perbedaan antara dua titik akhir.

dx = X₁ - X₀
dy = Y₁ - Y₀

Step 3- Berdasarkan perbedaan yang dihitung pada langkah-2, Anda perlu mengidentifikasi jumlah langkah untuk meletakkan piksel. Jika dx> dy, maka Anda membutuhkan lebih banyak langkah dalam koordinat x; jika tidak dalam koordinat y.

if (absolute(dx) > absolute(dy))
   Steps = absolute(dx);
else
   Steps = absolute(dy);

Step 4 - Hitung kenaikan dalam koordinat x dan koordinat y.

Xincrement = dx / (float) steps;
Yincrement = dy / (float) steps;

Step 5 - Letakkan piksel dengan berhasil menaikkan koordinat x dan y sesuai dan menyelesaikan gambar garis.

for(int v=0; v < Steps; v++)
{
   x = x + Xincrement;
   y = y + Yincrement;
   putpixel(Round(x), Round(y));
}

Generasi Garis Bresenham

Algoritme Bresenham adalah algoritme konversi pemindaian tambahan lainnya. Keuntungan besar dari algoritma ini adalah, ia hanya menggunakan kalkulasi integer. Bergerak melintasi sumbu x dalam interval satuan dan pada setiap langkah pilih di antara dua koordinat y yang berbeda.

Misalnya, seperti yang ditunjukkan pada ilustrasi berikut, dari posisi (2, 3) Anda perlu memilih antara (3, 3) dan (3, 4). Anda ingin titik yang lebih dekat ke garis aslinya.

Pada contoh posisi $ X_ {k} + 1, $ pemisah vertikal dari garis matematika diberi label sebagai $ d_ {upper} $ dan $ d_ {lower} $.

Dari ilustrasi di atas, koordinat y pada garis matematika pada $ x_ {k} + 1 $ adalah -

Y = m ($ X_ {k} $ + 1) + b

Jadi, $ d_ {upper} $ dan $ d_ {lower} $ diberikan sebagai berikut -

$$ d_ {lebih rendah} = y-y_ {k} $$

$$ = m (X_ {k} + 1) + b - Y_ {k} $$

dan

$$ d_ {atas} = (y_ {k} + 1) - y $$

$ = Y_ {k} + 1 - m (X_ {k} + 1) - b $

Anda dapat menggunakan ini untuk membuat keputusan sederhana tentang piksel mana yang lebih dekat dengan garis matematika. Keputusan sederhana ini didasarkan pada perbedaan antara dua posisi piksel.

$$ d_ {bawah} - d_ {atas} = 2m (x_ {k} + 1) - 2y_ {k} + 2b - 1 $$

Mari kita gantikan m dengan dy / dx di mana dx dan dy adalah perbedaan antara titik-titik akhir.

$$ dx (d_ {bawah} - d_ {atas}) = dx (2 \ frac {\ mathrm {d} y} {\ mathrm {d} x} (x_ {k} + 1) - 2y_ {k} + 2b - 1) $$

$$ = 2dy.x_ {k} - 2dx.y_ {k} + 2dy + 2dx (2b-1) $$

$$ = 2dy.x_ {k} - 2dx.y_ {k} + C $$

Jadi, parameter keputusan $ P_ {k} $ untuk langkah k sepanjang garis diberikan oleh -

$$ p_ {k} = dx (d_ {lower} - d_ {upper}) $$

$$ = 2dy.x_ {k} - 2dx.y_ {k} + C $$

Tanda parameter keputusan $ P_ {k} $ sama dengan tanda $ d_ {lower} - d_ {upper} $.

Jika $ p_ {k} $ negatif, pilih piksel yang lebih rendah, jika tidak pilih piksel atas.

Ingat, perubahan koordinat terjadi di sepanjang sumbu x dalam satuan langkah, jadi Anda dapat melakukan semuanya dengan penghitungan bilangan bulat. Pada langkah k + 1, parameter keputusan diberikan sebagai -

$$ p_ {k +1} = 2dy.x_ {k + 1} - 2dx.y_ {k + 1} + C $$

Mengurangi $ p_ {k} $ dari ini kita dapatkan -

$$ p_ {k + 1} - p_ {k} = 2dy (x_ {k + 1} - x_ {k}) - 2dx (y_ {k + 1} - y_ {k}) $$

Tapi, $ x_ {k + 1} $ sama dengan $ (xk) + 1 $. Jadi -

$$ p_ {k + 1} = p_ {k} + 2dy - 2dx (y_ {k + 1} - y_ {k}) $$

Dimana, $ Y_ {k + 1} - Y_ {k} $ bisa 0 atau 1 tergantung pada tanda $ P_ {k} $.

Parameter keputusan pertama $ p_ {0} $ dievaluasi pada $ (x_ {0}, y_ {0}) $ diberikan sebagai -

$$ p_ {0} = 2dy - dx $$

Sekarang, perhatikan semua poin dan perhitungan di atas, berikut adalah algoritma Bresenham untuk kemiringan m <1 -

Step 1 - Masukkan dua titik akhir baris, simpan titik akhir kiri dalam $ (x_ {0}, y_ {0}) $.

Step 2 - Plotkan titik $ (x_ {0}, y_ {0}) $.

Step 3 - Hitung konstanta dx, dy, 2dy, dan (2dy - 2dx) dan dapatkan nilai pertama untuk parameter keputusan sebagai -

$$ p_ {0} = 2dy - dx $$

Step 4 - Pada setiap $ X_ {k} $ di sepanjang garis, mulai dari k = 0, lakukan tes berikut -

Jika $ p_ {k} $ <0, titik plot berikutnya adalah $ (x_ {k} +1, y_ {k}) $ dan

$$ p_ {k + 1} = p_ {k} + 2dy $$ Jika tidak,

$$ (x_ {k}, y_ {k} +1) $$

$$ p_ {k + 1} = p_ {k} + 2dy - 2dx $$

Step 5 - Ulangi langkah 4 (dx - 1) kali.

Untuk m> 1, cari tahu apakah Anda perlu menaikkan x sambil menaikkan y setiap kali.

Setelah diselesaikan, persamaan untuk parameter keputusan $ P_ {k} $ akan sangat mirip, hanya x dan y dalam persamaan yang dipertukarkan.

Algoritma Titik Tengah

Algoritma titik tengah adalah karena Bresenham yang dimodifikasi oleh Pitteway dan Van Aken. Asumsikan Anda telah meletakkan titik P pada koordinat (x, y) dan kemiringan garisnya adalah 0 ≤ k ≤ 1 seperti pada ilustrasi berikut.

Sekarang Anda perlu memutuskan apakah akan meletakkan titik berikutnya di E atau N. Ini dapat dipilih dengan mengidentifikasi titik perpotongan Q yang paling dekat dengan titik N atau E. Jika titik perpotongan Q paling dekat dengan titik N maka N dianggap sebagai poin selanjutnya; jika tidak E.

Untuk menentukannya, pertama-tama hitung titik tengah M (x + 1, y + ½). Jika titik potong Q dari garis dengan garis vertikal yang menghubungkan E dan N berada di bawah M, maka ambil E sebagai titik berikutnya; jika tidak, ambil N sebagai poin berikutnya.

Untuk memeriksa ini, kita perlu mempertimbangkan persamaan implisit -

F (x, y) = mx + b - y

Untuk m positif pada X tertentu,

Jika y ada di garis, maka F (x, y) = 0
Jika y berada di atas garis, maka F (x, y) <0
Jika y berada di bawah garis, maka F (x, y)> 0