3 ms·
You’ve just described a single axis kd-tree roughly. Which means you’ll also perform catastrophically for patterns with say a line in the Z-axis. It’s not that
by boulos 9y ago
You’ve just described a single axis kd-tree roughly. Which means you’ll also perform catastrophically for patterns with say a line in the Z-axis. It’s not that hard to do a proper spatial tree. If you hate kd-trees, an octree or a grid are also more robust than a “single axis binary split tree”.
- geophile 9y agoNot 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.
- geophile 9y agoOh! I see the problem. I don't mean just a tree keyed on the z-axis. I mean z-order: https://en.wikipedia.org/wiki/Z-order https://en.wikipedia.org/wiki/Z-order
- boulos 9y agoAhh! I wasn’t sure, so sadly I chose “z as in z axis” not Z as in Z/space-filling/Hilbert/Morton order. That’s a grid in disguise! :).