Come faccio a determinare quali parallelepipedi un punto è in senza l'iterazione di tutti?

Question

Ho una serie di parallelepipedi le cui posizioni e le dimensioni sono date con coordinate (in modo che siano paralleli agli assi principali) minima e massima x, y e z.

es. Potrei avere i seguenti 3 parallelepipedi:

10.5 <= x <= 39.4,  90.73 <= y <= 110.2, 90.23 <= z <= 95.87
20.1 <= x <= 30.05,  9.4  <= y <=  37.6,  0.1  <= z <= 91.2
10.2 <= x <= 10.3,   0.1  <= y <=  99.8, 23.7  <= z <= 24.9

Se poi do un punto (ad esempio (25.3,10.2,90.65)), c'è un modo per determinare rapidamente quali cuboide (s) mi trovo?

• Ovviamente ho potuto solo iterare su tutti i parallelepipedi, ma ci sono potenzialmente milioni di loro, e ho bisogno di questo per andare più veloce di semplice iterazione (qualcosa di O (log n) o meglio sarebbe grande).

• Questo suona per me come un tipo di problema "fuzzy matching", e ho notato che Apache Lucene supporta query gamma , ma questo sembra per lavorare nel modo opposto rotondo (trovare un punto in un parallelepipedo piuttosto che un parallelepipedo che contiene un punto).

• A complicare ulteriormente le cose leggermente, il numero di dimensioni potrebbe essere maggiore di 3 (che potrebbe essere su 20); vale a dire che potrei essere alla ricerca di "hypercuboids" piuttosto che parallelepipedi.)

Answer 1

Un modo semplice per accelerare questa query è costruendo il seguente griglia uniforme struttura dati (spesso chiamato bidoni) come un passo di pre-elaborazione: Porre n x n x n (in 3d) griglia sopra la scena e per ogni cella della griglia memorizzare un puntatore a tutti i parallelepipedi intersecano quella cella. Ora, per un punto di domanda è possibile calcolare direttamente in quale cella è nella griglia uniforme, e poi si deve controllare solo i parallelepipedi associate a quella cella, e non tutti i parallelepipedi.

A seconda di come grande lo spazio e come variando le dimensioni cuboide sono questo metodo potrebbe non essere molto efficiente, perché si potrebbe essere difficile scegliere una buona risoluzione n per accelerare abbastanza e non hanno bisogno di una quantità enorme di cellule. Per ovviare a questo si potrebbe desiderare di provare a guardare in modi più adattivi per partizionare lo spazio, come ad esempio KD-alberi (kd-alberi a wikipedia) , che sono fondamentalmente alberi binari partizionamento lo spazio con asse allineato piani: Si veda ad esempio qui dove il piano rosso divide la scatola in due parti e poi il verde in parti più piccole, poi l'azzurro ...

Una query utilizzando kd-tree avrebbe prima traversata fino alla foglia di kd-albero dove si trova il punto la query e quindi verificare con i parallelepipedi locali in quella cella. struttura dati Altro spazio partizionamento opzioni possono essere trovate qui .

Un'altra opzione sarebbe quella di utilizzare le gerarchie del volume di delimitazione , quale gruppo oggetti insieme in delimitazione dei volumi, e quindi i volumi gruppo di delimitazione in volumi di delimitazione più grandi e così via ... per avere una gerarchia di volumi di delimitazione . Questi si adattano meglio ad una scena e possono più facile gestire le scene in cui gli oggetti si muovono, ma penso che per il partizionamento spazio impostazione potrebbe funzionare bene ... In ogni modo, per maggiori dettagli vedere questo libro capitolo .

Answer 2

si tendente nel territorio di "partizione binaria dello spazio" e "Rilevamento Collision"; essenzialmente le idee sono fondamentalmente memorizzando i parallelepipedi in una struttura tipo albero, che divide lo spazio occupato in piccole scatole ordinate. La decisione su quale "parte dello spazio" ogni parallelepipedo occupa è fatto durante l'inserimento nel strucutre albero.

Fare una ricerca su google octrees.

modo efficiente dividendo spazio 3D, e gli oggetti contenuti all'interno di quello spazio è piuttosto una grande porzione di informatica; in gran parte utilizzato per lo sviluppo di giochi per computer. Alcuni degli algoritmi prendono in considerazione il fattore tempo, vale a dire che gli oggetti si muovono tra spazi partizione.