Can R-Trees maintain z-order when using 2 dimensions?

Question

I'm writing an implementation of an R-Tree based on Guttman's original paper. I was thinking about using an R-Tree for a program I'm writing that involves a lot of rectangles on the screen that can be moved/re-sized with the mouse.

I want to efficiently only select rectangles that are in a particular rectangle and draw them (instead of iterating through potentially 100+ items and checking if bounds intersect). The problem that I'm finding after a couple reads of Guttman's paper is that z-order can't be maintained for 2D objects.

For example, if I move an object, it'd be deleted and then re-inserted. When it's re-inserted, the node it's inserted to wouldn't be able to keep track of the proper order. Most implementation's of an R-Tree that I've seen use an array and just find the empty position. The re-insertion would essentially destroy any z-order positioning.

So when I go to draw all rectangles that intersect with a rectangle, the order they're returned isn't necessarily correct.

Am I wrong on this assumption? I was thinking instead of using an array, I could use an AVL or Red-Black tree and use a Comparer that compares on z-index to insert into the tree. This way, z-order is always maintained (and it's the most important factor).

I was also just thinking of sorting them when they're returned, but this could be more expensive I'm thinking.

Answer 1

R-tree is not supposed to order answer records somehow.

Just sort answer. It's not too slow.

BTW, I can mail you my r-tree code. It works fine for me, but it would be very useful if someone would check is it what Guttman or Beckman wrote in theirs papers...

Order of spatial indexing is essentially different from strict order...it's difference between spatial indexing and just B+-tree.

You can also have two indexes and join them. Are you really shure you need index? Something works slow?