Tìm bao lồi của một tập điểm

Tìm bao lồi của tập hợp điểm: Đây là bài toán rất hay gặp. Hay còn gọi là bài toán "Gift Wrapping". Cho n điểm trên mặt phẳng tìm một hình đa giác lồi bao trùm các điểm đó. Ý tưởng để tìm khá đơn giản.

Step 1: Tìm một điểm chắc chắn thuộc đa giác lồi.
Step 2: Tìm các điểm tiếp theo sao cho gốc của nó và cạnh trước nó lớn nhất.
Step 3: Dừng lại khi điểm đầu điểm cuối trùng nhau.

step 1 chúng ta có thể tìm điểm ngoài cùng bên trái (tọa độ x nhỏ nhất) làm điểm khởi đầu.
step 2 thì chúng ta tính góc các cạnh và tìm được điểm tiếp theo. Với điểm thứ 2 thì chúng ta so với vector j (trục tung).

Mở rộng: Tìm chu vi hình chữ nhật nhỏ nhất chứa các điểm này? (Best Fit Rectangle)

Chúng ta cũng sẽ tìm bao lồi của tập hợp đỉnh và quy về bài toán tìm hình chữ nhật ngoại tiếp đa giác.
Để tìm hình chữ nhật một cách đơn giản thì ta giả sử một cạnh của đa giác cũng là cạnh của hình chữ nhật đó. Như hình bên dưới.


Khi đã có cạnh đáy thì ta chỉ cần tìm điểm cách xa cạnh đó nhất và lấy đó làm chiều cao của hình chữ nhật. Với hình đa giác n đỉnh thì ta cần thực hiện n*(n-2) phép tính để tìm ra hình chữ nhật đó.

Thường dùng trong các game va chạm, kiểm tra va chạm giữa 2 vật thể hoặc tìm chu vi sân nhỏ nhất.