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

问题描述

我知道我可以使用KD-Tree来存储点数，并在接近另一给定点的一小部分中快速迭代。我想知道是否有类似的行。

给定一组在 3D 中的行L（要存储在该数据结构中） ）和另一个查询行q，我想能够快速地遍历L中足够接近到q的所有行。我计划使用的距离是两点u和v之间的最小欧氏距离，其中u是第一行上的某个点，v是第二行上的某个点。计算距离不是一个问题（有一个很好的技巧涉及交叉产品）。

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

TIA，
s。

解决方案

p>另一个选项 - 最常用于基于磁盘的数据库系统中的空间索引，是 R-Tree 。与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.

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, s.

解决方案

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屋！