问题陈述:
我在 3D 空间中有 150k 个点,它们的坐标存储在尺寸为 [150k, 3](以毫米为单位)的矩阵中。
我想找到给定点的所有邻居p
在半径范围内r
。我想以最准确的方式做到这一点。
我应该如何选择我的leafsize
范围 ?
from scipy.spatial import KDTree
import numpy as np
pts = np.random.rand(150000,3)
T1 = KDTree(pts, leafsize=20)
T2 = KDTree(pts, leafsize=1)
neighbors1= T1.query_ball_point((0.3,0.2,0.1), r=2.0)
neighbors2= T2.query_ball_point((0.3,0.2,0.1), r=2.0)
np.allclose(sorted(neighbors1), sorted(neighbors2))
True
功能query_ball_point
将为任何版本的搜索树返回正确的点集。这leafsize
参数不会影响查询的结果,只会影响结果的性能。
想象一下下面显示的两棵树具有相同的数据(但叶大小参数不同),并且查询搜索红色圆圈内的所有点。
在这两种情况下,代码只会返回位于红色圆圈内的两个点。这是通过检查与圆相交的树的所有框中的所有点来完成的。这会导致每种情况下的工作量不同(即不同的性能)。对于左边的树(对应于较大的叶子尺寸),算法必须检查 13 个点是否在圆内(6 个位于上部相交框中,7 个位于下部相交框中)。在右侧的树(叶子尺寸较小)中,仅处理三个点(一个位于上部相交框中,两个位于下部相交框中)。
按照这个逻辑,您可能认为始终使用较小的叶子尺寸是有意义的:这将最大限度地减少算法结束时的实际比较数量(确定点是否实际上位于查询区域中)。但事情并不是那么简单:较小的叶子尺寸将生成更深的树,从而增加构建时间和树遍历时间的成本。获得树遍历性能与叶级比较的正确平衡实际上取决于进入树的数据类型以及您正在执行的特定叶级比较。这就是为什么 scipy 提供 leafsize 参数作为参数,以便您可以调整事物以在特定算法上获得最佳性能。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)