Hacker News Reader

Comment by quibono | Hacker News Reader

I'd love to see that. Could you link me to an implementation or explain this in more detail please?

Here's a 3D version used in the creation of sparse voxel octrees:

https://forceflow.be/2013/10/07/morton-encodingdecoding-thro...

Here's an example from AWS, where lat/long pairs are put into a Z-index, which is used as a DynamoDB sort key, letting you efficiently query for items near a point.

https://aws.amazon.com/blogs/database/z-order-indexing-for-m...

I would like to know about this more, too. Is there a code anywhere, ideally with comments? But I am fine without comments, too, I would just like to see the code and possibly with an example usage.

Okay, I was intrigued and I did some digging. Morton / Z-order is all about interleaving the individual bits of the x and y coordinates. You end up grouping by quadrants. Python one liner:

    points.sort(key=lambda p: sum(((p[0]>>i&1)<<(2*i))|((p[1]>>i&1)<<(2*i+1)) for i in range(16)))

Reply on news.ycombinator.com