Trova il punto più vicino di un vettore di punti

Question

ho vettore di puntatori a una classe molto semplice Point:

class Point{ 
public: 
    float x; 
    float y; 
    float z; 
}; 

Come faccio a trovare l'oggetto più vicino ad un punto referente utilizzando STL?
Devo prima ordinare il vettore o esiste un modo più efficiente?

Answer 1

L'ordinamento richiede O(n*log(N)), quindi non è molto efficiente. Puoi farlo in O(n) semplicemente iterando tra gli elementi e memorizzando la corrispondenza migliore.

Utilizzando for_each da <algorithm>, è possibile definire una funzione che tiene traccia degli elementi più vicini e completa in O(n).

Oppure, è possibile utilizzare anche min_element, anche da <algorithm>.

Answer 2

Non puoi andare più veloce di un confronto lineare se sai solo che ci sono punti in un vettore. Tuttavia se hai conoscenze aggiuntive molto può essere migliorato. Ad esempio, se si conoscono tutti i punti ordinati e si trovano sulla stessa linea, esiste una soluzione logaritmica.

Inoltre ci sono strutture dati migliori per risolvere il problema, ad esempio uno k-d tree. Non fa parte dell'STL: dovrai implementarlo tu stesso ma è LA struttura dati da utilizzare per risolvere il problema che hai.

Answer 3

La domanda di base è la frequenza con cui si eseguono le query su un singolo insieme di punti.

Se stai per trovare un punto più vicino nel set una volta, allora @Lucian ha ragione: potresti anche lasciare i punti non ordinati, e fare una ricerca lineare per trovare il punto giusto.

Se si esegue un numero relativamente elevato di query rispetto allo stesso insieme di punti, è utile organizzare i dati del punto per migliorare la velocità della query. @izomorphius ha già menzionato un albero k-d, e questo è sicuramente un buon suggerimento. Un'altra possibilità (certamente, abbastanza simile) è un albero di ottobre. Tra i due, trovo un albero di ottobre un po 'più facile da capire. In teoria, un albero k-d dovrebbe essere leggermente più efficiente (in media), ma non ho mai visto molta differenza - anche se forse con dati diversi la differenza sarebbe diventata significativa.

Si noti, tuttavia, che la costruzione di qualcosa di simile a un albero k-D o ottobre-albero non è terribilmente lento, quindi non c'è bisogno di fare un sacco di query in un insieme di punti per giustificare la costruzione di uno. Una query chiaramente non lo giustifica, e probabilmente due non lo faranno - ma contrariamente a quanto suggerisce Luchian, O (N log N) (solo per esempio) non è molto lento. In parole povere, log (N) è il numero di cifre nel numero N, quindi O (N log N) non è realmente molto più lento di O (N). Ciò, a sua volta, significa che non è necessario un numero particolarmente elevato di query per giustificare l'organizzazione dei dati per accelerare ciascuno di essi.

Answer 4

si può provare a utilizzare Quadtree http://en.wikipedia.org/wiki/Quadtree

o qualcosa di simile.