Internet of ThingsIoT platformsOwntracks

Bài 5: Thuật toán Ray-Casting và ứng dụng trong tọa độ cực (GPS)

1. Giới Thiệu

Trong hình học, bài toán “điểm trong đa giác” (point-in-polygon, PIP) đặt ra vấn đề về vị trí của một điểm trên 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 về 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, hệ thống thông tin địa lý, lập lịch chuyển động và CAD

Ray-Casting
Ray-Casting

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. Đó là quét tia (ray-casting) và phép cộng góc (angle summatio). Các kỹ thuật này đã được sử dụng từ những năm 1974.

-Thuật toán Ray-casting: thuật toán cho phép ta xác định được vị trí của điểm P nằm trong hay nằm ngoài một đa giác. Bằng việc tạo ra một tia ló bắt đầu từ điểm P giao với các cạnh của đa giác. Kiểm tra số giao điểm của tia ló với các cạnh của đa giác.

Nếu điểm P không nằm trên biên của đa giác thì:

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

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

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.

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

Giải pháp là so sánh từng cạnh của đa giác với tọa độ Y của điểm P và biên dịch ra danh sách các nút (giao điểm của cạnh và tia ló), trong đó một nút được tạo ra khi mà một đầu của cạnh vượt qua ngưỡng Y của điểm P.

Tia ló ở đây là tia song song với trục x và có d(tia ló,x)=Y

(Lưu ý: Thuật toán này không quan tâm liệu đa giác được tìm theo chiều kim đồng hồ hay ngược chiều kim đồng hồ)

TH1:

Ray-casting_TH1
Ray-casting_TH1

Hình 1 minh họa một trường hợp điển hình của một đa giác lồi lõm khá dị dạng với 14 cạnh. Dấu chấm màu đỏ là điểm P được xét để kiểm tra vị trí.

Trong trường hợp này, 8 cạnh của đa giác vượt qua ngưỡng Y, trong khi 6 cạnh kia thì không. Nếu có một số lẻ số lượng các nút ở mỗi bên của điểm P, thì nó nằm bên trong đa giác. Nếu có một số chẵn số lượng các nút ở mỗi bên của điểm P, thì P nằm bên ngoài đa giác. Trong hình có 5 nút ở bên trái của điểm kiểm tra và 3 nút ở bên phải nên điểm P nằm bên trong đa giác.

TH2:

Ray-castin_TH2
Ray-castin_TH2

Hình 2 là một đa giác có các lỗ hổng, các cạnh chồng lên nhau. Điểm P lúc này nằm bê ngoài đa giác, vì mỗi bên ta có 2 nút.

TH3:

Ray-casting_TH3
Ray-casting_TH3

Trong hình 3, đa giác có 2 cạnh chồng lên nhau. Nhưng thuật toán vẫn hoạt động tốt với mỗi bên của P là 1 nút được tạo ra.

TH4:

Ray-castin_TH4
Ray-castin_TH4

Hình 4 cho thấy vấn đề khi hai đỉnh của đa giác nằm ngay trên ngưỡng Y (tia ló đi qua đỉnh của đa giác). Một đầu của cạnh a và cạnh b đều chạm ngưỡng. Cả hai có nên tạo ra một nút hay không? Không, bởi vì nếu thế thì sẽ có hai nút ở mỗi bên của điểm P. Vì vậy điểm P nằm ngoài đa giác, nhưng trong hình vẽ thì rõ ràng là không.

Giải pháp cho tình huống này rất đơn giản. Các đỉnh của đa giác nằm chính xác trên ngưỡng Y phải được xem là thuộc về một bên của ngưỡng. Tức là nằm trên hoặc nằm dưới ngưỡng. Giả sử chúng ta tự quyết định rằng các đỉnh của đa giác nằm trên ngưỡng Y thuộc về phía trên của ngưỡng. Thì cạnh a sẽ tạo ra một nút vì nó có một đầu dưới và một đầu nằm trên hoặc cao hơn ngưỡng Y. Cạnh b không tạo ra nút, vì cả hai đầu của nó là nằm trên hoặc cao hơn ngưỡng Y. Do đó ta sẽ chỉ có một nút được tạo ra.

