Thuật toán Convex Hull (Graham Scan) là gì? Giải thích dễ hiểu kèm demo trực quan trên mặt phẳng 2D

Trong bài viết này, chúng ta sẽ:

• Hiểu Convex Hull là gì và trực giác hình học đằng sau.
• Nắm được ý tưởng của thuật toán Graham Scan.
• Biết Jarvis March là một cách tiếp cận khác cho Convex Hull.
• Xem demo trực quan: click tạo điểm trên mặt phẳng và để thuật toán vẽ hull bao ngoài bằng JavaScript.

Convex Hull là gì?

Cho một tập điểm trên mặt phẳng 2D, Convex Hull là đa giác lồi nhỏ nhất sao cho mọi điểm đều nằm bên trong hoặc trên biên của đa giác đó. Có thể hình dung:

• Đặt các đinh ghim lên bảng theo vị trí các điểm.
• Lấy một sợi dây cao su kéo căng bao quanh tất cả các đinh.
• Khi thả tay ra, dây cao su co lại ôm sát “vỏ ngoài” của các điểm.

Đường dây cao su đó chính là Convex Hull. Đa giác thu được luôn là đa giác lồi (mọi góc trong không vượt quá 180 độ).

Graham Scan: ý tưởng cơ bản

Thuật toán Graham Scan tìm Convex Hull bằng cách:

1. Chọn điểm gốc (pivot): thường là điểm có tung độ nhỏ nhất (y nhỏ nhất), nếu trùng thì chọn điểm có hoành độ nhỏ hơn (x nhỏ hơn).
2. Sắp xếp các điểm còn lại theo góc cực (polar angle) so với pivot, ví dụ từ trái sang phải (góc tăng dần).
3. Duyệt qua danh sách đã sắp xếp và dùng một stack để xây dựng hull:
   • Push lần lượt các điểm vào stack.
   • Mỗi khi thêm điểm mới, kiểm tra ba điểm “trước trước – trước – hiện tại” có tạo thành quẹo trái (left turn) hay không.
   • Nếu là “quẹo phải” hoặc thẳng hàng (không mong muốn cho hull lồi), pop điểm giữa ra khỏi stack và kiểm tra lại.
   • Tiếp tục cho đến khi đường đi luôn là “quẹo trái” quanh tập điểm.

Kết quả: stack cuối cùng chính là danh sách điểm của Convex Hull theo thứ tự ngược chiều kim đồng hồ.

Jarvis March (Gift Wrapping) là gì?

Jarvis March là một thuật toán khác để tìm Convex Hull, với trực giác:

• Bắt đầu từ điểm “ngoài cùng” (ví dụ điểm có x nhỏ nhất).
• Mỗi bước chọn điểm tiếp theo sao cho mọi điểm khác đều nằm về cùng một phía của đoạn thẳng nối hai điểm liên tiếp.
• “Quấn” dần quanh tập điểm như quấn quà, cho đến khi quay lại điểm ban đầu.

Độ phức tạp của Jarvis March là O(nh) với n là số điểm, h là số điểm nằm trên hull. Khi h nhỏ mà n lớn, thuật toán này có thể hiệu quả. Tuy nhiên, trong demo này, ta tập trung vào Graham Scan vì cách cài đặt và minh họa khá gọn.

Mô hình demo: vẽ Convex Hull cho các điểm 2D

Để trực quan, ta dùng một canvas nhỏ với các tính năng:

• Click chuột vào canvas để thêm điểm mới.
• Nút “Thêm điểm ngẫu nhiên” để sinh nhanh nhiều điểm.
• Nút “Xóa hết điểm” để làm lại từ đầu.
• Nút “Chạy Graham Scan”:
  • Tìm pivot.
  • Sắp xếp điểm theo góc.
  • Duyệt và tô đậm hull bao ngoài bằng đường nối các điểm.
• Khu vực log hiển thị các bước quan trọng (chọn pivot, sắp xếp, pop/push stack…).

Demo Convex Hull với Graham Scan bằng JavaScript

Giải thích ngắn gọn đoạn code Graham Scan

1. Biểu diễn điểm và vẽ trên canvas

Mỗi điểm được biểu diễn bằng một object đơn giản:

var points = []; // mỗi phần tử: { x: Number, y: Number }

