Bạn có thể nhận được một ước tính trên nhanh trên giới hạn trên khoảng cách sử dụng khoảng cách Manhattan (được chia tỷ lệ cho vĩ độ), điều này sẽ đủ tốt để từ chối 99,9% ứng cử viên nếu họ không ở gần (EDIT: kể từ đó bạn hãy cho chúng tôi biết họ đang ở gần. Trong trường hợp đó, số liệu của bạn phải là khoảng cách bình phương, theo nhận xét của Lars H). Hãy xem xét việc này tương đương với việc từ chối bất cứ điều gì bên ngoài một hộp hình chữ nhật hình cầu (như một xấp xỉ với một vòng tròn bao quanh hộp). tôi không làm Ruby vì vậy đây là thuật toán với giả:
Hãy vĩ độ, kinh độ của điểm tham chiếu P (pa, po) của bạn và điểm X khác (xa, xo). Precompute ka, hệ số chia tỷ lệ cho khoảng cách theo chiều dọc: ka (= cos (pa in °)). (Đúng ra, ka = liên tục là một xấp xỉ tuyến tính trong vùng lân cận của P.)
Sau đó, ước lượng khoảng cách là: D(X,P) = ka*|xa-pa| + |xo-po| = ka*da + do
nơi | z | có nghĩa là abs (z). Tại tồi tệ nhất, điều này đánh giá quá cao khoảng cách thực sự bởi hệ số √2 (khi da == làm), do đó chúng tôi cho phép như sau:
Thực hiện tìm kiếm và giữ Dmin, khoảng cách nhỏ nhất thứ năm-Manhattan-distance- ước tính. Do đó bạn có thể từ chối trả trước tất cả các điểm mà D (X, P)> √2 * Dmin (vì chúng phải cách xa ít nhất √ ((ka * da) ² + do²) - điều đó sẽ loại bỏ 99,9% điểm). Giữ một danh sách tất cả các điểm ứng cử viên còn lại với D (X, P) < = √2 * Dmin. Cập nhật Dmin nếu bạn tìm thấy hàng đợi thứ tự ưu tiên nhỏ thứ năm D. hoặc danh sách (coord, D) là cấu trúc dữ liệu tốt. Lưu ý rằng chúng tôi không bao giờ tính khoảng cách Euclide, chúng tôi chỉ sử dụng phép nhân nhân và phép cộng.
(Xem xét tương tự này để quadtree trừ lọc ra tất cả mọi thứ ngoại trừ các khu vực mà bạn quan tâm chúng ta, do đó không cần phải tính toán khoảng cách chính xác trả trước hoặc xây dựng cấu trúc dữ liệu.)
Nó sẽ giúp đỡ nếu bạn cho chúng tôi biết sự lây lan dự kiến Trong tất cả các điểm gần, yếu tố in2 trong bộ ước lượng này sẽ quá thận trọng và đánh dấu mọi điểm là ứng cử viên, một ước tính khoảng cách dựa trên bảng tra cứu sẽ thích hợp hơn.)
Mã giả:
initialize Dmin with the fifth-smallest D from the first five points in list
for point X in list:
if D(X,P) <= √2 * Dmin:
insert the tuple (X,D) in the priority-queue of candidates
if (Dmin>D): Dmin = D
# after first pass, reject candidates with D > √2 * Dmin (use the final value of Dmin)
# ...
# then a second pass on candidates to find lowest 5 exact distances
Nếu nó là vài điểm nó là ok để đi từng người một. – Andrey
Bất kể bạn chọn thuật toán nào, bạn có thể tiết kiệm thời gian bằng cách so sánh khoảng cách bình phương thay vì khoảng cách thực tế. Không cần phải thực hiện các thao tác căn bậc hai nếu bạn không cần biết khoảng cách thực tế. –