ближайших k соседей, удовлетворяющих условиям (python)

Question

У меня есть небольшой вариант на «найти k ближайших соседей» алгоритм, который предполагает отказ от тех, которые не удовлетворяют определенному условию, и я не могу придумать, как это сделать это эффективно.

То, что мне нужно, - это найти ближайших соседей, находящихся в текущей линии зрения. К сожалению, scipy.spatial.cKDTree не предоставляет возможность поиска с фильтром для условного отклонения точек.

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

Линия визирования меняется часто, поэтому я не могу повторно пересчитывать cKDTree каждый раз. Какие-либо предложения?

Answer 1

Если вы ищете сосед в прямой видимости, не может использовать метод как

cKDTree.query_ball_point (сам, х, г, р, EPS)

который позволяет запросить KDTree для соседей, находящихся внутри радиуса размера r вокруг x точки массива. Если я не понял ваш вопрос, кажется, что линия визирования известна и эквивалентна этому значению r.