Mỗi lần click vào canvas, ta lấy tọa độ chuột tương ứng, lưu vào mảng points rồi vẽ lại toàn bộ:

function drawPoints(ctx, pts) {
    ctx.clearRect(0, 0, width, height);
    // vẽ từng điểm nhỏ hình tròn
}

2. Hàm tính cross product để kiểm tra “quẹo trái”

Để biết ba điểm A, B, C có tạo thành “quẹo trái” hay “quẹo phải”, ta dùng tích có hướng (cross product) của hai vector AB và BC:

function cross(o, a, b) {
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

• Nếu cross > 0 → quẹo trái (left turn).
• Nếu cross < 0 → quẹo phải (right turn).
• Nếu cross = 0 → thẳng hàng.

3. Các bước chính của Graham Scan trong code

Quy trình triển khai Graham Scan trong đoạn code demo:

1. Tìm pivot: điểm có y nhỏ nhất (nếu trùng thì x nhỏ hơn).

   // tìm điểm đáy (pivot)
   var pivot = points[0];
   for (var i = 1; i < points.length; i++) {
       if (
           points[i].y < pivot.y ||
           (points[i].y === pivot.y && points[i].x < pivot.x)
       ) {
           pivot = points[i];
       }
   }

2. Sắp xếp các điểm khác theo góc cực so với pivot, có thể dùng Math.atan2 để tính góc:

   var sorted = points.slice().sort(function(a, b) {
       if (a === pivot) return -1;
       if (b === pivot) return 1;
       var angleA = Math.atan2(a.y - pivot.y, a.x - pivot.x);
       var angleB = Math.atan2(b.y - pivot.y, b.x - pivot.x);
       if (angleA === angleB) {
           var distA = (a.x - pivot.x)*(a.x - pivot.x) + (a.y - pivot.y)*(a.y - pivot.y);
           var distB = (b.x - pivot.x)*(b.x - pivot.x) + (b.y - pivot.y)*(b.y - pivot.y);
           return distA - distB;
       }
       return angleA - angleB;
   });

3. Duyệt và xây dựng hull bằng stack:

   var stack = [];
   for (var i = 0; i < sorted.length; i++) {
       var p = sorted[i];
       while (stack.length >= 2) {
           var q = stack[stack.length - 1];
           var r = stack[stack.length - 2];
           if (cross(r, q, p) <= 0) {
               // quẹo phải hoặc thẳng → loại bỏ q
               stack.pop();
           } else {
               break;
           }
       }
       stack.push(p);
   }
   // stack chính là Convex Hull theo thứ tự ngược chiều kim đồng hồ

4. Vẽ Convex Hull

Sau khi có danh sách các điểm trên hull trong stack, ta vẽ đa giác lồi bằng cách nối các điểm theo thứ tự và khép kín:

function drawHull(ctx, hull) {
    if (hull.length < 2) return;
    ctx.beginPath();
    ctx.moveTo(hull[0].x, hull[0].y);
    for (var i = 1; i < hull.length; i++) {
        ctx.lineTo(hull[i].x, hull[i].y);
    }
    ctx.closePath();
    ctx.stroke();
}

Trong demo, sau khi nhấn “Chạy Graham Scan”, code sẽ:

• Log lại quá trình chọn pivot, sắp xếp điểm.
• Duyệt từng điểm, pop/push stack khi phát hiện quẹo phải.
• Tô màu các điểm và vẽ đường bao hull bằng nét đậm.

Khi nào nên dùng Convex Hull (Graham Scan)?

• Khi cần tìm “biên ngoài” đơn giản cho một tập điểm: dữ liệu GPS, điểm trong biểu đồ, tọa độ trong UI.
• Khi cần bước tiền xử lý cho các thuật toán hình học khác (Delaunay, Voronoi, collision detection…).
• Khi muốn trực quan hóa hình dạng “bao ngoài” của một cụm dữ liệu trong 2D.

Từ demo JavaScript ở trên, bạn có thể mở rộng:

• Cho phép kéo thả điểm, xóa từng điểm bằng click phải.
• Thêm tùy chọn chạy Jarvis March để so sánh hành vi.
• Mở rộng lên 3D bằng các thuật toán Convex Hull trong không gian (như Quickhull).