Tìm cặp điểm gần nhất trên quả cầu

Question

Tôi biết cách thực hiện thuật toán cặp điểm gần nhất n log n (Shamos và Hoey) cho các trường hợp 2D (x và y). Tuy nhiên đối với một vấn đề mà vĩ độ và kinh độ được đưa ra cách tiếp cận này không thể được sử dụng. Khoảng cách giữa hai điểm được tính bằng công thức haversine.

Tôi muốn biết nếu có một số cách để chuyển đổi các vĩ độ và kinh độ này thành tọa độ x và y tương ứng và tìm cặp điểm gần nhất hoặc nếu có kỹ thuật khác có thể được sử dụng để thực hiện.

Answer 1

Tôi sẽ dịch chúng sang tọa độ ba chiều và sau đó sử dụng divide and conquer approach bằng máy bay chứ không phải đường thẳng. Điều này chắc chắn sẽ hoạt động chính xác. Chúng ta có thể yên tâm về điều này bởi vì khi chỉ kiểm tra các điểm trên quả cầu, hai điểm gần nhất bởi khoảng cách vòng cung (khoảng cách đi bộ trên bề mặt) cũng sẽ là hai điểm gần nhất với khoảng cách 3-d Descartes. Điều này sẽ có thời gian chạy O (nlogn).

Để dịch sang tọa độ 3 chiều, cách dễ nhất là tạo (0,0,0) tâm của trái đất và sau đó tọa độ của bạn là (cos (lat) * cos (lon), cos (lat) * tội lỗi (lan), tội lỗi (lat)). Với những mục đích đó, tôi sử dụng thang đo mà bán kính của Trái đất là 1 để đơn giản hóa các phép tính. Nếu bạn muốn khoảng cách trong một số đơn vị khác, chỉ cần nhân tất cả các đại lượng bằng bán kính của Trái Đất khi được đo trong đơn vị đó.

Tôi nên lưu ý rằng tất cả điều này giả định rằng trái đất là một hình cầu. Nó không chính xác một và điểm thực sự có thể có độ cao là tốt, vì vậy những câu trả lời sẽ không thực sự hoàn toàn chính xác, nhưng chúng sẽ rất gần đúng trong hầu hết mọi trường hợp.