分区的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的矢量指向

回答

相关问题