4

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.

sellibitze
  • 27,611
  • 3
  • 75
  • 95
  • This distance is always 0, unless the lines are parallel. Or are you talking about line *segments*? – Thomas Sep 30 '09 at 15:43
  • It doesn't matter actually. If it helps, I could make it line segments. But lines of infinite length is also fine. I don't expect the result to change. I currently parameterize my lines with two points and I expect the points u/v to be on those line segments. – sellibitze Sep 30 '09 at 15:47
  • 1
    Hum, in 3D two lines may not cross each others without being parallel, since they can be in different plans. – Matthieu M. Sep 30 '09 at 15:48
  • Sorry, I missed the "3D" part. All is clear now. – Thomas Sep 30 '09 at 15:49
  • Interesting question, by the way. – Thomas Sep 30 '09 at 15:49

2 Answers2

4

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.

Nick Johnson
  • 100,655
  • 16
  • 128
  • 198
  • +1. To name another advantage: Such a data structure doesn't require "splitting elements" (redundancy) because the nodes' bounding boxes may overlap -- much like a loose octree. – sellibitze Oct 01 '09 at 09:19
  • Accepted for suggesting another data structure that doesn't require splitting objects – sellibitze Oct 01 '09 at 16:24
3

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).

Reed Copsey
  • 554,122
  • 78
  • 1,158
  • 1,373
  • +1 Thanks for your suggestions. I'd have to check your link and think about it. – sellibitze Sep 30 '09 at 16:03
  • Instead of storing points in each leaf I could store line segments and split those segments. Either way I would end up storing the line somehow redundantly. Maybe other data structures are more appropriate (loose octree, R-Tree, ...) – sellibitze Oct 01 '09 at 09:11