geometry - 如何根据坐标对判断两者是否有交集？

Question

我有两个由两个 x,y 坐标表示的线段，如下所示：

[(x1,y1),(x2,y2)] //start & end of first line
[(x3,y3),(x4,y4)] //start & end of second line

确定这些线中是否存在交叉点的最有效方法是什么？

Answer 1

有一个交叉口当且仅当

(((X3-X1) * (Y2-Y1)-(Y3-Y1) * (X2-X1)) * ((X4-X1) * (Y2-Y1)-(Y4-Y1) * (X2-X1 )) <= 0)

和

(((X1-X3) * (Y4-Y3)-(Y1-Y3) * (X4-X3)) * ((X2-X3) * (Y4-Y3)-(Y2-Y3) * (X4-X3 )) <= 0)

Answer 2

取由第一个向量/线和要检查碰撞的线的端点形成的三角形，并通过行列式取其面积。将其面积与另一个端点形成的三角形面积进行比较。如果它们都是正/负，则没有交集。如果他们的标志不同，那么可能会有一个交叉点。

如果它们的符号不同，则执行与上述相同的操作，只是使用原始向量的端点而不是线的端点。（并使用整行而不是原始向量）。

如果它们的符号不同，那么肯定有一个交叉点，如果它们相同，那么就没有交叉点。

有用的链接：取三角形的行列式：这里

评估行列式：这里

如果有什么不明白的，请告诉我！