我如何通过地图的严格弱排序对数学向量进行排序?

How do i sort mathematical vectors by strict weak ordering for a map?

我尝试编写一个 std::map,其中共线(平行或反平行)向量应共享相同的键。

作为比较函数,我使用了我在 Using a (mathematical) vector in a std::map

的帮助下创建的以下函数(在 isEqualEnough() 中具有 1e-9 容差)
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 个:

比较函数有点错误,但每当我尝试修复它时,我都会得到一个断言告诉我 "Expression: invalid comparator"。

有人发现错误了吗?

在数学上不可能对关系运算符使用公差并产生严格的弱排序。任何一种收敛准则都无法满足排序算法和数据结构的要求。原因很简单:两个值的不相容性,使用公差,不会产生 等价关系 ,因为它 不可传递 。您可能有 almostEqual(a, b)almostEqual(b, c),但还有 ~almostEqual(a, c)。使用 a=1.0; b=2.0; c=3.0; tolerance=1.5; 试试这个。你可以看看这个答案:Is floating-point == ever OK?.

您仍然可以使用截断函数、floor、roof 或 round 类函数在浮点数上定义等价关系。让我们定义例如 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 的情况下,您可以使用浮点数上的普通 < 运算符回退。

将 Julien Villemure-Fréchette 的回答与@alterigel 发布的 link 相结合,我使我的比较函数起作用:

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