Поиск массива точек в определенном радиусе
Уфф, давно я не был на DTF. Появился у меня тут вопрос.
В общем задача такая, есть массив точек (x, y), далее мне нужно получить массив точек который лежит в пределах определенного радиуса(расстояния) с определенным центром. Изначальный массив может быть довольно большим, по этому обычный перебор массива и проверка расстояния от точки до точки не по…
я бы посоветовал перед построением kd дерева (потому что это алгоритм не для новичков) попробовать просто кластеризировать свой массив. т к. у тебя пространство двумерное, то сделай сетку пространства и по квадрантам определяй свои точки. т. е. ты на начальном этапе получишь квадранты и наборы точек для каждого из них. когда точка будет передвигаться - меняй ее квадрант.
а когда надо будет найти точки в радиусе, то просто определяй квадранты в которых нужно искать. ты получишь не большой набор точек до которых нужно будет посчитать расстояние. здесь можно прикинуть сложность и замерять время.
если решение подойдет по времени, то не нужно деревьев.
А можете рассказать, чем это будет отличаться от KD-дерева в 2D пространстве?
То, что вы описали - очень похоже как раз на него, просто другими словами с: