4

如果您查看kd trees的 Wikipedia 条目,您将看到将 2D 空间划分为矩形的点和平面的图示。

我的问题是如何获得结果矩形集?我认为到叶节点的每条“路径”都可能给我一个界限。对于任意深度的 N 个点,是否有一种通用的方法可以做到这一点?

请注意,我不要求的是超矩形结构的 kd 树,其中给定的输入是一组矩形,然后可以查询这些矩形进行范围搜索等。我的输入是一组随机点,我想输出完全“镶嵌”或细分笛卡尔空间的一组矩形。

4

2 回答 2

0

许多 kD-Trees 实际上存储了每个子树/叶子的边界超矩形,以便在 KNN 搜索中进行更好的修剪。请注意,这些不是覆盖所有空间的矩形,而是在没有任何点的叶子之间留下间隙。我个人认为它们更酷;-)

于 2012-12-14T20:56:39.743 回答
0

感谢 eh9 的编辑。只是为了澄清输入是由一组随机点构成的 kd 树,输出是一组结果矩形。

并感谢 Jerdak 的“简单”解决方案:实际上,只需从根节点开始沿着树向下走,并在每个轴深度处继续分割矩形。唯一的附加信息是原始矩形的外部边界。访问完所有节点后,您可以返回完整的集合。

于 2012-11-20T23:49:19.757 回答