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

问题描述

我知道我可以使用KD树存放点和快速迭代了一小部分人是接近到另一个指定点。我不知道是否有类似的东西线。

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.

给定一组线L的 3D （存储在该数据结构），另一个查询行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树。这是一个比较复杂一点，以实现比KD树，但它通常被认为是更快速，并且没有问题索引线，多边形。

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