yêu cầu một véc tơ các điểm dựa trên một vector khác

Question

Tôi đang làm việc trên ứng dụng C++.

tôi có 2 vectơ điểm

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

Point2f được định nghĩa typedef Point_<float> Point2f;

vectorAll có 1.000 điểm trong khi vectorSpecial có 10 điểm.

Bước đầu tiên:

tôi cần phải ra lệnh cho các điểm trong vectorSpecial tùy thuộc vào thứ tự của chúng trong vectorAll. Vì vậy, một cái gì đó như thế này:

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

Tôi có thể làm một vòng lặp đôi và lưu chỉ mục. và sau đó sắp xếp các điểm dựa trên các chỉ mục của chúng. Tuy nhiên, phương pháp này mất quá nhiều thời gian khi chúng tôi có nhiều điểm (ví dụ 10000 điểm trong vectơTất cả và 1000 điểm trong vectơ đặc biệt nên đó là mười triệu lần lặp lại)

Phương pháp nào tốt hơn?

Bước thứ hai:

Một số điểm trong vectorSpecial có thể không có sẵn trong vectorAll. Tôi cần phải lấy điểm gần nhất với nó (bằng cách sử dụng công thức khoảng cách thông thường sqrt((x1-x2)^2 + (y1-y2)^2))

Điều này cũng có thể được thực hiện khi lặp, nhưng nếu ai đó có bất kỳ gợi ý nào cho phương pháp tốt hơn, tôi sẽ đánh giá cao nó.

Cảm ơn rất nhiều sự giúp đỡ nào

Answer 1

Bạn có thể sử dụng std::sort trên vectorAll với Compare chức năng được thiết kế để đưa vào tài khoản các nội dung của 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

Đối với bạn Đầu tiên Bước, bạn có thể sử dụng C++ 11 lambda để có hiệu ứng tuyệt vời (special.size() = K, và 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]; 
}); 

Giải thích: thứ nhất, cho tất cả các điểm trong special, tính toán khoảng cách giữa đầu all và vị trí của các yếu tố đặc biệt trong all, và cửa hàng mà kết quả vào indices vector. Thứ hai, sắp xếp tất cả các phần tử của special bằng cách so sánh cho mỗi cặp phần tử các phần tử tương ứng trong vector indices.

Đối Second bạn Bước, bạn chỉ cần thay đổi cách bạn tính toán chỉ số

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

Giải thích: sự thay đổi duy nhất so với Bước đầu tiên của bạn là đối với mỗi phần tử trong special bạn tìm thấy phần tử trong all gần nhất với nó, mà bạn làm bằng cách tính toán khoảng cách Euclide tối thiểu như bạn đã đề xuất trong câu hỏi của bạn.

CẬP NHẬT: Bạn có thể làm cho một sự cân bằng không gian/thời gian bằng cách đầu tiên lưu trữ các chỉ số của mọi phần tử của all vào một bảng std::unordered_map băm, và sau đó thực hiện việc so sánh giữa các yếu tố của special dựa trên tra cứu vào đó bảng băm. Điều này làm giảm thời gian phức tạp của bước đầu tiên thành O (N) (giả sử K < N), nhưng thêm O (N) dung lượng lưu trữ cho bảng băm.