Một Computational Geometry vấn đề:
Điểm P0 được chọn một cách ngẫu nhiên trên một cạnh (ví dụ, EB) của một đa giác (ví dụ, BCDE), để tìm ra những điểm có thể (ví dụ, P1,P2,P3,...) trên khác các cạnh dựa trên khoảng cách nhất định (ví dụ: r). Các cuộc biểu tình sau đây cho thấy một giải pháp bằng cách tìm các nút giao giữa các vòng tròn tập trung vào các điểm P0 và các cạnh của đa giác. Vì vậy, vấn đề cơ bản có thể được giải quyết bằng cách phân tích giao lộ Circle--Line-Segment.nút giao thông Circle-Polygon
Tôi tự hỏi có phương pháp nào hiệu quả hơn cho vấn đề rất đơn giản này về chi phí tính toán không? Quá trình này sẽ được đánh giá một số million times vì vậy bất kỳ cải tiến nào đều được quan tâm.
- giải pháp cuối cùng sẽ được hưởng lợi từ Python điện;
- tính toán lõi sẽ là Fortran nếu được yêu cầu.
Cập nhật:
Cảm ơn ý kiến của bạn. Vui lòng xem xét nhận xét của tôi về các nhận xét giúp làm rõ câu hỏi hơn. Không sẵn sàng lặp lại chúng ở đây, khuyến khích để xem xét tất cả các ý kiến và câu trả lời;).
Tôi vừa triển khai phương pháp Circle--Line-Segment Intersection dựa trên thuật toán được tìm thấy [here]. Trên thực tế tôi đã điều chỉnh nó để làm việc với các phân đoạn dòng. Điểm chuẩn của thuật toán thực hiện trong Python là như sau:
Số đoạn thẳng là: 100,000 và hệ thống là máy tính để bàn thông thường. Thời gian trôi qua là: 15 seconds. Hy vọng đây là hữu ích để cung cấp cho một số ý tưởng về chi phí tính toán. Việc triển khai lõi trong Fortan có thể cải thiện hiệu suất đáng kể.
Tuy nhiên bản dịch là bước cuối cùng.
Khoảng cách 'r' của tất cả triệu truy vấn giống nhau không? Chúng ta có thể đếm trên đa giác được lồi không? –
@BorisStrandjev Đối với vấn đề của chúng tôi, tất cả các đa giác đều lồi. 'r' có thể thay đổi cho mỗi lần lặp lại vì vậy nó có thể thay đổi nhưng là hằng số cho mỗi đa giác riêng lẻ. – Developer
Và có hàng triệu truy vấn được thực hiện trong một đa giác đơn hay khác nhau không? –