如何计算两条线的交点

Question

我正在尝试使用霍夫变换计算光流算法的线之间的交点。但是，当我使用我的算法计算交叉点时，我没有得到应有的点数。

我将线条保存为我创建的名为

ImageLine

的类的实例。这是我的交集方法的代码。

Point ImageLine::intersectionWith(ImageLine other)
{
    float A2 = other.Y2() - other.Y1();
    float B2 = other.X2() - other.X1();
    float C2 = A2*other.X1() + B2*other.Y1();

    float A1 = y2 - y1;
    float B1 = x2 - x1;
    float C1 = A1 * x1 + B1 * y1;

   float det = A1*B2 - A2*B1;
   if (det == 0)
   {
        return Point(-1,-1);
   }
   Point d = Point((B2 * C1 - B1 * C2) / det, -(A1 * C2 - A2 * C1) / det);
   return d;
}

这个方法正确吗，还是我做错了什么？据我所知，它应该有效，就像我硬编码的单个点一样，但是，在使用真实数据时，我无法获得良好的交集。

Answer 1

考虑数学方面：如果我们有两个直线方程：

y = m1 * x + c1
y = m2 * x + c2

交点：(X , Y)，由以下方程描述的两条线：

Y = m1 * X + c1
Y = m2 * X + c2

是满足两个方程的点，即：

m1 * X + c1 = m2 * X + c2
(Y - c1) / m1 = (Y - c2) / m2

因此交点坐标为：

交集X = (c2 - c1) / (m1 - m2)
交集Y = (m1*c1 - c2*m2) / m1-m2 或交集Y = m1 * 交集X + c1

注意：c1、m1 和 c2、m2 是通过获取直线上的任意 2 个点并将它们放入直线方程来计算的。

Answer 2

当您使用浮点运算时，

(det == 0)

不太可能成立，因为它不精确。

通常使用类似

(fabs(det) < epsilon)

的值来表示 epsilon 的某个合适值（例如，

1e-6

）。

如果这不能解决问题，请显示一些实际数字，以及预期结果和实际结果。

Answer 3

详细公式请至此页。

但是我喜欢代码，所以在这里检查此代码（我从 github 获取它，所以所有功劳都归于该代码的作者）：

编辑：如果没有此摘录，来自 github 链接的前置代码甚至无法编译。

#include <iostream>
#include <cmath>
#include <assert.h>
using namespace std;

/** Calculate determinant of matrix:
        [a b]
        [c d]
*/
inline double Det(double a, double b, double c, double d)
{
        return a*d - b*c;
}
///Calculate intersection of two lines.
///\return true if found, false if not found or error
bool LineLineIntersect(double x1, double y1, //Line 1 start
    double x2, double y2, //Line 1 end
    double x3, double y3, //Line 2 start
    double x4, double y4, //Line 2 end
    double &ixOut, double &iyOut) //Output 
{
    //http://mathworld.wolfram.com/Line-LineIntersection.html

    double detL1 = Det(x1, y1, x2, y2);
    double detL2 = Det(x3, y3, x4, y4);
    double x1mx2 = x1 - x2;
    double x3mx4 = x3 - x4;
    double y1my2 = y1 - y2;
    double y3my4 = y3 - y4;

    double xnom = Det(detL1, x1mx2, detL2, x3mx4);
    double ynom = Det(detL1, y1my2, detL2, y3my4);
    double denom = Det(x1mx2, y1my2, x3mx4, y3my4);
    if(denom == 0.0)//Lines don't seem to cross
    {
        ixOut = NAN;
        iyOut = NAN;
        return false;
    }

    ixOut = xnom / denom;   
    iyOut = ynom / denom;
    if(!isfinite(ixOut) || !isfinite(iyOut)) //Probably a numerical issue
        return false;

    return true; //All OK
}

Answer 4

假设您的公式正确，请尝试将所有中间参数声明为“double”。获取几乎平行线的差异可能会导致您的产品彼此非常接近，因此“浮动”可能无法保持足够的精度。