如何检查两条线段是否相交？

Question

我该如何检查两条线段 L1(p1,p2) 和 L2(p3,p4) 是否相交？我不需要相交点，只需知道它们是否相交。由于我的应用程序需要频繁计算这个问题，因此我需要找到一种快速的解决方案。

谢谢

- trrrrrrm

---

你是指无限延伸的几何线吗？ - likeitlikeit

@ra_htial：我们正在讨论您真正想问的问题。请查看Andreas Wederbrand回答下的讨论。如果我的编辑没有反映您的意图，请重新编辑。您的问题是关于Java的java.awt.geom.Line2D（根据文档，“表示（x，y）坐标空间中的线段”）还是延伸到无限的几何线？ - oligofren

@ra_htial：你能接受一个答案或者就你所问的问题提出一些讨论吗？ - oligofren

Answer 1

要测试两条线段是否相交，您可以使用Java的2D API，具体使用Line2D类的方法。

Line2D line1 = new Line2D.Float(100, 100, 200, 200);
Line2D line2 = new Line2D.Float(150, 150, 150, 200);
boolean result = line2.intersectsLine(line1);
System.out.println(result); // => true

// Also check out linesIntersect() if you do not need to construct the line objects
// It will probably be faster due to putting less pressure on the garbage collector
// if running it in a loop
System.out.println(Line2D.linesIntersect(100,100,200,200,150,150,150,200));

如果您有兴趣了解代码的工作原理，以查看是否可以在特定领域中加快其速度，请查看OpenJDK实现的代码。 但请记住，在优化之前一定要进行分析; 它现在可能已经足够快了。

- oligofren

---

抱歉，我不明白你在问什么。交点之后是什么？ - oligofren

我猜他的意思是他也想知道线段相交的位置。顺便问一下，有没有办法排除线段的端点，比如 (0,0,1,1) 和 (1,1,2,2) 不相交？ - Thomas Ahle

@AlessioMTX 这是另一个问题。我会尝试阅读API方法来开始解决它... - oligofren

我在Line2D中没有找到，由于我不熟悉这个API，所以我看了一下，但没有找到解决办法，因此在这里提问，也许是我错过了什么。 - Mitro

@AlessioMTX 谷歌搜索的第一个结果：https://dev59.com/DGQo5IYBdhLWcg3wG8SE - oligofren

Answer 2

如果您想重新实现它，我建议直接使用可以帮助您完成此操作的方法，或查看其源代码：Line2D.linesIntersect()

- JB Nizet

---

同样的情况也适用于这里，linesIntersect 检查的是线而不是线段。有很多情况下，线相交但线段并不相交。 - anvarik

Javadoc 的说明：测试从点 (x1,y1) 到点 (x2,y2) 的线段是否与从点 (x3,y3) 到点 (x4,y4) 的线段相交（强调是“线段”）。 - JB Nizet

哇塞，太棒了！抱歉，我会给你们点赞的。 - anvarik