如何最好地存储kd树中的行

Question

我知道kd-tree传统上用于存储点,但我想存储线.是否最好在每个交叉点拆分kd-tree的分割线？或者只将端点存储到kd中以便最近邻找到？

Answer 1

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

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

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