Wiki › Thuật toán › Hình học tính toán › Point in Polygon (Điểm trong đa giác)

Point in Polygon (Điểm trong đa giác)

huunguyen Updated Tháng sáu 2, 2026

Cho một điểm $P = (p_{x}, p_{y})$ và một đa giác $Q$ gồm $N$ đỉnh, ta cần xác định $P$ nằm trong, ngoài, hay trên biên đa giác. Đây là một bài toán nền tảng của hình học tính toán, xuất hiện khi kiểm tra va chạm, đếm điểm trong vùng, hay xử lý bao lồi. Với đa giác bất kỳ ta giải được trong $O (N)$ bằng Ray Casting (bắn tia) hoặc Winding Number (số vòng quấn); nếu đa giác lồi và đã sắp đỉnh, ta hạ xuống $O (\log N)$ nhờ tìm kiếm nhị phân — quan trọng khi phải kiểm tra cùng một đa giác với rất nhiều truy vấn điểm.

Ý tưởng / Trực giác

Ray Casting (chẵn–lẻ)

Tưởng tượng bạn đứng tại $P$ và bắn một tia thẳng ra vô cực (thường chọn hướng ngang sang phải). Mỗi lần tia cắt qua một cạnh của đa giác, bạn bước qua một lần từ "trong" sang "ngoài" hoặc ngược lại. Vì điểm ở vô cực chắc chắn nằm ngoài, nên:

Nếu tia cắt biên một số lẻ lần → $P$ nằm trong (xuất phát từ trong, đi qua lẻ lần ranh giới mới ra tới ngoài).
Nếu chẵn lần → $P$ nằm ngoài.

Tính chất này không phụ thuộc đa giác lồi hay lõm, miễn là đa giác đơn (các cạnh không tự cắt). Khó khăn duy nhất là các trường hợp suy biến: tia đi đúng qua một đỉnh, hoặc tia trùng một cạnh ngang. Mẹo chuẩn để khử là dùng quy ước nửa mở: chỉ đếm cạnh khi một đầu mút nằm "dưới chặt" còn đầu kia nằm "trên hoặc bằng" tung độ $p_{y}$ — như vậy mỗi đỉnh được tính đúng một lần, không lặp.

Winding Number (số vòng quấn)

Thay vì đếm chẵn–lẻ, ta cộng dồn góc có dấu mà các cạnh quét quanh $P$ . Đi hết một vòng đa giác, tổng góc chia $2 π$ cho ra số nguyên gọi là winding number $w n$ : số lần biên quấn quanh $P$ . Nếu $w n \neq 0$ → $P$ nằm trong. Cách này mạnh hơn ray casting vì đúng cả với đa giác tự cắt và phân biệt được hướng quấn. Trong cài đặt số nguyên, ta không tính góc thật mà chỉ dựa vào dấu của tích có hướng (cross product) để biết cạnh đang quay sang trái hay phải khi vượt qua tung độ $p_{y}$ .

Tích có hướng — viên gạch nền

Cả hai phương pháp đều dựa trên tích có hướng. Với ba điểm $O, A, B$ :

$cross (O, A, B) = (A_{x} - O_{x}) (B_{y} - O_{y}) - (A_{y} - O_{y}) (B_{x} - O_{x})$

Dấu của nó cho biết $B$ nằm bên trái ( $> 0$ ), bên phải ( $< 0$ ) hay thẳng hàng ( $= 0$ ) so với tia $O \to A$ . Đây cũng là hai lần diện tích có dấu của tam giác $O A B$ . Toàn bộ bài toán điểm-trong-đa-giác quy về việc xét dấu này cho từng cạnh.

Ví dụ chạy tay

Xét đa giác (ngược chiều kim đồng hồ) và điểm $P = (2, 2)$ :

   y
 4 |        B(4,4)
 3 |       /     \
 2 |   P* /       \           <- bắn tia ngang sang phải từ P=(2,2)
 1 |     /         \
 0 |  A(1,1)------C(5,1)
   +----------------------- x
      1   2   3   4   5

