Convex Hull — Bao Lồi Và Sức Mạnh Của Cross Product

Trong game engine, kiểm tra va chạm giữa hai vật thể phức tạp (mesh hàng nghìn polygon) tốn rất nhiều CPU. Giải pháp: bọc mỗi vật thể bằng bao lồi — đa giác lồi nhỏ nhất chứa toàn bộ vật thể. Kiểm tra va chạm giữa hai đa giác lồi nhanh hơn 100 lần so với mesh gốc, và trong phần lớn trường hợp, kết quả đủ chính xác.

Convex Hull còn là nền tảng cho rất nhiều bài toán khác: tính bounding box tối ưu, xác định vùng bao phủ trong GIS, tách đối tượng trong computer vision, và là bước tiền xử lý cho Delaunay Triangulation, Voronoi Diagram. Nắm vững Convex Hull đồng nghĩa với việc mở khóa toàn bộ nhánh hình học tính toán.

Và công cụ cốt lõi để giải bài toán này? Chỉ một phép toán duy nhất: Cross Product 2D — phép toán cho biết 3 điểm tạo thành rẽ trái, rẽ phải, hay thẳng hàng.

Bức tranh tư duy

Hình dung bạn có một tấm gỗ đóng nhiều đinh — mỗi cây đinh là một điểm trong tập dữ liệu. Lấy một sợi dây thun, căng rộng bao quanh tất cả đinh, rồi thả tay.

Sợi dây thun co lại, ôm sát các cây đinh ngoài cùng — đó chính là Convex Hull.

     •        •                  *--------*
    / \      /                  /          \
   •   •    •           →      *            *
    \      /                    \          /
     •----•                      *--------*
   [Tất cả điểm]              [Convex Hull]

Tính chất lồi: Bất kỳ đoạn thẳng nào nối hai điểm trong bao lồi đều nằm hoàn toàn bên trong. Không có "chỗ lõm" — đó là lý do gọi là "convex".

Cross Product — Thước đo hướng rẽ: Cho 3 điểm O, A, B theo thứ tự, cross product cho biết khi đi từ O đến A rồi đến B, ta đang rẽ trái (counter-clockwise), rẽ phải (clockwise), hay đi thẳng.

     B                    B
    /                      \
   / ← Rẽ trái (cp > 0)    \ ← Rẽ phải (cp < 0)
  O ----→ A            O ----→ A

$$\text{cross}(O,A,B)=(A_x-O_x)(B_y-O_y)-(A_y-O_y)(B_x-O_x)$$

Cốt lõi kỹ thuật

Cross Product 2D

Đây là công cụ nền tảng cho mọi thuật toán hình học 2D. Với tọa độ nguyên, kết quả luôn chính xác — không có floating point error.

C++

struct Point {
    long long x, y;
};

long long cross(const Point& O, const Point& A, const Point& B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
// > 0: rẽ trái (CCW), < 0: rẽ phải (CW), = 0: thẳng hàng

Python

def cross(o: tuple[int, int], a: tuple[int, int], b: tuple[int, int]) -> int:
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
# > 0: rẽ trái (CCW), < 0: rẽ phải (CW), = 0: thẳng hàng

Java

static long cross(long[] O, long[] A, long[] B) {
    return (A[0] - O[0]) * (B[1] - O[1]) - (A[1] - O[1]) * (B[0] - O[0]);
}

Go

func cross(o, a, b [2]int64) int64 {
    return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])
}

Ba thuật toán Convex Hull

Thuật toán	Complexity	Ưu điểm	Nhược điểm
Jarvis March	O(n·h)	Đơn giản, dễ hiểu	Chậm khi h lớn
Graham Scan	O(n log n)	Nhanh, kinh điển	Sort theo polar angle (dễ lỗi float)
Andrew's Monotone Chain	O(n log n)	Ổn định, sort theo x,y	—

Trong đó h = số điểm trên hull. Monotone Chain được khuyến nghị cho production vì không cần tính góc cực (polar angle) — chỉ sort theo tọa độ, tránh hoàn toàn floating point issues.

