Алгоритм сортировки массива точек в трехмерном пространстве относительно заданной?

Question

[MPetukhov]

Приветствую!
Существует ли быстрый алгоритм сортировки массива точек в трехмерном пространстве относительно заданной?

Дано:
Точка (x, y, z)
Массив точек с координатами

Задача отсортировать массив по возрастанию расстояния от Точки.

Добавил:
Будет ли сортировка по AB = |xb - xa| + |yb - ya| + |zb - za| верной?

Comments

[Миша Кринкин]

@MPetukhov по-поводу вашего добавления, сортировка по манхэттенскому расстоянию не эквивалентна сортировке по евклидовому расстоянию, посмотрите хотя бы на точки (0,0,0), (5,5,5), (13,1,1) по вашей формуле последние точки равны относительно первой.

Answer 1

[throughtheether]

Существует ли быстрый алгоритм сортировки массива точек в трехмерном пространстве относительно заданной?

Я не знаю, что вы подразумеваете под словом "быстрый", но мои соображения таковы:
1) определить расстояние от каждой из n точек до заданной - O(n) (даже Θ(n)). Я не вижу здесь потенциала для фундаментального улучшения.
2) отсортировать массив - O(n*logn) в лучшем случае.
Итого - O(n)+O(n*logn)=O(n*logn).

Другое дело, что если входные данные имеют специфическую структуру, то можно, при соответствующем подходе, понизить (или попытаться понизить) "константы" O-нотации и соответственно время выполнения.

Comments

[Сергей Протько]

Ускорить можно только за счет паралелизма, устранения зависомостей по данным в алгоритме (по сути их там и нету особо), векторизация инструкций...

[MPetukhov]

Я боюсь что при большом количестве точек вычисление расстояния для пар точек по формуле
AB = √(xb - xa)2 + (yb - ya)2 + (zb - za)2 с последующей сортировкой будет узким местом.
Сортировка будет использована на веб странице в интерфейсе выбора значения.

[Миша Кринкин]

@MPetukhov ну корень извлекать совсем не обязательно, можно сравнивать квадраты расстояний.

[throughtheether]

Я боюсь что при большом количестве точек вычисление расстояния для пар точек по формуле AB = √(xb - xa)2 + (yb - ya)2 + (zb - za)2 с последующей сортировкой будет узким местом.

Если бы передо мной стояла задача ускорить подобные вычисления, я бы задумался о:
1) применении "функции Кармака" (fast inverse square root)
2) вычислении расстояния между точками тригонометрически, через соответствующие прямоугольные треугольники. Представляется разумным использовать целочисленные координаты, значения тригонометрических функций использовать из заранее подготовленных таблиц.
3) применении сферической системы координат
4) разделении пространства на "зоны" ("луковые слои") в зависимости от близости к заданной точке. Точки внутри одной зоны не сортировать (если это приемлемо). Сортировать точки в соответствии с номером зоны, в которые они входят.

[throughtheether]

Если само значение расстояния не требуется, то поддерживаю @kmu1990

[MPetukhov]

а без квадратов? Будет ли сортировка по AB = |xb - xa| + |yb - ya| + |zb - za| верной?

[Миша Кринкин]

@MPetukhov читайте комментарий к свою вопросу, на эту тему я уже отписался

[MPetukhov]

Спасибо

[Миша Кринкин]

@MPetukhov касательно этого:

> Я боюсь что при большом количестве точек вычисление расстояния для
> пар точек по формуле
> AB = √(xb - xa)2 + (yb - ya)2 + (zb - za)2 с последующей сортировкой будет > узким местом.
> Сортировка будет использована на веб странице в интерфейсе выбора
> значения.

при большом числе точек, даже если брать корень подсчет расстояний по сравнению с сортировкой не будет такой уж большой проблемой (конечно все зависит от числа точек).

[throughtheether]

а без квадратов? Будет ли сортировка по AB = |xb - xa| + |yb - ya| + |zb - za| верной?

Эта сортировка будет верной, если вас интересует "Манхэттенское" растояние, а не евклидово. Трудно судить, насколько корректно использовать подобную метрику, не зная о цели ее использования.

Вообще, я бы на вашем месте реализовал "наивное" вычисление евклидова расстояния (или его квадрата) вкупе с сортировкой и потом уже оценивал, насколько это решение адекватно задаче в терминах производительности.

[MPetukhov]

Всем спасибо! В голове сложилось направление в котором копать

Answer 2

[Виталий Желтяков]

Вычисляете расстояние до каждой точки и сортируете, как Вам угодно. Ничего сложного