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

In this visualization, we currently only support Graham's Scan algorithm.

We first pick a pivot point (bottom-most, left-most point) and then sort the other N-1 points in counter-clockwise order w.r.t. this pivot point.

3. Future Works

This visualization is currently only used once a year in NUS (around early April each year, for CS3233), hence it only gets updated briefly once a year.