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

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

你也可以使用kd树。

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

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