这个算法的名称是什么？并且是否有numpy/scipy实现？

Question

9

动机：

我看到过这种算法的描述，如果有标准实现，我不想重复造轮子。我也了解到，如果有scipy/numpy的实现，通常比我自己在python中编写的任何东西都要快得多。

我有许多平面上的点（几百万个）。从一个包含所有点的大框开始，我想将框连续细分为相等面积的子框。只要子框中至少有1,000个点，就会递归地进行细分。该算法返回描述细分和每个叶节点上点的映射的树。

这种算法的名称是什么（类似于分治算法？），当给定一个2D numpy点数组时是否有标准方法可以使用？

- Hooked

如果分割是在一个维度上进行的，则为N-kD树（对于N=2）。此外，分割应该这样做，使得两个部分的人口规模（大约）相等。 - wildplasser

从计算的角度来看，我同意您关于按相等大小的人口分割（以获得最小树深度）的观点。然而，我正在尝试复制一篇论文的结果，他们正是按照我所说的按相等“面积”进行分割。@wildplasser - Hooked

哎呀，那看起来很丑。但至少当大小 < 1000 时它们停止分裂。顺便说一句：更好的方法是在 N-1 D 超平面上分割（垂直于由点形成的超椭球体的主轴）。 - wildplasser

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ted Hopp · Accepted Answer

这被称为四叉树分区。关于Python代码，请参见此线程。

根据Joe Kington的评论，看一下scipy.spatial.KDTree和/或scipy.spatial.cKDTree。