代码之家 › 专栏 › 技术社区 › sellibitze

用于快速查询的数据结构?

nearest-neighbor geometry data-structures algorithm c++

3

sellibitze · 技术社区 · 16 年前

我知道我可以使用一个kd树来存储点,并在接近另一个给定点的一部分点上快速迭代。我想知道这句台词是否有相似之处。

给定一组行l in 三维 (存储在该数据结构中)和另一个“查询行”q,我希望能够快速迭代l中“足够接近”q的所有行。我计划使用的距离是两点u和v之间的最小欧几里得距离,其中u是第一行的某个点,v是第二行的某个点。计算距离并不是问题(交叉积有一个很好的技巧)。

也许你们有个好主意,或者知道在哪里找文件、描述等。

蒂亚 S.

2 回复 | 直到 16 年前

1

4

Nick Johnson 16 年前

在基于磁盘的数据库系统中,另一个最常用的空间索引方法是 R-Tree . 与kd树相比,实现起来要复杂一些,但通常认为它更快,而且索引线和多边形没有问题。

2

3

Reed Copsey 16 年前

你也可以使用kd树。

有可能构建一个基于基元而不是点的kd树。许多光线跟踪器这样做是为了使三角形命中测试更快。我看到的最好的描述就是这个 ray tracing tutorial .

一个可能更快的,虽然不是100%准确的解决方案,是只保留每行段的点列表,并将其插入到标准的基于点的KD树中。找到最近的点,然后用线段标记它们,然后用它来获得最近的线。它很粗糙,但与其他选择相比往往非常快。“诀窍”是找到正确的平衡,保持沿着段(更快)的点之间的大空间与将段分成更多点(更慢,但更准确)。