Algoritmo veloce per trovare tutti i punti all'interno di un rettangolo

Question

Dato un insieme di punti distinti nello spazio 2D e un rettangolo (le coordinate di tutti e quattro i punti, i lati paralleli con l'asse xy), come individuare rapidamente i punti all'interno del rettangolo?

Non sono interessato alla soluzione di base di passare attraverso tutti i punti e vedere quale si trova all'interno del rettangolo. Quello che sto cercando è un algoritmo che mi fornirà tempi di interrogazione veloci per rettangolo.

Non mi interessa quanto tempo trascorro nel passaggio di pre-elaborazione. Quello che mi interessa è che dopo aver elaborato i miei dati ottengo una struttura utile che mi dà tempi di interrogazione veloci per rettangolo.

So per esempio che posso contare quanti punti ho in un rettangolo in O (logN). Funziona perché faccio un sacco di elaborazione pesante all'inizio e poi interrogare i dati elaborati con un nuovo rettangolo ogni volta e ottenere un nuovo conteggio in tempo logN. Sto cercando un algoritmo simile per trovare i punti reali e non solo il loro conteggio.

Answer 1

Una risposta classica è il kD-tree (albero 2D in questo caso).

Per un'alternativa semplice, se i punti sono distribuiti in modo uniforme, puoi provare con la griglia.

Scegliere una dimensione di cella per una griglia quadrata (se il problema è anisotropico, utilizzare una griglia rettangolare).Assegna ogni punto alla cella della griglia che lo contiene, memorizzato in un elenco collegato. Quando si esegue una query, trovare tutte le celle che sono sovrapposte dal rettangolo e scansionarle per attraversare i loro elenchi. Per le celle parzialmente coperte, è necessario eseguire il test point-in-rectangle.

La scelta della dimensione è importante: troppo grande può comportare troppi punti che devono essere testati comunque; troppo piccolo può causare troppe celle vuote.

Answer 2

Se si ordinano i punti per asse X, si dovrebbe essere in grado di eseguire una ricerca binaria per trovare il punto più a sinistra (il più piccolo valore X) che si trova nel rettangolo.

Esegui un'altra ricerca binaria per trovare il punto più a destra (il più grande valore X) nel rettangolo.

Tutti i punti della lista ordinata tra questi due punti si troveranno entro i limiti sinistro-destro del rettangolo, anche se non ne hai mai controllati la maggior parte!

Ripetere lo stesso processo sull'asse verticale/Y.

---

Le due ricerche binarie lungo l'asse X devono essere entrambe O (logN).
Uguale alle due ricerche binarie lungo l'asse Y.
O (log N 4) == O (log N)

Ci sarà ancora una sorta di merge-passo, alla fine, che non sono immediatamente sicuro.

Answer 3

Penso che dovresti memorizzare i tuoi punti in un quadtree. Non ho elaborato i dettagli, ma dovrebbe consentire fondamentalmente di fare qualcosa di simile a una ricerca binaria che produce direttamente i punti che si trovano all'interno di un rettangolo.

Se i punti sono raggruppati, cioè esistono gruppi che contengono molti punti in una piccola area e altre aree che contengono no, o pochissimi punti uno R-tree potrebbe essere ancora meglio.

La complessità del runtime dovrebbe essere O (logN), penso.

Answer 4

È possibile raggruppare il punto in settori. Se un settore è completamente dentro o fuori dal rettangolo dato, anche tutti i punti all'interno di esso sono dentro o fuori. Se un settore è parzialmente inserito, devi cercare O (n) per i punti in quel settore per verificare se si trovano nel rettangolo. Cerca la ricerca k-d tree.

Answer 5

Stai cercando kd-tree range search o intervallo di query.

• quadtree (o octtrees o 16 alberi ...) sono meglio quando v'è un insieme mutevole di punti, ma ci si aspetta la distribuzione deve essere uniforme. Non sono necessari ulteriori passaggi di bilanciamento, poiché la struttura dell'albero è fissa.
• kd-tree funzionano meglio su un set fisso di punti, anche con una distribuzione non uniforme. Quando il set di punti cambia, è difficile (ma non impossibile) eseguire passaggi di auto-bilanciamento.
• Gli alberi AABB (o alberi grassi AABB) forniscono un modo rapido per testare forme sovrapposte, non solo punti. Gli alberi AABB necessitano di bilanciamento occasionale. Quando sono inclusi oggetti in movimento continuo, il modo comune è usare "AABB-s grassi", quindi non è necessario aggiornare l'albero in ogni fotogramma.
• L'ordinamento per un solo asse e l'utilizzo della ricerca binaria (qualcosa di simile suggerito da abelenky, ma penso che non abbia senso fare una seconda ricerca binaria) è una soluzione semplice ed elegante, ma sarà lento quando ad esempio si ordina dal Asse X, e tutti i punti sono su una linea parallela con Y. Devi fare un filtro lineare sui punti che sono abbinati dalle ricerche binarie per X. La complessità temporale è il caso peggiore O(n), ma questo caso peggiore accade abbastanza spesso.

Tutti questi algoritmi eseguono query in media O(log n + k) dove k è il conteggio dei punti corrispondenti.

La griglia, come suggerito da Yves, può eseguire la ricerca di intervallo nel tempo O(k), ma solo quando la dimensione del rettangolo di query è limitata. Questo è quello che fanno spesso in particle simulations. La griglia può essere utilizzata anche quando il set di input non è limitato: è sufficiente creare un numero fisso di bucket in base all'hash delle coordinate della griglia. Ma se il rettangolo di query può essere di dimensioni arbitrarie, la gridatura è un no-go.

Answer 6

Insieme ad altre risposte, è anche possibile esaminare i codici Morton (ordinamento della curva ordine z).

Nel tuo caso, che è dati statici, puoi anche rappresentare l'intero punto dati come una matrice.

https://en.wikipedia.org/wiki/Z-order_curve

Questo lavoro ha anche una linea temporale piuttosto complicato di diversi "metodi di accesso multi-dimensionale" - http://www.cc.gatech.edu/computing/Database/readinggroup/articles/p170-gaede.pdf