检查线是否相交，如果相交，则返回坐标 [英] Checking if lines intersect and if so return the coordinates
问题描述
我在下面编写了一些代码，以检查两个线段是否相交以及它们是否确实告诉我在哪里.作为输入，我具有每行两端的(x，y)坐标.它似乎工作正常，但是现在在A行(532.87,787.79)(486.34,769.85)和B行(490.89,764.018)(478.98,783.129)的情况下，当它们在(770.136，487.08)相交时根本不相交.
I've written some code below to check if two line segments intersect and if they do to tell me where. As input I have the (x,y) coordinates of both ends of each line. It appeared to be working correctly but now in the scenario where line A (532.87,787.79)(486.34,769.85) and line B (490.89,764.018)(478.98,783.129) it says they intersect at (770.136, 487.08) when the lines don't intersect at all.
有人知道下面的代码有什么不正确吗?
Has anyone any idea what is incorrect in the below code?
double dy[2], dx[2], m[2], b[2];
double xint, yint, xi, yi;
WsqT_Location_Message *location_msg_ptr = OPC_NIL;
FIN (intersect (<args>));
dy[0] = y2 - y1;
dx[0] = x2 - x1;
dy[1] = y4 - y3;
dx[1] = x4 - x3;
m[0] = dy[0] / dx[0];
m[1] = dy[1] / dx[1];
b[0] = y1 - m[0] * x1;
b[1] = y3 - m[1] * x3;
if (m[0] != m[1])
{
//slopes not equal, compute intercept
xint = (b[0] - b[1]) / (m[1] - m[0]);
yint = m[1] * xint + b[1];
//is intercept in both line segments?
if ((xint <= max(x1, x2)) && (xint >= min(x1, x2)) &&
(yint <= max(y1, y2)) && (yint >= min(y1, y2)) &&
(xint <= max(x3, x4)) && (xint >= min(x3, x4)) &&
(yint <= max(y3, y4)) && (yint >= min(y3, y4)))
{
if (xi && yi)
{
xi = xint;
yi = yint;
location_msg_ptr = (WsqT_Location_Message*)op_prg_mem_alloc(sizeof(WsqT_Location_Message));
location_msg_ptr->current_latitude = xi;
location_msg_ptr->current_longitude = yi;
}
FRET(location_msg_ptr);
}
}
FRET(location_msg_ptr);
}
推荐答案
关于线及其相交点，有一个绝对伟大而又简单的理论，其基础是为点和线添加了额外的尺寸.在该理论中，可以用一条代码行从两个点创建一条线，并且可以用一条代码行计算线的交点.此外，无穷远处的点和无穷远处的线可以用实数表示.
There is an absolutely great and simple theory about lines and their intersections that is based on adding an extra dimensions to your points and lines. In this theory a line can be created from two points with one line of code and the point of line intersection can be calculated with one line of code. Moreover, points at the Infinity and lines at the Infinity can be represented with real numbers.
当点[x，y]表示为[x，y，1]而线ax + by + c = 0表示为[a，b，c]时，您可能听说过齐次表示法? 对于点[x，y，w]的一般齐次表示，转换为笛卡尔坐标的值为[x/w，y/w].这个小技巧将使所有的差异包括无限远处的线表示(例如[1，0，0])以及使线表示看起来与第一点相似.这将GREAT对称性引入用于大量线/点操作的公式中，并且 必须在编程中使用绝对值.例如，
You probably heard about homogeneous representation when a point [x, y] is represented as [x, y, 1] and the line ax+by+c=0 is represented as [a, b, c]? The transitioning to Cartesian coordinates for a general homogeneous representation of a point [x, y, w] is [x/w, y/w]. This little trick makes all the difference including representation of lines at infinity (e.g. [1, 0, 0]) and making line representation look similar to point one. This introduces a GREAT symmetry into formulas for numerous line/point manipulation and is an absolute MUST to use in programming. For example,
通过向量积找到线相交非常容易
It is very easy to find line intersections through vector product
p = l1xl2
可以从两点创建一条线的方法类似:
A line can be created from two points is a similar way:
l=p1xp2
在OpenCV的代码中，它只是:
In the code of OpenCV it it just:
line = p1.cross(p2);
p = line1.cross(line2);
请注意，此处不涉及任何边际情况(例如被零除或平行线分隔).我的意思是，我建议重写您的代码，以利用关于线条和点的优美理论.
Note that there are no marginal cases (such as division by zero or parallel lines) to be concerned with here. My point is, I suggest to rewrite your code to take advantage of this elegant theory about lines and points.
最后，如果您不使用openCV，则可以使用3D点类并创建类似于此的叉积函数:
Finally, if you don't use openCV, you can use a 3D point class and create your own cross product function similar to this one:
template<typename _Tp> inline Point3_<_Tp> Point3_<_Tp>::cross(const Point3_<_Tp>& pt) const
{
return Point3_<_Tp>(y*pt.z - z*pt.y, z*pt.x - x*pt.z, x*pt.y - y*pt.x);
}
这篇关于检查线是否相交，如果相交，则返回坐标的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
