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

Question

如果您查看 k-d trees 的维基百科条目, 你会看到这个 illustration将二维空间划分为矩形的点和平面。

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

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

Answer 1

感谢 eh9 的编辑。只是为了澄清输入是由一组随机点构造的 k-d 树，输出是结果矩形的集合。

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