Cần một lời khuyên về khuôn khổ cho đường dẫn trên xác thực bản đồ

Question

Vấn đề tôi đang gặp phải như sau:

Cho hai đa giác xác định đường viền của mê cung và đường dẫn ở giữa (xem hình bên dưới), tôi muốn biết khi tôi vượt qua biên giới của mê cung.

Đối với các yếu tố đầu tôi có:

• Một tập tin định cạnh của hai đa giác (chỉ những điểm mà kết nối đường thẳng)
• Một tập tin với tất cả các waypoints Tôi đã đến thăm, trong thứ tự xuất hiện

Tôi cần tính điểm cho đường dẫn đó dựa trên lượng thời gian dành cho khu vực bị hạn chế.

Cách tốt nhất để làm điều đó là gì? (Thuật toán/Công nghệ/Library) Tôi không có hạn chế công nghệ vì vậy giải pháp có thể được bất cứ điều gì như Java, C, Perl (đây là yêu thích của tôi), vv

tôi bắt đầu làm việc trên một giải pháp, nhưng sau đó tôi nhận ra vấn đề này phải được giải quyết hàng triệu lần trong quá khứ và không có lý do gì để "phát minh lại bánh xe" :)

Tôi mới sử dụng loại hình địa lý/hình học và tôi rất cảm kích mọi lời khuyên về cách tiếp cận nào .

Cheers

Answer 1

Đây là một Point in polygon

1. Xây dựng một danh sách các đa giác từ "Một tập tin cạnh việc xác định của hai đa giác (chỉ các điểm kết nối các đường thẳng)"
2. Áp dụng point_in_polygon() (perl implementation, yêu thích của bạn) cho mỗi "điểm tham chiếu tôi đã truy cập"