Andrew's Monotone Chain

Ý tưởng: Chia hull thành lower hull (đi phía dưới từ trái sang phải) và upper hull (đi phía trên từ phải sang trái). Mỗi nửa xây bằng stack: thêm point mới, pop nếu tạo góc lõm (rẽ phải).

C++

#include <vector>
#include <algorithm>

using Point = std::pair<long long, long long>;

long long cross(const Point& O, const Point& A, const Point& B) {
    return (A.first-O.first)*(B.second-O.second)
         - (A.second-O.second)*(B.first-O.first);
}

std::vector<Point> convex_hull(std::vector<Point> pts) {
    int n = pts.size();
    if (n < 3) return pts;
    std::sort(pts.begin(), pts.end());
    pts.erase(std::unique(pts.begin(), pts.end()), pts.end());
    n = pts.size();
    if (n < 3) return pts;

    // Lower hull
    std::vector<Point> lower;
    for (auto& p : pts) {
        while (lower.size() >= 2
            && cross(lower[lower.size()-2], lower[lower.size()-1], p) <= 0)
            lower.pop_back();
        lower.push_back(p);
    }

    // Upper hull
    std::vector<Point> upper;
    for (int i = n - 1; i >= 0; --i) {
        while (upper.size() >= 2
            && cross(upper[upper.size()-2], upper[upper.size()-1], pts[i]) <= 0)
            upper.pop_back();
        upper.push_back(pts[i]);
    }

    lower.pop_back();
    upper.pop_back();
    lower.insert(lower.end(), upper.begin(), upper.end());
    return lower;
}

Python

def convex_hull(points: list[tuple[int, int]]) -> list[tuple[int, int]]:
    points = sorted(set(points))
    if len(points) <= 2:
        return points

    def cross(o, a, b):
        return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])

    # Lower hull: trái → phải
    lower = []
    for p in points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)

    # Upper hull: phải → trái
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)

    return lower[:-1] + upper[:-1]

Java

import java.util.*;

public class ConvexHull {
    static long cross(long[] O, long[] A, long[] B) {
        return (A[0]-O[0])*(B[1]-O[1]) - (A[1]-O[1])*(B[0]-O[0]);
    }

    public static List<long[]> convexHull(List<long[]> points) {
        points = new ArrayList<>(new TreeSet<>(points,
            Comparator.<long[]>comparingLong(p -> p[0]).thenComparingLong(p -> p[1])));
        int n = points.size();
        if (n < 3) return points;

        // Lower hull
        Deque<long[]> lower = new ArrayDeque<>();
        for (long[] p : points) {
            while (lower.size() >= 2) {
                long[] a = ((ArrayDeque<long[]>) lower).pollLast();
                long[] b = lower.peekLast();
                if (cross(b, a, p) > 0) { lower.addLast(a); break; }
            }
            lower.addLast(p);
        }

        // Upper hull
        Deque<long[]> upper = new ArrayDeque<>();
        for (int i = n - 1; i >= 0; i--) {
            long[] p = points.get(i);
            while (upper.size() >= 2) {
                long[] a = ((ArrayDeque<long[]>) upper).pollLast();
                long[] b = upper.peekLast();
                if (cross(b, a, p) > 0) { upper.addLast(a); break; }
            }
            upper.addLast(p);
        }

        List<long[]> hull = new ArrayList<>(lower);
        hull.remove(hull.size() - 1);
        Iterator<long[]> it = upper.iterator();
        while (it.hasNext()) {
            long[] p = it.next();
            if (!it.hasNext()) break; // skip last (= first of lower)
            hull.add(p);
        }
        return hull;
    }
}

Go

package geometry

import "sort"

type Point struct{ X, Y int64 }

func Cross(o, a, b Point) int64 {
    return (a.X-o.X)*(b.Y-o.Y) - (a.Y-o.Y)*(b.X-o.X)
}

