Điểm trong đa giác

Trong Hình học tính toán, bài toán "Điểm trong đa giác" (tiếng Anh: point-in-polygon, viết tắt: PIP) đặt ra câu hỏi xét xem một điểm trên một mặt phẳng nằm trong, nằm ngoài hay nằm trên biên của một đa giác. Đây là trường hợp đặc biệt của loạt các bài toán hay vấn đề "Vị trí điểm" và có rất nhiều ứng dụng trong việc xử lý dữ liệu hình học như trong Đồ họa máy tính (Computer Graphics), Hệ thống Thông tin Địa lý (Geographical Information Systems - GIS), Lập lịch chuyển động và CAD (tin học).

Trong thời kỳ đầu của đồ họa máy tính, vấn đề này thường được tiếp cận theo hai cách: quét tia (ray casting) và phép cộng góc (angle summation). Các kỹ thuật này đã được sử dụng từ những năm 1974.

Thuật toán Ray casting

Mô phỏng thuật toán ray tracing tính toán các giao điểm

Một cách đơn giản để xác định xem một điểm P nằm bên trong hay bên ngoài một đa giác đơn giản đó là kiểm tra

xem một tia (ra) bắt đầu từ điểm P đó giao với các cạnh của đa giác bao nhiêu lần. Nếu điểm P không nằm trên biên của đa giác thì:

- P nằm trong đa giác nếu tổng số giao điểm là số lẻ

- P nằm ngoài đa giác nếu tổng số giao điểm là số chẵn

Thuật toán này dựa trên một quan sát đơn giản là nếu ta có một điểm đi dọc theo một tia từ vô cực đến P thì điểm đó sẽ giao (có thể nhiều lần) với biên của đa giác, điểm này có thể đi từ ngoài vào trong rồi lại từ trong ra ngoài,...Chính vì vậy sau mỗi hai lần giao với biên của đa giác thì điểm đó sẽ đi ra ngoài đa giác. Quan sát này có thể được chứng minh toán học bằng cách sử dụng định lý đường cong Jordan.

Lưu ý:

1. Do các sai số làm tròn, nếu thuật toán này được cài đặt trên một máy tính có độ chính xác số học hữu hạn kết quả có thể sai lệch khi P nằm rất gần biên của đa giác. Tuy nhiên trong đồ họa máy tính người ta thường ưu tiên tốc độ hơn độ chính xác tuyệt đối nên điều này cũng không phải là vấn đề phải bận tâm lớn. Người ta có thể sử dụng một dung sai nào đó để chỉ rằng "P rất gần biên đa giác". Ngoài ra chúng ta cũng cần phải xem xét cẩn thận khi áp dụng thuật toán này cho các trường hợp đa giác phức tạp như đa giác có các đường biên giao nhau.
2. Trong trường hợp tia cắt ngang đỉnh của đa giác, như vậy tia này đã cắt 2 cạnh cùng 1 lượt và có sai sót sẽ xảy ra. Điểm có thể nằm trong hoặc ngoài đa giác. Để kết luận được, ta cần xét thêm 2 đỉnh liền kề của đỉnh được cắt nằm cùng phía hay khác phía với tia.

Các thuật toán khác

Ngoài thuật toán ray casting ở trên, một số thuật toán khác cũng có thể được áp dụng để giải quyết bài toán này, ví dụ như thuật toán số uốn cong (winding number algorithm),...

Các trường hợp đặc biệt

Các thuật toán đơn giản có thể dùng để giải quyết bài toán cho các trường hợp đặc biệt như đa giác monotone, đa giác hình sao hay các đa giác lồi.