hiệu quả tìm tọa độ cặp gần nhất từ ​​một bộ bằng Python

Question

Vấn đề

Hãy tưởng tượng tôi đang đứng trong sân bay. Với một cặp tọa độ địa lý, làm cách nào để xác định một cách hiệu quả sân bay nào tôi đang đứng?

Đầu vào

• Một phối hợp cặp (x,y) đại diện cho vị trí tôi đang đứng ở.
• Một tập hợp các cặp tọa độ [(a1,b1), (a2,b2)...] trong đó mỗi cặp tọa độ đại diện cho một sân bay.

mong muốn Output

Một phối hợp cặp (a,b) từ tập các sân bay phối hợp cặp đại diện cho các sân bay gần nhất với điểm (x,y).

không hiệu quả Giải pháp

Đây là nỗ lực không hiệu quả của tôi tại giải quyết vấn đề này. Nó rõ ràng là tuyến tính trong chiều dài của tập hợp các sân bay.

shortest_distance = None 
shortest_distance_coordinates = None 

point = (50.776435, -0.146834) 

for airport in airports: 
    distance = compute_distance(point, airport) 
    if distance < shortest_distance or shortest_distance is None: 
     shortest_distance = distance 
     shortest_distance_coordinates = airport 

Các Câu hỏi

Làm thế nào giải pháp này có thể được cải thiện? Điều này có thể liên quan đến một số cách lọc trước danh sách các sân bay dựa trên tọa độ của vị trí chúng tôi hiện đang đứng hoặc sắp xếp chúng theo thứ tự nhất định trước đó.

Answer 1

Nếu tọa độ của bạn là không được phân loại , tìm kiếm của bạn chỉ có thể được cải thiện một chút, giả sử rằng nó là (latitude,longitude) bằng cách lọc theo vĩ độ trước tiên cho trái đất

1 độ vĩ độ trên mặt cầu là 111,2 km hoặc 69 dặm

nhưng điều đó sẽ không đưa ra một sự tăng tốc rất lớn.

Nếu bạn sắp xếp các sân bay bởi vĩ độ đầu tiên sau đó bạn có thể sử dụng tìm kiếm nhị phân cho việc tìm kiếm các sân bay đầu tiên mà thể trận đấu (airport_lat >= point_lat-tolerance) và sau đó chỉ so sánh tới người cuối cùng mà thể trận đấu (airport_lat <= point_lat+tolerance) - nhưng chăm sóc 0 độ bằng 360. Trong khi bạn không thể sử dụng thư viện đó trực tiếp, các nguồn của bisect là một khởi đầu tốt để thực hiện tìm kiếm nhị phân.

Mặc dù về mặt kỹ thuật theo cách này, tìm kiếm vẫn là O (n), bạn có ít hơn nhiều tính toán khoảng cách thực tế (tùy thuộc vào dung sai) và so sánh một số vĩ độ.Vì vậy, bạn sẽ có một tốc độ rất lớn.

Answer 2

Từ SO question này:

import numpy as np 
def closest_node(node, nodes): 
    nodes = np.asarray(nodes) 
    deltas = nodes - node 
    dist_2 = np.einsum('ij,ij->i', deltas, deltas) 
    return np.argmin(dist_2) 

nơi node là một tuple với hai giá trị (x, y) và nodes là một mảng của bộ dữ liệu với hai giá trị ([(x_1, y_1), (x_2, y_2),])

Answer 3

>>> from scipy import spatial 
>>> airports = [(10,10),(20,20),(30,30),(40,40)] 
>>> tree = spatial.KDTree(airports) 
>>> tree.query([(21,21)]) 
(array([ 1.41421356]), array([1])) 

Nơi 1.41421356 là khoảng cách giữa điểm truy vấn và hàng xóm gần nhất và 1 là chỉ số của hàng xóm.

Xem: http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.KDTree.query.html#scipy.spatial.KDTree.query