TUGAS GRAFIKA KOMPUTER

Analisis dan Penerapan Algoritma Divide and Conquer Dalam
Penyelesaian Masalah Convex Hulls

Permasalahan convex hull adalah sebuah permasalahan yang memiliki aplikasi terapan yang cukup banyak, seperti pada permasalahan grafika komputer, otomasi desain, pengenalan pola (pattern recognition), dan penelitian operasi. Banyak sekali terdapat algoritma untuk menyelesaikan permasalahan convex hull ini, misalnya saja dengan pendekatan brute force, algoritma gift wrapping, algoritma Graham’s Scan, dengan metode Divide and Conquer, dll. Tiap algoritma memiliki kompleksitas yang berbeda-beda, hal ini tentu saja
sangat bergantung pada metode atau pendekatan apa yang digunakan pada algoritma tersebut. Misalkan saja Brute Force O(n^4), Gift Wrapping O(nh), Gra - ham Scan O(n log n), Jarvis March O(nh), QuickHull O(nh), Divide-and-Conquer O(n log n), Monotone Chain O(n log n), Incremental O(n log n) Pada makalah ini, penulis akan mencoba membahas penyelesaian permasalahan convex hull ini dengan metode divide and conquer, dan khususnya untuk convex hull 2-D. Pada permasalahan convex hull ini, algoritma divide and conquer mempunyai kompleksitas waktu yang cukup kecil, yaitu hanya O(nlog n), dan selain itu juga algoritma ini memiliki beberapa kelebihan dan dapat digeneralisasi untuk permasalahan convex hull yang melibatkan dimensi lebih dari tiga.

Permasalahan dalam pencarian convex hull, dalam praktiknya, diaplikasikan dalam permasalahan grafika komputer, otomasi desain, pengenalan pola (pattern recognition), penelitian operasi, pemrosesan gambar,
statistik, dll. Convex hull ini juga merupakan sebuah alat untuk membangun blok untuk sejumlah algoritma
komputasi geometrik. Sebagai contoh, permasalahan dalam pencarian diameter dari himpunan titik-titik, yang
merupakan pasangan titik-titik dengan jarak yang maksimum. Solusi dari diameternya selalu merupakan jarak antara dua buah titik dalam convex hull. Pada permasalahan convex hull, kita diberikan himpunan titik P. Kita ingin menghitung suatu convex hull dari P. Secara formal, convex hull adalah himpunan convex yang mengandung P. Atau convex hull dapat didefinisikan juga sebagai convex poligon terbesar yang titik-titiknya merupakan keseluruhan titik-titik pada P. Setiap vertex dari convex hull dinamakan dengan extreme point, dan keluarannya berupa list-of-extreme points.

INSTANSIASI MASALAH

Secara sederhana, pemasalahan convex hull ini adalah diberikan sebuah himpunan titik-titik dalam sebuah
bidang, lalu temukan convex hull dari titik-tititk ini dengan keluaran dapat berupa list-of-verteks. Atau lebih
formalnya: Input: Himpunan S = (p1, p2, ..., pn) dimana p1,p2,...,pn merupakan titik-titik pada bidang koordinat kartesius. Output: Convex Hull CH(S) dari n titik-titik diatas.

- Misalkan Pmax dan Pmin adalah dua buah titik pada himpunan S yang masing-masing merupakan titik 

  maksimum dan titik minimum berdasarkan koordinat absis-X.
- Lalu Pmax dan Pmin merupakan verteks dari convex hull
- Lalu, jika Pmax dan Pmin dihubungkan, akan terdapat garis yang akan membagi convex hull menjadi dua  

  bagian, yaitu upper hull dan lower hull.
- Garis L disebut dengan tangen dari convex poligon P jika semua verteks dari P berada pada sisis yang sama
  dari L.

PEMECAHAN MASALAH

- Pertama-tama lakukan pengurutan terhadap titik-titik dari himpunan S yang diberika berdasarkan koordinat
   absis-X, dengan kompleksitas waktu O(n log n).

- Jika |S| ≤ 3, maka lakukan pencarian convex hull secara brute-force dengan kompleksitas waktu O(1).  

  (Basis)
- Jika tidak, partisi himpunan titik-titik pada S menjadi 2 buah himpunan A dan B, dimana A terdiri dari  

  setengah jumlah dari |S| dan titik dengan koordinat absix-X yang terendah dan B terdiri dari setengah dari  

  jumlah |S| dan titik dengan koordinat absis-X terbesar.
- Secara rekursif lakukan penghitungan terhadap HA = conv(A) dan HB = conv(B).
- Lakukan penggabungan (merge) terhadap kedua hull tersebut menjadi convex hull, H, dengan menghitung   

  dan mencari upper dan lower tangents untuk HA dan HB dengan mengabaikan semua titik yang berada  

  diantara dua buah tangen ini.

Berikut ini adalah pseudo-code yang penulis buat sendiri  untuk algoritmanya:

procedure D_and_C_CH (input P [1..n] : array
of Point, Output L : List of Point)
{ Menyelesaikan masalah convex hull dengan
algoritma D-and-C.
Masukan: masukan array of point yang
berukuran n
Keluaran: solusi dari masalah
}
Deklarasi
r : integer
la : list of point
Algoritma
L = {}
if n ≤ 30 then {ukuran masalah sudah cukup
kecil }
SOLVE upa-masalah dengan metode bruteforce
else
Bagi menjadi r upa-masalah, masingmasing
berukuran n/k
Ha = P[1..n/2]
HB = P[n/2+1..n]
C_and_D_CH(Ha)
C_and_D_CH(HB)
{gabungkan solusi dari r upa-masalah
menjadi solusi masalah semula }
H = prosedur gabung Ha dan Hb dengan
mencari lower tangen dan upper tangen
La = listPoint(H)
L = L ∪ la
endif

LowerTangen(HA, HB):
1) Misalkan a merupakan titik terkanan dari HA
2)Misalkan b merupakan titik terkanan dari HB
3)While (ab bukan merupakan lower tangen dari HA
   dan HB)do
- While(ab bukan merupakan lower tangen dari
   HA) do a -> a.predesesor
- While(ab bukan merupakan lower tangen dari
   HA) do b-> b.suksesor
4)Return ab
Untuk lebih jelasnya, jika dibuatkan pseudo-codenya akan menjadi:

function LowerTangent (input HA, HB : list of
point): list of point
{mencari lower tangen dari Ha dan Hb, untuk
mencari lower tangen, analogi}
Algoritma
a = rightmost point dari Ha
b = leftmost point dari Hb
while ab bukan lower tangen dar ha dan Hb do
while ab bukan lower tangen dari Ha do
a.pred()
while ab bukan lower tangen dari Ha do
b.succ()
return ab

KESIMPULAN
Permasalahan convex hull adalah sebuah permasalahan yang memiliki aplikasi terapan yang cukup banyak,
seperti pada permasalahan grafika komputer, otomasi desain, pengenalan pola (pattern recognition), dan penelitian operasi.