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

Wiki › Thuật toán › Hình học tính toán

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

huunguyen · Last updated 8, Tháng 4, 2026, 15:33

Kiểm tra một điểm $P$ có nằm trong đa giác $Q$ hay không. Có hai phương pháp chính: Ray Casting và Winding Number.

Ray Casting — $O (N)$

Bắn tia từ $P$ theo hướng ngang (sang phải), đếm số lần tia cắt cạnh đa giác. Số lần lẻ → trong; số lần chẵn → ngoài.

struct Point { double x, y; };

// Kiểm tra P có nằm trong đa giác polygon không
// Trả về: 1 (trong), 0 (trên cạnh), -1 (ngoài)
int point_in_polygon(Point P, vector<Point>& poly) {
    int n = poly.size();
    int cnt = 0;

    for (int i = 0; i < n; i++) {
        Point A = poly[i], B = poly[(i+1)%n];

        // Kiểm tra P có nằm trên cạnh AB không
        // (tích có hướng = 0 và nằm trong bounding box)
        double cross = (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 (abs(cross) < 1e-9 && dot >= -1e-9 && dot <= len2+1e-9) return 0;

        // Ray casting: tia từ P sang phải cắt AB?
        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 : -1;
}

Với tọa độ nguyên — $O (N)$

Dùng tích có hướng (cross product) để tránh số thực:

struct Point { long long x, y; };

long long cross(Point O, Point A, Point B) {
    return (A.x-O.x)*(long long)(B.y-O.y) - (A.y-O.y)*(long long)(B.x-O.x);
}

// Kiểm tra P nằm trên đoạn AB
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);
}

int point_in_polygon_int(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;   // trên cạnh

        // Dùng tia theo hướng x+ từ P
        // Tránh đếm đỉnh hai lần: chỉ đếm khi A.y < P.y <= B.y hoặc B.y < P.y <= A.y
        if ((A.y < P.y) != (B.y < P.y)) {
            long long c = cross(P, A, B);
            // c > 0 khi A→B nằm bên trái P (tia hướng x+ cắt cạnh AB)
            if ((A.y < P.y) == (c > 0)) cnt++;
        }
    }
    return (cnt % 2) ? 1 : -1;
}

Winding Number — $O (N)$

Đếm số vòng đa giác quanh điểm P. Winding number $\neq 0$ → trong đa giác (kể cả non-convex và self-intersecting):

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) {
            if (B.y > P.y && cross(A, B, P) > 0) wn++;
        } else {
            if (B.y <= P.y && cross(A, B, P) < 0) wn--;
        }
    }
    return wn;   // != 0: trong đa giác
}

So sánh

	Ray Casting	Winding Number
Đa giác đơn giản	✅	✅
Đa giác tự cắt	❌	✅
Tốc độ	$O (N)$	$O (N)$
Xử lý biên	Cần xử lý cẩn thận	Tương tự

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

Với đa giác lồi, có thể kiểm tra trong $O (\log N)$ bằng binary search:

// Giả sử polygon sắp theo CCW, polygon[0] là điểm cực dưới-trái
bool in_convex_polygon(Point P, vector<Point>& poly) {
    int n = poly.size();
    if (n < 3) return false;
    if (cross(poly[0], poly[1], P) < 0) return false;
    if (cross(poly[0], poly[n-1], P) > 0) return false;

    // Binary search tìm sector chứa P
    int lo = 1, hi = n-1;
    while (lo + 1 < hi) {
        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;
}

Bình luận

Không có bình luận tại thời điểm này.