如何在 scipy KDTree 中找到位置两个半径之间的点

Question

我在 KDTree 对象中有一组位置，我需要有效地找到距离大于 r1 但小于 r2 距离的点

有没有比以下更好的方法：

idx_1 = kd_tree.query_ball_point(pos, r1)
idx_2 = kd_tree.query_ball_point(pos, r2)
# ...
idx_n = kd_tree.query_ball_point(pos, rn)

然后迭代所有列表并弹出索引或迭代每个点并检查范围？

KDTree.query()

将提供索引及其距离，但您必须指定要返回的点数，这是不可预测的。

编辑：我想我找到了一种通过此解决方案划分索引的简单方法：使用唯一条目获取两个列表之间的差异

但仍然需要多次运行 KDTree.query_ball_point()

Answer 1

您没有描述业务领域的任何方面 这会激发您的用例。

WLOG 让我们考虑一些二维靶心。 给定 r1=40 和 r2=50，我们寻找一个未知数 宽度为十的圆环中的匹配点。

将一个圆放到 X 轴上，以 (45, 0) 为中心。 选择一些方便的半径，大于五。 Theta 为零，即指向 X 轴。 增加 theta，这样我们就可以删除另一个这样的圆， 完全覆盖环面的下一部分。 继续删除循环搜索区域，直到 我们又回到了起点。 对每个人发出

.query_ball_point()

查询， 并通过

r1 < r < r2

进行筛选，得到最终结果。

在更高维度的空间中，这可能会导致 令人烦恼的大量查询， 这可能是通过稀疏体积来平衡的 提供零结果点。 仅基于 OP 中概述的假设， 目前尚不清楚这种方法是否会 与简单的差异相比，会获胜 一对结果集。