检查两条线段是否相交（仅检查它们是否相交，而不是在哪里相交）

Question

我需要一个快速的算法来检查两条不无限线是否相交。必须要快，因为它将在手机上频繁运行。

该算法只需要返回是或否，不必精确地找出线的交点！

我已经在这里查找过：如何检测两条线段是否相交？ 但那个帖子很乱，人们总是说“这就是答案”，但另外两个人则说它因为某种错误而不正确。

请帮助我找到一个好的、可行的算法。

只是为了明确：我需要一个函数，您输入...
lineApointAx
lineApointAy
lineApointBx
lineApointBy
lineBpointAx
lineBpointAy
lineBpointBx
lineBpointBy
...并且根据两条线是否相交返回true或false。

如果您使用（伪）代码回答，我会非常感激，而不是公式。

- Mike

---

可能是重复的问题：如何确定两条线段是否相交？ - Ray Hayes

"最佳的过早优化！" 哦是吗？平均每帧需要进行30个交叉检查，而在每帧之间的约16毫秒内还需要进行渲染和大量其他计算。考虑到我还想支持预算手机，这些手机最多只有两年的历史，我认为想要在任何可以优化的地方进行代码优化是可以理解的。特别是因为未来还会添加更多的计算。但也许你是对的，但是嘿，快速的代码从来没有错。 - Mike

这不是过早的优化，而是算法优化。只有在编译器可以合理地期望执行优化时，优化才是过早的，无论它是否实际执行。编译器可能能够智能地将除以二的操作转换为位运算（而手动执行这个操作就是过早的优化），但编译器永远无法将插入排序算法转换为快速排序算法。至少，在编译器只编译我们的指令而不实际协作编程的情况下是这样的。 - meustrus

@RayHayes我不明白为什么这个问题被关闭了。大多数简单的计算机几何问题都有一个被广泛接受的“最佳方法”或“最便宜”的算法。我来到这里是因为我很匆忙，想要获取算法，而不是坐下来思考一堆公式。将他所寻找的答案（类似于https://dev59.com/pHRB5IYBdhLWcg3wpYmo，但更简化）标记为已接受，并进行调整，这将非常有帮助。 - M Conrad

实际上，我只是坐下来敲了一下，想在这里发布它，但无法。https://gist.github.com/nrdvana/fe002742e45ed4ff58031eb32f99c6f8 - M Conrad

Answer 1

判断两条线段是否相交，必要且充分条件是这两条线段的两端在另一条线段的不同侧，反之亦然。为了判断一个点在哪一侧，只需进行叉积运算并看结果是否为正或负：

(B_x - A_x)(P_y - B_y) - (B_y - A_y)(P_x - B_x)

编辑：
明确一下：假设您正在查看两条线段 [AB] 和 [CD]。当且仅当 ((A和B在[CD]的不同侧)且(C和D在[AB]的不同侧)) 时，这两条线段相交。

要查看两点 P 和 Q 是否在线段 [EF] 的不同侧，请计算两个叉积，一个针对 P，另一个针对 Q：

(F_x - E_x)(P_y - F_y) - (F_y - E_y)(P_x - F_x)

(F_x - E_x)(Q_y - F_y) - (F_y - E_y)(Q_x - F_x)

如果结果具有相同的符号（都为正或负），则无需考虑，点在同一侧，线段不相交。如果一个为正，一个为负，则这些点在不同的侧面。

- Beta

---

@Beta交叉积是向量之间的运算，其结果也是一个向量。但我有些困惑： a）您好像在建议对线段（没有方向，因此不是向量）和点（绝对不是向量）进行叉积运算。 b）结果是一个标量。 请帮助我理解，我的26年记忆是否正确，或者这只是术语上的松散使用。我很想使用它，但我需要提高信心水平。 - juanchito

@AlexWien：是的，编写代码可能是一项艰苦的工作。 - Beta

嗯...所以...我只是在一个小问题上有点困惑......我看到您正在进行叉积(B - A) x (P - B)。我不明白原因-难道您不应该将“A”作为原点，然后进行叉积(B - A) x (P - A)吗？如果我这样做，算法仍然有效吗？要注意墨菲定律完全发挥作用，使我两个公式都跨越了2行。该死。 - MaiaVictor

注意：对于未来的读者，如果这是正确的，您可以在此处使用我的JavaScript实现：http://jsfiddle.net/ytr9314a/4/ - MaiaVictor

@Viclib：如果你那样做，算法仍然可以工作。选择A或B（或任何中间点）是任意的。 - Beta

Answer 2

如果你有两个给定的点(X1,Y1)和(X2,Y2)，那么想象它们都是无限长的直线，而不仅仅是线段：

1. 确定两条直线的公式（参见：http://en.wikipedia.org/wiki/Linear_equation#Two-point_form） 2. 确定两条直线的交点（参见：http://zonalandeducation.com/mmts/intersections/intersectionOfTwoLines1/intersectionOfTwoLines1.html） 3. 如果X1 < 交点X < X2并且Y1 < 交点Y < Y2，则这两个线段相交。

- Jonathan M

---

我认为重点是他想要一种更快的方法来完成这个任务，对我来说，这意味着一种不需要找到交点的方法。唯一的问题是，好吧，找到交点并检查它 - 就像你建议的那样 - 实际上相当快速。 - Patrick87

是的，我不确定“更快”是什么意思。比什么更快？他只是说“快”。 - Jonathan M

然而，对于那些想要知道段交叉点在哪里的后来者来说，这仍然是有用的。 - Martin

对于那些来得更晚的人：这不是一个稳定的算法，你将不得不为接近重合的线对以及接近与坐标轴平行的线进行特殊处理。 - Franz

@Franz，你能举个例子吗？ - Jonathan M