Làm thế nào tôi có thể nhanh chóng ước tính khoảng cách giữa hai (vĩ độ, kinh độ) điểm?

Question

Tôi muốn có thể ước tính khoảng cách giữa hai (vĩ độ, kinh độ). Tôi muốn undershoot, vì điều này sẽ cho tìm kiếm đồ thị A * và tôi muốn nó là nhanh. Các điểm cách nhau tối đa 800 km.

Answer 1

Câu trả lời cho Haversine Formula in Python (Bearing and Distance between two GPS points) cung cấp triển khai Python trả lời câu hỏi của bạn.

Sử dụng triển khai bên dưới I thực hiện 100.000 lần lặp trong chưa đầy 1 giây trên máy tính xách tay cũ hơn. Tôi nghĩ rằng cho mục đích của bạn, điều này là đủ. Tuy nhiên, bạn nên cấu hình bất cứ điều gì trước khi bạn tối ưu hóa cho hiệu suất.

from math import radians, cos, sin, asin, sqrt 
def haversine(lon1, lat1, lon2, lat2): 
    """ 
    Calculate the great circle distance between two points 
    on the earth (specified in decimal degrees) 
    """ 
    # convert decimal degrees to radians 
    lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2]) 
    # haversine formula 
    dlon = lon2 - lon1 
    dlat = lat2 - lat1 
    a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2 
    c = 2 * asin(sqrt(a)) 
    # Radius of earth in kilometers is 6371 
    km = 6371* c 
    return km

Để đánh giá thấp haversine(lat1, long1, lat2, long2) * 0.90 hoặc bất kỳ yếu tố nào bạn muốn. Tôi không thấy cách giới thiệu lỗi để đánh giá thấp của bạn là hữu ích.

Answer 2

Một ý tưởng cho tốc độ là chuyển đổi độ dài/lat phối hợp thành tọa độ 3D (x, y, z). Sau khi tiền xử lý các điểm, sử dụng khoảng cách Euclide giữa các điểm như một phần dưới của tính toán nhanh chóng của khoảng cách thực tế.

Answer 3

Để có tốc độ tối đa, bạn có thể tạo một cái gì đó như là rainbow table cho khoảng cách tọa độ. Có vẻ như bạn đã biết khu vực mà bạn đang làm việc, vì vậy có vẻ như việc tính toán trước chúng có thể khả thi. Sau đó, bạn có thể tải kết hợp gần nhất và chỉ sử dụng kết hợp đó.

Ví dụ: ở lục địa Hoa Kỳ, kinh độ là khoảng 55 độ và vĩ độ là 20, tổng số là 1100 điểm. Khoảng cách giữa tất cả các kết hợp có thể là handshake problem được trả lời bởi (n-1) (n)/2 hoặc khoảng 600k kết hợp. Điều đó có vẻ khá khả thi để lưu trữ và truy xuất. Nếu bạn cung cấp thêm thông tin về yêu cầu của mình, tôi có thể cụ thể hơn.

Answer 4

Vì khoảng cách là tương đối nhỏ, bạn có thể sử dụng xấp xỉ khoảng cách equirectangular. Phép tính xấp xỉ này nhanh hơn việc sử dụng công thức Haversine. Vì vậy, để có được khoảng cách từ điểm tham chiếu của bạn (lat1/lon1) đến điểm bạn đang thử nghiệm (lat2/lon2), hãy sử dụng công thức bên dưới. Lưu ý quan trọng: bạn cần phải chuyển đổi tất cả các điểm vĩ độ/điểm ảnh thành radian:

R = 6371 // radius of the earth in km 
x = (lon2 - lon1) * cos(0.5*(lat2+lat1)) 
y = lat2 - lat1 
d = R * sqrt(x*x + y*y) 

Vì 'R' bằng km, khoảng cách 'd' sẽ là km.

Tham chiếu: http://www.movable-type.co.uk/scripts/latlong.html

Answer 5

Vui lòng sử dụng mã sau.

def distance(lat1, lng1, lat2, lng2): 
    #return distance as meter if you want km distance, remove "* 1000" 
    radius = 6371 * 1000 

    dLat = (lat2-lat1) * math.pi/180 
    dLng = (lng2-lng1) * math.pi/180 

    lat1 = lat1 * math.pi/180 
    lat2 = lat2 * math.pi/180 

    val = sin(dLat/2) * sin(dLat/2) + sin(dLng/2) * sin(dLng/2) * cos(lat1) * cos(lat2)  
    ang = 2 * atan2(sqrt(val), sqrt(1-val)) 
    return radius * ang