Recuperare l'rettangoli contenenti un punto specificato

Question

Non riesco a capire come implementare questo in un modo di eseguire, così ho deciso di chiedere a voi ragazzi.

ho una lista di rettangoli - in realtà atm solo piazze, ma potrebbe essere necessario migrare a rettangoli più tardi, quindi cerchiamo di bastone a loro e tenerlo un po 'più generale - in uno spazio tridimensionale 2. Ogni rettangolo è specificato da due punti, rettangoli possono sovrapporsi e non mi importa tutto troppo di tempo di configurazione, perché i rettangoli sono statici decidessino e c'è un certo spazio per precalculate qualsiasi materiale di installazione (come la costruzione di alberi, la cernita, il ricalcolo vettori aggiuntivi, qualunque cosa, ecc). Oh sto sviluppando in JavaScript se questo è di alcuna preoccupazione.

Per la mia domanda effettiva: dato un punto, come faccio ad ottenere un set di tutti i rettangoli che includono quel punto?

lineare si avvicina non eseguire abbastanza bene. Così cerco qualcosa che esegue meglio di O (n). Ho letto alcune cose, come su gerarchie bounding volume e cose simili, ma qualunque cosa ho provato il fatto che i rettangoli possono sovrapporsi (e io in realtà voglio ottenere tutti loro, se le bugie di punti all'interno di più rettangoli) sembra ottenere sempre nel mio modo .

Ci sono suggerimenti? Ho perso qualcosa di ovvio? Sono BVH anche applicabile ai possibilmente sovrapposte limiti? Se sì, come faccio a costruire un tale albero possibilmente sovrapposte? Se no, che altro potrei usare? E 'motivo di preoccupazione per me, se i confini sono dentro, fuori o non determinato.

Se qualcuno potesse venire con utile qualche cosa come un link o un rant su quanto sono stupido usare BVH e non Some_Super_Cool_Structure_Perfectly_Suited_For_My_Problem mi piacerebbe davvero apprezzare!

Modifica Ok, ho giocato un po 'con R-alberi e questo è esattamente quello che stavo cercando. Infatti Attualmente sto usando l'attuazione R-tree http://stackulator.com/rtree/ come suggerito da endy_c. Svolge molto bene e capace di soddisfare qualunque mie esigenze del tutto. Grazie mille per i vostri ragazzi di supporto!

Answer 1

Si potrebbe guardare a R-alberi

codice Java

c'è anche un wiki, ma può collegare una sola postale; -)

Answer 2

È possibile suddividere lo spazio in rete, e per ogni cella della griglia avere una lista di rettangoli (o gli identificatori rettangolo) che esistono almeno parzialmente in quella griglia. Verificare la rettangoli solo nella corrispondente cella della griglia. La complessità dovrebbe essere O (sqrt (n)).

Un altro approccio è quello di mantenere quattro schiere ordinate di x1, y1, x2, y2 valori e binari cercare il vostro punto all'interno di quei 4 array. Il risultato di ogni ricerca è un insieme di candidati rettangolo, e il risultato finale è intersezione di quei 4 set. A seconda di come set di intersezione è implementato questo dovrebbe essere efficiente di O (n).