Как аппроксимировать евклидово расстояние на целочисленной плоскости без переполнения?

Я работаю над платформой, которая имеет только целочисленную арифметику. Приложение использует географическую информацию, и я представляю точки с помощью координат (x, y), где x и y — расстояния, измеренные в метрах. В качестве приближения я хочу вычислить евклидово расстояние между двумя точками. Но для этого мне нужно возвести расстояния в квадрат, а с 32-битными целыми числами самое большое расстояние, которое я могу представить, составляет 32 километра. Фигово. Мои потребности больше порядка 1000 километров. Но я хотел бы иметь возможность определять расстояния в масштабе менее 30 метров.

Отсюда мой вопрос: как я могу вычислить евклидово расстояние, используя только целочисленную арифметику, без переполнения, на расстояниях, квадраты которых не помещаются в одно слово?

ETA: Я хотел бы иметь возможность вычислять расстояния, но я мог бы согласиться на возможность их сравнения.


euclidean-distance integer-arithmetic
person Norman Ramsey    schedule 18.02.2016    source источник
comment
Вы действительно хотите действительно вычислить расстояния или сравнить расстояния? Надеюсь, вы не убьете котенка, когда увидите мой комментарий. :)   -  person gsamaras    schedule 19.02.2016
comment
@gsamaras Предпочитаю вычислять, но соглашусь на сравнение. Все котята живы и счастливы!   -  person Norman Ramsey    schedule 19.02.2016
comment
Есть ли ограничение по памяти? Я сделал что-то подобное, предварительно вычислив значения в сетке и сохранив их, а затем выполнив приблизительную билинейную интерполяцию.   -  person yhenon    schedule 19.02.2016
comment
В этот ответ SO есть несколько умных алгоритмов.   -  person Raymond Chen    schedule 19.02.2016

Ответы (2)


arrow_upward
2
arrow_downward

Возможно, будет достаточно сравнения восьмиугольного расстояния?

Чуть более актуальной является эта статья о функциях быстрого приблизительного расстояния.

person whybird    schedule 19.02.2016

arrow_upward
0
arrow_downward

Я бы оставил квадрат вне игры, чтобы можно было аппроксимировать евклидово расстояние. Однако при сравнении расстояний этот подход дает вам 100% точность, поскольку сравнение будет таким же, если вы возведете расстояния в квадрат.

Я почти уверен в этом, так как я использовал этот подход при поиске ближайших соседей в многомерных пространствах. Вы можете проверить мой код и теорию в kd-GeRaF.

person gsamaras    schedule 19.02.2016