I already implemented some spatial partitioning with a Z order curve, it's not too difficult to write and understand, but it works well. If I remember, the mai

I already implemented some spatial partitioning with a Z order curve, it's not too difficult to write and understand, but it works well. If I remember, the main advantage is that you can use a sorted multimap, insert item by converting 2D coordinates to 1D with some function. Multimaps are already implemented and fast. The result is that your data is packed, and "sorted" by 2D location, so when you query items in an area, it's supposed to be very fast because of cache friendliness, I think. The interesting trick is when you query a rectangle, you calculate 2 corner bounds, and use them to query the multimap. Of course, this is a simple way to index 2D data, and R trees are still faster, but no engineers will enjoy implementing an R-tree. BSP or Kd-trees are also much harder to implement than a Z-order curve. I am not good at those subjects, but I feel like a Z order curve is the "best" way to index 2D, since it's a very good trade-off between simplicity and performance, which is if one wants to write lean software, like for a video game for example. Feel free to correct me. Although I think there are things around Z order curves that are still under patent.