Làm thế nào để ước tính khoảng cách Euclide trên mặt phẳng nguyên, không tràn?

Question

Tôi đang làm việc trên nền tảng chỉ có số học số nguyên. Ứng dụng sử dụng thông tin địa lý và tôi đại diện cho các điểm theo các tọa độ là (x, y) trong đó x và y là khoảng cách tính bằng mét. Là một xấp xỉ, tôi muốn tính toán khoảng cách Euclide giữa hai điểm. Nhưng để làm điều này tôi phải có khoảng cách vuông, và với số nguyên 32 bit, khoảng cách lớn nhất tôi có thể đại diện là 32 km. Không tốt. Nhu cầu của tôi nhiều hơn theo thứ tự 1000 km. Nhưng tôi muốn có thể giải quyết khoảng cách trên thang đo nhỏ hơn 30 mét.

Do đó câu hỏi của tôi: làm cách nào tôi có thể tính toán khoảng cách Euclide, chỉ sử dụng số học số nguyên, không tràn, trên khoảng cách có ô vuông không vừa với một từ?

ETA: Tôi muốn có thể tính toán khoảng cách, nhưng tôi có thể giải quyết để có thể so sánh chúng.

Answer 1

Có lẽ so sánh octagonal distance approximation là đủ?

Hơi cập nhật hơn là this article on fast approximate distance functions.

Answer 2

Tôi sẽ rời khỏi hình vuông khi phát, để tôi có thể ước tính khoảng cách Euclide. Tuy nhiên, khi so sánh khoảng cách, phương pháp này mang đến cho bạn độ chính xác 100%, vì so sánh sẽ giống nhau nếu bạn bình phương khoảng cách.

Tôi khá chắc chắn về điều đó, vì tôi đã sử dụng cách tiếp cận đó khi tìm kiếm những người hàng xóm gần nhất trong không gian chiều cao. Bạn có thể kiểm tra mã của tôi và lý thuyết trong kd-GeRaF.