Il modo più veloce per trovare il punto più vicino

Se i punti sono in costante movimento, allora è impossibile fare meglio di O(n) , perché devi controllare ogni punto ogni volta che si muove. Hai qualche codice da qualche parte che sposta i punti, basta aggiungere il controllo dei limiti in quel codice. Mantenere una lista ordinata o aggiornare un quadruplo o qualcosa sarebbe più efficace se le posizioni dei punti non cambiano frequentemente e invece stai controllando diverse caselle di delimitazione, ad esempio la ricerca di punti su una mappa, per esempio.

Se i punti si muovono secondo uno schema preimpostato, come in una linea retta a una velocità costante, allora puoi cambiare il tuo algoritmo per fare solo il controllo dei limiti quando la direzione o la velocità sono cambiate. Ad esempio, se stai spostando un pixel al secondo e il riquadro di delimitazione è a 10 pixel di distanza, sai che non devi controllare quel punto per altri 10 secondi. 100 punti è un numero piuttosto piccolo, tuttavia, e in quella piccola scala, il sovraccarico dovuto alla complessità aggiuntiva potrebbe non superare le iterazioni aggiuntive dell'algoritmo più semplice.

Inoltre, quella piccola scala mi fa chiedere se sei sicuro che il controllo dei limiti è il collo di bottiglia. Un computer moderno dovrebbe essere facilmente in grado di controllare i limiti di 100 punti in meno di 10 microsecondi. Lo hai effettivamente misurato?

Se possibile, utilizzerei una struttura dati diversa, progettata per l'indicizzazione spaziale. per esempio. un quadtree (ce ne sono molti altri però)

Ciò dovrebbe consentire (assumendo dati non degenerati) di trovare un punto più vicino in tipici confronti O (log n). Puoi anche usare un DB spaziale per farlo per te.

modifica: i quadrifoli aiutano davvero quando i punti sono (relativamente) statici nella tua casella di ricerca, la tua modifica suggerisce che hai il problema opposto, nel qual caso potresti non essere in grado di fare meglio di O (n) cioè probabilmente non vuoi per costruire un quadruplo ogni volta che i punti si muovono, a meno che non stiate controllando molte caselle di delimitazione per ogni mossa

Come affermato da te, non c'è modo di essere più veloce di O (n). Ogni punto della lista potrebbe essere un successo, quindi è necessario eseguire la scansione dell'intero elenco.

Sarebbe possibile organizzare l'elenco in modo tale da poter terminare anticipatamente la ricerca se è possibile dimostrare che nessuno dei seguenti punti sarà nella casella di delimitazione desiderata. Ad esempio, ordinando il punto con le loro coordinate X, è possibile interrompere la ricerca quando il valore diventa più alto del limite superiore. A seconda del tipo di elenco di punti che ottieni, altri schemi potrebbero essere più efficienti.

Che cosa significa "in costante movimento"?

Per esempio, se questi punti rappresentano particelle che si muovono con una velocità costante e sono influenzate solo dalla collisione con la sfera dura con altre particelle e con il muro, allora è possibile calcolare il tempo di intersezione di ogni particella con il riquadro di delimitazione, e calcolare il tempo per la prossima collisione. Il tempo per l'intersezione successiva può essere mantenuto in una coda di priorità e quando si verifica un'intersezione o una collisione, è necessario solo calcolare, nel tempo O (n), l'intersezione successiva di quella particella / quelle particelle con ogni altra particella.

I meccanismi di questo sono delineati in link e riassunti prima da Karl Bielefeldt.

Se il movimento è casuale, ma i cambiamenti sono piccoli e limitati, c'è un limite massimo su quanto possono muoversi le cose. Usalo come un limite. Ad esempio, se la velocità massima è di 0,1 unità per valutazione e il riquadro di delimitazione è la cella (10,10) - (11,11), puoi facilmente determinare le particelle all'interno di, diciamo, 10 unità di quella cella e sapere che non c'è modo che nessuna altra particella possa raggiungere quella cella per 100 valutazioni.

Se le coordinate cambiano drasticamente ogni volta, allora la ricerca lineare O (n) è la soluzione migliore perché qualsiasi struttura dati (quadtree, griglia hash, ecc.) richiede almeno O (n) tempo per impostare, se solo perché ha bisogno di visitare ogni punto.