Mari Cuba Lukis          Contoh dan Penyelesaian       Soalan dan Penyelesaian (Input Pengguna)

Persampelan dilakukan pada setiap unit bagi menentukan piksel yang paling hampir dengan laluan bulatan.  

Pertimbangkan dulu satu bulatan yang berpusat di asalan.  Pada sempadan bulatan di oktan pertama (bahagian di antara x = 0 hingga x = y), kecerunan garis tangen pada setiap titik di sempadan berubah dari 0 hingga –1.  Memandangkan | m | < 1, persampelan dilakukan pada setiap unit x dan nilai y yang sempadan ditentukan.  

Bagi bulatan dengan jejari r dan berpusat di ( x_c, y_c ), pengiraan akan dillakukan berdasarkan bulatan dengan jejari yang sama tetapi berpusat di asalan.  Piksel yang akan diplotkan didapati dengan menambahkan nilai ( x_c, y_c ) kepada nilai yang didapati berdasarkan bulatan yang berpusat di asalan, iaitu :

Memandangkan persampelan dilakukan pada unit x dalam oktan pertama, nilai x akan sentiasa bertambah sebanyak 1 unit.  Katakan piksel semasa adalah (x_k, y_k), piksel berikutnya yang akan diplotkan adalah sama ada (x_k + 1, y_k) atau (x_k + 1, y_k – 1) seperti yang ditunjukkan di dalam rajah 3.5.

Rajah 3.5 : Titik tengah di antara 2 piksel yang terlibat pada kedudukan persampelan semasa dalam algoritma bulatan titik tengah.

Titik tengah di antara 2 piksel yang menjadi ‘calon’ untuk diplot seterusnya akan diuji sama ada : ia berada di dalam atau di luar sempadan bulatan.  Fungsi yang digunakan :

                            f ( x, y ) = x² + y² – r²

Gantikan sebarang titik ( x, y ) :

Pemalar penentu digunakan diwakili pk, yang menguji titik tengah di antara 2 titik yang terlibat.  (Titik tengah tersebut iaitu ( x_k + 1, y_k - ½ ))

Berdasarkan nilai yang diperolehi :

Algoritma bulatan titik tengah adalah seperti berikut :

1. Input nilai jejari, r, serta pusat bulatan ( x_c, y_c ).  Tetapkan titik pertama di atas lilitan bulatan yang berpusat di asalan sebagai ( 0, r ).

2. Kira nilai awal pemalar penentu sebagai :

                       p₀  =  5/4  -  r

3. Pada setiap x_k, bermula pada k = 0, uji nilai pemalar penentu :

   Jika p_k < 0, titik seterusnya adalah ( x_{k + 1}, y_k ) dan

          p_k+1 = p_k + 2x_k+1 + 1,

   Jika p_k > 0, titik seterusnya adalah (x_k+1, y_k-1) dan

           p_k+1 = p_k + 2x _k+1 + 1 – 2y_k+1

    

4. Tentukan titik-titik simetri pada 7 oktan yang lain.

5. Dapatkan kordinat sebenar titik yang akan diplotkan bagi bulatan berpusat di (x_c, y_c) iaitu (x + x_c, y + y_c)

6. Ulang langkah 3 hingga 5 sehingga x > y.

Carta Alir Algoritma Bulatan Titik Tengah (Midpoint Circle Algorithm) :