Re:Using k-d trees to efficiently calculate nearest neighbor...
by geophile on Saturday February 10, 2018 @06:01PM
(#16350135)
Not sure what you mean by a single-axis kd-tree.
Z-order + sorted array/tree/etc. is a generalization of an oct-tree. An octtree is just z-order combined with a degree 8 trie. And an octtree is simply an encoding of a 3-d grid.
So I really don't understand your objections.
Also, I haven't tried NN search using z-order, but range searches work very well. The partitioning induced by z-order adapts well to all sorts of distributions.
Z-order + sorted array/tree/etc. is a generalization of an oct-tree. An octtree is just z-order combined with a degree 8 trie. And an octtree is simply an encoding of a 3-d grid.
So I really don't understand your objections.
Also, I haven't tried NN search using z-order, but range searches work very well. The partitioning induced by z-order adapts well to all sorts of distributions.