Thuật Toán Point-in-Polygon: Tuyệt Chiêu Xác Định "Shipper Có Đang Ở Trong Vùng Giao Hàng?"

Chào anh em Viblo! 👋

Nếu anh em từng làm việc trong các dự án về TMĐT, Gojek/Grab-like, hay đặc biệt là hệ thống Logistics, chắc chắn anh em sẽ gặp bài toán phân vùng địa lý (Geofencing). Ví dụ: Doanh nghiệp định nghĩa một vùng giao hàng miễn phí trên bản đồ bằng cách nối các tọa độ lại thành một đa giác (Polygon). Khi khách hàng nhập vị trí của họ (một điểm Point gồm Latitude, Longitude), hệ thống phải kiểm tra xem điểm này có nằm trong vùng giao hàng đó hay không để tính phí shipping.

Hồi mới đụng bài toán này, mình lười lật sách giải thuật nên chơi chiêu "ngây thơ": Viết một đống hàm if-else so sánh kinh độ, vĩ độ cực đại, cực tiểu. Kết quả là nó chỉ đúng với... hình vuông hoặc hình chữ nhật. Đến khi khách hàng vẽ một đa giác méo mó, lồi lõm trên bản đồ, code của mình hoàn toàn "bó tay".

Sau pha "ăn hành" đó, mình mới biết đến một thuật toán kinh điển trong hình học máy tính để giải quyết triệt để bài toán này: Point-in-Polygon (PIP) – mà phổ biến nhất là thuật toán Ray Casting (Bắn tia).

Hôm nay, mình sẽ cùng anh em mổ xẻ cách hoạt động và code triển khai thuật toán này một cách thực tế nhất nhé!

1. Thuật toán Ray Casting (Even-Odd Rule) là gì?

Ý tưởng cốt lõi của thuật toán Ray Casting (Bắn tia) vô cùng thông minh và mang đậm tính trực quan hình học.

Tưởng tượng bạn có một điểm $P$ và một đa giác trên mặt phẳng. Để biết $P$ ở trong hay ở ngoài đa giác, ta làm như sau:

1. Từ điểm $P$, ta "bắn" một tia thẳng tắp về một hướng bất kỳ kéo dài đến vô tận (thường là bắn nằm ngang sang phía bên phải để dễ tính toán).
2. Ta đếm số lần mà tia này cắt (giao nhau) với các cạnh của đa giác.
3. Chốt hạ quy tắc:

• Nếu số lần cắt là Số Lẻ (1, 3, 5...) $\rightarrow$ Điểm $P$ nằm TRONG đa giác.
• Nếu số lần cắt là Số Chẵn (0, 2, 4...) $\rightarrow$ Điểm $P$ nằm NGOÀI đa giác.

Tại sao lại như vậy? Hãy tưởng tượng bạn đang đứng ngoài một ngôi nhà (đa giác). Mỗi lần bạn đi xuyên qua một bức tường (cạnh), trạng thái của bạn sẽ thay đổi: Vào trong $\rightarrow$ Ra ngoài $\rightarrow$ Vào trong. Vì xuất phát điểm ban đầu của tia bắn từ $P$ ra vô tận chắc chắn là nằm ngoài đa giác, nên nếu tổng số lần đổi trạng thái là số lẻ, điểm xuất phát $P$ bắt buộc phải ở bên trong!

2. Triển Khai Code Thực Chiến (JavaScript / TypeScript)

Để kiểm tra xem tia ngang từ điểm $P(x, y)$ có cắt đoạn thẳng nối giữa hai đỉnh $A(x_1, y_1)$ và $B(x_2, y_2)$ của đa giác hay không, ta cần áp dụng một chút toán hình học phẳng. Điểm giao nhau của tia ngang với cạnh phải thỏa mãn:

• Tọa độ $y$ của điểm $P$ phải nằm giữa đoạn $y_1$ và $y_2$ của cạnh.
• Tọa độ $x$ tại điểm giao nhau trên cạnh phải lớn hơn tọa độ $x$ của điểm $P$.

Công thức tìm tọa độ $x$ của điểm giao nhau dựa trên phương trình đường thẳng là:

$$x_{\text{intersection}} = x_1 + \frac{(y - y_1) \cdot (x_2 - x_1)}{y_2 - y_1}$$

Dưới đây là hàm hoàn chỉnh giúp anh em "vả bug" PIP:

