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

我知道kd-tree传统上用于存储点，但我想要存储行。将kd-tree分裂的每个交叉点分割线最好吗？或者只是将端点存储到kd中就足以用于最近的邻居发现？如何在kd-tree中最好地存储行

2010-10-28 newDelete

这取决于你想要做什么。记住一条线（段）只是两个坐标的集合，所以它可以用一个单一的坐标来描述，其尺寸是其两倍。因此，可以将线存储为高维kd树中的点。 – 2010-10-28 23:26:06

我正尝试用线条创建一个距离场。所以我会利用kd-tree的最近邻居功能。但是，我不想添加比我拥有更多的数据（线段的终点。 – newDelete 2010-10-31 18:19:40

那么，你必须在十字路口上分割线条，否则你会遇到树叶重量的问题。另一方面，如果你不使用SAH或任何其他算法来遍历树，你可以自由地做任何你想要的与kd-tree的初始想法。但是如果你将绑定到一些传统的算法，你有拆分线。你必须这样做，只是因为树的每一片叶子都有一个重量（我想你的情况取决于它的长度）。

如果你不分割线条，你也会得到错误的叶子重量。不，如果你没有分割线条，你应该在线条所属的两条线上重复它们。

2011-07-29 09:40:32 avp

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

2012-06-13 13:39:40 atb

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

R*-tree (Wikipedia)可能是一个更好的选择。它确实是为空间扩展的对象设计的。如果您查阅相关出版物，他们甚至会尝试不同的复杂对象的近似值;例如是否支付三角形化他们，使用一个环形边界框，并且有趣的是IIRC 5角多边形在某些情况下提供了最好的性能。

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

2013-01-01 16:29:05

回答