Kiểm tra điểm có nằm trong đa giác không

Giới thiệu

Trong bài toán này, cho một đa giác và một điểm P. Ta cần kiểm tra xem điểm có nằm bên trong đa giác hay bên ngoài.

Để giải quyết, ta vẽ một đường thẳng từ điểm P. Nó kéo dài đến vô cùng. Đường thẳng này nằm ngang, hoặc song song với trục x.

Từ đường thẳng đó, ta đếm bao nhiêu lần đường thẳng cắt các cạnh của đa giác. Khi điểm nằm trong đa giác, nó sẽ cắt các cạnh một số lẻ lần, nếu P đặt trên bất kỳ cạnh nào của đa giác, thì nó sẽ cắt số chẵn lần. Nếu không có điều kiện nào đúng, thì nó nằm ngoài đa giác.

Đầu vào và Đầu ra

Đầu vào: Các điểm của đa giác {(0, 0), (10, 0), (10, 10), (0, 10)}. Và điểm P (5, 3) để kiểm tra.
Đầu ra: Điểm nằm bên trong.

Thuật toán

checkInside(Poly, n, p)
Đầu vào: Các điểm của đa giác, số điểm của đa giác, điểm p cần kiểm tra.
Đầu ra: True khi p nằm trong đa giác, ngược lại false.

Begin
    if n < 3, then
        return false
    tạo đường thẳng exLine từ điểm p đến vô cùng, Độ dốc là 0°.
    count := 0 và i := 0
    repeat
        tạo đường thẳng side, từ điểm poly[i] đến poly[(i+1) mod n]
        if side và exLine cắt nhau, then
            if side và exLine thẳng hàng, then
                if điểm p trên side, then
                    return true
                else return false
            count := count + 1
        i := (i + 1) mod n
    until i ≠ 0
    return true nếu count là lẻ
End

Ví dụ (C++)

#include <iostream>
using namespace std;

struct Point {
    int x, y;
};

struct line {
    Point p1, p2;
};

bool onLine(line l1, Point p) {
    // kiểm tra p có trên đoạn thẳng hay không
    if(p.x <= max(l1.p1.x, l1.p2.x) && p.x >= min(l1.p1.x, l1.p2.x) &&
       (p.y <= max(l1.p1.y, l1.p2.y) && p.y >= min(l1.p1.y, l1.p2.y)))
        return true;
    return false;
}

int direction(Point a, Point b, Point c) {
    int val = (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
    if (val == 0)
        return 0;  // thẳng hàng
    else if(val < 0)
        return 2;  // ngược chiều kim đồng hồ
    return 1;  // cùng chiều kim đồng hồ
}

bool isIntersect(line l1, line l2) {
    // bốn hướng cho hai đường và điểm của đường kia
    int dir1 = direction(l1.p1, l1.p2, l2.p1);
    int dir2 = direction(l1.p1, l1.p2, l2.p2);
    int dir3 = direction(l2.p1, l2.p2, l1.p1);
    int dir4 = direction(l2.p1, l2.p2, l1.p2);
    if(dir1 != dir2 && dir3 != dir4)
        return true;  // chúng cắt nhau
    if(dir1==0 && onLine(l1, l2.p1))  // khi p2 của line2 nằm trên line1
        return true;
    if(dir2==0 && onLine(l1, l2.p2))  // khi p1 của line2 nằm trên line1
        return true;
    if(dir3==0 && onLine(l2, l1.p1))  // khi p2 của line1 nằm trên line2
        return true;
    if(dir4==0 && onLine(l2, l1.p2))  // khi p1 của line1 nằm trên line2
        return true;
    return false;
}

bool checkInside(Point poly[], int n, Point p) {
    if(n < 3)
        return false;  // khi đa giác có ít hơn 3 cạnh, không phải đa giác
    line exline = {p, {9999, p.y}};  // tạo điểm ở vô cùng, y giống điểm p
    int count = 0;
    int i = 0;
    do {
        line side = {poly[i], poly[(i+1)%n]};  // tạo đường từ hai điểm liên tiếp của poly
        if(isIntersect(side, exline)) {  // nếu cạnh cắt exline
            if(direction(side.p1, p, side.p2) == 0)
                return onLine(side, p);
            count++;
        }
        i = (i+1)%n;
    } while(i != 0);
    return count & 1;  // khi count là lẻ
}

int main() {
    Point polygon[] = {{0, 0}, {10, 0}, {10, 10}, {0, 10}};
    Point p = {5, 3};
    int n = 4;
    if(checkInside(polygon, n, p))
        cout << "Point is inside.";
    else
        cout << "Point is outside.";
}

Kết quả

Point is inside.