我知道有许多网站可以解释如何检查两条直线的相交，但是对于这样一个简单的数学任务，我觉得只是复制和粘贴代码非常无聊。更让我沮丧的是，我无法让我的代码工作。我知道带有“我的代码有什么问题？”的问题很蠢，但我不知道我的数学/代码到底哪里出了问题，尽管我的代码已经被很好地注释（除了可耻的变量命名），所以我认为应该会有人对其背后的数学感兴趣：
所以这个算法有4个点a、b、c、d（第1行：a--b，第2行：c--d），它们都有绝对x和y值。首先通过计算deltay/deltax来计算出线的梯度。然后通过使用点a（或相应的c）在线上的事实来计算偏移量。这样我们就将这4个点转换成了这些线的数学表示形式，即方程a + bx，其中x为0表示我们在第一个点（a / c），x为1表示我们在第二个点（b / d）。接下来，我们计算这两条线的交点（基本代数运算）。之后，我们检查交点的x值是否有效。据我所知，一切都正确。有人看到错误了吗？
这已经被经验证是不正确的。该代码不会给出任何错误的正面结果（表示存在交点时），但它会给出错误的负面结果（当实际上存在交点时，它会说不存在交点）。因此，当它说存在交点时是正确的，但如果它说不存在交点，则您不能总是相信我的算法。
同样，我在网上查过，但算法不同（含有一些方向技巧和其他内容），我只是想自己想出一个算法，如果有人能帮忙，我会非常高兴。 :)
编辑：这里是一个最小的不起作用的可重现示例，这次不是Qt，而只是C++：
bool segment::checkforIntersection(QPointF a, QPointF b) { //line 1: a+bx, line 2: c+dx, note that a and c are called offset and bx and dx are called gradients in this code
QPointF bx = b-a;
double firstGradient = bx.y() / bx.x(); //gradient of line 1
//now we have to calculate the offset of line 1: we have b from a+bx. Since QPointF a is on that line, it is:
//a + b * a.x = a.y with a as free variable, which yields a = a.y - b*a.x.
//One could also use the second point b for this calculation.
double firstOffset = a.y() - firstGradient * a.x();
double secondGradient, secondOffset;
for (int i = 0; i < poscount-3; i++) { //we dont check with the last line, because that could be the same line, as the one that emited intersection checking
QPointF c = pos[i];
QPointF d = pos[i+1];
QPointF dx = d-c;
secondGradient = dx.y() / dx.x(); //same formula as above
secondOffset = c.y() - secondGradient * c.x();
//a+bx=c+dx <=> a-c = (d-b)x <=> (a-c)/(d-b) = x
double x = (firstOffset - secondOffset) / (secondGradient - firstGradient);
//we have to check, if those lines intersect with a x \in [a.x,b.x] and x \in [c.x,d.x]. If this is the case, we have a collision
if (x >= a.x() && x <= b.x() && x >= c.x() && x <= d.x()) {
return true;
}
}
return false;
}
所以这个算法有4个点a、b、c、d（第1行：a--b，第2行：c--d），它们都有绝对x和y值。首先通过计算deltay/deltax来计算出线的梯度。然后通过使用点a（或相应的c）在线上的事实来计算偏移量。这样我们就将这4个点转换成了这些线的数学表示形式，即方程a + bx，其中x为0表示我们在第一个点（a / c），x为1表示我们在第二个点（b / d）。接下来，我们计算这两条线的交点（基本代数运算）。之后，我们检查交点的x值是否有效。据我所知，一切都正确。有人看到错误了吗？
这已经被经验证是不正确的。该代码不会给出任何错误的正面结果（表示存在交点时），但它会给出错误的负面结果（当实际上存在交点时，它会说不存在交点）。因此，当它说存在交点时是正确的，但如果它说不存在交点，则您不能总是相信我的算法。
同样，我在网上查过，但算法不同（含有一些方向技巧和其他内容），我只是想自己想出一个算法，如果有人能帮忙，我会非常高兴。 :)
编辑：这里是一个最小的不起作用的可重现示例，这次不是Qt，而只是C++：
#include <iostream>
#include <math.h>
using namespace std;
class Point {
private:
double xval, yval;
public:
// Constructor uses default arguments to allow calling with zero, one,
// or two values.
Point(double x = 0.0, double y = 0.0) {
xval = x;
yval = y;
}
// Extractors.
double x() { return xval; }
double y() { return yval; }
Point sub(Point b)
{
return Point(xval - b.xval, yval - b.yval);
}
};
bool checkforIntersection(Point a, Point b, Point c, Point d) { //line 1: a+bx, line 2: c+dx, note that a and c are called offset and bx and dx are called gradients in this code
Point bx = b.sub(a);
double firstGradient = bx.y() / bx.x(); //gradient of line 1
//now we have to calculate the offset of line 1: we have b from a+bx. Since Point a is on that line, it is:
//a + b * a.x = a.y with a as free variable, which yields a = a.y - b*a.x.
//One could also use the second point b for this calculation.
double firstOffset = a.y() - firstGradient * a.x();
double secondGradient, secondOffset;
Point dx = d.sub(c);
secondGradient = dx.y() / dx.x(); //same formula as above
secondOffset = c.y() - secondGradient * c.x();
//a+bx=c+dx <=> a-c = (d-b)x <=> (a-c)/(d-b) = x
double x = (firstOffset - secondOffset) / (secondGradient - firstGradient);
//we have to check, if those lines intersect with a x \in [a.x,b.x] and x \in [c.x,d.x]. If this is the case, we have a collision
if (x >= a.x() && x <= b.x() && x >= c.x() && x <= d.x()) {
return true;
}
return false;
}
int main(int argc, char const *argv[]) {
if (checkforIntersection(Point(310.374,835.171),Point(290.434,802.354), Point(333.847,807.232), Point(301.03,827.172)) == true) {
cout << "These lines do intersect so I should be printed out\n";
} else {
cout << "The algorithm does not work, so instead I do get printed out\n";
}
return 0;
}
举个例子，我拿到了这些点 (310,835) -- (290,802) 和 (333,807) -- (301,827)。这两条线相交：
\documentclass[crop,tikz]{standalone}
\begin{document}
\begin{tikzpicture}[x=.1cm,y=.1cm]
\draw (310,835) -- (290,802);
\draw (333,807) -- (301,827);
\end{tikzpicture}
\end{document}
相交证明。然而，当运行以上C++代码时，它会显示它们不相交。
