Есть плоскость XY, на ней множество точек A1...An , координаты всех известны.

Задача: для заданной новой точки B с координатами X1, Y1 определить все точки, попадающие в круг с центром (X1, Y1) радиусом R, и отсортировать по возрастанию расстояния.

Перебор не подходит, исходное множество велико - медленно.

Какие еще варианты? Какие-то вариации BSP, может?

Используй квадраты

ох уж эти скучающие математики

(1) квантовать всю плоскость в квадраты и индексировать?

(2) это практическая задача

https://yandex.ru/search/?clid=2186620&text=наличие%20точки%20в%20круге&lr=9&redircnt=1591087287.1

(5) это рядом, но не совсем то. Из того, что предлагает яндекс, можно организовать только перебор. Перебор неприемлем в данном случае, уж лучше действительно квантовать плоскость, найти квадрат, в котором новая точка, и собрать точки из соседних. Погрешность более допустима, чем перебор.

(3)
Сначала выбрать точки, которые попали в квадрат с вершинами (X1-R, Y1-R) - (X1+R, Y1+R)
Потом посчитать точное расстояние для входящих точек.

(3) С учетом R

(7) для этого надо перебрать все точки и вычислить, попали ли они в квадрат. Т.е. опять перебор/

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

(9) Сначала ЗАПРОСОМ выбрать точки, которые попали в квадрат с вершинами (X1-R, Y1-R) - (X1+R, Y1+R). Условие на простое неравенство без сложных вычислений

(6) Если погрешность тогда полярные координаты по сетке.
Делаешь сетку из точек.
Заранее для всех точек находишь их полярные координаты принимая точки сетки за центр.
Далее банально для X1, Y1 берешь ближайшую точку сетки и готово.

в PostgreSQL есть готовые типы данных и библиотеки для решения подобных задач

(9) Используйте базу постгре с дополнением - там можно запросом быстро выбирать нужную вам информацию.

(13) Дай пять!

в мс скл тип геоданных появился задолго о постгреса

в 1с для такой задачи можно задействовать "новый" функционал решения слау. а для решения "квадратами" подойдет механизм анализ данных.кластеризация.

в MySQL есть функции для сабжа, работают с типом "геометрия"

(0) твоя зада решается совмещением двух патентов "строй и престраивай" и "разделяй и властвуй".
Почитай "Триангуляция Делона" - я реализовывал, алгоритм не очень сложный...

(0) Попробуй копнуть в сторону полярных координат.

(18) квадраты самое лучшее...

банально
1. быстрая проверка прямо в запросе "если (х в диапазоне х_точки-радиус и х_точки+радиус) И (у в диапазоне у_точки-радиус и у_точки+радиус)"
2. дальше вторая итерация с перебором точек которые прошли первое условие

(0) https://github.com/nmslib/hnswlib

(20) нет .это аппроксимация. подошла бы для ближайших к окружности