以数值稳健的方式测试三点的共线性

可以测试三个二维点，a，b，和c，落在一条线通过注意线段（的斜率a，b）将必须是相同的（b，c），或通过注意到它们限定的三角形的面积当且仅当三个点共线时才为零。我选择了前一种方法，因为数学看起来更简洁：这个答案包含公式。

上面的问题是，虽然当我们将测试转换为代码时数学是完全正确的，但我们发现它的表现很差，因为浮点类型的基本不精确性。考虑以下 C++：

using point = std::tuple<float, float>;

bool are_collinear(point a, point b, point c, float eps) {
    auto [a_x, a_y] = a;
    auto [b_x, b_y] = b;
    auto [c_x, c_y] = c;

    auto test = (b_x - a_x) * (c_y - a_y) - (c_x - a_x) * (b_y - a_y);
    return std::abs(test) < eps;
}

int main()
{
    point a = { 28.8171,77.9103 };
    point b = { 55.7515,75.5051 };
    point c = { 122.831,69.8003 };

    std::cout << "are_collinear(a, b, c, 0.01) => "
        << (are_collinear(a, b, c, 0.001) ? "yesn" : "non"); // no

    std::cout << "are_collinear(a, b, c, 0.1) => "
        << (are_collinear(a, b, c, 0.1) ? "yesn" : "non"); // no

    std::cout << "are_collinear(a, b, c, 10) => "
        << (are_collinear(a, b, c, 10) ? "yesn" : "non"); // yes
}

该代码中的三点如下所示：

正在发生的事情是，testinare_collinear(...)大约为 7.685，这远远超出了我们认为可接受的误差的典型值。这里的问题是公式中的项是绝对坐标中的相对长度的乘积，例如(b_x - a_x) * (c_y - a_y)。为了使这个函数表现得更好，我们需要以某种方式对坐标进行归一化。

下面我缩放坐标，使三角形 (a,b,c) 的最长边的长度为 1 个单位：

using point = std::tuple<float, float>;

float distance(point a, point b) {
    auto [a_x, a_y] = a;
    auto [b_x, b_y] = b;
    auto x_diff = a_x - b_x;
    auto y_diff = a_y - b_y;
    return std::sqrt(x_diff * x_diff + y_diff * y_diff);
}

float max_distance(point a, point b, point c) {
    auto d1 = distance(a, b);
    auto d2 = distance(b, c);
    auto d3 = distance(a, c);
    return std::max(d1, std::max(d2, d3));
}

bool are_collinear(point a, point b, point c, float eps) {
    auto scale = max_distance(a, b, c);
    if (scale == 0)
        return true; // they are the same point.

    auto [a_x, a_y] = a;
    auto [b_x, b_y] = b;
    auto [c_x, c_y] = c;

    a_x /= scale;
    a_y /= scale;
    b_x /= scale;
    b_y /= scale;
    c_x /= scale;
    c_y /= scale;

    auto test = (b_x - a_x) * (c_y - a_y) - (c_x - a_x) * (b_y - a_y);
    return std::abs(test) < eps;
}

int main()
{
    point a = { 28.8171,77.9103 };
    point b = { 55.7515,75.5051 };
    point c = { 122.831,69.8003 };

    std::cout << "are_collinear(a, b, c, 0.01) => "
        << (are_collinear(a, b, c, 0.001) ? "yesn" : "non"); // yes

    std::cout << "are_collinear(a, b, c, 0.1) => "
        << (are_collinear(a, b, c, 0.1) ? "yesn" : "non"); // yes

    std::cout << "are_collinear(a, b, c, 10) => "
        << (are_collinear(a, b, c, 10) ? "yesn" : "non"); // yes
}

以上解决了问题，但我有两个问题（1）它是任意的，因为我凭直觉构成了缩放因子；（2）我最初选择斜率方法是因为代码是单行的；新版本明显更长，因此为了简洁而选择此测试不再有意义。

有没有比我的第二个版本更好的方法来执行这个测试，我遗漏的代码有什么问题吗？

回答