Membuat Garis pada Komputer

Jumat, 29 Maret 2019

Sebuah garis pada dasarnya membutuhkan dua buah titik yang sudah diketahui lokasinya (titik pangkal dan titik ujung), yang kemudian dihubungkan dengan menghidupkan pixel diantara kedua titik tersebut. Pembuatan garis pada komputer biasanya dibantu dengan sebuah fungsi yang memiliki 4 argument sebagai: plotLine(x1,y1,x2,y2), dimana argument tersebut merupakan koordinat titik pangkal (x1,y1), dan koordinat titik ujung (x2,y2).
Ada beberapa cara yang dapat digunakan untuk penyelesaiannya, dan sebagai contoh untuk ketiganya menggunakan permasalahan berikut:

         x1 y1  x2 y2
plotLine( 2, 1,  8, 4 ).

Persamaan Garis Lurus

algoritma ini menggunakan rumus y = mx + c untuk penerapannya, dimana
m merupakan gradient (perbandingan selisih masing-masing x dan y)
c merupakan perpotongan garis terhadap sumbu y

cara menggunakan: plotLine(2,1,8,4)

1. cari nilai m.

        m =   dy   /  dx
        m = (y2-y1)/(x2-x1)
          = (4 - 1)/(8 - 2)
          =    3   /   6
          =       1/2      --> (0.5)
   

2. cari nilai c.

        y = mx + c
   
        c = y - mx         --> (gunakan x1 dan y1)
          = 1 - (1/2) * 2
          = 1 - 1
          = 0
   

3. Masukkan hasil yang telah diketahui pada rumus sebelumnya.

     y = mx + c
     y = 1/2(x) + 0
   

Contoh pengerjaan:

   |  x  |       y        | pembulatan |
   |     |                |     y      |
   |-----|----------------|------------|
   |  2  | 1/2(2)+0 = 1   |     1      |
   |  3  | 1/2(3)+0 = 1.5 |     2      |
   |  .  |       .        |     .      |
   |  .  |       .        |     .      |
   |  8  | 1/2(8)+0 = 4   |     4      |

DDA (Digital Differential Analyzer)

Algoritma ini bekerja atas dasar penambahan nilai x dan y. penambahan tersebut didapat dari perbandingan masing-masing selisih sumbu terhadap selisih terbesar kedua sumbu tersebut.

cara menggunakan: plotLine( 2, 1, 8, 4 )

1. cari selisih masing-masing sumbu

        dx = x2 - x1 = 8 - 2 = 6
        dy = y2 - y1 = 4 - 1 = 3
   

2. cari nilai terbesar kedua selisih diatas

        nBesar = 6    (karena 6 > 3)
   

3. bandingkan delta dengan nBesar sebagai penambah masing-masing sumbu

        xi = dx / nBesar = 6 / 6 = 1.0
        yi = dy / nBesar = 3 / 6 = 0.5
   

4. buat tabel perulangan,
   lihat parameter nBesar, didapat nilai X, sehingga perulangan dimulai dari 0 s.d. 6 dengan rumus :

        xk = xk + xi
        yk = yk + yi
   

Contoh pengerjaan:

     | k |      x      |        y         | pembulatan |
     |   |             |                  |     y      |
     |---|-------------|------------------|------------|
     | 0 |  2 + 1 = 3  | 1   + 0.5 = 1.5  |     2      |
     | 1 |  3 + 1 = 4  | 1.5 + 0.5 = 2    |     2      |
     | . |      .      |        .         |     .      |
     | . |      .      |        .         |     .      |
     | 5 |  7 + 1 = 8  | 3.5 + 0.5 = 4    |     4      |

* plotting dilakukan didalam perulangan setelah perhitungan dan pembulatan.

Bressenham

Algoritma ini memilih titik terdekat dari solusi pertama diatas, sehingga setiap sampling akan ditambahkan menjadi 1 atau 0.

cara menggunakan: plotLine( 2, 1, 8, 4 )

1. Masukkan dua endpoint, simpan endpoint kiri sebagai (x0,y0)
2. Plot titik pertama.
3. Hitung konstanta dx, dy, 2dy, dan 2(dy-dx) dan nilai awal parameter keputusan.

               dx = 8 - 2 = 6
               dy = 4 - 1 = 3
               
            (2dy) = 2*3
                  = 6
                  
        (2dy-2dx) = 2*3 - 2*6
                  =   6 - 12
                  = -6
       
               p0 = 2dy - dx
                  =   6 - 6
                  = 0
   

4. Masukkan kedalam tabel, pada setiap xk di garis, dimulai dari k = 0, periksa:

         pk < 0  lakukan:            (kondisi A)
                 - x = x + 1
                 - p = p + (2dy)
         pk >= 0 lakukan:            (kondisi B)
                 - x = x + 1
                 - y = y + 1
                 - p = p + (2dy-2dx)
   

5. Ulangi tahap 4 sebanyak dy kali.

Contoh pengerjaan:

     | k |  p               |           Sumbu           |  P lanjut  |
     |   |                  |      x      |      y      |            |
     |---|------------------|-------------|-------------|------------|
     |   |                  |      2      |      1      |     0      | > (langkah 2)
     | 0 |  0  (kondisi B)  | x = 2+1 = 3 | y = 1+1 = 2 |  0 + (-6)  | > (langkah 4 dan 5)
     | 1 | -6  (kondisi A)  | x = 3+1 = 4 |      2      | -6 + 6     | > (langkah 4 dan 5)
     | 2 |  0  (kondisi B)  | x = 4+1 = 5 | y = 2+1 = 3 |  0 + (-6)  | > (langkah 4 dan 5)
     | 3 | -6  (kondisi A)  | x = 5+1 = 6 |      3      | -6 + 6     | > (langkah 4 dan 5)
     | 4 |  0  (kondisi B)  | x = 6+1 = 7 | y = 3+1 = 4 |  0 + (-6)  | > (langkah 4 dan 5)
     | 5 | -6  (kondisi A)  | x = 7+1 = 8 |      4      | -6 + 6     | > (langkah 4)

Sumber: http://sumarna.staff.gunadarma.ac.id/Downloads/files/29157/4+Grafik+Komp-Geometri+Primitive.pdf