geometry - 如何从 kd 树中获取矩形集？

Question

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

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

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

Answer 1

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

Answer 2

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

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