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

Question

4

如果你查看k-d树的维基百科条目，你会看到这个插图，它将点和平面分割成矩形。

我的问题是如何获得矩形的结果集？我认为每个通向叶节点的“路径”可能会给我边界。是否有一般的方法可以对任意深度的N个点进行此操作？

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

- Progger

这里似乎有两个问题。您是在寻找一个从随机点集构建k-d树的算法，还是一个给定k-d树并枚举划分矩形集合的算法？还是两者都需要？ - eh9

1

k-d树通常不存储矩形，而是存储分割轴。您可以通过编写一小段矩形分割代码来实现这一点，基本上将每个节点沿着分割轴切割的2D矩形传递给子节点，从而轻松实现此操作。 - Jerdak

2个回答

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

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

- Progger · Answer 1

感谢eh9的编辑。只是为了澄清，输入是从一组随机点构建的k-d树，输出是生成的矩形集合。

同时感谢Jerdak提供的“平凡”解决方案：实际上只需要从根节点开始遍历整棵树，并在每个轴深度处分割矩形。唯一额外的信息是原始矩形的外界边界。一旦访问完所有节点，就可以返回完整的集合。

- jkflying · Answer 2

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