c++ - 以数值稳健的方式测试三个点的共线性

Question

您可以通过注意线段的斜率来测试三个二维点 a、b 和 c 落在一条线上(a,b) 必须与 (b,c) 相同，或者通过请注意，当且仅当这三个点共线时，它们定义的三角形面积将为零。我选择了前一种方法，因为数学看起来更简洁:this answer contains the formula .

上面的问题在于，尽管当我们将测试转换为代码时数学是完全正确的，但考虑到浮点类型的基本不精确性，它的表现很差。考虑以下 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) ? "yes\n" : "no\n"); // no

    std::cout << "are_collinear(a, b, c, 0.1) => "
        << (are_collinear(a, b, c, 0.1) ? "yes\n" : "no\n"); // no

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

该代码中的三个点如下所示:

发生的事情是 are_collinear(...) 中的 test 计算出大约 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) ? "yes\n" : "no\n"); // yes

    std::cout << "are_collinear(a, b, c, 0.1) => "
        << (are_collinear(a, b, c, 0.1) ? "yes\n" : "no\n"); // yes

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

上面解决了这个问题，但我有两个问题(1)它是任意的，因为我是凭直觉来组成比例因子的；(2)我最初选择斜率方法是因为代码是一个-衬垫;新版本明显更长，因此为了简洁而选择此测试不再有意义。

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

Answer 1

对于具有数值意义的测试，请考虑最长边长度上的(双)区域。这给你中间点与其他两个线的偏差。它以长度为单位。