Các cạnh: $A (1, 1) \to B (4, 4)$ , $B (4, 4) \to C (5, 1)$ , $C (5, 1) \to A (1, 1)$ .

Tia từ $P$ đi sang phải ( $y = 2$ cố định, $x$ tăng). Áp dụng quy ước nửa mở "một đầu dưới chặt $p_{y}$ , đầu kia trên-hoặc-bằng":

Cạnh	$A_{y}, B_{y}$ so với $p_{y} = 2$	Cắt tia?	$x$ giao	So với $p_{x} = 2$	Đếm?
$A (1, 1) \to B (4, 4)$	$1 < 2$ và $4 \geq 2$ → vượt qua	có	$x = 1 + \frac{2 - 1}{4 - 1} (4 - 1) = 2$	$2 ⧸ < 2$ ? giao tại đúng $P$	xem dưới
$B (4, 4) \to C (5, 1)$	$4 \geq 2$ và $1 < 2$ → vượt qua	có	$x = 4 + \frac{2 - 4}{1 - 4} (5 - 4) = 4.67$	$4.67 > 2$	✅ +1
$C (5, 1) \to A (1, 1)$	$1 < 2$ và $1 < 2$ → không vượt	không	—	—	—

Ở cạnh đầu, giao điểm rơi đúng vào $P$ , nghĩa là $P$ nằm trên cạnh $A B$ . Hàm tốt sẽ phát hiện điều này trước (qua on_segment) và trả về 0 (trên biên). Nếu dời $P$ vào hẳn trong, ví dụ $P = (3, 2)$ :

cạnh AB: x giao = 1 + (1/3)*3 = 2.0  < 3   -> không đếm
cạnh BC: x giao = 4.67               > 3   -> đếm  (+1)
cạnh CA: không vượt qua y=2                 -> không
=> cnt = 1 (lẻ)  => P nằm TRONG

Một lần cắt (số lẻ) khẳng định $P = (3, 2)$ nằm trong tam giác — khớp trực giác hình vẽ.

Cài đặt

Tọa độ nguyên — Ray Casting + kiểm tra biên (khuyến nghị thi đấu)

Dùng số nguyên giúp tránh hoàn toàn sai số dấu phẩy động. Đây là phiên bản nên dùng khi tọa độ là số nguyên.

struct Point { long long x, y; };

