ordenar un vector de puntos basado en otro vector

Question

Estoy trabajando en una aplicación C++.

tengo 2 vectores de puntos

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

Point2f se define typedef Point_<float> Point2f;

vectorAll tiene 1000 punto mientras vectorSpecial tiene 10 puntos.

Primer paso:

necesito para ordenar los puntos en vectorSpecial en función de su orden en vectorAll. Así que algo como esto:

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

que puede hacer un bucle doble y guardar los índices. y luego ordena los puntos según sus índices. Sin embargo, este método lleva demasiado tiempo cuando tenemos muchos puntos (por ejemplo, 10000 puntos en vectorAll y 1000 puntos en vectorSpecial así que son diez millones de iteraciones)

¿Cuáles son los mejores métodos para hacerlo?

Segundo paso:

Algunos puntos en vectorSpecial podrían no estar disponibles en vectorAll. Necesito tomar el punto más cercano (usando la fórmula de distancia habitual sqrt((x1-x2)^2 + (y1-y2)^2))

Esto también se puede hacer cuando se realiza un bucle, pero si alguien tiene alguna sugerencia para mejores métodos, se lo agradecería.

Muchas gracias por cualquier ayuda

Answer 1

Usted puede utilizar std::sort en vectorAll con la función Compare diseñado para tener en cuenta el contenido de 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

Para su primer paso, puede utilice C++ 11 lambda con gran efecto (special.size() = K, y 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]; 
}); 

Explicación: primero, para cada punto en special, calcular la distancia entre el comienzo de all y la ubicación del elemento especial en all, y tienda que resulta en el vector de indices. Segundo, clasifique todos los elementos de special comparando para cada par de elementos los elementos correspondientes en el vector indices.

Para su Segundo Paso, es suficiente con cambiar la forma de calcular los índices

// 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  
     }); 
    ); 
}); 

Explicación: el único cambio en comparación con el primer paso es que por cada elemento en special a encontrar la elemento en all que está más cerca de él, lo cual se hace calculando la distancia euclidiana mínima como sugirió en su pregunta.

ACTUALIZACIÓN: Se podría hacer un compromiso de espacio/tiempo al tener primero el índice de cada elemento de all en una tabla de hash std::unordered_map, y luego hacer la comparación entre los elementos de special sobre la base de las operaciones de búsqueda en esa tabla hash. Esto reduce la complejidad de tiempo del primer paso a O (N) (suponiendo K < N), pero agrega O (N) de almacenamiento para la tabla hash.