How to best store lines in a kd-tree

问题:

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?

回答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.

回答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.

回答3:

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