快速线路查询的数据结构?
我知道我可以使用 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.
相关文章