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

Question

您可以通过注意线段的斜率 (a, a, b, 和 c 来测试三个二维点是否落在一条线上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

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

Answer 2

如果您的坐标表示为具有有限精度的浮点数，则无法正确执行 all[=17= 的共线性测试] 可能的情况 - 这意味着您将不可避免地遇到一些情况，当此测试会给您错误的结果时。

您可以尝试 CGAL library, where this problem has been solved using more sophisticated coordinate representation. Actually, the collinearity test is used in the CGAL tutorial to explain differences between such representations - please read this 页面了解更多信息。

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

Testing three points for collinearity in a numerically robust way

c++

numerical-methods

computational-geometry