Поиск всех точек в определенном радиусе другой точки

Question

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

Позвольте мне бросить картину здесь для лучшего понимания проблемы:

Теперь проблема не о вычислении расстояния. Я знаю, как это сделать.

Сначала у меня было около 10 баллов, и я мог просто проверить каждую комбинацию, но, как вы уже можете предположить, это крайне неэффективно с увеличением количества очков. Что, если бы у меня было всего миллион очков, но все они были бы очень далеки друг от друга?

Я пытаюсь найти подходящую структуру данных или способ взглянуть на эту проблему, поэтому каждая точка может учитывать только их окружающее и не все пространство. Существуют ли для этого известные алгоритмы? Я точно не знаю, как назвать эту проблему, чтобы я мог Google точно, что хочу.

Если вы не знаете такого известного алгорима, все идеи приветствуются.

Answer 1

Вы по-прежнему придется повторять через каждую точку, но есть два оптимизаций вы можете выполнить:

1) Вы можете устранить очевидные моменты, проверяя, если x1 < радиус и если y1 < Радиус (как и Брент, уже упоминавшийся в другом ответе).

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

Это, вероятно, лучшее качество, которое вы получите.

Answer 2

Если бы вы могли отсортировать эти точки по значениям x и y, вы могли бы быстро выбрать эти точки (бинарный поиск?), Которые находятся в ящике центральной точки: x + - r, y + - р. Когда у вас есть это подмножество точек, вы можете использовать формулу расстояния, чтобы увидеть, находятся ли они в радиусе.

Answer 3

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

https://en.wikipedia.org/wiki/K-d_tree

Answer 4

разбиение пространства, что вы хотите .. https://en.wikipedia.org/wiki/Quadtree

Answer 5

Это проблема range searching. Более конкретно - 2-мерный круглый диапазон проблема.

Цитируя "Solving Query-Retrieval Problems by Compacting Voronoi Diagrams" [Aggarwal, Hansen, Leighton, 1990]:

• Вход: Множество Р из п точек в плоскости E² евклидовой
• Запрос: Найти все точки P, содержащихся в диске в E² с радиус r с центром в q.

Наилучшие результаты были получены в "Optimal Halfspace Range Reporting in Three Dimensions" [Afshani, Chan, 2009]. Их метод требует O (n) пространственной структуры данных, которая поддерживает запросы в O (log n + k) в худшем случае. Структура может быть предварительно обработана рандомизированным алгоритмом, который выполняется в ожидаемом времени O (n log n). (n - количество входных точек, k - количество выходных точек).

Библиотека CGAL поддерживает запросы поиска по круглому диапазону. См. here.