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

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

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

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

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

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

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

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

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

Спасибо

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

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

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

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

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

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

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