如何在 kd 树中最好地存储行
我知道 kd 树传统上用于存储点，但我想存储线。最好是在每个交叉点处用 kd 树的分割来分割线吗？或者仅将端点存储到 kd-足以进行最近邻居查找？
I know kd-trees are traditionally used to store points, but I want to store lines instead. Would it be best to split the line at every intersection with the splitting of the kd-tree? or would storing just the end-points into kd-suffice for nearest neighbor finding?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
kd树本身是为点对象设计的。甚至对于盒子、球体或类似的东西也不行。我相信您可以以某种方式使用存储
minx、maxx、miny、maxy、minz、maxz的6d树；但我不完全确定如何正确查询它。R*-tree (Wikipedia) 在这里可能是更好的选择。它确实是为具有空间延伸的物体而设计的。如果你查阅相关出版物，他们甚至尝试了复杂物体的不同近似值；例如，将它们三角形化、使用外接球、边界框是否值得，有趣的是，IIRC 5 角多边形在某些情况下提供了最佳性能。
不管怎样，R* 树系列可能是一个有趣的选择。
The kd-tree itself is designed for point objects. Not even for boxes, spheres or something like this. I believe you can somehow use a 6d tree that stores
minx, maxx, miny, maxy, minz, maxz; but I'm not entirely sure on how to query it correctly.The R*-tree (Wikipedia) might be a better choice here. It is really designed for objects with a spatial extend. If you look up the related publications, they even experimented with different approximations of complex objects; for example whether it pay off to triangularize them, use a circumsphere, bounding box, and interestingly enough IIRC the 5-corner-polygon provided the best performance in some cases.
Anyway, the R*-tree family might be an interesting choice.
好吧，你必须在交叉点处分割线，否则你会遇到树叶权重的麻烦。
另一方面，如果您不使用 SAH 或任何其他算法来遍历树，您可以自由地使用 kd 树的原始想法做任何您想做的事情。但是，如果您受限于某些传统算法，则必须分割线。你必须这样做只是因为树的每片叶子都有一个重量（我想在你的情况下它取决于其中的线的长度）。
如果你不分割线，你也会得到错误的叶子重量。不，如果你不分割行，你应该在该行所属的两个叶子中复制它们。
Well, you have to split lines on intersections, otherwise you get in trouble with weights of leafs of the tree.
On the other hand, if you don't use SAH or any other algorithm for traversing the tree, you are free to do whatever you want with original idea of the kd-tree. But if you are bound to some traditional algorithms, you have to split lines. You have to do it just because each leaf of the tree has a weight (I guess in your case it depends on the length of lines in it).
And if you don't split lines, you'll get wrong weights of the leaves, too. Nay, if you don't split lines, you should duplicate them in both leaves the line belongs to.
你必须使用kd树吗？对于扩展原语，bv 树可能更有效。
Do you have to use a kd-tree? For extended primitives a bv-tree might be more efficient.