C++ 如何计算两条线之间的交点
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16524096/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to calculate the point of intersection between two lines
提问by AndrewSchade
I am attempting to calculate the point of intersection between lines for a Optical Flow algorithm using a Hough Transform. However, I am not getting the points that I should be when I use my algorithm for calculating the intersections.
我正在尝试使用霍夫变换计算光流算法的线之间的交点。但是，当我使用我的算法计算交点时，我没有得到我应该得到的分数。
I save the Lines as an instance of a class that I created called ImageLine. Here is the code for my intersection method.
我将 Lines 保存为我创建的名为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;
}
Is this method correct, or did I do something wrong? As far as I can tell, it should work, as it does for a single point that I hard-coded through, however, I have not been able to get a good intersection when using real data.
这种方法是正确的，还是我做错了什么？据我所知，它应该可以工作，就像我硬编码的单个点一样，但是，在使用真实数据时，我无法获得良好的交集。
回答by sethi
Considering the maths side: if we have two line equations:
考虑数学方面：如果我们有两个直线方程：
y = m1 * x + c1
y = m2 * x + c2
y = m1 * x + c1
y = m2 * x + c2
The point of intersection: (X , Y), of two lines described by the following equations:
由以下等式描述的两条线的交点：(X , Y)：
Y = m1 * X + c1
Y = m2 * X + c2
Y = m1 * X + c1
Y = m2 * X + c2
is the point which satisfies both equation, i.e.:
是满足两个方程的点，即：
m1 * X + c1 = m2 * X + c2
(Y - c1) / m1 = (Y - c2) / m2
m1 * X + c1 = m2 * X + c2
(Y - c1) / m1 = (Y - c2) / m2
thus the point of intersection coordinates are:
因此交点坐标为：
intersectionX = (c2 - c1) / (m1 - m2)
intersectionY = (m1*c1 - c2*m2) / m1-m2 or intersectionY = m1 * intersectionX + c1
交点X = (c2 - c1) / (m1 - m2)
交点Y = (m1*c1 - c2*m2) / m1-m2 或交点Y = m1 * 交点X + c1
Note: c1, m1 and c2, m2 are calculated by getting any 2 points of a line and putting them in the line equations.
注：c1、m1 和 c2、m2 是通过获取一条直线上的任意 2 个点并将它们放入直线方程中来计算的。
回答by Useless
(det == 0)is unlikely to be true when you're using floating-point arithmetic, because it isn't precise.
(det == 0)当您使用浮点运算时，不太可能是真的，因为它不精确。
Something like (fabs(det) < epsilon)is commonly used, for some suitable value of epsilon (say, 1e-6).
(fabs(det) < epsilon)对于某些合适的 epsilon 值（例如，1e-6），通常使用类似的东西。
If that doesn't fix it, show some actual numbers, along with the expected result and the actual result.
如果这不能解决问题，请显示一些实际数字，以及预期结果和实际结果。
回答by 123iamking
For detailed formula, please go to this page.
有关详细公式，请转到此页面。
But I love code so, here, check this code (I get it from github, so all credit goes to the author of that code):
但我喜欢代码，所以，在这里，检查这段代码（我从github得到它，所以所有的功劳都归功于该代码的作者）：
///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
}
回答by NPAssoc
Assuming your formulas are correct, try declaring all your intermediate arguments as 'double'. Taking the difference of nearly parallel lines could result in your products being very close to each other, so 'float' may not preserve enough precision.
假设您的公式是正确的，请尝试将所有中间参数声明为“double”。采用几乎平行的线的差异可能会导致您的产品彼此非常接近，因此“浮动”可能无法保持足够的精度。
