다른 벡터를 기반으로 한 점의 벡터를 정렬하십시오.

Question

저는 C++ 응용 프로그램을 만들고 있습니다.

제가

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

Point2f가 typedef Point_<float> Point2f;

vectorAll 정의 vectorSpecial 10 점을 갖는다 1,000 포인트가되는 점의 2 개 경로를 갖는다.

첫 번째 단계 : 나는 vectorAll의 순서에 따라 vectorSpecial에 포인트를 주문해야

. 이 같은 그래서 뭔가 :

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

내가 이중 루프를하고 인덱스를 저장할 수 있습니다. 인덱스에 따라 포인트를 정렬하십시오. 그러나이 방법은 많은 포인트 (예 : vectorAll의 10000 포인트와 vectorSpecial의 1000 포인트이므로 1 천만 반복이므로)를 사용하면 너무 오래 걸립니다.

더 좋은 방법은 무엇입니까?

두 번째 단계 : vectorSpecial에서

어떤 점 vectorAll에서 제공되지 않을 수 있습니다. 가장 가까운 점을 취해야합니다 (일반적인 거리 공식 sqrt((x1-x2)^2 + (y1-y2)^2)을 사용하여)

이 작업은 루핑 할 때 수행 할 수 있지만 더 나은 방법에 대한 제안이 있으면 감사하겠습니다.

덕분에 어떤 도움이 많이

Answer 1

당신은 vectorSpecial의 계정에 내용을하도록 설계 Compare 기능을 vectorAll에 std::sort을 사용할 수 있습니다 : 당신의 첫 번째 단계, 당신이 할 수있는 내용은

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

C++ 11 람다를 사용하여 (special.size() = K 및 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]; 
}); 

설명 첫째 special 모든 지점은 indices 벡터에 결과 all의 시작과 all의 특별한 요소의 위치 및 점포 간의 거리를 계산한다. 둘째, 모든 요소 쌍을 indices 벡터의 해당 요소와 비교하여 special의 모든 요소를 ​​정렬합니다. 당신의 두 번째 단계를 들어

, 당신은 단지 당신이 인덱스

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

설명을 계산하는 방식 변경해야합니다 : 유일하게 변화 첫 번째 단계와 비교하는 것은 special의 모든 요소에 대해 당신이 찾을 것입니다 요소가 가장 가까운 all에 있습니다. 질문에서 제안한대로 최소 유클리드 거리를 계산하면됩니다.

UPDATE : 당신은 우선 std::unordered_map 해시 테이블에 all의 각 요소의 인덱스를 저장하고, 그 해시 테이블에 대한 조회에 기초 special의 소자들 사이의 비교를 수행하여 공간/시간의 트레이드 오프를 할 수있다. 이는 첫 번째 단계의 시간 복잡도를 O (N) (K < N으로 가정)로 줄이지 만 해시 테이블에 O (N)의 저장 공간을 추가합니다.