點基於另一個向量的點向量

我有

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

Point2f定義typedef Point_<float> Point2f;

vectorAll有1000點，同時具有vectorSpecial 10分點的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點，所以這是千萬次迭代），這種方法花費的時間太長了。

什麼是更好的方法？

第二步：

在vectorSpecial幾點可能無法在vectorAll可用。我需要採取最接近它的點（通過使用通常距離公式sqrt((x1-x2)^2 + (y1-y2)^2)）

這也可以在循環時完成，但如果有人有任何更好的方法的建議，我將不勝感激。

非常感謝您的幫助

來源

2012-07-05 Youssef

請注意，調用STL算法不會消除循環，它只是將它們隱藏在抽象層之後。 – TemplateRex 2012-07-05 10:28:08

您可以在vectorAll使用std::sort與Compare功能設計要考慮到的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);

來源

2012-07-05 09:31:44

看來這是我所需要的。但有2件事：1）在運算符函數中，它將其作爲輸入2點並比較它們的x和y？ 2）我需要排序「特殊」向量而不是「全部」，所以我通過調用'std :: sort（special.begin（），special.end（），compareObject）;'？我不是非常有經驗的C++謝謝你回答 – Youssef 2012-07-05 09:43:56

@Youssef ok。那麼你的操作員應該把2點作爲參數，而不是int - 這只是一個例子。對於第二個問題，是的，我認爲你想排序所有。將編輯。 – 2012-07-05 09:47:43

@Youssef編輯。 – 2012-07-05 09:48:33

爲了您第一步，你可以使用C++ 11 lambda的效果很好（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每個點，計算的all開始和特殊元件的在all的位置，並存儲導致進入indices矢量之間的距離。其次，通過比較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：您可以通過第一存儲all每個元素的索引到一個std::unordered_map哈希表，然後做基於查找到該哈希表的special元素之間的比較做出一個空間/時間權衡。這將第一步的時間複雜度減少到O（N）（假設K < N），但爲散列表添加O（N）存儲。

來源

2012-07-05 10:11:12 TemplateRex

點基於另一個向量的點向量

回答

相關問題