Поиск массива точек в определенном радиусе
Уфф, давно я не был на DTF. Появился у меня тут вопрос.
В общем задача такая, есть массив точек (x, y), далее мне нужно получить массив точек который лежит в пределах определенного радиуса(расстояния) с определенным центром. Изначальный массив может быть довольно большим, по этому обычный перебор массива и проверка расстояния от точки до точки не подходит из за своей медленности.
Я ищу быстрый алгоритм для решения этой задачи, сейчас склоняюсь к K-D Tree, но хотелось бы получить еще каких-нибудь интересный алгоритмов решения данной задачи.
Всем спасибо!
UDP: Как оказалось и на DTF сидят умные люди. Спасибо все за советы, спасибо что спасли от изучений k-d дерева.
UPD2: Если что уточню. Мне нужно найти точки который находятся в определенном радиусе от координат игрока. Искать это будет сервер, для каждого игрока. Примерно до 20 раз в секунду, нужно искать точки(x,y).
При этом элементы в массив могут добавляться и удаляться.
Уфф, давно я не был на DTF
В общем задача такая, есть массив точек (x, y)й.
Тупо, но почему-то смешно
я бы посоветовал перед построением kd дерева (потому что это алгоритм не для новичков) попробовать просто кластеризировать свой массив. т к. у тебя пространство двумерное, то сделай сетку пространства и по квадрантам определяй свои точки. т. е. ты на начальном этапе получишь квадранты и наборы точек для каждого из них. когда точка будет передвигаться - меняй ее квадрант.
а когда надо будет найти точки в радиусе, то просто определяй квадранты в которых нужно искать. ты получишь не большой набор точек до которых нужно будет посчитать расстояние. здесь можно прикинуть сложность и замерять время.
если решение подойдет по времени, то не нужно деревьев.
А можете рассказать, чем это будет отличаться от KD-дерева в 2D пространстве?
То, что вы описали - очень похоже как раз на него, просто другими словами с:
Чет я не очень понял, каким образом проход по массиву с проверкой элементарного условия (O(n)) может не подходить из-за медлительности. Но при этом ты хочешь строить k-d дерево, сложность чего больше.
Элементарное условие? Для двумерного случая для каждой точки по 2 сложения и возведение в квадрат и ещё 1 сложение после этого. Я чертила по образованию, могу хуйню нести, но разве это не O(n**2)?
А как выше написали, кд — н*лог(н)