Memorizza punti 2D per un rapido recupero di quelli all'interno di un rettangolo

Question

Ho un gran numero di punti 2D e voglio ottenere rapidamente quelli che giacciono in un certo rettangolo. Diciamo un '.' è un punto qualsiasi e 'X' è un punto che voglio trovare all'interno di un rettangolo che ha 'T' come TopLeft e 'B' come punti BottomRight:

. . . . . .
. T-----+ .
. | X X | .
. +-----B .
. . . . . .

Ho provato uno std :: set con una funzione di ordinamento che ordina il punto TopLeft all'inizio e il BottomRight alla fine del set. Quando si ordina prima per valore X, ciò comporterebbe la ricerca dei seguenti punti.

. . . . . .
. T-----+ .
X | X X | X
. +-----B .
. . . . . .

Ciò significa che dovrei controllare ogni punto trovato, se è davvero all'interno del rettangolo. Non proprio bene.

Quale sarebbe un modo migliore per farlo?

La mia lingua è C ++ (Windows) e ho STL e boost disponibili.

Aggiornamento

Dopo aver letto le risposte finora, ho notato che non ho tenuto conto di tutti i parametri del mio problema: non esiste un rettangolo fisso. I rettangoli possono essere impostati dall'utente in fase di esecuzione. Ciò significa che l'ordinamento dell'insieme di punti promette di essere più efficiente di una ricerca lineare in tutti i punti, come suggerito da Artelius prima di questo aggiornamento. Ci proverò comunque, comunque! Non mi aspetto che l'utente imposti un rettangolo molto frequente. Quindi, per quanto riguarda lo sforzo di implementazione, potrebbe rivelarsi una buona soluzione per me.

Answer 1

È possibile memorizzare i punti in un indice spaziale usando quad o r-alberi. Quindi dato il rettangolo potresti trovare tutti i nodi dell'albero che lo sovrappongono, dovresti quindi confrontare ogni punto in questo sottoinsieme per vedere se cade nel rettangolo.

In sostanza, l'albero spaziale ti aiuta a potare lo spazio di ricerca.

Potresti essere in grado di utilizzare una soluzione più semplice, come il partizionamento dei punti negli intervalli. Di 'dove x è da 0,10 come intervallo, 11,20 come altro. Qualsiasi soluzione che ti consente di potare lo spazio di ricerca ti aiuterà.

Answer 2

Vedi questa domanda . The Stony Brook Algorithm Repository ha alcune implementazioni di KDTrees in C ++, sebbene non facciano parte di STL né di Boost.

Answer 3

L'ordinamento di un array richiede O ( n log n ). Il semplice controllo di ciascun punto singolarmente (senza ordinamento) richiede tempo O ( n ).

Ergo, basta passare e controllare ogni punto è più veloce rispetto all'ordinamento. Ed è anche più veloce della costruzione di un quadrifoglio.

EDIT: se hai molti rettangoli da controllare, è una storia diversa. Ma se hai solo bisogno di controllare un piccolo numero fisso di rettangoli, fai semplicemente il "ovvio" modo!

Answer 4

usa un quadtree e hai 3 tipi di nodi qtree:

Il nodo
1. è esterno al rettangolo di destinazione: ignora
2. il nodo si trova all'interno del rettangolo di destinazione: include tutti i punti all'interno del nodo
3. il nodo è parzialmente esterno al rettangolo: verifica i limiti sui punti all'interno del nodo

Answer 5

Seguendo il link di Yuval F, ho trovato Ricerca intervallo , che sembra essere esattamente il tipo di cosa che stai cercando. Ho seguito alcuni link da lì e ho trovato CGAL , una libreria C ++ open source, che implementa una ricerca di intervallo, con esempi qui .

Answer 6

La tua funzione di ordinamento potrebbe controllare i punti quando vengono aggiunti per l'interno del rettangolo, e ordinare tutti i punti all'interno del rettangolo prima di tutti i punti all'esterno del rettangolo. Dovresti tenere traccia di quanti ne esistono ciascuno o utilizzare una ricerca binaria sull'intero set per trovare il punto di interruzione al momento della ricerca.