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

Question

我知道 kd-trees 传统上用于存储点，但我想存储线。最好在每个交叉点分割线与 kd 树的分割吗？或者将端点存储到 kd-suffix 中是否足以用于最近邻查找？

Answer 1

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

R*-tree (Wikipedia)这里可能是更好的选择。它确实是为具有空间延伸的对象而设计的。如果您查看相关出版物，他们甚至尝试了复杂对象的不同近似；例如，是否将它们三角化、使用外 catch 面、边界框以及有趣的 IIRC 是否值得，5 角多边形在某些情况下提供了最佳性能。

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