如何在kd-tree中最好地存储行 [英] How to best store lines in a kd-tree

问题描述

我知道kd-tree常常用于存储积分，但是我想要存储线条。在kd-tree的分割处，在每个交叉点分割线是最好的吗？或者只是将端点存储到最接近的邻居发现的kd-suff中？

解决方案

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

R * -tree（Wikipedia）可能是一个更好的选择。它真正设计用于具有空间延伸的对象。如果您查找相关出版物，他们甚至尝试了复杂对象的不同近似值;例如，它是否偿还三角化，使用环圈，边框和有趣的IIRC，五角形多边形在某些情况下提供了最好的表现。

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

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?

解决方案

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.

这篇关于如何在kd-tree中最好地存储行的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！