How to best store lines in a kd-tree

Question

I know kd-trees are traditionally used to store points, but I want to store lines instead. Would it be best to split the line at every intersection with the splitting of the kd-tree? or would storing just the end-points into kd-suffice for nearest neighbor finding?

Wormwood

It depends what you want to do. Remember that a line (segment) is just a collection of two coordinates, so it can be described by a single coordinate, with twice as many dimensions. Therefore, you could store lines as points in a higher-dimensional kd-tree. – Grizelda

I am trying to create a distance field with the lines. So I will be utilizing the nearest neighbor functionality of the kd-tree. However, I don't want to add more data than what I have (the end points of the line segments. – Wormwood

Answer 1

The kd-tree itself is designed for point objects. Not even for boxes, spheres or something like this. I believe you can somehow use a 6d tree that stores minx, maxx, miny, maxy, minz, maxz; but I'm not entirely sure on how to query it correctly.

The R*-tree (Wikipedia) might be a better choice here. It is really designed for objects with a spatial extend. If you look up the related publications, they even experimented with different approximations of complex objects; for example whether it pay off to triangularize them, use a circumsphere, bounding box, and interestingly enough IIRC the 5-corner-polygon provided the best performance in some cases.

Anyway, the R*-tree family might be an interesting choice.

Albata

Answer 2

Well, you have to split lines on intersections, otherwise you get in trouble with weights of leafs of the tree.

On the other hand, if you don't use SAH or any other algorithm for traversing the tree, you are free to do whatever you want with original idea of the kd-tree. But if you are bound to some traditional algorithms, you have to split lines. You have to do it just because each leaf of the tree has a weight (I guess in your case it depends on the length of lines in it).

And if you don't split lines, you'll get wrong weights of the leaves, too. Nay, if you don't split lines, you should duplicate them in both leaves the line belongs to.

Orangy

Answer 3

Do you have to use a kd-tree? For extended primitives a bv-tree might be more efficient.

Fencer