Thuật toán để tính toán khoảng cách giữa nhiều điểm địa lý

Question

Tôi có ma trận có khoảng 1000 điểm không gian địa lý (Kinh độ, Vĩ độ) và tôi đang cố gắng tìm các điểm nằm trong phạm vi 1KM.

LƯU Ý: "Những điểm là năng động, Imagine 1000 xe đang di chuyển, vì vậy tôi phải tất cả các khoảng cách mỗi vài giây tính toán lại"

tôi đã làm một số tìm kiếm và đọc về các thuật toán đồ thị tương tự (Floyd- Warshall) để giải quyết điều này, và tôi đã kết thúc với nhiều từ khóa, và bây giờ tôi đã mất. Tôi đang xem xét hiệu suất và vì bán kính tìm kiếm ngắn, tôi sẽ không xem xét độ cong của trái đất.

Về cơ bản, Có vẻ như tôi phải tính khoảng cách giữa mọi điểm đến mọi điểm khác rồi sắp xếp khoảng cách bắt đầu từ mọi điểm trong ma trận và nhận được các điểm nằm trong phạm vi của nó. Vì vậy, nếu tôi có 1000 tọa độ, tôi phải hoàn thành quá trình này (1000^2-1000) lần và tôi không tin đây là giải pháp tối ưu. Cảm ơn bạn.

Answer 1

Trong trường hợp của bạn, bạn nên xem GeoHash cho phép bạn nhanh chóng truy vấn các tọa độ trong một khoảng cách nhất định.

FYI, MongoDB sử dụng geohash trong nội bộ và hoạt động xuất sắc.

Answer 2

Bạn có thể tính toán mã địa lý có phạm vi 1km xung quanh mỗi 1000 toạ độ đó và kiểm tra xem một số điểm có nằm trong phạm vi đó hay không. Có thể nó không phải là tối ưu, nhưng bạn sẽ tiết kiệm cho mình một số phân loại.

Answer 3

Nếu bạn thực hiện một modell với một mạng lưới các 1km khoảng cách:

0 1 2 3 
___|____|____|____ 
0 | | | 
    c| b|a | d 
___|____|____|____ 
1 | | | 
    | |f | 
___|e___|____|____ 
2 | |g | 

chúng ta hãy giả định điểm khởi đầu của bạn là một. Nếu lưới của bạn có kích thước 1km, các điểm trong phạm vi 1km phải ở trong cùng một ô hoặc một trong 8 hàng xóm (Điểm b, d, đ, f).

Mỗi ô khác có thể bỏ qua (c, g).

Trong khi d gần bằng khoảng cách tương tự với c, c có thể bị bỏ sớm, vì có 2 rào cản để vượt qua, trong khi a và d nằm trên các khu vực đối diện biên giới của chúng và do đó gần 2 km từ nhau.

Để giảm phần tử sớm, bạn có thể loại trừ, đủ để kiểm tra phần x hoặc y của tọa độ. Vì thuộc về (0,2), nếu x bằng 0 hoặc nhỏ hơn, hoặc> 3, điểm đã nằm ngoài phạm vi.

Sau khi lọc chỉ một vài ứng cử viên, bạn có thể sử dụng tìm kiếm toàn diện.

Answer 4

Nếu bạn muốn tra cứu ma trận cho mỗi điểm so với mỗi điểm thì bạn đã có công thức phù hợp (1000^2-1000). Không có bất kỳ lối tắt nào cho phép tính này. Tuy nhiên khi bạn biết bắt đầu tìm kiếm ở đâu và bạn muốn tìm các điểm trong bán kính 1KM, bạn có thể sử dụng thuật toán lưới hoặc thuật toán không gian để tăng tốc độ tìm kiếm. Nhiều khả năng nó sử dụng thuật toán phân chia và chinh phục và rẻ nhất của nó là đường cong geohash hoặc z. Bạn cũng có thể thử kd-tree. Có lẽ điều này thậm chí còn đơn giản hơn. Nhưng nếu điểm của bạn đang ở trong không gian euklidian thì có phương pháp phẳng này mô tả ở đây: http://en.wikipedia.org/wiki/Closest_pair_of_points_problem.

Chỉnh sửa: Khi tôi nói 1000^2-1000 thì tôi có nghĩa là kích thước của lưới nhưng thực sự là 1000^(1000 - 1)/2 cặp điểm nên ít hơn rất nhiều toán.

Answer 5

Tôi có thứ gì đó tương tự trên trang web mà tôi đã nghiên cứu, tôi nghĩ vậy.Người dùng nhấp vào một vị trí trên bản đồ và đi vào bán kính và hàm trả về tất cả các vị trí trong cơ sở dữ liệu trong bán kính đã cho. Bạn có nghĩa là bạn đang cố gắng tìm các điểm nằm trong phạm vi 1km của một trong các điểm trong bán kính? Hay bạn đang cố gắng tìm những điểm nằm trong phạm vi 1km của nhau? Tôi nghĩ bạn nên làm một cái gì đó như thế này.

radius = given radius 
x1 = latitude of given point; 
y1 = longitude of given point; 
x2 = null; 
y2 = null; 
x = null; 
y = null; 
dist = null; 

for (i=0; i<locationArray.length; i++) { 
    x2 = locationArray[i].latitude; 
    y2 = locationArray[i].longitude; 
    x = x1 - x2; 
    y = y1 - y2; 
    dist = sqrt(x^2 + y^2); 
    if (dist <= radius) 
     these are your points 
} 

Nếu bạn đang cố gắng để tính toán tất cả các điểm có trong vòng 1km điểm khác, bạn có thể thêm một vòng lặp bên ngoài đưa ra các thông tin của x1 và y1, sau đó sẽ làm cho vòng lặp bên trong kiểm tra khoảng cách giữa điểm cho trước và mọi điểm khác cho mỗi điểm trong ma trận của bạn làm đầu vào. Các tính toán sẽ không mất quá nhiều thời gian, vì nó rất cơ bản.

Answer 6

Thử với R-Tree. R-Tree hỗ trợ các hoạt động để tìm tất cả các điểm gần nhất với một điểm nhất định mà không phải là xa hơn một bán kính nhất định. Thời gian thực hiện là tối ưu và tôi nghĩ rằng đó là O (number_of_points_in_the_result).

Answer 7

Tôi đã gặp vấn đề tương tự nhưng trong phát triển dịch vụ web Trong trường hợp của tôi để tránh vấn đề về thời gian tính toán, tôi đã sử dụng một giải pháp chinh phục đơn giản là &: Ý tưởng bắt đầu tính khoảng cách giữa điểm mới và điểm khác trong mỗi lần chèn dữ liệu mới, để ứng dụng của tôi truy cập trực tiếp khoảng cách giữa các điểm kéo đã được tính toán và đặt vào cơ sở dữ liệu của tôi