У меня есть небольшой вариант алгоритма "найти k ближайших соседей", который включает в себя отклонение тех, которые не удовлетворяют определенному условию, и я не могу придумать, как это сделать эффективно.
Мне нужно найти k ближайших соседей, которые находятся на линии прямой видимости. К сожалению, scipy.spatial.cKDTree
не предоставляет возможности поиска с фильтром для условного отклонения баллов.
Лучший алгоритм, который я могу придумать, - это запросить n ближайших соседей, и если нет k, находящихся в зоне прямой видимости, снова запросить 2n ближайших соседей и повторить. К сожалению, в худших случаях это означало бы повторное вычисление n ближайших соседей. Чем больше раз мне приходится повторять этот запрос, тем хуже ухудшается производительность. С другой стороны, установка слишком большого значения n потенциально бесполезна, если большая часть возвращаемых баллов не нужна.
Линия обзора часто меняется, поэтому я тоже не могу каждый раз пересчитывать cKDTree
. Какие-либо предложения?