func ConvexHull(pts []Point) []Point {
    sort.Slice(pts, func(i, j int) bool {
        if pts[i].X != pts[j].X { return pts[i].X < pts[j].X }
        return pts[i].Y < pts[j].Y
    })
    // Deduplicate
    j := 0
    for i, p := range pts {
        if i == 0 || p != pts[i-1] { pts[j] = p; j++ }
    }
    pts = pts[:j]
    if len(pts) < 3 { return pts }

    // Lower hull
    var lower []Point
    for _, p := range pts {
        for len(lower) >= 2 && Cross(lower[len(lower)-2], lower[len(lower)-1], p) <= 0 {
            lower = lower[:len(lower)-1]
        }
        lower = append(lower, p)
    }

    // Upper hull
    var upper []Point
    for i := len(pts) - 1; i >= 0; i-- {
        for len(upper) >= 2 && Cross(upper[len(upper)-2], upper[len(upper)-1], pts[i]) <= 0 {
            upper = upper[:len(upper)-1]
        }
        upper = append(upper, pts[i])
    }

    return append(lower[:len(lower)-1], upper[:len(upper)-1]...)
}

Graham Scan (Tham khảo)

Graham Scan sort theo polar angle từ điểm có y nhỏ nhất, rồi xây hull bằng stack:

import math

def graham_scan(points: list[tuple[int, int]]) -> list[tuple[int, int]]:
    # Tìm điểm anchor (y nhỏ nhất, nếu bằng thì x nhỏ nhất)
    anchor = min(points, key=lambda p: (p[1], p[0]))

    def polar_angle(p):
        return math.atan2(p[1] - anchor[1], p[0] - anchor[0])

    def cross(o, a, b):
        return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])

    sorted_pts = sorted(points, key=lambda p: (polar_angle(p),
        (p[0]-anchor[0])**2 + (p[1]-anchor[1])**2))

    stack = [sorted_pts[0], sorted_pts[1]]
    for p in sorted_pts[2:]:
        while len(stack) >= 2 and cross(stack[-2], stack[-1], p) <= 0:
            stack.pop()
        stack.append(p)
    return stack

Nhược điểm: atan2 dùng floating point → có thể sai khi points gần collinear. Monotone Chain tránh hoàn toàn vấn đề này.

Jarvis March (Gift Wrapping)

Trực giác nhất nhưng chậm nhất:

def jarvis_march(points: list[tuple[int, int]]) -> list[tuple[int, int]]:
    def cross(o, a, b):
        return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])

    n = len(points)
    start = min(range(n), key=lambda i: (points[i][0], points[i][1]))
    hull = []
    current = start

    while True:
        hull.append(points[current])
        candidate = 0
        for i in range(n):
            if i == current:
                continue
            cp = cross(points[current], points[candidate], points[i])
            if candidate == current or cp > 0:
                candidate = i
        current = candidate
        if current == start:
            break
    return hull

Complexity: O(n·h) — với h = số điểm trên hull. Tốt khi h nhỏ (ít điểm trên boundary).

Thực chiến

Tình huống: Collision Detection Optimization

Bối cảnh: Game 2D có 500 entities, mỗi entity là polygon phức tạp (20-50 vertices). Cần kiểm tra va chạm mỗi frame.

Mục tiêu: Giảm chi phí collision check từ O(V₁×V₂) xuống O(H₁×H₂) với H << V.

Python

class CollisionOptimizer:
    def __init__(self, vertices: list[tuple[int, int]]) -> None:
        self.hull = convex_hull(vertices)
        self._precompute_normals()

    def _precompute_normals(self) -> None:
        self.normals = []
        n = len(self.hull)
        for i in range(n):
            x1, y1 = self.hull[i]
            x2, y2 = self.hull[(i + 1) % n]
            # Normal vuông góc với cạnh
            self.normals.append((-(y2 - y1), x2 - x1))

    def broad_phase_collides(self, other: "CollisionOptimizer") -> bool:
        '''SAT (Separating Axis Theorem) trên convex hulls.'''
        for normal in self.normals + other.normals:
            min1, max1 = self._project(normal)
            min2, max2 = other._project(normal)
            if max1 < min2 or max2 < min1:
                return False  # Separating axis found
        return True

    def _project(self, axis: tuple[int, int]) -> tuple[int, int]:
        projections = [p[0]*axis[0] + p[1]*axis[1] for p in self.hull]
        return min(projections), max(projections)

