分區的std :: 2D的矢量指向

假設我有一個std::vector<Point>其中Point是struct Point { double x; double y;} 我想這樣的載體分成組（存儲桶），其中在同一個桶中的所有點具有彼此之間相同歐幾里得範數（例如dist（PointA，PointB）== X，其中X是常數）。我已經決定使用std::map這樣的任務自定義排序操作：分區的std :: 2D的矢量指向

struct ClosePoints 
{ 
    bool operator()(Point const& A, Point const& B) const 
    { 
     bool same = dist(A,B) < x; 
     //If not close enough use lexical sort 
     return same ? false : std::tie(A.x, A.y) < std::tie(B.x,); 
    } 
}

分區代碼：

std::map<Point, std::list<Point>, ClosePoints> map; 
for(const auto& p : pointsVector) 
    map[p].push_back(p);

經過一番測試，並打印我注意到，有些點是聽從了給予桶歐幾里得標準限制X以不同的桶結束。我不明白爲什麼這樣？

來源

2016-07-28 JobNick

我建議您提供一個完整的，可編譯的工作示例，包括測試輸入，可以重現您的問題。 – vordhosbn

1）什麼是'x'？ 2）什麼是'dist（）'？ 3）如果dist（A，B） PaulMcKenzie

您的操作員不遵循嚴格的排序規則，因爲A <= A + eps'和'A + eps <= A + 2 * eps'，但不是'A <= A + 2 * eps'。 – Jarod42

問題是您定義的比較運算符不提供等價關係。例如，你可以有一個接近於A和C的點B，但是點A和C可以相距很遠。因此，如果您將B與A和C進行比較，您會將它們與B放在同一個籃子中。但是，如果首先主持A和C，結果將不可預測。

來源

2016-07-28 16:31:44 slav

這是正確的一般情況下，但在我的情況（我正在處理的數據）這樣的點ABC從你的例子都將服從的距離：（A，B）（B，C）（C，A）將都有相同的距離彼此 – JobNick

@JobNick好吧，我假設你有彼此的距離大於x，並且每個子集可以放置在半徑爲x的球中。那麼你的邏輯是正確的。但是，您需要訂購不同的子集才能使操作員工作。這沒有解決方案，因爲操作符可能僅基於整個子集的幾何特徵，例如，所有元素的平均座標，整個子集的某個座標的最小值或最大值。它可以很容易證明。 – slav

我認爲問題是元素插入的順序。也許在某個時間點，當樹重新平衡自身時，已經具有代表性集合的元素的插入創建它自己的樹節點（集合）。 – JobNick

分區的std :: 2D的矢量指向

回答

相關問題