ordina un vettore di punti basato su un altro vettore

Question

Sto lavorando su un'applicazione C++.

Ho 2 vettori di punti

vector<Point2f> vectorAll; 
vector<Point2f> vectorSpecial; 

Point2f è definito typedef Point_<float> Point2f;

vectorAll ha 1000 punti mentre vectorSpecial ha 10 punti.

Primo passo:

ho bisogno di ordinare i punti in vectorSpecial a seconda del loro ordine in vectorAll. Quindi qualcosa di simile:

For each Point in vectorSpecial 
    Get The Order Of that point in the vectorAll 
    Insert it in the correct order in a new vector 

posso fare un doppio anello e salvare gli indici. e quindi ordinare i punti in base ai loro indici. Tuttavia questo metodo richiede troppo tempo quando abbiamo molti punti (ad esempio 10000 punti in vectorAll e 1000 punti in vectorSpecial quindi dieci milioni di iterazioni)

Quali sono i metodi migliori per farlo?

Secondo passo:

Alcuni punti in vectorSpecial potrebbero non essere disponibili in vectorAll. Ho bisogno di prendere il punto più vicino (usando la solita formula di distanza sqrt((x1-x2)^2 + (y1-y2)^2))

Questo può essere fatto anche in loop, ma se qualcuno ha suggerimenti per metodi migliori, lo apprezzerei.

Grazie molto per qualsiasi aiuto

Answer 1

È possibile utilizzare std::sort sul vectorAll con la funzione Compare progettato per prendere in considerazione il contenuto di vectorSpecial:

struct myCompareStruct 
{ 
    std::vector<Point2f> all; 
    std::vector<Point2f> special; 
    myCompareStruct(const std::vector<Point2f>& a, const std::vector<Point2f>& s) 
     : all(a), special(s) 
    { 
    } 
    bool operator() (const Point2f& i, const Point2f& j) 
    { 
     //whatever the logic is 
    } 
}; 

std::vector<Point2f> all; 
std::vector<Point2f> special; 
//fill your vectors 
myCompareStruct compareObject(all,special); 

std::sort(special.begin(),special.end(),compareObject); 

Answer 2

Per la vostra First Step, è possibile usa C++ 11 lambda's con grande effetto (special.size() = K e all.size() = N)

#include <algorithm> // std::sort, std::transform, std::find, std::min_element 
#include <iterator> // std::distance 

std::vector<int> indices; 
indices.reserve(special.size()); 

// locate exact index in all for every element of special. Complexity = O(K * N) 
std::transform(special.begin(), special.end(), indices.begin(), [&all](Point2f const& s){     
    return std::distance(
     all.begin(), 
     std::find(all.begin(), all.end(), s) 
    ); 
}); 

// sort special based on index comparison. Complexity = O(K * log(K)) 
std::sort(special.begin(), special.end(), [&indices](Point2f const& r, Point2f const& s){ 
    auto i = std::distance(special.begin(), r); 
    auto j = std::distance(special.begin(), s); 
    return indices[i] < indices[j]; 
}); 

Spiegazione: prima, per ogni punto in special, calcolare la distanza tra l'inizio del all e la posizione dell'elemento speciale all, e negozio che risultato nella indices vettoriale. In secondo luogo, ordina tutti gli elementi di special confrontando per ogni coppia di elementi gli elementi corrispondenti nel vettore indices.

Per la vostra Secondo passo, dovete solo cambiare il modo di calcolare gli indici

// locate closest element in all for every element of special. Complexity = O(K * N) 
std::transform(special.begin(), special.end(), indices.begin(), [&all](Point2f const& s){     
    return std::distance(
     all.begin(), 
     std::min_element(all.begin(), all.end(), [&s](Point2f const& a){ 
       return // Euclidean 2D-distance between a and s  
     }); 
    ); 
}); 

Spiegazione: l'unica variazione rispetto al tuo primo passo è che per ogni elemento in special a trovare il elemento in all che è più vicino ad esso, che si ottiene calcolando la distanza euclidea minima come suggerito nella domanda.

AGGIORNAMENTO: Si potrebbe fare un compromesso spazio/tempo memorizzando prima l'indice di ogni elemento di all in una tabella hash std::unordered_map, e poi fare il confronto tra elementi di special sulla base di ricerca in quella tabella di hash. Ciò riduce la complessità temporale del primo passaggio a O (N) (assumendo K < N), ma aggiunge O (N) di spazio di archiviazione per la tabella hash.