如何在kd树中最佳存储线段

Question

8

我知道kd树通常用于存储点，但我想存储线条。是否最好在每个交点处拆分线条以与kd树的分割相匹配？或者只将端点存储到kd树中是否足以找到最近的邻居？

- newDelete

这取决于你想做什么。请记住，一条线（线段）只是两个坐标的集合，因此它可以用单个坐标描述，具有两倍的维数。因此，您可以将线路存储为高维kd树中的点。 - Oliver Charlesworth

我正在尝试使用线段创建距离场。因此，我将利用kd树的最近邻功能。但是，我不想添加比我已有的数据更多的数据（即线段的端点）。 - newDelete

3个回答

0

你必须使用kd-tree吗？对于扩展的基元，bv-tree可能更有效率。

- atb

0

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

另一方面，如果你不使用SAH或任何其他算法来遍历树，你可以自由地处理kd-tree的原始想法。但是，如果你被绑定到一些传统算法，你就必须分割线条。你必须这样做，因为树的每个叶子都有一个权重（我猜在你的情况下，它取决于其中线条的长度）。

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

- avp

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

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

- Has QUIT--Anony-Mousse · Accepted Answer

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

在这里，R*-tree (Wikipedia)可能是更好的选择。它真正为具有空间扩展的对象设计。如果您查阅相关出版物，他们甚至尝试了不同的复杂对象近似方法；例如是否值得将其三角化、使用外接圆球、边界框等，有趣的是，在某些情况下，据我所知，五角形提供了最佳性能。

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