c++ - 快速线路查询的数据结构？

Question

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

给定一组3D行 L （将存储在该数据结构中）和另一个“查询行”q，我希望能够快速迭代 L 中与 q“足够接近”的所有行。我打算使用的距离是两点 u 和 v 之间的最小欧几里得距离，其中 u 是第一行的某个点，v 是第二行的某个点。计算该距离不是问题（有一个涉及叉积的好技巧）。

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

TIA，S。

Answer 1

另一种选择——也是基于磁盘的数据库系统中空间索引最常用的一种——是R-Tree。它的实现比 KD-Tree 稍微复杂一些，但通常被认为更快，并且索引线和多边形没有问题。

Answer 2

您也可以为此使用 KD-Trees。

可以构建一个适用于基元而不是点的 KD-Tree。许多光线追踪器这样做是为了使三角形命中测试更快。我见过的最好的描述是在这个光线追踪教程中。

一个可能更快但不是 100% 准确的解决方案是只保留每个线段的点列表，并将这些点插入到标准的基于点的 KD-Tree 中。找到最近的点，然后用线段标记它们，并使用它来获取最近的线。它很粗糙，但与其他选项相比通常非常快。“诀窍”是找到在沿线段的点之间保持大空间（更快）与将线段分成更多点（更慢，但更准确）之间的正确平衡。