Hull Cembung

1. Introduction

Hull Konveks dari sebuah himpunan titik-titik P adalah poligon konveks terkecil CH(P) di mana tiap titik dalam P terletak antara di perbatasan dari CH(P) atau di dalamnya. Bayangkan titik-titik tersebut sebagai paku di sebuah bidang datar dan kita memiliki karet yang cukup panjang untuk mengelilingi keseluruh paku tersebut. Jika karet ini dilepas, maka karet tersebut akan mengelilingi paku-paku tersebut dengan luas sekecil mungkin. Luas tersebut adalah luas dari hull konveks dari titik-titik / paku-paku tersebut. Mencari hull konveks dari sekelompok titik memiliki banyak kegunaan dalam masalah pengepakan.

2. Graham's Scan

Di dalam visualisasi ini, kita sekarang hanya menyediakan algoritma Graham's Scan.

Kita memulai dengan memilih sebuah titik pivot (yakni titik paling bawah dan paling kiri) lalu mengurutkan N-1 titik lainnya dalam urutan berlawanan arah jarum jam terhadap titik pivot ini.

3. Pekerjaan Untuk Kedepannya

Visualisasi ini saat ini hanya digunakan sekali setahun di NUS (sekitar awal April tiap tahun untuk CS3233),, sehingga hanya diperbarui secara singkat sekali setahun.