快速线路查询的数据结构? [英] Data structure for fast line queries?

问题描述

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

I know that I can use a KD-Tree to store points and iterate quickly over a fraction of them that are close to another given point. I'm wondering whether there is something similar for lines.

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

Given a set of lines L in 3D (to be stored in that data structure) and another "query line" q, I'd like to be able to quickly iterate through all lines in L that "are close enough" to q. The distance I'm planning to use is the minimal Euclidean distance between two points u and v where u is some point on the first line and v is some point on the second line. Computing that distance is not a problem (there's a nice trick involving the cross product).

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

Maybe you guys have a good idea or know where to look for papers, descriptions, etc...

TIA,秒.

推荐答案

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

Another option - and the most commonly used one for spatial indexing in disk-based database systems - is the R-Tree. It's a bit more complicated to implement than a KD-Tree, but it's generally considered to be faster, and has no problem indexing lines and polygons.

这篇关于快速线路查询的数据结构?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！