Spatial index on a sorted set

Question

I have a large set of objects to render in 2D, which I have sorted from bottom to top. I'm currently using an R-tree to get a subset of them out that are within the current viewport. However, after getting them out of the spatial index, I have to re-sort them by their Z order. That sorting takes about 6 times longer than looking up the list of them in the spatial index (where several hundred items have matched my query).

Is there a kind of 2D spatial index which has fast lookup by rectangular bounding box, which will return the elements in a sorted order?

Answer 1

You can build the R-tree on the Z-order directly.

Usually, the Hilbert order is preferred, this is known as an Hilbert-R-tree.

But you can do the same with the Z-order, too.

However, you may also consider to store the data fully in Z-order right away; in a B+-tree for example.

Instead of querying with a rectangle, translate your query into Z-order intervals, and query for the Z indexes. This is a very classic approach predating the R-trees:

Morton, G. M. (1966)
A computer Oriented Geodetic Data Base; and a New Technique in File Sequencing
Technical Report, Ottawa, Canada: IBM Ltd.