data-structures - 如何在 kd-tree 中最好地存储行

Question

我知道 kd-trees 传统上用于存储点，但我想存储线。用kd-tree的分割在每个交叉点分割线会更好吗？还是仅将端点存储到 kd 中就可以找到最近的邻居？

Answer 1

kd-tree 本身是为点对象设计的。甚至对于盒子、球体或类似的东西也不行。我相信您可以以某种方式使用存储的 6d 树minx, maxx, miny, maxy, minz, maxz；但我不完全确定如何正确查询它。

R*-tree（维基百科）在这里可能是一个更好的选择。它实际上是为具有空间扩展的对象而设计的。如果您查找相关出版物，他们甚至尝试了复杂对象的不同近似值；例如，是否将它们三角化、使用外接球、边界框以及有趣的是 IIRC，5 角多边形在某些情况下提供了最佳性能。

无论如何，R*-tree 家族可能是一个有趣的选择。

Answer 2

好吧，你必须在交叉点上分割线，否则你会遇到树叶的权重问题。

另一方面，如果您不使用 SAH 或任何其他算法来遍历树，您可以根据 kd-tree 的原始想法自由地做任何您想做的事情。但是如果你受限于一些传统的算法，你就不得不分割线。你必须这样做只是因为树的每一片叶子都有一个重量（我想在你的情况下它取决于它的线条长度）。

如果你不分割线，你也会得到错误的叶子重量。不，如果您不拆分行，则应该在该行所属的两个叶子中复制它们。

Answer 3

你必须使用kd-tree吗？对于扩展原语，bv-tree 可能更有效。