3

我尝试编写一个 std::map< Vector3D, double > ，其中共线（平行或反平行）向量应该共享相同的键。

作为比较函数，我使用以下函数（在 isEqualEnough() 中具有 1e-9 容差），该函数是在使用 std::map 中的（数学）向量的帮助下创建的 

struct Vector3DComparator 
{ 
    bool operator() (const Vector3D& lhsIn, const Vector3D& rhsIn) const
    {
        Vector3D lhs = lhsIn.absolute(); // make all members positive
        Vector3D rhs = rhsIn.absolute(); 

        if ((lhs.z < rhs.z)) 
            return true;

        if ((isEqualEnough(lhs.z, rhs.z)) 
            && (lhs.y < rhs.y)) 
            return true;

        if ((isEqualEnough(lhs.z, rhs.z)) 
            && (isEqualEnough(lhs.y, rhs.y))
            && (lhs.x < rhs.x))
            return true;

        return false;
    }
};

当我将立方体的法线插入我的地图时，我应该得到 3 个不同的值（因为我不关心方向）但我得到 4 个：

  • x=1 y=0 z=0
  • x=0 y=1 z=0
  • x=0 y=0 z=1
  • x=0 y=2.2e-16 z=1

比较函数在某种程度上是错误的，但每当我尝试修复它时，我都会收到一个断言告诉我“表达式：无效比较器”。

有人发现错误吗？

4

2 回答 2

8

在数学上不可能对关系运算符使用容差并产生严格的弱排序。任何一种收敛标准都不能满足排序算法和数据结构的要求。原因很简单：使用容差的两个值的不兼容不会产生等价关系，因为它不是传递性的。你可能有almostEqual(a, b)和almostEqual(b, c)然而~almostEqual(a, c)。尝试使用a=1.0; b=2.0; c=3.0; tolerance=1.5;. 你可以看看这个答案：浮点 == 可以吗？.

您仍然可以使用截断、地板、屋顶或圆形函数定义浮点数的等价关系。例如，让我们定义less3(a, b)当且仅当floor(a * 8) < floor(b * 8)假设 a 和 b 是二进制浮点数并且不是 NAN 并且乘法不会产生相同的有符号无穷大；这使用 3 位精度（十进制为 0.125）比较 a 和 b。现在定义equiv3(a, b)当且仅当!less3(a, b) && ~less3(b, a)。可以证明，eqiv3(a, b)产生适当的等价关系。因为less3是顺序关系并且equiv3是等价关系，所以less3是浮点数上的严格弱顺序（不包括 NAN）。此外，在这种情况下，a * 8 == +INF && b * 8 == +INF || a * 8 == -INF && b * 8 == -INF您可能会在浮点数上使用普通的 < 运算符。

于 2018-11-22T20:37:46.123 回答
2

将 Julien Villemure-Fréchette 的答案与@alterigel 发布的链接相结合，我使我的比较功能起作用：

struct Vector3DComparator 
{ 
    bool operator() (const Vector3D& lhsIn, const Vector3D& rhsIn) const
    {
        int p = 100000; // precision factor

        Vector3D lhs = lhsIn.absolute(); // make all members positive
        Vector3D rhs = rhsIn.absolute();

        auto lhsTied = std::tie((int)(lhs.x * p), (int)(lhs.y * p), (int)(lhs.z * p));
        auto rhsTied = std::tie((int)(rhs.x * p), (int)(rhs.y * p), (int)(rhs.z * p));
        return lhsTied < rhsTied;
    }
};

请注意：此代码包含不良风格，如 c 风格转换、不良命名等。我的函数和类与此处发布的不同。我只是剥离了所有内容以使其易于理解。

编辑：

我注意到另外两个错误：

第一：它并不总是适用于几乎相同的向量。基于@tetorea对我的问题的最后评论，我更改了函数以始终获得非常相似的比较值。我为此使用点积，因为它对于并行向量是±1（或至少接近）。

第二： .absolute() 不起作用，因为使用此函数，两个向量 (-1,1,0) 和 (1,1,0) 被认为是平行的，但它们显然不是。

在下面的代码中，您可以找到更正后的版本：

struct Vector3DComparator 
{ 
    bool operator() (const Vector3D& lhs, const Vector3D& rhs) const
    {
        if (isEqualEnough(fabs(lhs * rhs), 1.0)) // dot product
            return false;

        int p = 100000; // precision factor

        auto lhsTied = std::tie((int)(lhs.x * p), (int)(lhs.y * p), (int)(lhs.z * p));
        auto rhsTied = std::tie((int)(rhs.x * p), (int)(rhs.y * p), (int)(rhs.z * p));

        return lhsTied < rhsTied;
    }
};
于 2018-11-22T21:13:37.103 回答