[Học thuật] Point Inside Polygon.

[tannguyen291 174]

Chào mọi cả nhà. khoảng thời gian gần đây diễn đàn có vẻ hơi yên tĩnh và chính mình cũng đang khá bận với công việc không tham gia diễn đàn nhiều. 

Hôm nay mình trở lại với một thuật toán khá hay để kiểm tra điểm nằm bên trong đường polyline kín. 

Việc kiểm tra này có khá nhiều thuật toán và nhiều người viết chương trình cũng rất ổn thường biết đến như Ray cating, Triangulation Method, Winding number...

Với Các ngôn ngữ bậc cao hơn còn tận dụng được các ưu thế có sẵn như Brep hoặc Mpolygon đển xác định.

Đối với chúng ta dễ tìm nhất là Thuật toán Ray Catting tuy nhiên Việc tạo ra đối tượng Ray mới, Tính toán giao điểm + Loại từ đi qua đỉnh hoặc chạm biên làm thuật toán khá cồng kềnh.

Hôm nay mình xin giới thiệu đến các bạn 2 ý tưởng cho hàm kiểm tra Point Inside Polygon. Không tạo ra đối tượng mới để kiểm tra (Ray, Brep, Mpolygon) dẫn đến tối ưu thuật toán và thời gian chạy chương trình.

Phương pháp 1: Orientation Test.

 - Tính diện tich có hướng của polyline (Shoelace Formula)

 - Tìm điểm gần nhất của Point đến Polyline => vector V1.

 - Xác định tích có hướng của V1 với vector tiếp tuyến tại điểm đó.

 - Khi 2 hướng này ngược chiều có thể xác định Point nằm trong Polyline.

Phương pháp 2: Winding number extension.

- Phươnng pháp này mình mở rộng từ Winding number chuẩn (đếm vòng quấn quanh polygon) để có thể tính được cạnh cong trong pline.

- Chia Pline thành 2 phần: 1 là pline không có đường cong và 2 tập hợp các hình viên phân (hình được giới hạn bởi đường cong và dây cung)

- Dùng phương pháp Winding number để kiểm tra Point in Pline (kết quả -1 nếu nằm trong 1 nếu nằm ngoài)

- Duyệt qua từng hình viên phân xác định điểm nằm trong hình 

- Nhân toàn bộ kết quả với nhau nếu < 0 là nằm trong nêu > 0 là nằm ngoài.

 

Mở rộng: Nếu có nhiều Polyline có thể tính từng polyline rồi nhân kết quả lại âm là trong dương là ngoài.

Với 2 cách trên chúng ta có thể xác định điểm nằm trong Polyline không quan tâm Polyline có tự giao hay nhiều Polyline có giao với nhau hay không.

Trân trọng.