Data structure for fast line queries?

Question

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.

Answer 1

You can use KD-Trees for this as well.

It's possible to build a KD-Tree that works on primitives, not points. Many ray tracers do this to make triangle hit testing much faster. The best description I've seen is in this ray tracing tutorial.

A potentially faster, though not 100% accurate, solution, is to just keep a list of points per line segment, and insert these into a standard point-based KD-Tree. Find the nearest points, then have them tagged with the line segment, and use that to get the nearest lines. It's crude, but often very fast compared to other options. The "trick" is to find the right balance of keeping large spaces between points along the segment (faster) vs. breaking the segment into more points (slower, but more accurate).

Answer 2

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.