Bao lồi - Phương pháp Graham - Loại bỏ phần trong


Như chúng ta đã biết, thường thì các thuật toán hình học thì khó phân tích hơn các thuật toán trong những lĩnh vực khác. Vì khó mô tả được đặc điểm của đầu vào (và đầu ra) hơn. Bài này, là một trong những thuật toán hình học rất hay mà không hề khó hiểu. Gramham là phương phám đáng chú ý vì hầu hết các tính toán dành cho việc sắp xếp: thuật toán có chứa một sắp xếp không tốn kém lắm. Thuật toán bắt đầu bằng việc xây dựng một đa giác đơn khép kín từ các điểm đã cho. Việc xây dựng này dùng một hàm: sắp các điểm theo khoá là giá trị của hàm theta (chúng ta sẽ xét cụ thể trong bài) tương ứng với góc giữa trục hoành và đường thẳng nối mỗi điểm chốt p[1] (điểm có tung độ nhỏ nhất), và khi lần theo p[1], p[2],…, p[N], p[1] ta sẽ được một đa giác khép kín.
Bao lồi được tìm bằng cách đi vòng: thử đặt một điểm vào bao và kiểm tra các điểm trước đấy có còn thuộc bao hay không. Ví dụ, ta xét các điểm theo thứ tự B M J L N P K F I E C O A H G D; ta có các bước đầu tiên được bắt đầu như sau:


Khi bắt đầu, ta biết B, M thuộc bao. Khi xét J, nó được đưa vào bao và tạo thành hình tam giác. Tiếp đó, khi xét đến L, ta nhận thấy rằng J không thể thuộc bao (vì J lọt trong tam giác BML).
Dễ dàng kiểm tra để loại một điểm khỏi bao. Sau khi thêm vào một điểm, ta sẽ lần quanh các điểm đã đưa vào bao và xét xem có loại điểm nào hay không. Khi lần quanh bao, ta chờ sự quẹo trái ở mỗi đỉnh của bao. Tại điểm mới thêm, nếu có quẹo phải, thì ta loại điểm này vì đa giác lồi đang có đã chứa trong điểm vừa thêm. Giả sử khi ta xét các điểm p[1…i-1], ta đã xác định được p[1…M] là bao. Khi xét điểm mới p[i], nếu ccw(p[M], p[M-1], p[i]) là không âm, ta loại p[M] ra khỏi bao. Nếu không , p[M] vẫn thuộc bao.


Hình trên cho thấy quá trình thực hiện cách xử lý này trên tập điểm. Mỗi điểm mới được xử lý như sau: điểm mới này được đưa vào bao và dùng làm ‘nhân chứng’ cho việc loại bỏ các điểm có sẵn trên bao. Sau khi L, N, P được thêm vào bao, P bị loại bỏ khi xét tới K (vì NPK là một quẹo phải), rồi F và I được thêm vào. Khi xét E, điểm I bị loại vì FIE là một quẹo phải; … Như vậy sẽ có nhiều hơn một điểm bị loại khi xét một điểm mới. Tiếp tục theo cách này, sau cùng thuật toán của chúng ta sẽ quay về điểm B.
Sự sắp xếp ban đầu đảm bảo mỗi điểm được xét lần lượt đều có khả năng thuộc bao, vì mọi điểm được xét trước đó có giá trị theta nhỏ hơn. Mỗi đường thẳng nối p[1] và p[i], tồn tại các phép loại trừ, có tính chất là một điểm được xét trước đó đều nằm về cùng một phía của đường thẳng này. Vì vậy khi xét tới điểm p[N] (cũng phải thuộc bao do thứ tự sắp xếp), ta đã tìm đủ các điểm trên bao.
Trong phương pháp bọc - gói ta đã xét ở số trước, các điểm trên cùng một cạnh của bao có thể được hoặc không được nhắc đến dù có tới 2 trường hợp đối với các điểm cộng tuyến. Trước tiên, nếu có 2 điểm cộng tuyến với p[1] thì việc sắp xếp dùng hàm theta có thể hoặc không thể lấy chúng theo thứ tự của chúng trên đường thẳng chung. Các điểm không đúng trật tự sẽ bị loại trong quá trình quét. Thứ hai, có thể xuất hiện các điểm cộng tuyến trên các bao thử nghiệm (tất nhiên không thể khử các điểm này)
Chúng ta sẽ cần chú ý một số chi tiết khi cài đặt thuật toán này dù rằng nó không có gì phức tạp. Ban đầu, điểm có giá trị x lớn nhất trong các điểm số điểm có y nhỏ nhất được đổi chỗ với p[1]. Sau đó shellsort được dùng để sắp lại các điểm (chúng ta có thể dùng bất kỳ cách sắp xếp nào cũng được), bằng cách dùng giá trị theta của các điểm này với p[1]. Sau khi sắp, p[N] được chép vào p[0] để làm biến cầm canh trong trường hợp p[3] không thuộc bao. Sau cùng, tiến hành việc quét như đã