Can R Alberi mantenere ordine z quando si utilizzano 2 dimensioni?

Question

Sto scrivendo un'implementazione di un R-Tree basato su carta originale di Guttman. Stavo pensando di utilizzare un R-Tree per un programma che sto scrivendo che comporta un sacco di rettangoli sullo schermo che può essere spostato / ridimensionato con il mouse.

Voglio selezionare in modo efficiente solo rettangoli che si trovano in un particolare rettangolo e disegnarli (invece di iterazione attraverso potenzialmente 100 + oggetti e controllare se i limiti si intersecano). Il problema che mi sto trovando dopo un paio legge di carta di Guttman è che z-ordine non può essere mantenuta per gli oggetti 2D.

Per esempio, se mi muovo un oggetto, sarebbe eliminata e poi reinserito. Quando è reinserito, il nodo è inserito per non sarebbe in grado di tenere traccia dell'ordine corretto. La maggior parte implementazione di un R-Tree che ho visto l'uso di un array e appena trovato la posizione vuota. Il reinserimento sarebbe essenzialmente distruggere qualsiasi posizionamento ordine z.

Così, quando vado a disegnare tutti i rettangoli che si intersecano con un rettangolo, nell'ordine in cui sono tornati non è necessariamente corretto.

Mi sbaglio su questa ipotesi? Stavo pensando invece di utilizzare un array, potrei usare un albero AVL o Red-Black e utilizzare un Comparer che mette a confronto su z-index per inserire nell'albero. In questo modo, ordine z è sempre mantenuta (ed è il fattore più importante).

Sono stato anche solo pensando di ordinare loro quando sono tornati, ma questo potrebbe essere più costoso che sto pensando.

Answer 1

R-albero non si suppone che i record ordine di risposta in qualche modo.

Proprio sorta rispondere. Non è troppo lento.

A proposito, posso spedire il mio codice di R-tree. Funziona bene per me, ma sarebbe molto utile se qualcuno avrebbe controllare è quello Guttman o Beckman ha scritto nei documenti loro ...

Ordine di indicizzazione spaziale è essenzialmente diverso da rigoroso ordine ... è differenza tra l'indicizzazione spaziale e solo albero B +.

Si può anche avere due indici e unirsi a loro. Sei davvero Shure è necessario index? Qualcosa funziona lenta?