interface Point {
    x: number; // Thường tương ứng với Longitude (Kinh độ)
    y: number; // Thường tương ứng với Latitude (Vĩ độ)
}

function isPointInPolygon(point: Point, polygon: Point[]): boolean {
    const x = point.x;
    const y = point.y;
    let inside = false;

    const numVertices = polygon.length;
    
    // Duyệt qua từng cạnh của đa giác (nối đỉnh i và đỉnh j)
    for (let i = 0, j = numVertices - 1; i < numVertices; j = i++) {
        const xi = polygon[i].x, yi = polygon[i].y;
        const xj = polygon[j].x, yj = polygon[j].y;

        // Kiểm tra xem tia ngang từ điểm P có cắt cạnh (i, j) hay không
        const intersect = ((yi > y) !== (yj > y))
            && (x < (xj - xi) * (y - yi) / (yj - yi) + xi);
            
        if (intersect) {
            inside = !inside; // Đảo trạng thái (Chẵn <-> Lẻ)
        }
    }

    return inside;
}

3. Những "Vết Sẹo" Thực Chiến Và Cách Tối Ưu

Thuật toán Ray Casting chạy với độ phức tạp là $O(N)$ (với $N$ là số đỉnh của đa giác) vì nó phải duyệt qua tất cả các cạnh. Khi áp dụng vào hệ thống thực tế có hàng triệu request, anh em cần nằm lòng các bí kíp tối ưu sau:

Chiêu số 1: Tấm lá chắn Bounding Box (Hộp giới hạn)

Nếu đa giác của bạn là một khu vực phức tạp (ví dụ: Bản đồ toàn bộ Thành phố Hà Nội với hàng ngàn đỉnh), việc cứ mỗi request tọa độ vào lại lôi hàng ngàn đỉnh ra chạy vòng lặp là một tội ác với CPU.

• Giải pháp: Hãy tính sẵn Bounding Box của đa giác đó (tìm $x_{\min}, x_{\max}, y_{\min}, y_{\max}$ nhỏ nhất và lớn nhất của đa giác).
• Trước khi chạy thuật toán Ray Casting phức tạp, ta chỉ cần check nhanh: Nếu tọa độ của điểm $P$ nằm ngoài cái hộp chữ nhật bao quanh này, ta kết luận luôn là NẰM NGOÀI trong vòng $O(1)$. Chỉ khi nào điểm lọt vào trong hộp, ta mới kích hoạt vòng lặp kiểm tra chi tiết.

Chiêu số 2: Điểm nằm ngay trên Cạnh hoặc Đỉnh (Edge Cases)

Thuật toán Ray Casting thuần túy có thể cho ra kết quả không ổn định nếu điểm $P$ nằm chính xác 100% trên cạnh hoặc trùng với một đỉnh của đa giác (do sai số làm tròn của số thực).

• Trong logistics, nếu shipper đứng ngay ranh giới, hệ thống có tính phí không? Thường là có. Do đó, nếu bài toán đòi hỏi nghiêm ngặt, bạn cần viết thêm một đoạn code nhỏ để check xem điểm đó có nằm trên các đoạn thẳng của cạnh hay không trước khi thực hiện bắn tia.

Chiêu số 3: Tận dụng sức mạnh của Extension Database (PostGIS)

Nếu bạn lưu trữ vùng địa lý dưới Database, đừng bốc toàn bộ danh sách tọa độ lên tầng Code để tính toán bằng hàm trên. Hãy chuyển sang sử dụng các Database hỗ trợ GIS như PostgreSQL với PostGIS hoặc MySQL Spatial Extensions. Chúng đã được tối ưu hóa bằng các cấu trúc cây chỉ mục không gian như R-Tree bên dưới tầng cánh gà. Bạn chỉ cần viết một câu lệnh SQL thượng đẳng như thế này là xong:

SELECT ST_Contains(delivery_zone_polygon, ST_GeomFromText('POINT(106.6601 10.7626)'));

Đúc kết lại

Xác định điểm trong đa giác là một bài toán nền tảng nhưng vô cùng quyền lực trong thế giới công nghệ bản đồ và định vị. Hiểu rõ bản chất toán học của thuật toán Ray Casting sẽ giúp bạn làm chủ logic hệ thống, tự tin tối ưu hiệu năng và thiết kế các tính năng phân vùng địa lý chuẩn chỉ, không góc chết.

Hy vọng bài viết này mang lại những kiến thức thực tế giúp ích cho các dự án sắp tới của anh em. Happy Coding!