c – 快速查询的数据结构？

我知道我可以使用KD-Tree来存储点并快速迭代它们接近另一个给定点的一小部分.我想知道线路是否有类似的东西.

给定一组3D中的行L(存储在该数据结构中)和另一个“查询行”q,我希望能够快速遍历L中与q“足够接近”的所有行.我计划使用的距离是两点u和v之间的最小欧几里德距离,其中u是第一行上的某个点,v是第二行上的某个点.计算距离不是问题(有一个很好的技巧涉及交叉产品).

也许你们有个好主意或知道在哪里寻找论文,描述等……

TIA,
秒.

另一个选项 – 也是最常用的基于磁盘的数据库系统中的空间索引的选项 – 是 R-Tree.它实现起来比KD-Tree要复杂一些,但它通常被认为更快,并且没有问题索引线和多边形.