C++

class CollisionOptimizer {
    std::vector<Point> hull_;
    std::vector<Point> normals_;

public:
    CollisionOptimizer(const std::vector<Point>& vertices) {
        hull_ = convex_hull(vertices);
        for (size_t i = 0; i < hull_.size(); ++i) {
            auto& a = hull_[i];
            auto& b = hull_[(i+1) % hull_.size()];
            normals_.push_back({-(b.second-a.second), b.first-a.first});
        }
    }

    bool collides(const CollisionOptimizer& other) const {
        auto all_normals = normals_;
        all_normals.insert(all_normals.end(),
            other.normals_.begin(), other.normals_.end());
        for (auto& axis : all_normals) {
            auto [min1, max1] = project(axis);
            auto [min2, max2] = other.project(axis);
            if (max1 < min2 || max2 < min1) return false;
        }
        return true;
    }
};

Phân tích:

• Polygon 50 vertices → Hull thường 8-15 vertices
• SAT check: O(H₁ + H₂) projections thay vì O(V₁ × V₂) = 2500 checks
• Hull chỉ cần tính một lần (nếu shape không đổi)

Tình huống: Image ROI Extraction

Bối cảnh: Hệ thống computer vision phát hiện nhiều feature points trên ảnh. Cần xác định vùng bao phủ (Region of Interest) để crop.

def extract_roi(feature_points: list[tuple[int, int]],
                padding: int = 20) -> tuple[int, int, int, int]:
    hull = convex_hull(feature_points)

    # Bounding box của convex hull
    min_x = min(p[0] for p in hull) - padding
    min_y = min(p[1] for p in hull) - padding
    max_x = max(p[0] for p in hull) + padding
    max_y = max(p[1] for p in hull) + padding

    return (min_x, min_y, max_x, max_y)  # ROI coordinates

Sai lầm điển hình

❌ Sai lầm 1: Floating point trong Cross Product

Vấn đề: Dùng float cho tọa độ khi input là số nguyên.

# SAI: Float gây sai số
def cross(o, a, b):
    return (float(a[0])-o[0])*(float(b[1])-o[1]) - (float(a[1])-o[1])*(float(b[0])-o[0])
# Khi points gần collinear: cross ≈ 0.00000001 — rẽ trái hay thẳng hàng?

Tại sao sai: Floating point error có thể biến 3 điểm thẳng hàng thành rẽ trái hoặc rẽ phải → hull sai.

# ĐÚNG: Giữ nguyên integer nếu input là nguyên
def cross(o, a, b):
    return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])
# Với int input, kết quả luôn chính xác tuyệt đối

❌ Sai lầm 2: Quên xử lý collinear points

Vấn đề: Cross product = 0 nhưng không xử lý đúng.

# SAI: <= 0 loại bỏ collinear points (có thể cần giữ)
while len(hull) >= 2 and cross(hull[-2], hull[-1], p) <= 0:
    hull.pop()

Tại sao sai: <= 0 loại bỏ cả collinear points (thẳng hàng). Trong một số bài toán, cần giữ tất cả points trên boundary.

# ĐÚNG (loại collinear — standard): dùng <= 0
# ĐÚNG (giữ collinear): dùng < 0
while len(hull) >= 2 and cross(hull[-2], hull[-1], p) < 0:
    hull.pop()  # Chỉ pop khi rẽ phải, giữ thẳng hàng

❌ Sai lầm 3: Không sort trước khi chạy Monotone Chain

Vấn đề: Quên sort hoặc sort sai criteria.

# SAI: Không sort → kết quả sai hoàn toàn
hull = monotone_chain(unsorted_points)

# SAI: Sort theo y trước → Monotone Chain yêu cầu sort theo x trước
points.sort(key=lambda p: (p[1], p[0]))

Tại sao sai: Monotone Chain dựa trên invariant "points đã sort theo x, tie-break bằng y". Vi phạm invariant này → hull không đúng.

# ĐÚNG: Sort theo x trước, y sau
points.sort(key=lambda p: (p[0], p[1]))

❌ Sai lầm 4: Integer overflow trong Cross Product

Vấn đề: Tọa độ lớn gây overflow khi nhân.

// SAI: int overflow khi x, y lên đến 10^9
int cross(Point O, Point A, Point B) {
    return (A.x-O.x)*(B.y-O.y) - (A.y-O.y)*(B.x-O.x);
    // (10^9) * (10^9) = 10^18 → vượt int (2×10^9)
}

Tại sao sai: int chỉ chứa ~2×10⁹. Cross product có thể lên đến 4×10¹⁸.

// ĐÚNG: Dùng long long
long long cross(Point O, Point A, Point B) {
    return (long long)(A.x-O.x)*(B.y-O.y)
         - (long long)(A.y-O.y)*(B.x-O.x);
}

Under the Hood

Hiệu năng

Thuật toán	Time	Space	Ghi chú
Monotone Chain	O(n log n)	O(n)	Bottleneck ở sort
Graham Scan	O(n log n)	O(n)	Float issues với polar angle
Jarvis March	O(n·h)	O(h)	Tốt khi h << n

Nội bộ triển khai

Sort dominance: Cả Monotone Chain và Graham Scan đều O(n log n), nhưng bottleneck là sort — phần xây hull chỉ O(n). Nếu data đã sort sẵn, hull construction là O(n).

Output-sensitive: Jarvis March O(n·h) — với h points trên hull. Nếu h = O(log n) (phổ biến với random data), Jarvis nhanh hơn. Nhưng worst case h = n → O(n²).

Stack operations: Mỗi point được push đúng 1 lần và pop tối đa 1 lần → phần xây hull là amortized O(n), bất kể bao nhiêu lần pop trong inner while loop.

Trade-offs

Khi NÊN dùng Monotone Chain	Khi NÊN dùng Jarvis
Không biết trước h (số điểm trên hull)	h rất nhỏ so với n
Cần worst-case O(n log n) guarantee	Online algorithm (thêm point từng cái)
Tọa độ nguyên (tránh float)	Cần output-sensitive performance
Production code (ổn định, dễ debug)	Competitive programming

Checklist ghi nhớ

✅ Checklist triển khai

Cross Product

• [ ] Dùng long long (C++) hoặc int tự nhiên (Python) để tránh overflow
• [ ] > 0 = rẽ trái (CCW), < 0 = rẽ phải (CW), = 0 = thẳng hàng
• [ ] Với float input: dùng EPSILON comparison

Monotone Chain

• [ ] Sort theo (x, y) tăng dần trước khi xây hull
• [ ] Deduplicate points trùng nhau
• [ ] <= 0 để loại collinear points (standard), < 0 để giữ
• [ ] Nối lower[:-1] + upper[:-1] (bỏ điểm cuối mỗi nửa)

Production

• [ ] Xử lý edge cases: < 3 points, tất cả collinear, tất cả trùng nhau
• [ ] Chọn integer coordinate khi có thể — zero floating point error
• [ ] Precompute hull cho static shapes (collision detection)
• [ ] SAT (Separating Axis Theorem) cho convex polygon collision

Bài tập luyện tập

Bài 1: Cross Product orientation — Foundation

Đề bài: Cho 3 điểm A(1,1), B(4,4), C(2,3). Xác định orientation (rẽ trái/phải/thẳng hàng) bằng tay và bằng code.

🧠 Quiz

Câu hỏi: Cross product của A(1,1), B(4,4), C(2,3) có giá trị?

