避免浮点运算的最大线上点问题

Question

我正在尝试解决Leet代码中的"Max Points on Line“问题。我不可避免地需要做浮点运算来计算每条线的Y-截距和斜率。由于我过去的糟糕经历，我尽量避免浮点运算。你有什么建议吗?我该怎么做呢？

我使用LeetCode框架进行开发，几乎只能访问标准的C++库。尝试使用double或long double，但其中一个测试用例已经将数字推到了这些数据类型的准确性极限。

//P1[0] is X coordinate for point P1 and P1[1] is Y coordinate

long double slopeCalc( vector<int> &p1, vector<int> &p2 )
{
    if( p1[0] == p2[0] && p1[1] == p2[1] )
    {
        return DBL_MIN;
    }

    if( p1[0] == p2[0] && p1[1] != p2[1] )
    {
        return DBL_MAX;
    }

    return ( (long double)p2[1] - (long double)p1[1] ) / ((long double)p2[0] - (long double)p1[0]);
}

long double yIntersectionCalc( vector<int> &p1, vector<int> &p2 )
{
    if( p1[0] == p2[0] && p1[1] == p2[1] )
    {
        return DBL_MIN;
    }

    if( p1[0] == p2[0] && p1[1] != p2[1] )
    {
        return DBL_MAX;
    }

    return ((long double)p1[1]*(long double)p2[0] - (long double)p2[1]*(long double)p1[0]) / (long double)(p2[0] - p1[0]);        
}

如果两个点分别为(94911150，0)和(94911150,94911151)，则坡度将计算为1，这是不准确的。如果可能的话，我会尽量避免浮点除法。

注:线上的最大点数问题是在2D空间中给出点(在这种情况下是整数坐标)，并找出在一条线上的最大点数。例如，如果点是(0,0)，(2,2)，(4,3)，(1,1)，答案是3，它们是点(0,0)，(1,1)和(2,2)

Answer 1

在整数坐标中，三个点的对齐测试可写为表达式

(Xb - Xa) (Yc  - Ya) - (Yb - Ya) (Xc - Xa) = 0

假设坐标范围需要N位，增量的计算需要N+1位，表达式的精确计算需要2N+2位。你对此几乎无能为力。

在您的例子中，64位整数应该足够了。

一条建议:避免使用斜率/截距表示。

Answer 2

如果要避免使用浮点数，则可以通过计算矩阵的行列式来确定一个点z是否与其他两个点x和y共线

{{1,z1,z2},{1,x1,x2},{1,y1,y2}}

如果行列式为0，则它们是共线的。由于使用置换定义计算行列式只涉及乘法和加法/减法，因此所有计算都将保留为整数。它将是0的原因是行列式是以x，y，z为顶点的三角形面积的两倍，当且仅当三角形退化时，行列式为零。

另一种方法是使用分数对象，特别是由两个整数定义的线的斜率和截距被标识为分数(“有理数”)，而减少的分数由其分子和分母标识，因此您可以使用这对分数(斜率，截距)作为标识符，并且由于您从不使用浮点运算，因此不需要处理舍入误差。有关分数的示例实现，请参阅https://martin-thoma.com/fractions-in-cpp/，重要的部分是您可以使用算术运算符和归一化。

编辑: boost有一个有理数库，如果你想使用它https://www.boost.org/doc/libs/1_68_0/libs/rational/

Answer 3

给定点a,b,c，看看b,c到一个公共点的坡度a

ba.x = b.x - a.x
ba.y = b.y - a.y

ba.s = ba.y / ba.x

ca.x = c.x - a.x
ca.y = c.y - a.y

ca.s = ca.y / ca.x

当线AB和BC具有共同的斜率时，点a,b,c是共线的，即：

ba.s == ca.s

替换和重新排列以删除分隔符：

ba.y / ba.x == ca.y / ca.x
ba.y * ca.x / ba.x == ca.y
ba.y * ca.x == ca.y * ba.x

在原始公式中用这些替换，那么a,b,c是共线性的当量：

(b.y - a.y) * (c.x - a.x) == (c.y - a.y) * (b.x - a.x)

请注意，行列式答案也可以重新排列为这种形式，这证明了这种方法。但是这种形式只有2次乘法，而不是12次简单的行列式实现。