// Tích có hướng: >0 nếu B bên trái tia O->A, <0 bên phải, =0 thẳng hàng
long long cross(Point O, Point A, Point B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

// P có nằm trên đoạn AB không (đã giả định thẳng hàng thì kẹp tọa độ)
bool on_segment(Point P, Point A, Point B) {
    return cross(A, B, P) == 0
        && min(A.x, B.x) <= P.x && P.x <= max(A.x, B.x)
        && min(A.y, B.y) <= P.y && P.y <= max(A.y, B.y);
}

// Trả về: 1 (trong), 0 (trên biên), -1 (ngoài)
int point_in_polygon(Point P, vector<Point>& poly) {
    int n = poly.size(), cnt = 0;
    for (int i = 0; i < n; i++) {
        Point A = poly[i], B = poly[(i + 1) % n];

        if (on_segment(P, A, B)) return 0;        // nằm đúng trên cạnh

        // Quy ước nửa mở: chỉ xét cạnh "vượt qua" tung độ P theo một chiều
        // (A.y < P.y) khác (B.y < P.y) <=> cạnh cắt đường ngang y = P.y
        if ((A.y < P.y) != (B.y < P.y)) {
            long long c = cross(P, A, B);
            // c>0 nghĩa giao điểm nằm bên phải P theo đúng chiều cạnh đi lên
            if ((A.y < P.y) == (c > 0)) cnt++;
        }
    }
    return (cnt % 2) ? 1 : -1;                     // lẻ -> trong, chẵn -> ngoài
}

Winding Number (đúng cả với đa giác tự cắt)

// Trả về số vòng quấn wn; wn != 0 => P nằm trong
int winding_number(Point P, vector<Point>& poly) {
    int n = poly.size(), wn = 0;
    for (int i = 0; i < n; i++) {
        Point A = poly[i], B = poly[(i + 1) % n];
        if (A.y <= P.y) {
            // cạnh đi LÊN vượt qua P, quay trái -> +1 vòng
            if (B.y > P.y && cross(A, B, P) > 0) wn++;
        } else {
            // cạnh đi XUỐNG vượt qua P, quay phải -> -1 vòng
            if (B.y <= P.y && cross(A, B, P) < 0) wn--;
        }
    }
    return wn;
}

Đa giác lồi — $O (\log N)$

Khi đa giác lồi và các đỉnh đã sắp ngược chiều kim đồng hồ, ta tách thành các tam giác hình quạt từ đỉnh poly[0] rồi tìm kiếm nhị phân quạt chứa $P$ .

// Giả định poly lồi, sắp ngược chiều kim đồng hồ, n >= 3
bool in_convex_polygon(Point P, vector<Point>& poly) {
    int n = poly.size();
    // P phải nằm bên trái cạnh (poly[0],poly[1]) và bên phải (poly[0],poly[n-1])
    if (cross(poly[0], poly[1], P) < 0) return false;
    if (cross(poly[0], poly[n - 1], P) > 0) return false;

    int lo = 1, hi = n - 1;
    while (lo + 1 < hi) {                   // tìm quạt [poly[lo],poly[hi]] chứa P
        int mid = (lo + hi) / 2;
        if (cross(poly[0], poly[mid], P) >= 0) lo = mid;
        else hi = mid;
    }
    return cross(poly[lo], poly[hi], P) >= 0; // P bên trong cạnh đáy của quạt
}

Phiên bản tọa độ thực (double)

Khi tọa độ là số thực, dùng double kèm hằng số sai số eps:

struct Point { double x, y; };

int point_in_polygon_d(Point P, vector<Point>& poly) {
    int n = poly.size(), cnt = 0;
    const double eps = 1e-9;
    for (int i = 0; i < n; i++) {
        Point A = poly[i], B = poly[(i + 1) % n];

        double cr  = (B.x-A.x)*(P.y-A.y) - (B.y-A.y)*(P.x-A.x);
        double dot = (P.x-A.x)*(B.x-A.x) + (P.y-A.y)*(B.y-A.y);
        double len2 = (B.x-A.x)*(B.x-A.x) + (B.y-A.y)*(B.y-A.y);
        if (fabs(cr) < eps && dot >= -eps && dot <= len2 + eps) return 0; // trên cạnh

        if ((A.y <= P.y && B.y > P.y) || (B.y <= P.y && A.y > P.y)) {
            double t = (P.y - A.y) / (B.y - A.y);
            if (P.x < A.x + t * (B.x - A.x)) cnt++;
        }
    }
    return (cnt % 2) ? 1 : -1;
}

Độ phức tạp

Ray Casting / Winding Number: $O (N)$ thời gian — mỗi cạnh được xét đúng một lần với công việc $O (1)$ (một tích có hướng, vài phép so sánh). Bộ nhớ $O (1)$ ngoài mảng đỉnh; nếu mảng đỉnh đã có sẵn thì không cần thêm.
Đa giác lồi $O (\log N)$ : mỗi truy vấn chỉ làm tìm kiếm nhị phân trên $N$ đỉnh, mỗi bước $O (1)$ . Cần đa giác đã lồi và đã sắp; nếu phải sắp/dựng bao lồi trước thì tốn $O (N \log N)$ một lần, sau đó mỗi truy vấn $O (\log N)$ — rất đáng khi có nhiều điểm cần kiểm tra trên cùng đa giác.

⚠️ Lỗi thường gặp

Tràn số khi nhân tích có hướng. Với tọa độ tới $10^{9}$ , tích $(A_{x} - O_{x}) (B_{y} - O_{y})$ có thể đạt $~ 4 \cdot 10^{18}$ , vượt int (và sát giới hạn long long). Luôn ép long long trước khi nhân, không phải sau. Hiệu hai tọa độ $10^{9}$ rồi nhân là $~ 4 \cdot 10^{18}$ — vẫn vừa long long (giới hạn $~ 9.2 \cdot 10^{18}$ ), nhưng nếu tọa độ lớn hơn phải dùng __int128.
Đếm trùng/sót khi tia đi qua đỉnh. Nếu dùng điều kiện đối xứng A.y <= P.y && B.y <= P.y cho cả hai đầu, một đỉnh chung của hai cạnh sẽ bị đếm hai lần hoặc không lần nào, cho kết quả sai. Phải dùng quy ước nửa mở (một đầu so sánh <, đầu kia <= hoặc >), đảm bảo mỗi giao điểm tại đỉnh được tính đúng một lần.
Quên xử lý điểm trên biên. Nhiều bài coi điểm trên cạnh là "nằm trong" (ví dụ bao lồi tính cả biên), số khác lại coi là "ngoài". Ray casting thuần không phân biệt được; phải gọi on_segment riêng trước khi đếm, và đọc kỹ đề để quyết định trả 0/1/-1 cho biên.
Dùng double cho tọa độ nguyên. Chia t = (P.y - A.y)/(B.y - A.y) đưa sai số dấu phẩy động vào, làm điểm sát biên bị phân loại nhầm. Khi đề cho tọa độ nguyên, hãy dùng phiên bản số nguyên (chỉ xét dấu của tích có hướng, không chia).
Áp dụng phiên bản $O (\log N)$ cho đa giác lõm hoặc chưa sắp. Tìm kiếm nhị phân quạt chỉ đúng khi đa giác lồi và đỉnh đã sắp (thường ngược chiều kim đồng hồ). Nếu đỉnh sắp theo chiều ngược lại, các bất đẳng thức dấu cross phải đảo; đừng quên chuẩn hóa hướng.
Đa giác tự cắt với ray casting. Ray casting chẵn–lẻ cho kết quả không trực quan với đa giác tự cắt (vùng "đè nhau" có thể bị coi là ngoài). Nếu đề có đa giác tự cắt, dùng winding number.

Biến thể / Mở rộng

Điểm trong tam giác: trường hợp riêng $N = 3$ , chỉ cần ba tích có hướng cùng dấu (hoặc bằng 0 nếu tính biên). Dùng rất nhiều trong bài đếm điểm trong tam giác.
Nhiều truy vấn trên đa giác cố định: tiền xử lý lồi để mỗi truy vấn $O (\log N)$ ; với đa giác lõm có thể chia tam giác/sweep để tăng tốc.
Diện tích đa giác: cùng công thức tích có hướng (Shoelace) cho diện tích có dấu, đồng thời cho biết đa giác đang sắp CW hay CCW — hữu ích để chuẩn hóa hướng trước khi chạy các thuật toán trên.

Bài tập luyện

Hàng rào kim đồng hồ (clockfnc) — (Học việc) Xác định một đường đi khép kín là CW hay CCW bằng dấu diện tích có hướng — làm quen viên gạch nền (tích có hướng) trước khi vào điểm-trong-đa-giác.
Cow Curling (cowcurling) — (Kỳ cựu) Đếm số điểm nằm trong hoặc trên biên bao lồi của tập điểm — ứng dụng trực tiếp point-in-convex-polygon (có thể dùng bản $O (\log N)$ ).
Hoán Vị Tam Giác (permut21) — (Kỳ cựu) Lời giải dựa trên kiểm tra một điểm có nằm trong tam giác hay không làm subroutine — luyện point-in-triangle trong bài đếm hoán vị.
Rất nhiều tam giác (lotstriangle) — (Bậc thầy) Đếm số cây nằm hoàn toàn bên trong mỗi tam giác — point-in-triangle hàng loạt, đòi hỏi cài đặt tích có hướng nguyên thật vững và xử lý biên cẩn thận.