Поиск массива точек в определенном радиусе
Уфф, давно я не был на DTF. Появился у меня тут вопрос.
В общем задача такая, есть массив точек (x, y), далее мне нужно получить массив точек который лежит в пределах определенного радиуса(расстояния) с определенным центром. Изначальный массив может быть довольно большим, по этому обычный перебор массива и проверка расстояния от точки до точки не по…
KD-дерево как вариант, конечно
Но можно посмотреть в сторону VP-дерева - сам с ним не работал, но этот принцип можно использовать для предварительного разбиения пространства в KD-дереве
С другой стороны, если объем данных небольшой, то поиск в лоб по предварительно отсортированному массиву тоже может дать хороший результат и не будет излишне медленным
Плюс еще возникают вопросы по самой проблеме:
1. Сколько ожидается в среднем точек?
2. Будут ли они добавляться/удаляться из изначального массива точек?
3. Как часто будет происходить добавление/удаление?
4. Как часто нужно находить точки в радиусе?
На данный момент выглядит так, словно О(n) не есть плохо
если я не ошибаюсь, kd дерево подходит для 3д пространства, в условии 2д.
к тому же, kd дерево не обязательно будет построено по принципу удаленности. но подобная кластеризация может быть довольно полезна, да