Dividendo la griglia 2D alla ricerca più efficiente

Requisiti

1. Ho Grid di dimensione illimitata (non lo so e non so quale sia la sua dimensione)
2. C'è Object che dovrebbe essere posizionato sulla griglia, ogni oggetto ha una distanza di flusso (in altre parole: intervallo, default: 300) e coordinate 2D (posizione)
3. Esiste la funzione find che prende le coordinate 2D e dovrebbe restituire quale oggetto è mostrato

Sembra che R-tree sia la risposta alla mia domanda, c'è qualche spiegazione su come funziona esattamente l'algoritmo?

A modo mio

1. Dividendo le dimensioni della cella in livelli, il livello 1 è 600x600 (2 volte più grande della distanza del flusso predefinito), il livello 2 è 1200x1200 e così via ... (ogni volta che le dimensioni della cella vengono moltiplicate per 2).
2. Associare gli oggetti nella cella corrispondente moltiplicando la distanza del flusso per 2 e arrotondando al multiplo successivo di 600, ad esempio: la distanza del flusso è 450, moltiplicandola per 2 corrisponde a 900, arrotondandola al multiplo successivo di 600 si ottiene 1200.
3. Ogni volta che l'oggetto inserito controlla quali celle si adattano all'oggetto e aggiunge l'oggetto all'elenco di oggetti della cella.

4. Quando la funzione find viene chiamata, cerca solo nella cella della coordinata specificata.

   [Assumi triangolo è un oggetto]

   

Domandesimili

• Il modo più efficace per trovare le entità in una griglia? (La risposta accettata )