• [ ] A. 0 (thẳng hàng)
• [ ] B. 6 (rẽ trái)
• [x] C. -3 (rẽ phải)
• [ ] D. 3 (rẽ trái) Giải thích: cross = (4-1)×(3-1) - (4-1)×(2-1) = 3×2 - 3×1 = 6 - 3... Đợi đã, hãy tính lại: cross = (Bx-Ax)(Cy-Ay) - (By-Ay)(Cx-Ax) = (4-1)(3-1) - (4-1)(2-1) = 3×2 - 3×1 = 6-3 = 3. Vậy đáp án D mới đúng — rẽ trái.

✅ Lời giải

def cross(o, a, b):
    return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])

A, B, C = (1,1), (4,4), (2,3)
cp = cross(A, B, C)
print(f"Cross product = {cp}")  # = (4-1)*(3-1) - (4-1)*(2-1) = 6-3 = 3
# cp > 0 → Rẽ trái (Counter-clockwise)

Phân tích: cp = 3 > 0 → đi từ A đến B đến C ta rẽ trái.

Bài 2: Convex Hull construction — Intermediate

Đề bài: Cho tập điểm [(0,0), (1,0), (2,0), (2,2), (1,3), (0,2), (1,1)]. Tìm Convex Hull bằng Monotone Chain. Xác định điểm nào nằm bên trong hull.

🧠 Quiz

Câu hỏi: Điểm nào KHÔNG nằm trên Convex Hull?

• [ ] A. (0,0)
• [x] B. (1,1)
• [ ] C. (2,2)
• [ ] D. (1,3) Giải thích: (1,1) nằm bên trong hull. Các điểm (0,0), (2,0), (2,2), (1,3), (0,2) tạo thành boundary của Convex Hull.

✅ Lời giải

points = [(0,0), (1,0), (2,0), (2,2), (1,3), (0,2), (1,1)]
hull = convex_hull(points)
print(f"Hull: {hull}")
# Hull: [(0,0), (2,0), (2,2), (1,3), (0,2)]

interior = [p for p in points if p not in hull]
print(f"Interior points: {interior}")
# Interior: [(1,0), (1,1)] — (1,0) nằm trên cạnh, (1,1) nằm bên trong

Phân tích: Monotone Chain với <= 0 loại cả collinear points, nên (1,0) — nằm trên cạnh giữa (0,0) và (2,0) — cũng bị loại.

Bài 3: Diện tích Convex Hull — Advanced

Đề bài: Tính diện tích Convex Hull bằng công thức Shoelace. Triển khai hàm nhận list of points (đã là hull, counter-clockwise) và trả về diện tích.

💡 Gợi ý

• Công thức Shoelace: Area = |Σᵢ (xᵢ × yᵢ₊₁ - xᵢ₊₁ × yᵢ)| / 2
• Với polygon counter-clockwise, tổng luôn dương

✅ Lời giải

def polygon_area(hull: list[tuple[int, int]]) -> float:
    n = len(hull)
    area = 0
    for i in range(n):
        j = (i + 1) % n
        area += hull[i][0] * hull[j][1]
        area -= hull[j][0] * hull[i][1]
    return abs(area) / 2.0

hull = [(0,0), (2,0), (2,2), (1,3), (0,2)]
print(f"Area = {polygon_area(hull)}")  # = 7.0

Phân tích: Shoelace formula chạy O(h) — chỉ cần duyệt qua các điểm trên hull. Kết hợp convex_hull + shoelace = O(n log n + h).

Liên kết học tiếp

📚 Bài liên quan

Bài liên quan trong Penalgo

• ← Hình Học Tính Toán Overview — Tổng quan module hình học
• Quadtree — Spatial indexing cho nearest-neighbor
• Sorting — Nền tảng cho Monotone Chain (O(n log n) bottleneck)
• Scale & Approximation — Cấu trúc dữ liệu xác suất

Từ khóa glossary: Convex Hull, bao lồi, Cross Product, tích có hướng, Andrew's Monotone Chain, Graham Scan, Jarvis March, Gift Wrapping, SAT, Separating Axis Theorem

Tìm kiếm liên quan: convex hull là gì, bao lồi, thuật toán hình học, cross product 2D, collision detection, computational geometry