时间戳

首页 > 解决方案 > Improve numerical accuracy of LineLine intersection method (3D)

c++ - Improve numerical accuracy of LineLine intersection method (3D)

问题描述

I coded the following LineLine intersection method:

double LineLineIntersection(
    const Eigen::Vector3d& origin1,
    const Eigen::Vector3d& ray1,
    const Eigen::Vector3d& origin2,
    const Eigen::Vector3d& ray2)
{
    if(abs((origin1 - origin2).norm() - 1.0) < 0.000001) return 0;
    auto n1 = (origin2 - origin1).cross(ray2);
    auto n2 = ray1.cross(ray2);

    // Use this to test whether the vectors point in the same or opposite directions
    auto n = n2.normalized();
    // If n2 is the 0 vector or if the cross products are not colinear, no solution exists
    if(n2.norm() < 0.00001 || abs(abs(n1.dot(n)) - n1.norm()) > 0.000001)
        return std::numeric_limits<double>::infinity();;

    return n1.dot(n) / n2.dot(n);
}

The theory for how this works is explained here. However the page has a mistake, taking just the absolute value has only the magnitude, it erases the direction. So instead, the dot product with the cross direction must be taken. That way the distance can be either positive or negative depending on whether the vectors point in the same direction or not.

This technically works but I am running into big numerical errors. For example in one of my tests I am getting:

The difference between i1.x() and Eigen::Vector3d(-0.581, 1.232, 0).x() is 0.0024061184231309873, which exceeds 0.001, where
i1.x() evaluates to -0.58340611842313095,
Eigen::Vector3d(-0.581, 1.232, 0).x() evaluates to -0.58099999999999996, and
0.001 evaluates to 0.001.

An error bigger than 0.001 is huge. What can I do to make the method more accurate?

This is the value of i1: -0.583406 1.23237 0 sorry to not have included it before.

标签： c++mathprecisioneigen

解决方案

您正在使用“double”类型，如果它存在于您的 G++ 版本中，请尝试将其更改为“long double”或“__float128”。此外，您可以在 Java 中使用“BigDecimal”以获得更好的准确性，或者使用 Python 中的一些长算法。

推荐阅读