TH5:

Ray-casting_TH5
Ray-casting_TH5

Trường hợp của hình 5 là một đa giác có một trong các cạnh của nó nằm hoàn toàn trên ngưỡng. Chỉ cần thực hiện theo quy tắc như được mô tả ở hình 4. Cạnh c tạo ra một nút. Vì nó có một đầu bên dưới ngưỡng và một đầu nằm trên hoặc cao hơn ngưỡng. Cạnh d không tạo ra nút, vì nó có cả hai đầu nằm trên hoặc cao hơn ngưỡng. Và cạnh e cũng không tạo ra nút, vì nó có cả hai đầu nằm trên hoặc cao hơn ngưỡng.

TH6:

Ray-casting_TH6
Ray-casting_TH6

Hình 5.6 là một trường hợp đặc biệt hơn cả. Một góc bên trong của đa giác chạm vào ngưỡng Y của P. Thuật toán vẫn đúng với trường hợp này. Trong hình, chỉ có cạnh được tô màu đỏ mới tạo ra một nút.

Ở hình bên trên, cạnh bên trái của điểm P tạo ra nút. Hai cạnh có một đầu nằm trên ngưỡng Y không tạo ra nút. Vì có hai đầu đều nằm trên hoặc cao hơn ngưỡng Y.

Hình bên dưới có 3 cạnh tạo ra nút. Hai cạnh có một đầu nằm trên ngưỡng Y tạo ra nút. Là vì chúng có một đầu nằm dưới ngưỡng và đầu còn lại nằm trên hoặc cao hơn ngưỡng Y.

Con số nút được tạo ra là lẻ và điểm kiểm tra P nằm bên trong ngưỡng Y

Chú ý:

Nếu điểm kiểm tra P nằm trên đường viền của đa giác, thuật toán này sẽ cung cấp kết quả không thể dự đoán được. Tức là kết quả có thể là bên trong hoặc bên ngoài tùy thuộc vào các yếu tố tùy ý như cách đa giác được định hướng đối với hệ tọa độ. Nhưng đây không phải vấn đề. Bởi vì cạnh của đa giác là vô cùng mỏng và điểm rơi ngay trên cạnh có thể đi theo một trong hai cách mà không làm tổn hại đến giao diện của đa giác.

3. Vấn đề sử dụng thuật toán Ray-casting trong tọa độ cực (GPS)

Tọa độ cực GPS
Tọa độ cực GPS

Việc áp dụng thuật toán trong tọa độ cực (GPS) là hoàn toàn được. Ta có thể sử dụng kinh độ cho X và vĩ độ cho Y. Nhưng thường chỉ khi đa giác được giới hạn trong một khu vực tương đối nhỏ. Ví dụ trong  một phạm vi quốc gia của Đông Nam Á. Có hai vấn đề chính:

– Nếu đa giác có bất kỳ một cạnh nào đi qua một khoảng cách lớn trên quả địa cầu thì thuật toán đa giác điểm sẽ theo một đường cong đáng kể cho cạnh đó (đặc biệt là gần cực). Có thể tránh vấn đề này nếu đảm bảo rằng không có cạnh nào trong đa giác đi qua một khoảng cách lớn.

– Nếu đa giác vượt qua đường truyền dữ liệu quốc tế thì thuật toán sẽ hoàn toàn bị nhầm lẫn do thiết bị lập lại kinh độ đột ngột. Có thể phải cộng hoặc trừ 360 độ cho một số vĩ độ của các góc để ngăn điều này xảy ra. Nhưng giải pháp này sẽ không hoạt động nếu đa giác đi hoàn toàn xung quanh cực bắc hoặc cực nam.

Bình luận

Related Articles

Close
Close