如何使用 KDTree.query_ball_tree 在 x,y 网格中查找点集 [英] How to find set of points in x,y grid using KDTree.query_ball_tree

问题描述

我在 python 中工作，我有一个 x,y 网格，它们是 numpy 数组.我需要为网格中的每个点 (x1,y1) 找到与 (x1,y1) 相距 r 的点.Scipy 有一个函数 KDTree.query_ball_tree，它将一个 KD Tree 对象(可以从 numpy 数组构造)和一个距离 r 作为输入，但我无法理解它是如何工作的.

I am working in python and I have a x,y mesh grid which are numpy arrays. I need to find for each point (x1,y1) in the grid, the points which are present at a distance r from (x1,y1). Scipy has a function KDTree.query_ball_tree which takes as input, a KD Tree object (which can be constructed from the numpy arrays) and a distance r, but I am not able to understand how it works.

例如，请考虑以下几点:

For example, consider the following points below:

[(1, 1), (2, 1), (3, 1), (4, 1), (1, 2), (2, 2), (3, 2), (4, 2), (1, 3), (2, 3), (3, 3), (4, 3), (1, 4), (2, 4), (3, 4), (4, 4)]`

我想找到距离(1,1) 2 处的所有点.输出应该是:

I want to find all the points which are at a distance 2 from (1,1). The the output should be:

[(1,2),(1,3),(2,1),(3,1)]

我使用 KDTree 是因为，我想避免遍历网格的 for 循环，因为网格是 601x90 (YxX)，如果使用 for 循环，它在时间上不会是最佳的.有人可以为我提供一个示例来说明我的情况 KDTree.query_ball_tree 吗?

I am using KDTree because, I want to avoid for loops for traversing the grid, because the mesh grid is 601x90 (YxX) and it will not be optimum in time, if for loops are used. Can someone provide me with an example illustrating KDTree.query_ball_tree for my situation?

推荐答案

如果您要查找单个点距离内的所有点，请使用 scipy.spatial.KDTree.query_ball_point 不是 query_ball_tree.当您需要将组点相互比较时使用后者.

If you are looking for all points close within a distance of a single point, use scipy.spatial.KDTree.query_ball_point not query_ball_tree. The latter when you need to compare sets of points against each other.

import numpy as np
from scipy.spatial import KDTree

pts = np.array([(1, 1), (2, 1), (3, 1), (4, 1), (1, 2), (2, 2), (3, 2), (4, 2), (1, 3), (2, 3), (3, 3), (4, 3), (1, 4), (2, 4), (3, 4), (4, 4)])

T = KDTree(pts)
idx = T.query_ball_point([1,1],r=2)
print pts[idx]

返回

[[1 1]
 [2 1]
 [1 2]
 [2 2]
 [1 3]
 [3 1]]

请注意，您的输出还必须包括点 (1,1)，因为它与目标的距离为零.

Note that your output must include the point (1,1) as well since that is a distance of zero from your target.

这篇关于如何使用 KDTree.query_ball_tree 在 x,y 网格中查找点集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！